Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms

Abstract

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^η) for any constant η < 1/2 and run in polynomial time, unless NP ⊆ 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.

Files

Additional details