Notes on Inapproximability for VCG-Based Combinatorial Auctions

As with all my handwritten notes, this has the usual disclaimer: these posts are just so I can use nice inedxed search to easily search for my notes, which are sufficient for me to recall talks and papers but probably not much use to anyone else. Paper here. Commentary here (from Paul Goldberg).

This presentation was based on the merger of VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension and Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms, so the notes for each are pretty brief.

In this paper, we consider the problem of designing incentive compatible auctions for multiple (homogeneous) units of a good, when bidders have private valuations and private budget constraints. When only the valuations are private and the budgets are public, Dobzinski {\em et al} show that the {\em adaptive clinching} auction is the unique incentive-compatible auction achieving Pareto-optimality. They further show thatthere is no deterministic Pareto-optimal auction with private budgets. Our main contribution is to show the following Budget Monotonicity property of this auction: When there is only one infinitely divisible good, a bidder cannot improve her utility by reporting a budget smaller than the truth. This implies that a randomized modification to the adaptive clinching auction is incentive compatible and Pareto-optimal with private budgets.
The Budget Monotonicity property also implies other improved results in this context. For revenue maximization, the same auction improves the best-known competitive ratio due to Abrams by a factor of 4, and asymptotically approaches the performance of the optimal single-price auction.
Finally, we consider the problem of revenue maximization (or social welfare) in a Bayesian setting. We allow the bidders have public size constraints (on the amount of good they are willing to buy) in addition to private budget constraints. We show a simple poly-time computable 5.83-approximation to the optimal Bayesian incentive compatible mechanism, that is implementable in dominant strategies. Our technique again crucially needs the ability to prevent bidders from over-reporting budgets via randomization.


Links to the un-merged papers: Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms and VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension

The existence of incentive-compatible computationally-efficient protocols for combinatorial auctions with decent approximation ratios is the paradigmatic problem in computational mechanism design. It is believed that in many cases good approximations for combinatorial auctions may be unattainable due to an inherent clash between truthfulness and computational efficiency. However, to date, researchers lack the machinery to prove such results. In this paper, we present a new approach that we believe holds great promise for making progress on this important problem. We take the first steps towards the development of new technologies for lower bounding the VC dimension of k-tuples of disjoint sets. We apply this machinery to prove the first computational-complexity inapproximability results for incentive-compatible mechanisms for combinatorial auctions. These results hold for the important class of VCG-based mechanisms, and are based on the complexity assumption that NP has no polynomial-size circuits.

Many commonly-used auction mechanisms are “maximal-in-range”. We show that any maximal-in-range mechanism for n bidders and m items cannot both approximate the social welfare with a ratio better than min(n,m^eta) for any constant eta < 1/2 and run in polynomial time, unless NP is contained in P/poly . This significantly improves upon a previous bound on the achievable social welfare of polynomial time maximal-in-range mechanisms of 2n/(n+1) for constant n. Our bound is tight, as a min(n,2m^1/2) approximation of the social welfare is achievable.

Notes on Inapproximability for VCG-Based Combinatorial Auctions

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s