## Invited Session Tue.1.H 3010

#### Tuesday, 10:30 - 12:00 h, Room: H 3010

**Cluster 1: Approximation & online algorithms** [...]

### Approximation in algorithmic game theory

**Chair: Chaitanya Swamy**

**Tuesday, 10:30 - 10:55 h, Room: H 3010, Talk 1**

**Konstantinos Georgiou**

Black-box reductions for cost-sharing mechanism design

**Coauthor: Chaitanya Swamy**

**Abstract:**

We consider the design of *strategyproof* cost-sharing mechanisms, focusing mainly on the single-dimensional setting. We give two simple, but extremely versatile, *black-box reductions*, that in combination reduce the cost-sharing mechanism-design problem to the *algorithmic* problem of finding a minimum-cost solution for a set of players. Our first reduction shows that any *α*-approximation, truthful mechanism for the social-cost-minimization (SCM) problem that satisfies a technical no-bossiness condition can be morphed into a truthful mechanism that achieves an *α**log* n-approximation where the prices recover the cost incurred. This disconnects the task of truthfully computing an outcome with near-optimal social cost from the cost-sharing problem. Complementing this, our second reduction shows that any LP-based *ρ*-approximation for the problem of finding a min-cost solution for a set of players can be used to obtain a truthful, no-bossy, *(ρ+1)*-approximation for the SCM problem (and hence, a truthful *(ρ + 1)**log* n-approximation cost-sharing mechanism).

**Tuesday, 11:00 - 11:25 h, Room: H 3010, Talk 2**

**Berthold VĂ¶cking**

A universally-truthful approximation scheme for multi-unit auctions

**Abstract:**

We present a randomized, polynomial-time approximation scheme for multi-unit auctions. Our mechanism is truthful in the universal sense, i.e., a distribution over deterministically truthful mechanisms. Previously known approximation schemes were truthful in expectation which is a weaker notion of truthfulness assuming risk neutral bidders. The existence of a universally truthful approximation scheme was questioned by previous work showing that multi-unit auctions with certain technical restrictions on their output do not admit a polynomial-time, universally truthful mechanism with approximation factor better than two.

Our new mechanism employs VCG payments in a non-standard way: The deterministic mechanisms underlying our universally truthful approximation scheme are not maximal in range and do not belong to the class of affine maximizers which, on a first view, seems to contradict previous characterizations of VCG-based mechanisms. Instead, each of these deterministic mechanisms is composed of a collection of affine maximizers, one for each bidder which yields a subjective variant of VCG.

**Tuesday, 11:30 - 11:55 h, Room: H 3010, Talk 3**

**Deeparnab Chakrabarty**

Matching markets with ordinal preferences

**Coauthors: Anand Bhalgat, Sanjeev Khanna, Chaitanya Swamy**

**Abstract:**

In this talk we will consider the following basic economic problem: given *n* agents and *n* items with agents having a preference over these items, how should we allocate items to agents? The answer will depend on what we hope to achieve - we will see this goal is not very clear always. Furthermore, we would like our mechanisms which achieve these goals to be strategyproof - we will see that the definition of the same also is also arguable. After covering some groundwork, we'll describe some new analysis of old mechanisms, and (also new) analysis of some new algorithms.