Nie jesteś zalogowany | Zaloguj się

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.