Multi-Player Discrete-Bidding Games; Determinacy, Equilibria, and Complexity

Abstract

Games on graphs constitute a fundamental model. Applications include reactive synthesis, which reduces to solving a zero-sum two-player game, and reasoning about multi-agent systems by modeling them as a multi-player game. We study a class of graph games called bidding games in which the players are allocated a budget, and in each turn, an auction determines which player moves the token. Two-player bidding games have been extensively studied. We study, for the first time, multi-player bidding games. We focus on discrete bidding, which imposes granularity restrictions on the players'budgets and bids. The original motivation for discrete bidding is practical applications, and technically, it is appealing that the game has only finitely-many configurations. We initiate our study by considering a game between two coalitions of players. We show that under mild assumptions on the mechanism that is applied to break bidding ties, bidding games are determined: from every initial configuration, one of the coalitions has a winning strategy. Thus, we identify a sub-class of multi-player concurrent games that is determined. We extend the result to existence of a value in mean-payoff games. Using determinacy, we show that a pure Nash equilibrium always exists in qualitative games. Finally, we show that the complexity of deciding which coalition wins from a given configuration is PSPACE-hard already in reachability games and already for budgets given in unary. This is in stark contrast to two-player games, which are known to be in NP and coNP even for budgets given in binary.