Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.06626 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912077518471168 |
|---|---|
| author | Sauerberg, Nathaniel Oesterheld, Caspar |
| author_facet | Sauerberg, Nathaniel Oesterheld, Caspar |
| contents | Prior work has studied the computational complexity of computing optimal strategies to commit to in Stackelberg or leadership games, where a leader commits to a strategy which is observed by one or more followers. We extend this setting to one where the leader can additionally commit to outcome-conditional utility transfers. We characterize the computational complexity of finding optimal strategies in normal-form and Bayesian games, giving a mix of efficient algorithms and NP-hardness results. Finally, we allow the leader to also commit to a signaling scheme which induces a correlated equilibrium. In this setting, optimal commitments can be found in polynomial time for arbitrarily many players. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_06626 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing Optimal Commitments to Strategies and Outcome-Conditional Utility Transfers Sauerberg, Nathaniel Oesterheld, Caspar Computer Science and Game Theory Prior work has studied the computational complexity of computing optimal strategies to commit to in Stackelberg or leadership games, where a leader commits to a strategy which is observed by one or more followers. We extend this setting to one where the leader can additionally commit to outcome-conditional utility transfers. We characterize the computational complexity of finding optimal strategies in normal-form and Bayesian games, giving a mix of efficient algorithms and NP-hardness results. Finally, we allow the leader to also commit to a signaling scheme which induces a correlated equilibrium. In this setting, optimal commitments can be found in polynomial time for arbitrarily many players. |
| title | Computing Optimal Commitments to Strategies and Outcome-Conditional Utility Transfers |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2402.06626 |