## Invited Session Thu.1.MA 005

#### Thursday, 10:30 - 12:00 h, Room: MA 005

**Cluster 8: Game theory** [...]

### Mechanisms for resource allocation problems

**Chair: Giorgos Christodoulou**

**Thursday, 10:30 - 10:55 h, Room: MA 005, Talk 1**

**Carmine Ventre**

Using lotteries to approximate the optimal revenue

**Coauthor: Paul W. Goldberg**

**Abstract:**

There has been much recent work on the revenue-raising properties of truthful mechanisms for selling goods. Typically the revenue of a mechanism is compared against a benchmark (such as, the maximum revenue obtainable by an omniscient seller selling at a fixed price to at least two customers), with a view to understanding how much lower the mechanism's revenue is than the benchmark, in the worst case. Here we study this issue in the context of *lotteries*, where the seller may sell a probability of winning an item. We are interested in two general issues.

Firstly, we aim at using the true optimum revenue as benchmark for our auctions. Secondly, we study the extent to which the additional expressive power resulting from lotteries, helps to improve the worst-case ratio.

We study this in the well-known context of digital goods, where the production cost is zero.

We show that in this scenario, collusion-resistant lotteries (these are lotteries for which no coalition of bidders exchanging side payments has an advantage in lying) are as powerful as truthful ones.

**Thursday, 11:00 - 11:25 h, Room: MA 005, Talk 2**

**Vangelis Markakis**

On worst-case allocations in the presence of indivisible goods

**Coauthor: Christos-Alexandros Psomas**

**Abstract:**

We study a fair division problem with indivisible goods. In such settings, proportional allocations do not always exist, i.e., allocations where every agent receives a bundle of goods worth to him at least 1/*n*, with *n* being the number of agents. Hence one would like to find worst case guarantees on the value that every agent can have. We focus on algorithmic and mechanism design aspects of this problem. In the work of [Hill 1987], an explicit function was identified, such that for any instance, there exists an allocation that provides at least this guarantee to everybody. The proof however did not imply an efficient algorithm for finding such allocations. Following upon the work of Hill, we first provide a slight strengthening of the guarantee we can make for every agent, as well as a polynomial time algorithm for computing such allocations. We then move to the design of truthful mechanisms. For deterministic mechanisms, we obtain a negative result showing that a truthful 2/3-approximation of this guarantee is impossible. We complement this with a constant approximation for a constant number of goods. Finally we also establish some negative results for randomized algorithms.

**Thursday, 11:30 - 11:55 h, Room: MA 005, Talk 3**

**Annamaria Kovacs**

Characterizing anonymous scheduling mechanisms for two tasks

**Coauthor: Giorgos Christodoulou**

**Abstract:**

We study truthful mechanisms for domains with additive valuations, like scheduling mechanisms on unrelated machines, or additive combinatorial auctions. Providing a global, Roberts-like characterization of such mechanisms is a classic, long open problem. Among others, such a characterization could yield a definitive bound on the makespan approximation ratio of truthful scheduling.

We investigate special classes of allocation functions, and show that any allocation that is either locally efficient (envy-free) or anonymous ('player-symmetric') must be an special affine minimizer, i.e. a weighted version of the VCG allocation. This is the first characterization result for truthful unrelated scheduling on more than two machines.

Interestingly, for the `mirrored' problem of additive combinatorial auctions our characterization admits mechanisms different from affine minimizers. Thus our result demonstrates the inherent difference between the scheduling and the auctions domain, and inspires new questions related to truthfulness in additive domains.