Strategy proof location mechanisms on graphs with a cycle
- Prelegent(ci)
- Krzysztof Rogowski
- Afiliacja
- University of Warsaw
- Język referatu
- angielski
- Termin
- 17 października 2024 12:15
- Pokój
- p. 4050
- Tytuł w języku polskim
- Strategy proof location mechanisms on graphs with a cycle
- Seminarium
- Seminarium „Gry, mechanizmy i sieci społeczne”
The facility location problem involves selecting an optimal point on a graph to serve a group of agents, who may act strategically by misreporting their preferences to maximize their individual utility. This behavior motivates the study of strategyproof mechanisms, which aim to elicit truthful preferences from agents, often at the expense of returning suboptimal solutions. Over the years, significant progress has been made in understanding the trade-off between truthfulness and optimality, leading to various performance bounds for strategyproof mechanisms across different settings.
In my master’s thesis, I investigate this trade-off in a standard setting with a single facility location problem where the objective is to minimize social cost. Specifically, I study the PCD (Proportional Circle Distance) mechanism, establishing new performance bounds when the underlying graph is a circle and the number of agents is fixed. Additionally, I propose new mixed mechanisms, which, based on numerical experiments, show promising improvements over existing approaches. In my presentation, I will share these theoretical findings and provide an overview of the methods used in recent studies of mixed mechanisms.