Feeds:
Posts

## A new randomized mechanism for multi-unit auctions

Shahar Dobzinski and Shaddin Dughmi just posted a new paper to the arXiv: On the Power of Randomization in Algorithmic Mechanism Design.

The mechanism design problem that they study in this paper is the basic one of a multi-unit auction: There are $M$ identical indivisible units of some good for sale among $n$ bidders, and each bidder $i$ has a valuation function $v_i : \{1 ... M\} \rightarrow \Re^+$, where $v_i(k)$ specifies his value from acquiring $k$ units.   The normal assumptions are free disposal i.e. that the valuation functions $v_i$ are monotone non-decreasing.   The goal is to find an allocation that gives $k_i$ units to each each bidder $i$ (and thus $\sum_i k_i \le M$) optimizing the social welfare $\sum_i v_i(k_i)$.

This problem is perhaps the simplest one exhibiting the key clash between computational complexity and incentive compatibility: since this is a social welfare maximization problem, the VCG mechanism that finds the optimal allocation is incentive compatible.  However, if we view the number of units $M$ as large, and require algorithms that work in time polynomial in $n$ and $\log M$, (assuming that the valuation functions are either concisely represented or are given as “black boxes”) then finding the optimal allocation is a knapsack problem and is thus computationally hard.  On the other hand, it is well known that the knapsack problem can be well-approximated efficiently (there is an FPTAS).  The clash is that we don’t know how to turn such an approximation algorithm into an incentive-compatible approximation mechanism.

This paper manages to find a randomized incentive-compatible approximation mechanism.  It also highlights the role and necessity of randomization in this setting.

### One Response

1. […] On the Power of Randomization in Algorithmic Mechanism Design by Shahar Dobzinski and Shaddin Dughmi.  (A link to the paper and some discussion in this blog post.) […]