Discrete Richman-bidding scoring games

Ravi Kant Rai (), Urban Larsson () and Neel Patel ()
Additional contact information
Ravi Kant Rai: Indian Institute of Technology Bombay
Urban Larsson: National University of Singapore
Neel Patel: National University of Singapore

International Journal of Game Theory, 2021, vol. 50, issue 3, No 7, 695-728

Abstract: Abstract We study zero-sum combinatorial games within the framework of so-called Richman auctions (Lazarus et al., in Games No Chance 29:439–449, 1996). We modify the alternating play scoring ruleset Cumulative Subtraction (Cohensius et al., in Electron J Combin 26(P4):52, 2019), to a discrete bidding scheme, similar to Develin and Payne (Electron J Combin 17(1):85, 2010). Players bid to move, and the player with the highest bid wins the move and hands over the winning bid amount to the other player. The new game is dubbed Bidding Cumulative Subtraction. In so-called unitary games, players remove exactly one item out of a single heap of identical items, until the heap is empty, and their actions contribute to a common score, which increases or decreases by one unit depending on whether the maximizing player wins the turn or not. We show that there is a unique bidding equilibrium for a much larger class of games that generalize standard scoring play. We prove that for all sufficiently large heap sizes, the equilibrium outcomes of unitary games are eventually periodic, with period 2. We show that the periodicity appears at the latest for heaps of sizes quadratic in the total budget.

Keywords: Combinatorial games; Discrete bidding; Richman auction; Scoring games (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00182-020-00753-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:50:y:2021:i:3:d:10.1007_s00182-020-00753-x

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-020-00753-x

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().