Bidding Games and Efficient Allocations

Abstract

Bidding games are extensive form games, where in each turn players bid in order to determine who will play next. Zero-sum bidding games (also known as Richman games) have been extensively studied, focusing on the fraction of the initial budget that can guaranty the victory of each player [Lazarus et al.'99, Develin and Payne'10]. We extend the theory of bidding games to general-sum two player games, showing the existence of pure subgame-perfect Nash equilibria (PSPE), and studying their properties. We show that if the underlying game has the form of a binary tree (only two actions available to the players in each node), then there exists a natural PSPE with the following highly desirable properties: (a) players' utility is weakly monotone in their budget; (b) a Pareto-efficient outcome is reached for any initial budget; and (c) for any Pareto-efficient outcome there is an initial budget s.t. this outcome is attained. In particular, we can assign the budget so as to implement the outcome with maximum social welfare, maximum Egalitarian welfare, etc. We show implications of this result for combinatorial bargaining. In particular, we show that the PSPE above is fair, in the sense that a player with a fraction of X% of the total budget prefers her allocation to X% of the possible allocations. In addition, we discuss the computational challenges of bidding games, and provide a polynomial-time algorithm to compute the PSPE.