## 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**

**Abstract:**

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**

**Abstract:**

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**

**Abstract:**

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.