enter search term and/or author name
Competitive equilibrium from equal incomes (CEEI) is a well-known fair allocation mechanism with desirable fairness and efficiency properties; however, with indivisible resources, a CEEI may not exist [Foley 1967; Varian 1974; Thomson and Varian...
We introduce the notion of local computation mechanism design—designing game-theoretic mechanisms that run in polylogarithmic time and space. Local computation mechanisms reply to each query in polylogarithmic time and space, and the...
Incentives are more likely to elicit desired outcomes when they are designed based on accurate models of agents’ strategic behavior. A growing literature, however, suggests that people do not quite behave like standard economic agents in a...
Recency, Records, and Recaps: Learning and Nonequilibrium Behavior in a Simple Decision Problem
Drew Fudenberg, Alexander Peysakhovich
Article No.: 23
Nash equilibrium takes optimization as a primitive, but suboptimal behavior can persist in simple stochastic decision problems. This has motivated the development of other equilibrium concepts such as cursed equilibrium and behavioral equilibrium....
Bounds for the Query Complexity of Approximate Equilibria
Paul W. Goldberg, Aaron Roth
Article No.: 24
We analyze the number of payoff queries needed to compute approximate equilibria of multi-player games. We find that query complexity is an effective tool for distinguishing the computational difficulty of alternative solution concepts, and we...
Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries
John Fearnley, Rahul Savani
Article No.: 25
We study the deterministic and randomized query complexity of finding approximate equilibria in a k × k bimatrix game. We show that the deterministic query complexity of finding an ε-Nash equilibrium when &epsilon <...