|
on Game Theory |
| By: | Bary S. R. Pradelski; Bassel Tarbush |
| Abstract: | We show that for any $\epsilon>0$ the probability that a randomly drawn game has a pure $\epsilon$-equilibrium goes to 1 as the number of agents gets large. This contrasts sharply with the known fact that if $\epsilon = 0$, that is, for pure Nash equilibrium, the probability is asymptotically $1- 1/e\approx 0.63$. |
| Date: | 2025–02 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2502.07585 |
| By: | Stephen Morris; Takashi Ui |
| Abstract: | Consider an analyst who models a strategic situation using an incomplete information game. The true game may involve correlated, duplicated belief hierarchies, but the analyst lacks knowledge of the correlation structure and can only approximate each belief hierarchy. To make predictions in this setting, the analyst uses belief-invariant Bayes correlated equilibria (BIBCE) and seeks to determine which one is justifiable. We address this question by introducing the notion of robustness: a BIBCE is robust if, for every nearby incomplete information game, there exists a BIBCE close to it. Our main result provides a sufficient condition for robustness using a generalized potential function. In a supermodular potential game, a robust BIBCE is a Bayes Nash equilibrium, whereas this need not hold in other classes of games. |
| Date: | 2025–02 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2502.19075 |
| By: | Cesare Carissimo; Jan Nagler; Heinrich Nax |
| Abstract: | We investigate the dynamics of Q-learning in a class of generalized Braess paradox games. These games represent an important class of network routing games where the associated stage-game Nash equilibria do not constitute social optima. We provide a full convergence analysis of Q-learning with varying parameters and learning rates. A wide range of phenomena emerges, broadly either settling into Nash or cycling continuously in ways reminiscent of "Edgeworth cycles" (i.e. jumping suddenly from Nash toward social optimum and then deteriorating gradually back to Nash). Our results reveal an important incentive incompatibility when thinking in terms of a meta-game being played by the designers of the individual Q-learners who set their agents' parameters. Indeed, Nash equilibria of the meta-game are characterized by heterogeneous parameters, and resulting outcomes achieve little to no cooperation beyond Nash. In conclusion, we suggest a novel perspective for thinking about regulation and collusion, and discuss the implications of our results for Bertrand oligopoly pricing games. |
| Date: | 2025–02 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2502.18984 |
| By: | Ruofei Ma; Wenpin Tang; David Yao |
| Abstract: | In this paper, we consider the impact of the order flow auction (OFA) in the context of the proposer-builder separation (PBS) mechanism through a game-theoretic perspective. The OFA is designed to improve user welfare by redistributing maximal extractable value (MEV) to the users, in which two auctions take place: the order flow auction and the block-building auction. We formulate the OFA as a multiplayer game, and focus our analyses on the case of two competing players (builders). We prove the existence and uniqueness of a Nash equilibrium for the two-player game, and derive a closed-form solution by solving a quartic equation. Our result shows that the builder with a competitive advantage pays a relatively lower cost, leading to centralization in the builder space. In contrast, the proposer's shares evolve as a martingale process, which implies decentralization in the proposer (or, validator) space. Our analyses rely on various tools from stochastic processes, convex optimization, and polynomial equations. We also conduct numerical studies to corroborate our findings, and explore other features of the OFA under the PBS mechanism. |
| Date: | 2025–02 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2502.12026 |
| By: | Juanjuan Fan; Ying Wang |
| Abstract: | This paper introduces a new solution concept for the Cooperative Game with Public Externalities, called the w-value, which is characterized by three properties (axioms), namely Pareto-optimality (PO), Market-equilbrium (ME) and Fiscal-balance (FB). Additionally, the implementation mechanism for w-value is also provided. The w-value exists and is unique. It belongs to the core. And, more specifically, it belongs to the -core. Meanwhile, the computational cost of w-value is very low. Therefore, the w-value is a theoretically more compelling solution concept than the existing cooperation game solutions when analyzing cooperative games with public externalities. A numerical illustration shows the calculation steps of w-value. Meanwhile, the w-value well explains the reason why the mandatory emission reduction mechanism must be transformed into a "nationally determined contribution" mechanism in current international climate negotiations. |
| Date: | 2025–02 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2502.16800 |
| By: | Péter Bayer (TSE-R - Toulouse School of Economics - UT Capitole - Université Toulouse Capitole - UT - Université de Toulouse - EHESS - École des hautes études en sciences sociales - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement); Ani Guerdjikova (GAEL - Laboratoire d'Economie Appliquée de Grenoble - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement - UGA - Université Grenoble Alpes - Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology - UGA - Université Grenoble Alpes) |
| Abstract: | We analyze a model of endogenous two-sided network formation where players are affected by uncertainty about their opponents' decisions. We model this uncertainty using the notion of equilibrium under ambiguity as in Eichberger and Kelsey (2014). Unlike the set of Nash equilibria, the set of equilibria under ambiguity does not always include underconnected and thus inefficient networks such as the empty network. On the other hand, it may include networks with unreciprocated, one-way links, which comes with an efficiency loss as linking efforts are costly. We characterize equilibria under ambiguity and provide conditions under which increased player optimism comes with an increase in connectivity and realized benefits in equilibrium. Next, we analyze network realignment under a myopic updating process with optimistic shocks and derive a global stability condition of efficient networks in the sense of Kandori et al. (1993). Under this condition, a subset of the Pareto optimal equilibrium networks is reached, specifically, networks that maximize the players' total benefits of connections. |
| Keywords: | Pessimism, Optimism, Pareto-optimality, Equilibrium selection, Ambiguity, Network formation |
| Date: | 2024–08–22 |
| URL: | https://d.repec.org/n?u=RePEc:hal:journl:hal-03005107 |
| By: | Yike Wang; Yusha Chen |
| Abstract: | This paper is devoted to time-consistent control problems of portfolio selection with strictly monotone mean-variance preferences. These preferences are variational modifications of the conventional mean-variance preferences, and remain time-inconsistent as in mean-variance optimization problems. To tackle the time-inconsistency, we study the Nash equilibrium controls of both the open-loop type and the closed-loop type, and characterize them within a random parameter setting. The problem is reduced to solving a flow of forward-backward stochastic differential equations for open-loop equilibria, and to solving extended Hamilton-Jacobi-Bellman equations for closed-loop equilibria. In particular, we derive semi-closed-form solutions for these two types of equilibria under a deterministic parameter setting. Both solutions are represented by the same function, which is independent of wealth state and random path. This function can be expressed as the conventional time-consistent mean-variance portfolio strategy multiplied by a factor greater than one. Furthermore, we find that the state-independent closed-loop Nash equilibrium control is a strong equilibrium strategy in a constant parameter setting only when the interest rate is sufficiently large. |
| Date: | 2025–02 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2502.11052 |
| By: | Denizalp Goktas; Amy Greenwald; Sadie Zhao; Alec Koppel; Sumitra Ganesh |
| Abstract: | In this paper, we study inverse game theory (resp. inverse multiagent learning) in which the goal is to find parameters of a game's payoff functions for which the expected (resp. sampled) behavior is an equilibrium. We formulate these problems as generative-adversarial (i.e., min-max) optimization problems, for which we develop polynomial-time algorithms to solve, the former of which relies on an exact first-order oracle, and the latter, a stochastic one. We extend our approach to solve inverse multiagent simulacral learning in polynomial time and number of samples. In these problems, we seek a simulacrum, meaning parameters and an associated equilibrium that replicate the given observations in expectation. We find that our approach outperforms the widely-used ARIMA method in predicting prices in Spanish electricity markets based on time-series data. |
| Date: | 2025–02 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2502.14160 |
| By: | Bar Light |
| Abstract: | Mean field equilibrium (MFE) has emerged as a computationally tractable solution concept for large dynamic games. However, computing MFE remains challenging due to nonlinearities and the absence of contraction properties, limiting its reliability for counterfactual analysis and comparative statics. This paper focuses on MFE in dynamic models where agents interact through a scalar function of the population distribution, referred to as the \textit{scalar interaction function}. Such models naturally arise in a wide range of applications in operations and economics, including quality ladder models, inventory competition, online marketplaces, and heterogeneous-agent macroeconomic models. The main contribution of this paper is to introduce iterative algorithms that leverage the scalar interaction structure and are guaranteed to converge to the MFE under mild assumptions. Unlike existing approaches, our algorithms do not rely on monotonicity or contraction properties, significantly broadening their applicability. Furthermore, we provide a model-free algorithm that learns the MFE by employing simulation and reinforcement learning techniques such as Q-learning and policy gradient methods without requiring prior knowledge of payoff or transition functions. We establish finite-time performance bounds for this algorithm under technical Lipschitz continuity assumptions. We apply our algorithms to classic models of dynamic competition, such as capacity competition, and to competitive models motivated by online marketplaces, including ridesharing, dynamic reputation, and inventory competition, as well as to social learning models. Using our algorithms, we derive reliable comparative statics results that illustrate how key market parameters influence equilibrium outcomes in these stylized models, providing insights that could inform the design of competitive systems in these contexts. |
| Date: | 2025–02 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2502.12024 |
| By: | Rachitesh Kumar; Omar Mouchtaki |
| Abstract: | First-price auctions are one of the most popular mechanisms for selling goods and services, with applications ranging from display advertising to timber sales. Unlike their close cousin, the second-price auction, first-price auctions do not admit a dominant strategy. Instead, each buyer must design a bidding strategy that maps values to bids -- a task that is often challenging due to the lack of prior knowledge about competing bids. To address this challenge, we conduct a principled analysis of prior-independent bidding strategies for first-price auctions using worst-case regret as the performance measure. First, we develop a technique to evaluate the worst-case regret for (almost) any given value distribution and bidding strategy, reducing the complex task of ascertaining the worst-case competing-bid distribution to a simple line search. Next, building on our evaluation technique, we minimize worst-case regret and characterize a minimax-optimal bidding strategy for every value distribution. We achieve it by explicitly constructing a bidding strategy as a solution to an ordinary differential equation, and by proving its optimality for the intricate infinite-dimensional minimax problem underlying worst-case regret minimization. Our construction provides a systematic and computationally-tractable procedure for deriving minimax-optimal bidding strategies. When the value distribution is continuous, it yields a deterministic strategy that maps each value to a single bid. We also show that our minimax strategy significantly outperforms the uniform-bid-shading strategies advanced by prior work. Our result allows us to precisely quantify, through minimax regret, the performance loss due to a lack of knowledge about competing bids. We leverage this to analyze the impact of the value distribution on the performance loss, and find that it decreases as the buyer's values become more dispersed. |
| Date: | 2025–02 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2502.09907 |
| By: | Jack Hirsch; Eric Tang |
| Abstract: | We study the effect of providing information to agents who queue before a scarce good is distributed at a fixed time. When agents have quasi-linear utility in time spent waiting, they choose entry times as they would bids in a descending auction. An information designer can influence their behavior by providing updates about the length of the queue. Many natural information policies release "sudden bad news, " which occurs when agents learn that the queue is longer than previously believed. We show that sudden bad news can cause assortative inefficiency by prompting a mass of agents to simultaneously attempt to join the queue. As a result, if the value distribution has an increasing (decreasing) hazard rate, information policies that release sudden bad news increase (decrease) total surplus, relative to releasing no information. When agents face entry costs to join the queue and the value distribution has a decreasing hazard rate, an information designer maximizes total surplus by announcing only when the queue is full. |
| Date: | 2025–02 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2502.19553 |
| By: | Siddarth Srinivasan; Ezra Karger; Michiel Bakker; Yiling Chen |
| Abstract: | Common sense suggests that when individuals explain why they believe something, we can arrive at more accurate conclusions than when they simply state what they believe. Yet, there is no known mechanism that provides incentives to elicit explanations for beliefs from agents. This likely stems from the fact that standard Bayesian models make assumptions (like conditional independence of signals) that preempt the need for explanations, in order to show efficient information aggregation. A natural justification for the value of explanations is that agents' beliefs tend to be drawn from overlapping sources of information, so agents' belief reports do not reveal all that needs to be known. Indeed, this work argues that rationales-explanations of an agent's private information-lead to more efficient aggregation by allowing agents to efficiently identify what information they share and what information is new. Building on this model of rationales, we present a novel 'deliberation mechanism' to elicit rationales from agents in which truthful reporting of beliefs and rationales is a perfect Bayesian equilibrium. |
| Date: | 2025–02 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2502.13410 |
| By: | Hoang Vu; Tomoyuki Ichiba |
| Abstract: | We investigate the full dynamics of capital allocation and wealth distribution of heterogeneous agents in a frictional economy during booms and busts using tools from mean-field games. Two groups in our models, namely the expert and the household, are interconnected within and between their classes through the law of capital processes and are bound by financial constraints. Such a mean-field interaction explains why experts accumulate a lot of capital in the good times and reverse their behavior quickly in the bad times even in the absence of aggregate macro-shocks. When common noises from the market are involved, financial friction amplifies the mean-field effect and leads to capital fire sales by experts. In addition, the implicit interlink between and within heterogeneous groups demonstrates the slow economic recovery and characterizes the deviating and fear-of-missing-out (FOMO) behaviors of households compared to their counterparts. Our model also gives a fairly explicit representation of the equilibrium solution without exploiting complicated numerical approaches. |
| Date: | 2025–02 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2502.10666 |