Infinite-Duration Bidding Games

11^th December 2019, 13:00
Guy Avni
IST Austria

Abstract

Graph games are two-player zero-sum games of infinite duration. The game proceeds by placing a token on a vertex in the game graph and allowing the two players to move it throughout the graph thereby producing an infinite path, which determines the payoff of the game. Bidding games are graph games in which in each turn, an auction is held in order to determine which player moves the token. We study the effect that the auction mechanism has on the properties of the game. Specifically, I will describe an intriguing equivalence between bidding games with first-price auctions and a fragment of stochastic games called “random-turn games”, and how changes to the auction mechanism lead to different equivalences. I will conclude by surveying directions for future work and describe our preliminary results in these directions.

The talk will cover results from the following papers:

Guy Avni, Thomas A. Henzinger, Ventsislav Chonev:
Infinite-Duration Bidding Games. CONCUR 2017
(this one has a J.acm journal version as well)

Guy Avni, Thomas A. Henzinger, Dorde Zikelic:
Bidding Mechanisms in Graph Games. MFCS 2019

Guy Avni, Thomas A. Henzinger, Rasmus Ibsen-Jensen:
Infinite-Duration Poorman-Bidding Games. WINE 2018