Bidding mechanisms in graph games

• Main Authors: AVNI, Guy, HENZINGER, Thomas A., ZIKELIC, Dorde
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2021
• Subjects: Graph games; Bidding games; Richman bidding; Poorman bidding; Mean-payoff games; Parity games; Stochastic games; Random-turn games; Graphics and Human Computer Interfaces; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/9060; https://ink.library.smu.edu.sg/context/sis_research/article/10063/viewcontent/1_s2.0_S0022000021000234_main.pdf
• Institution: Singapore Management University

A graph game proceeds as follows: two players move a token through a graph to produce a finite or infinite path, which determines the payoff of the game. We study bidding games in which in each turn, an auction determines which player moves the token. Bidding games were largely studied in combinatio...