2013/11/04 by Gil Kalai, Kalai, Gil, Reshef Meir +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Mathematics · #Auction Theory and Applications #Bidding #Computer Science and Game Theory (cs.GT) #Computer science #Context (archaeology) #Economics #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #Game theory #I.2.11 #Mathematical economics #Mathematical optimization #Mathematics #Microeconomics #Monotone polygon #Outcome (game theory) #Pareto principle #Subgame perfect equilibrium #cs.GT
paper · pdf · doi:10.48550/arxiv.1311.0913
A preliminary version of this paper appeared in the 16th ACM Conference on Economics and Computation (EC-2015). Paper accepted to Games and Economic Behavior
openalex publication_date 2013/11/04 · arxiv created 2018/08/10 · arxiv updated 2018/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Richman games are zero-sum games, where in each turn players bid in order to determine who will play next [Lazarus et al.'99]. 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.