2020/07/10 by Natalie Collina, S. Matthew Weinberg, Collina, Natalie +1
Business, Management and Accounting · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Consumer Market Behavior and Pricing #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2007.05164
openalex publication_date 2020/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a revenue-maximizing single seller with m items for sale to a\nsingle buyer whose value v(\⋅) for the items is drawn from a known\ndistribution D of support k. A series of works by Cai et al. establishes\nthat when each v(\⋅) in the support of D is additive or unit-demand (or\nc-demand), the revenue-optimal auction can be found in\n\poly(m,k) time.\n We show that going barely beyond this, even to matroid-based valuations (a\nproper subset of Gross Substitutes), results in strong hardness of\napproximation. Specifically, even on instances with m items and k \≤ m\nvaluations in the support of D, it is not possible to achieve a\n1/m1-\ε-approximation for any \ε>0 to the\nrevenue-optimal mechanism for matroid-based valuations in (randomized)\npoly-time unless NP \⊆ RP (note that a 1/k-approximation is\ntrivial).\n Cai et al.'s main technical contribution is a black-box reduction from\nrevenue maximization for valuations in class \V to optimizing the\ndifference between two values in class \V. Our main technical\ncontribution is a black-box reduction in the other direction (for a wide class\nof valuation classes), establishing that their reduction is essentially tight.\n