CS Seminar – Ravi Kant Rai (Indian Institute of Technology)

Discrete Richman-Bidding Scoring Games

We study zero-sum combinatorial games within the framework of so-called Richman auctions (Lazarus et al., 1996). We modify the alternating play scoring ruleset Cumulative Subtraction (Cohensius et al., 2019), to a discrete bidding scheme, similar to Develin and Payne (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.

July 16 (Thursday), 14:30

This is an internal seminar for members of the Department of Computer Science only. Ask at poliakar@fel.cvut.cz for the Zoom link.

Ravi Kant Rai

Ravi Kant Rai is a PhD student at the Indian Institute of Technology, Bombay, India. He did his graduation in Statistics Honours and then joined IIT Bombay, India for dual-degree M.Sc. Ph.D. course. More about Ravi can be found on the university's website here.