2015/11/07 by Michal Feldman, Feldman, Michal, Nick Gravin +3 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1511.02399
openalex publication_date 2015/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the power of item-pricing as a tool for approximately optimizing social welfare in a combinatorial market. We consider markets with m indivisible items and n buyers. The goal is to set prices to the items so that, when agents purchase their most demanded sets simultaneously, no conflicts arise and the obtained allocation has nearly optimal welfare. For gross substitutes valuations, it is well known that it is possible to achieve optimal welfare in this manner. We ask: can one achieve approximately efficient outcomes for valuations beyond gross substitutes? We show that even for submodular valuations, and even with only two buyers, one cannot guarantee an approximation better than Ω(√(m)). The same lower bound holds for the class of single-minded buyers as well. Beyond the negative results on welfare approximation, our results have daunting implications on revenue approximation for these valuation classes: in order to obtain good approximation to the collected revenue, one would necessarily need to abandon the common approach of comparing the revenue to the optimal welfare; a fundamentally new approach would be required.