Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.15068 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910583934156800 |
|---|---|
| author | Blažej, Václav Gupta, Sushmita Ramanujan, M. S. Strulo, Peter |
| author_facet | Blažej, Václav Gupta, Sushmita Ramanujan, M. S. Strulo, Peter |
| contents | Over the last decade, extensive research has been conducted on the algorithmic aspects of designing single-elimination (SE) tournaments. Addressing natural questions of algorithmic tractability, we identify key properties of input instances that enable the tournament designer to efficiently schedule the tournament in a way that maximizes the chances of a preferred player winning. Much of the prior algorithmic work on this topic focuses on the perfect (complete and deterministic) information scenario, especially in the context of fixed-parameter algorithm design. Our contributions constitute the first fixed-parameter tractability results applicable to more general settings of SE tournament design with potential imperfect information. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_15068 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Controlling Knockout Tournaments Without Perfect Information Blažej, Václav Gupta, Sushmita Ramanujan, M. S. Strulo, Peter Data Structures and Algorithms Computer Science and Game Theory Over the last decade, extensive research has been conducted on the algorithmic aspects of designing single-elimination (SE) tournaments. Addressing natural questions of algorithmic tractability, we identify key properties of input instances that enable the tournament designer to efficiently schedule the tournament in a way that maximizes the chances of a preferred player winning. Much of the prior algorithmic work on this topic focuses on the perfect (complete and deterministic) information scenario, especially in the context of fixed-parameter algorithm design. Our contributions constitute the first fixed-parameter tractability results applicable to more general settings of SE tournament design with potential imperfect information. |
| title | On Controlling Knockout Tournaments Without Perfect Information |
| topic | Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2408.15068 |