Algorithmic mechanism design with a focus on scheduling mechanisms

• Applicant: Dr. Annamária Kovács
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 178419010

Motivated by the conquest of the Internet, algorithmic mechanism design (AMD) originated 10 years ago, in the idea to apply a classic micro-economic framework to traditional algorithmic optimization problems like routing or scheduling. The actors and resources in a typical interaction over the Internet belong to different parties, each supposed to show rational, selfish behaviour. This is modelled in AMD by a set of agents, holding private data as input to an algorithmic application whose outcome is of some value to them, and willing to falsify data if this serves their monetary interests. We aim to carry out basic research on major open problems of AMD. For instance, in a scheduling application where workloads are distributed among machines of different speeds, a machine-owner might bid a lower or higher speed so as to get less work, or higher payment. The task is to find a scheduling algorithm, extended with payments that motivate truthful bidding. These strategic variants of the classic optimization problems of scheduling on related (resp. unrelated) machines were formulated in fundamental works, and are known as paradigmatic problems of AMD. While being of interest in their own right, they also serve as a perfect test-field for how the new strategic component influences solvability of a classic problem. The partial solutions and answers provided so far, leave open many of the basic questions. We will focus on (1) near-optimal mechanisms for related scheduling; (2) approximability of unrelated scheduling; (3) Bayesian price of anarchy in combinatorial auctions.

• DFG Programme: Research Grants