Poorman Bidding Games on Graphs

18^th September 2019, 13:00
Rasmus Ibsen-Jensen
University of Liverpool

Abstract

Bidding games are graph games similar to parity or simple stochastic games. More precisely, the game is played on some graph. Initially, a pebble is placed on some state of the graph and each player is given some amount of play money (of no real value). Whenever the pebble is moved to some state, each player submits a bid and the high bidder moves the pebble to some adjacent state. In poorman games, the focus of this talk, the winner pays the auctioneer his bid. This defines a path in the graph and the outcome is then determined from that path. There is a variety of game objectives for how to determine the outcome from a path, e.g. reachability (has the path ever visited a specific node) or mean-payoff (for weighted graphs - the outcome is the average edge weight of the path). Previous work has focused on reachability and in this talk we consider many other objectives and find their computational complexity.

This work is based mainly on:
[Guy Avni, Thomas A. Henzinger, Rasmus Ibsen-Jensen: Infinite-Duration Poorman-Bidding Games (WINE 2018)] and also
[Guy Avni, Thomas A. Henzinger, Rasmus Ibsen-Jensen, Petr Novotný: Bidding Games on Markov Decision Processes (RP 2019)].