(New) 8 May 2026, Computational Social Choice Seminar, Sophie Klumper

Abstract

We initiate the study of mechanism design with outliers and consider facility location with n strategic agents as a test case. In this setting, a mechanism may exclude z<n-1 agents from the social cost objective. Accounting for outliers is particularly meaningful when some agents are malicious or have extreme preferences, as it can prevent them from disproportionately influencing the solution, thereby yielding more equitable outcomes for the broader population. We provide a comprehensive analysis of the impact of outliers under both the utilitarian and egalitarian objectives. In particular, we study deterministic, randomized, and learning-augmented mechanisms, and obtain matching upper and lower bounds. Our results reveal several counterintuitive phenomena: for example, our lower bound for the egalitarian objective persists for mechanisms that are strategyproof in expectation or have access to a prediction of the optimal location, both in stark contrast to the setting without outliers. This is joint work with Argyrios Deligkas, Eduard Eiben, Guido Schäfer, and Artem Tsikiridis.

For more information on the Computational Social Choice Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/.