Tata Institute of Fundamental Research
Bidding Games on Graphs : in Theory and in Practice
STCS Colloquium
Speaker:
Dr. Suman Sadhukhan (University of Haifa)
Organiser:
Shibashis Guha
Date:
Tuesday, 27 Feb 2024, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
In a two-player zero-sum graph game, the players move a token throughout the game, producing an infinite play, which determines the winner of the game. Bidding games are graph games in which in each turn, a bidding (auction) determines which player moves the token: the players have budgets, and in each turn, both players simultaneously submit the bids that do not exceed the available budgets. The higher bidder moves the token, and pays the bid to the lower bidder (called Richman bidding).
The standard solution concept of interest in bidding games are threshold budgets: the necessary and sufficient budget for winning the game.
In this survey talk, on the theoretical side, we will explore discrete bidding games, where the keyword discrete stands for the bids having a fixed granularity. We obtain membership in NP \cap coNP for solving parity bidding games with exponentially succinct representation.
This will be followed by our newly proposed application of bidding games to a decentralized synthesis problem for multi-objective decision making.
Here, synthesized policies express their scheduling urgency via bids and a bounded budget guarantees long-run fairness. Moreover, our proposed solution framework is modular, in the sense that if one objective changes, we may still combine the policy for the other objective without having the need to recompute it from scratch.
If time permits, we will also walk through the theoretical development of poorman counter-part of discrete bidding games, which we study for the first time, where instead of handing over the winning bid to the lower bidder, the winner of a bid pays to a bank.
These works have been in collaboration with Guy Avni, Kaushik Mallik, Tobias Meggendorfer, Josef Tkadlec, and Đorđe Žikelić.
Short Bio:
Suman Sadhukhan is currently a postdoctoral researcher at the University of Haifa. He obtained his PhD in 2022 from Inria Rennes where he was advised by Nathalie Bertrand, Nicolas Markey and Ocan Sankur. He is interested in, but not restricted to, Games on Graphs, studying different game theoretic models from formal verification and reactive synthesis viewpoint. Prior to his PhD training, he was a student at Chennai Mathematical Institute where he studied Theoretical Computer Science and Mathematics.
| Speaker: | Dr. Suman Sadhukhan (University of Haifa) |
| Organiser: | Shibashis Guha |
| Date: | Tuesday, 27 Feb 2024, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
In a two-player zero-sum graph game, the players move a token throughout the game, producing an infinite play, which determines the winner of the game. Bidding games are graph games in which in each turn, a bidding (auction) determines which player moves the token: the players have budgets, and in each turn, both players simultaneously submit the bids that do not exceed the available budgets. The higher bidder moves the token, and pays the bid to the lower bidder (called Richman bidding).
The standard solution concept of interest in bidding games are threshold budgets: the necessary and sufficient budget for winning the game.
In this survey talk, on the theoretical side, we will explore discrete bidding games, where the keyword discrete stands for the bids having a fixed granularity. We obtain membership in NP \cap coNP for solving parity bidding games with exponentially succinct representation.
This will be followed by our newly proposed application of bidding games to a decentralized synthesis problem for multi-objective decision making.
Here, synthesized policies express their scheduling urgency via bids and a bounded budget guarantees long-run fairness. Moreover, our proposed solution framework is modular, in the sense that if one objective changes, we may still combine the policy for the other objective without having the need to recompute it from scratch.
If time permits, we will also walk through the theoretical development of poorman counter-part of discrete bidding games, which we study for the first time, where instead of handing over the winning bid to the lower bidder, the winner of a bid pays to a bank.
These works have been in collaboration with Guy Avni, Kaushik Mallik, Tobias Meggendorfer, Josef Tkadlec, and Đorđe Žikelić.
Short Bio:
Suman Sadhukhan is currently a postdoctoral researcher at the University of Haifa. He obtained his PhD in 2022 from Inria Rennes where he was advised by Nathalie Bertrand, Nicolas Markey and Ocan Sankur. He is interested in, but not restricted to, Games on Graphs, studying different game theoretic models from formal verification and reactive synthesis viewpoint. Prior to his PhD training, he was a student at Chennai Mathematical Institute where he studied Theoretical Computer Science and Mathematics.