# Turing's Invisible Hand

Feeds:
Posts
Comments

## A new randomized mechanism for multi-unit auctions

April 28, 2009 by algorithmicgametheory

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.

About these ads

Posted in Uncategorized | Tagged auctions, New papers | 1 Comment

### 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.) [...]

Cancel
Post was not sent - check your email addresses!
Email check failed, please try again
Sorry, your blog cannot share posts by email.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 14, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.912431538105011, "perplexity_flag": "middle"}