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 2019
• Subjects: Bidding games; Richman bidding; poorman bidding; taxman bidding; meanpayoff games; random-turn games; Graphics and Human Computer Interfaces; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/9061; https://ink.library.smu.edu.sg/context/sis_research/article/10064/viewcontent/LIPIcs.MFCS.2019.11.pdf
• Institution: Singapore Management University

In two-player games on graphs, the players move a token through a graph to produce a finite or infinite path, which determines the qualitative winner or quantitative payoff of the game. We study bidding games in which the players bid for the right to move the token. Several bidding rules were studie...