From worst-case to beyond: fair, efficient, and truthful decision-making algorithms

Abstract

Algorithms increasingly play a central role in decision-making, from selecting representatives and allocating shared resources to scheduling tasks in large-scale systems. Designing such algorithms raises a range of challenges. In some settings, outcomes should be fair and representative, as studied in social choice theory. In others, participants may act strategically, requiring mechanisms that ensure truthful behavior. In many applications, decisions must be made online, without full knowledge of future inputs. These challenges are unified by the presence of incomplete information. This thesis studies algorithmic decision-making under incomplete information across social choice, mechanism design, and online algorithms. It combines classical worst-case analysis with beyond-worst-case approaches that exploit additional structure, including potentially incorrect predictions. The thesis develops algorithms that achieve strong performance guarantees while respecting constraints such as fairness, truthfulness, and robustness. A central theme is understanding which forms of additional information are truly useful, how they interact with algorithmic guarantees, and when fundamental limitations cannot be overcome. Together, the results advance the theoretical foundations of decision-making algorithms and provide a unified perspective on fairness, incentives, uncertainty, and prediction in algorithmic systems.

Algorithmen spielen eine zunehmend zentrale Rolle in Entscheidungsprozessen, etwa bei der Auswahl von Repräsentanten, der Zuteilung gemeinsamer Ressourcen oder der Planung von Aufgaben in großen Systemen. Die Entwicklung solcher Algorithmen ist mit unterschiedlichen Herausforderungen verbunden. In einigen Kontexten sollen Entscheidungen fair und repräsentativ sein, etwa bei Wahlen. In anderen handeln Beteiligte strategisch, sodass Mechanismen erforderlich sind, die wahrheitsgemäßes Verhalten sicherstellen. In vielen Anwendungen müssen Entscheidungen zudem online getroffen werden, ohne Kenntnis zukünftiger Eingaben. Allen diesen Problemen ist gemeinsam, dass Entscheidungen unter unvollständiger Information getroffen werden. Diese Dissertation untersucht algorithmische Entscheidungsfindung unter unvollständiger Information bei Wahlen, im Mechanismendesign und bei Online-Algorithmen. Sie verbindet klassische Worst-Case-Analyse mit Beyond-Worst-Case-Ansätzen, die zusätzliche Struktur nutzen, etwa in Form möglicherweise unzuverlässiger Vorhersagen. Ziel ist es, Algorithmen zu entwickeln, die trotz Fairness-, Anreiz- und Robustheitsanforderungen starke Leistungszusagen bieten. Ein zentrales Thema ist, welche zusätzliche Information tatsächlich hilfreich ist, wie sie algorithmische Garantien beeinflusst und wann grundlegende Grenzen bestehen.