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


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


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


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.


  Most online loan lenders allow getting Payday Loans New Jersey without visiting a bank, straight to your bank account. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.