Bidding mechanisms in graph games

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...

Full description

Saved in:
Bibliographic Details
Main Authors: AVNI, Guy, HENZINGER, Thomas A., ZIKELIC, Dorde
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2019
Subjects:
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
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-10064
record_format dspace
spelling sg-smu-ink.sis_research-100642024-08-01T15:33:07Z Bidding mechanisms in graph games AVNI, Guy HENZINGER, Thomas A. ZIKELIC, Dorde 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 studied previously. In Richman bidding, in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Poorman bidding is similar except that the winner of the bidding pays the “bank” rather than the other player. Taxman bidding spans the spectrum between Richman and poorman bidding. They are parameterized by a constant τ ∈ [0, 1]: portion τ of the winning bid is paid to the other player, and portion 1 − τ to the bank. While finite-duration (reachability) taxman games have been studied before, we present, for the first time, results on infinite-duration taxman games. It was previously shown that both Richman and poorman infinite-duration games with qualitative objectives reduce to reachability games, and we show a similar result here. Our most interesting results concern quantitative taxman games, namely mean-payoff games, where poorman and Richman bidding differ significantly. A central quantity in these games is the ratio between the two players’ initial budgets. While in poorman mean-payoff games, the optimal payoff of a player depends on the initial ratio, in Richman bidding, the payoff depends only on the structure of the game. In both games the optimal payoffs can be found using (different) probabilistic connections with random-turn games in which in each turn, instead of bidding, a coin is tossed to determine which player moves. While the value with Richman bidding equals the value of a random-turn game with an un-biased coin, with poorman bidding, the bias in the coin is the initial ratio of the budgets. We give a complete classification of mean-payoff taxman games that is based on a probabilistic connection: the value of a taxman bidding game with parameter τ and initial ratio r, equals the value of a random-turn game that uses a coin with bias F(τ, r) = r+τ·(1−r) 1+τ . Thus, we show that Richman bidding is the exception; namely, for every τ 2019-08-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/9061 info:doi/10.4230/LIPICS.MFCS.2019.11 https://ink.library.smu.edu.sg/context/sis_research/article/10064/viewcontent/LIPIcs.MFCS.2019.11.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Bidding games Richman bidding poorman bidding taxman bidding meanpayoff games random-turn games Graphics and Human Computer Interfaces Theory and Algorithms
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Bidding games
Richman bidding
poorman bidding
taxman bidding
meanpayoff games
random-turn games
Graphics and Human Computer Interfaces
Theory and Algorithms
spellingShingle Bidding games
Richman bidding
poorman bidding
taxman bidding
meanpayoff games
random-turn games
Graphics and Human Computer Interfaces
Theory and Algorithms
AVNI, Guy
HENZINGER, Thomas A.
ZIKELIC, Dorde
Bidding mechanisms in graph games
description 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 studied previously. In Richman bidding, in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Poorman bidding is similar except that the winner of the bidding pays the “bank” rather than the other player. Taxman bidding spans the spectrum between Richman and poorman bidding. They are parameterized by a constant τ ∈ [0, 1]: portion τ of the winning bid is paid to the other player, and portion 1 − τ to the bank. While finite-duration (reachability) taxman games have been studied before, we present, for the first time, results on infinite-duration taxman games. It was previously shown that both Richman and poorman infinite-duration games with qualitative objectives reduce to reachability games, and we show a similar result here. Our most interesting results concern quantitative taxman games, namely mean-payoff games, where poorman and Richman bidding differ significantly. A central quantity in these games is the ratio between the two players’ initial budgets. While in poorman mean-payoff games, the optimal payoff of a player depends on the initial ratio, in Richman bidding, the payoff depends only on the structure of the game. In both games the optimal payoffs can be found using (different) probabilistic connections with random-turn games in which in each turn, instead of bidding, a coin is tossed to determine which player moves. While the value with Richman bidding equals the value of a random-turn game with an un-biased coin, with poorman bidding, the bias in the coin is the initial ratio of the budgets. We give a complete classification of mean-payoff taxman games that is based on a probabilistic connection: the value of a taxman bidding game with parameter τ and initial ratio r, equals the value of a random-turn game that uses a coin with bias F(τ, r) = r+τ·(1−r) 1+τ . Thus, we show that Richman bidding is the exception; namely, for every τ
format text
author AVNI, Guy
HENZINGER, Thomas A.
ZIKELIC, Dorde
author_facet AVNI, Guy
HENZINGER, Thomas A.
ZIKELIC, Dorde
author_sort AVNI, Guy
title Bidding mechanisms in graph games
title_short Bidding mechanisms in graph games
title_full Bidding mechanisms in graph games
title_fullStr Bidding mechanisms in graph games
title_full_unstemmed Bidding mechanisms in graph games
title_sort bidding mechanisms in graph games
publisher Institutional Knowledge at Singapore Management University
publishDate 2019
url 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
_version_ 1814047720582676480