|
Computer Science Seminar Date: Tuesday, 5 March 2024 Time: 3:30 PM to 4:30 PM Venue: Seminar Hall Bidding Games on Graphs - In theory and in practice Suman Sadhukhan Haifa University, Israel. 05-03-24 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. These works have been in collaboration with Guy Avni and Kaushik Mallik.
|
