TU Wien Informatics

20 Years

Talk: Designing Truthful Mechanisms

  • 2011-05-10
  • Research

Dr. Vidali will present her work on aspects of one fundamental problem in algorithmic game theory, the scheduling of unrelated machines to minimize the makespan

In this talk I will present my work on many different aspects of one of the most fundamental problems in algorithmic game theory (and more specifically algorithmic mechanism design), the problem of scheduling unrelated machines to minimize the makespan and I will also explain its connection with the problem of designing truthful combinatorial auctions.

We assume that the machines behave like selfish players: they have to get paid in order to process the tasks, and would lie about their processing times if they could increase their utility in this way. The problem was proposed and studied in the seminal paper of Nisan and Ronen, where it was shown that the approximation ratio of mechanisms is between 2 and n.

Speakers

  • Dr. Angelina Vidali, Research Group of Theory and Applications of Algorithms, University Vienna

Links

Curious about our other news? Subscribe to our news feed, calendar, or newsletter, or follow us on social media.

Note: This is one of the thousands of items we imported from the old website. We’re in the process of reviewing each and every one, but if you notice something strange about this particular one, please let us know. — Thanks!