| Popis: |
In combinatorial allocation problems, indivisible objects have to be assigned to selfish agents. A standard assumption for those problems is that agents have quasilinear utility functions. However, in many environments either money cannot be exchanged or agents cannot be assumed to maximize payoff. We focus on two specific non-quasilinear environments. First, we analyze a course allocation problem where students have preferences over schedules and report on a large-scale course assignment application at the TU Munich. Second, we study non-quasilinear utility functions as they have been reported for display ad auctions, and propose a truthful randomized approximation mechanism. In kombinatorischen Allokationsproblemen müssen unteilbare Objekte an eigennützige Agenten vergeben werden. Eine Standardannahme für solche Probleme ist, dass Agenten quasilineare Nutzenfunktionen haben. In vielen Umgebungen kann jedoch Geld nicht verwendet werden oder Agenten maximieren nicht den Gewinn. Wir fokussieren uns auf zwei spezielle nicht-quasilineare Umgebungen. Zunächst analysieren wir ein Kursvergabeproblem, bei dem Studenten Präferenzen über Stundenpläne haben und berichten über dessen Anwendung an der TU München. Außerdem analysieren wir nicht-quasilineare Nutzenfunktionen, wie für Display-Ad Auktionen und stellen einen anreizkompatiblen randomisierten Approximationsmechanismus vor. |
