Bidding mechanisms in graph games
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...
Saved in:
Main Authors: | , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2021
|
Subjects: | |
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 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-10063 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-100632024-08-01T15:33:35Z Bidding mechanisms in graph games AVNI, Guy HENZINGER, Thomas A. ZIKELIC, Dorde 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 combination with two variants of first-price auctions called “Richman” and “poorman” bidding. We study taxman bidding, which span the spectrum between the two. The game is 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: we unify, generalize, and simplify previous equivalences between bidding games and a class of stochastic games called random-turn games. 2021-08-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/9060 info:doi/10.1016/j.jcss.2021.02.008 https://ink.library.smu.edu.sg/context/sis_research/article/10063/viewcontent/1_s2.0_S0022000021000234_main.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 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 |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
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 |
spellingShingle |
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 AVNI, Guy HENZINGER, Thomas A. ZIKELIC, Dorde Bidding mechanisms in graph games |
description |
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 combination with two variants of first-price auctions called “Richman” and “poorman” bidding. We study taxman bidding, which span the spectrum between the two. The game is 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: we unify, generalize, and simplify previous equivalences between bidding games and a class of stochastic games called random-turn games. |
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 |
2021 |
url |
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 |
_version_ |
1814047720322629632 |