Bidding games and efficient allocations

Richman games are zero-sum games, where in each turn players bid in order to determine who will play next (Lazarus et al., 1999). We extend the theory to impartial general-sum two player games called bidding games, showing the existence of pure subgame-perfect equilibria (PSPE). In particular, we sh...

Full description

Saved in:
Bibliographic Details
Published in:Games and economic behavior 2018-11, Vol.112, p.166-193
Main Authors: Meir, Reshef, Kalai, Gil, Tennenholtz, Moshe
Format: Article
Language:English
Subjects:
Bargaining
Combinatorial games
Extensive form games
Richman games
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Richman games are zero-sum games, where in each turn players bid in order to determine who will play next (Lazarus et al., 1999). We extend the theory to impartial general-sum two player games called bidding games, showing the existence of pure subgame-perfect equilibria (PSPE). In particular, we show that PSPEs form a semilattice, with a unique and natural Bottom Equilibrium. Our main result shows that if only two actions available to the players in each node, then the Bottom Equilibrium has additional properties: (a) utilities are monotone in budget; (b) every outcome is Pareto-efficient; and (c) any Pareto-efficient outcome is attained for some budget. In the context of combinatorial bargaining, we show that a player with a fraction of X% of the total budget prefers her allocation to X% of the possible allocations. In addition, we provide a polynomial-time algorithm to compute the Bottom Equilibrium of a binary bidding game.
ISSN:0899-8256
1090-2473
DOI:10.1016/j.geb.2018.08.005