On the complexity of approximating a nash equilibrium by Daskalakis, Constantinos

“…We show that computing a relative---that is, multiplicative as opposed to additive---approximate Nash equilibrium in two-player games is PPAD-complete, even for constant values of the approximation. …”
Get full text
Get full text

Pareto optimality and Nash equilibrium for building stable systems by Doufene, Abdelkrim, Krob, Daniel

“…While Pareto optimality is used to select best architectures and to support independent decisions, Nash equilibrium is used to find out architectural equilibrium and to support interdependent decisions. …”
Get full text
Get full text

Operant Matching as a Nash Equilibrium of an Intertemporal Game by Loewenstein, Yonatan, Prelec, Drazen, Seung, H. Sebastian

“…If each self is blind to the state of the world and discounts future rewards completely, then the resulting game has at least one Nash equilibrium that satisfies both Herrnstein's matching law and the unpredictability of individual choices. …”
Get full text
Get full text

Selfish Routing in Capacitated Networks by Correa, Jose R., Schulz, Andreas S., Stier Moses, Nicolas E.

Subjects: Get full text

Competitive Multi-period Pricing with Fixed Inventories by Perakis, Georgia, Sood, Anshul

Subjects: Get full text

A Game Theoretic Modeling and Analysis for Internet Access Market by Weiss, Martin, Shin, Seung-Jae, Correa, Hector

Subjects: Get full text

Playing is believing: the role of beliefs in multi-agent learning by Chang, Yu-Han, Kaelbling, Leslie P.

Subjects: Get full text

On Learning Algorithms for Nash Equilibria by Daskalakis, Constantinos, Frongillo, Rafael, Papadimitriou, Christos H., Pierrakos, George, Valiant, Gregory

Get full text
Get full text

Price of Airline Frequency Competition by Vaze, Vikrant, Barnhart, Cynthia

“…We characterize the conditions for existence and uniqueness of a Nash equilibrium for the 2-player case. We analyze two different myopic learning dynamics for the non-equilibrium situations and prove their convergence to Nash equilibrium under mild conditions. …”
Get full text

Zero-Sum Polymatrix Games: A Generalization of Minmax by Cai, Yang, Candogan, Ozan, Papadimitriou, Christos, Daskalakis, Konstantinos

“…In contrast, other important properties of two-person zero-sum games are not preserved: Nash equilibrium payoffs need not be unique, and Nash equilibrium strategies need not be exchangeable or max-min.…”
Get full text
Get full text

Bayesian Proportional Resource Allocation Games by Tsitsiklis, John N., Xu, Yunjian

“…We prove the existence of a Bayes-Nash equilibrium. Furthermore, under some mild assumptions, we establish asymptotic efficiency: we show that the per user social welfare achieved at any Bayes-Nash equilibrium is asymptotically equal to the maximum possible.…”
Get full text
Get full text

Parameterized Supply Function Bidding: Equilibrium and Efficiency by Johari, Ramesh, Tsitsiklis, John N.

“…We show that by restricting the strategy space of the firms to parameterized supply functions, we can provide upper bounds on both the inflation of aggregate cost at the Nash equilibrium relative to the socially optimal level, as well as the markup of the Nash equilibrium price above the competitive level: as long as N > 2 firms are competing, these quantities are both upper bounded by 1 + 1/(N − 2). …”
Get full text
Get full text

Complexity of finding Nash equilibria in 0-1 bimatrix games by Abbott, Tim, Kane, Daniel, Valiant, Paul

“…We exhibit a polynomial reduction from the problem of finding a Nashequilibrium of a bimatrix game with rational coefficients to the problemof finding a Nash equilibrium of a bimatrix game with 0-1 coefficients.…”
Get full text

Tight SoS-Degree Bounds for Approximate Nash Equilibria by Wu, Xiaodi, Harrow, Aram W, Natarajan, Anand Venkat

“…The LMM algorithm can also be used to find an approximate Nash equilibrium with near-maximal total welfare. Matching hardness results for this optimization problem were found assuming the hardness of the planted-clique problem (by Hazan and Krauthgamer) and assuming the Exponential Time Hypothesis (by Braverman, Ko and Weinstein). …”
Get full text
Get full text
Get full text

On the complexity of Nash equilibria of action-graph games by Daskalakis, Constantinos, Schoenebeck, Grant, Valiant, Gregory, Valiant, Paul

“…In particular, we show that even if the action graph is a tree but the number of agent-types is unconstrained, it is NP- complete to decide the existence of a pure-strategy Nash equilibrium and PPAD-complete to compute a mixed Nash equilibrium (even an approximate one). …”
Get full text

On minmax theorems for multiplayer games by Cai, Yang, Daskalakis, Constantinos

“…We show that finding a pure Nash equilibrium in coordination-only polymatrix games is PLS-complete; hence, computing a mixed Nash equilibrium is in PLS ∩ PPAD, but it remains open whether the problem is in P. …”
Get full text
Get full text

Monotone Equilibrium in Multi-Unit Auctions by McAdams, David

“…In a large class of multi-unit auctions of identical objects that includes the uniform-price, as-bid (or discriminatory), and Vickrey auctions, a Bayesian Nash equilibrium exists in monotone pure strategies whenever there is a finite price / quantity grid and each bidder's interim expected payoff function satisfies single-crossing in own bid and type. …”
Get full text

Robust Predictions in Infinite-Horizon Games--an Unrefinable Folk Theorem by Weinstein, Jonathan, Yildiz, Muhamet

“…We show that in any game that is continuous at infinity, if a plan of action ai is played by a type ti in a Bayesian Nash equilibrium, then there are perturbations of ti for which ai is the only rationalizable plan and whose unique rationalizable belief regarding the play of the game is arbitrarily close to the equilibrium belief of ti. …”
Get full text
Get full text

Technical Note—Nonlinear Pricing Competition with Private Capacity Information by Nazerzadeh, Hamid, Perakis, Georgia

“…We prove the existence of a (pure strategy) Nash equilibrium for this game. We show that at the equilibrium each (infinitesimal) unit of the supply is assigned a marginal price that is independent of the capacities and depends only on the valuation function of the retailer and the distribution of the capacities. …”
Get full text
Get full text

Marriage, Honesty, and Stability by Immorlica, Nicole, Mahdian, Mohammad

“…In themore realistic setting of a game of incomplete information, we willshow that the set of truthful strategies form a (1+o(1))-approximateBayesian-Nash equilibrium. Our results have implications in manypractical settings and were inspired by the work of Roth and Peranson[23] on the National Residency Matching Program.…”
Get full text