Informatik-Oberseminar: Selfishness and Uncertainty - Algorithmic Approaches in Truthful Mechanism Design

Montag, 23.04.2018, 14.30 Uhr

Ort: 4017 - Seminarraum Informatik I

Referentin: Rebecca Reiffenhäuser

Abstract:

When conducting an auction or election with the goal of welfare maximization, one has to rely on the participant's statements regarding their valuations for certain goods. However, the participants are in general likely to strategically misreport those valuations in their own favor. Designing truthful mechanisms or rules circumvents this trust problem by making truth-telling everyone's best strategy. We have a closer look at some offline and online auction problems and show how to design such rules with good approximation factors based on randomization. In particular, we focus on auctions based on the well-known generalized assignment problem and maximum-weight matchings in the online setting.

Es laden ein: Die Dozenten der Informatik