|
|
Warut Suksompong (National University of Singapore, Singapore)
|
|
August 4 (Sunday), Early afternoon session (1:45 hours)
|
|
The theory of social choice is primarily concerned with choosing a socially desirable outcome from a given set of alternatives. In many practical scenarios, these decisions are made based on pairwise comparisons between alternatives, also known as tournaments. A familiar example of tournaments arises in sports competitions, where players or teams compete against each other in head-to-head matches in order to determine the winner of the competition. For instance, several sports competitions, including Grand Slam tennis, NCAA basketball, and FA Cup football, are run using single-elimination tournaments, also known as knockout tournaments. Beyond sports competitions, tournaments serve to model a number of scenarios ranging from voting to webpage ranking to biological interactions. Problems pertaining to tournaments often involve the use of algorithms and have therefore attracted significant attention from computational social choice researchers over the past two decades. Much of the relevant research has been published in major artificial intelligence venues, including IJCAI.
In this tutorial, we will begin by providing an introduction to tournaments and their applications for newcomers in the area. In the first main part, we will discuss tournament solutions, which are methods for selecting the best alternatives according to pairwise comparisons. After providing an overview of the most common tournament solutions, we will address recent frameworks and perspectives in the study of tournament solutions. This includes the margin of victory, which allows us to refine tournament solutions by differentiating among winners, and strategic considerations in randomized tournament solutions. We will then proceed in the second part to single-elimination tournaments, in particular the problem of fixing such a tournament, also known as the tournament fixing problem. We will outline algorithms as well as structural results that guarantee a player’s ability to win the tournament under some bracket. In addition, we will highlight important variants such as allowing bribery or taking seed constraints into account. Finally, we will specify a number of open questions and directions for future work.
No prior knowledge of tournaments or game theory is assumed. We believe that the tutorial will be useful for anyone who wants to find out about current directions in tournaments, learn interesting frameworks and tools, or simply get an introduction to the area.
|
|
Warut Suksompong is an assistant professor in the School of Computing at the National University of Singapore. Previously, he was a postdoctoral researcher at the University of Oxford, UK, and completed his PhD in the Department of Computer Science at Stanford University, USA. He is interested in algorithmic game theory, mechanism design, social choice theory, and other problems at the interface between computer science, economics, mathematics, and operations research. In addition to tournaments, he has worked extensively on fair resource allocation, as well as on multiwinner voting, donor coordination, and coalition formation.
|
|
|
|
Survey: Tournaments in Computational Social Choice: Recent Developments, IJCAI 2021
|
|