Invited Session Wed.2.MA 005

Wednesday, 13:15 - 14:45 h, Room: MA 005

Cluster 8: Game theory [...]

Polynomial-time algorithms for mechanism design


Chair: Berthold Vöcking



Wednesday, 13:15 - 13:40 h, Room: MA 005, Talk 1

Piotr Krysta
Combinatorial auctions with verification

Coauthors: Dimitris Fotakis, Carmine Ventre


We study mechanism design for social welfare maximization in combinatorial auctions with general bidders. It is a major open problem in this setting to design a deterministic truthful auction which would provide the best possible approximation guarantee in polynomial time, even if bidders are double-minded (i.e., they assign positive value to only two sets in their demand collection of sets). On the other hand, there are known such randomized truthful auctions in this setting. We introduce a general model of verification (i.e., some kind of overbidding can be detected) and we design in this model the first deterministic truthful auctions which indeed provide essentially the best possible approximation guarantees achievable by any polynomial-time algorithm. This shows that deterministic truthful auctions have the same power as randomized ones if the bidders withdraw from unrealistic lies.



Wednesday, 13:45 - 14:10 h, Room: MA 005, Talk 2

Gergely Csapo
The private provision of a public good: Digging for gold

Coauthor: Rudolf Müller


We study the problem of finding the profit-maximizing mechanism for the provision of a single, non-excludable public good. This problem has been well studied for the case when the valuations of the agents are independently distributed, but the literature is silent about the general case. We focus on general joint distributions, characterizing the deterministic mechanism implementable in dominant-strategies that yields the maximum revenue for the monopolistic provider of the public good. We investigate the problem from an automated mechanism design perspective and show that finding
the optimal mechanism can be solved in time polynomial in the number of types by reducing it to a maximal closure problem with respect to sum of conditional virtual values. We also conclude that in case of independent type distributions the optimal mechanism is the same as under Bayesian implementation and interim individual rationality.



Wednesday, 14:15 - 14:40 h, Room: MA 005, Talk 3

Angelina Vidali
Scheduling, auctions and truthfulness

Coauthors: George Christodoulou, Amos Fiat, Anna Karlin, Elias Koutsoupias


I will give an introduction and present some of my recent results in one of the most fundamental problems in algorithmic game theory and mechanism design: the problem of scheduling unrelated machines to minimize the makespan. I will emphasize the connection between this problem and the problem of designing truthful auctions for selling multiple items.
Finally I will present a geometrical characterization of truthfulness and also some very recent work on strongly truthful mechanisms.
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 thirteen years ago in the seminal paper of Nisan and Ronen, where it was shown that the approximation ratio of mechanisms is between 2 and n. I improve this to 1+√2 for three or more machines and to 1+\varphi for many machines. I also characterize the class of truthful mechanisms for the case of two players (regardless of approximation ratio) and show how the result can be used as a black box to obtain characterizations for other domains.


  online loans . But at the same time, it acts only with sexual arousal. Cheap Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.