Approximate Mechanisms without Payments

• Antragsteller: Dr. Felix Fischer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2009 bis 2012
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 153869771

Mechanism design is concerned with the design of protocols - so-called mechanisms - for aggregating the preferences of a group of human or artificial agents, who may misrepresent their preferences to achieve a better outcome for themselves. In this context, a mechanism is called incentive compatible if it is in the best interest of each agent to reveal his preferences truthfully. A common technique to make mechanisms incentive compatible uses monetary transfers between agents. The assumption that such payments can be made is however problematic for a variety of reasons: for example, it is often not clear how to enforce payments in open systems like the Internet, and ethical or legal considerations may prevent the use of money in specic scenarios. The goal of the proposed project is to study the power of mechanisms that sacrice optimality of the outcome in order to achieve incentive compatibility without payments. More specifically, I intend to improve and extend results recently obtained for a machine learning problem, and design mech- anisms without payments for central problems in algorithmic mechanism design, like scheduling or resource allocation. Two specific issues I want to investigate concern resistance against manipulation by groups of agents, a property large classes of payment-based mechanisms cannot guarantee, andthe role of randomization in the design of mechanisms without payments.

• DFG-Verfahren: Forschungsstipendien
• Internationaler Bezug: USA
• Gastgeber: Professor David C. Parkes