Publication Type

Journal Article

Version

publishedVersion

Publication Date

8-2021

Abstract

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.

Keywords

Graph games, Bidding games, Richman bidding, Poorman bidding, Mean-payoff games, Parity games, Stochastic games, Random-turn games

Discipline

Graphics and Human Computer Interfaces | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

Journal of Computer and System Sciences

Volume

119

First Page

133

Last Page

144

ISSN

0022-0000

Identifier

10.1016/j.jcss.2021.02.008

Publisher

Elsevier

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1016/j.jcss.2021.02.008

Download

Share

COinS