Automated Mechanism Design for Facility Location

Prelegent(ci)

Krzysztof Rogowski

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

25 czerwca 2026 14:00

Informacje na temat wydarzenia

seminar online

Seminarium

Seminarium „Ekonomia algorytmiczna”

---

We study the design of strategyproof (SP) mechanisms for facility location on metric graphs, with the objective of minimizing the total cost of agents. We develop a computational method that heuristically approximates the optimal mechanism by solving a finite linear program (LP). In the process, we introduce two new notions related to the problem: attributions, a non-uniform generalization of mixing mechanisms, and strong strategyproofness (SSP), a strengthening of SP that depends only on the local behavior of the mechanism. We apply our method to the special case of the cycle graph with 3 agents, obtaining a new mechanism that outperforms previously known mechanisms from the literature.

---