Robin Hood Reachability Bidding Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909439311740928 |
|---|---|
| author | Almagor, Shaull Avni, Guy Dafni, Neta |
| author_facet | Almagor, Shaull Avni, Guy Dafni, Neta |
| contents | Two-player graph games are a fundamental model for reasoning about the interaction of agents. These games are played between two players who move a token along a graph. In bidding games, the players have some monetary budget, and at each step they bid for the privilege of moving the token. Typically, the winner of the bid either pays the loser or the bank, or a combination thereof. We introduce Robin Hood bidding games, where at the beginning of every step the richer player pays the poorer a fixed fraction of the difference of their wealth. After the bid, the winner pays the loser. Intuitively, this captures the setting where a regulating entity prevents the accumulation of wealth to some degree.
We show that the central property of bidding games, namely the existence of a threshold function, is retained in Robin Hood bidding games. We show that finding the threshold can be formulated as a Mixed-Integer Linear Program. Surprisingly, we show that the games are not always determined exactly at the threshold, unlike their standard counterpart. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_17718 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Robin Hood Reachability Bidding Games Almagor, Shaull Avni, Guy Dafni, Neta Computer Science and Game Theory Two-player graph games are a fundamental model for reasoning about the interaction of agents. These games are played between two players who move a token along a graph. In bidding games, the players have some monetary budget, and at each step they bid for the privilege of moving the token. Typically, the winner of the bid either pays the loser or the bank, or a combination thereof. We introduce Robin Hood bidding games, where at the beginning of every step the richer player pays the poorer a fixed fraction of the difference of their wealth. After the bid, the winner pays the loser. Intuitively, this captures the setting where a regulating entity prevents the accumulation of wealth to some degree. We show that the central property of bidding games, namely the existence of a threshold function, is retained in Robin Hood bidding games. We show that finding the threshold can be formulated as a Mixed-Integer Linear Program. Surprisingly, we show that the games are not always determined exactly at the threshold, unlike their standard counterpart. |
| title | Robin Hood Reachability Bidding Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2412.17718 |