2011/06/06 by Saeed Alaei, Alaei, Saeed · 15 citations
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 #Housing Market and Economics #Law, Economics, and Judicial Systems
paper · pdf · doi:10.48550/arxiv.1106.0961
openalex publication_date 2011/06/06 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
For Bayesian combinatorial auctions, we present a general framework for\napproximately reducing the mechanism design problem for multiple buyers to\nsingle buyer sub-problems. Our framework can be applied to any setting which\nroughly satisfies the following assumptions: (i) buyers' types must be\ndistributed independently (not necessarily identically), (ii) objective\nfunction must be linearly separable over the buyers, and (iii) except for the\nsupply constraints, there should be no other inter-buyer constraints. Our\nframework is general in the sense that it makes no explicit assumption about\nbuyers' valuations, type distributions, and single buyer constraints (e.g.,\nbudget, incentive compatibility, etc).\n We present two generic multi buyer mechanisms which use single buyer\nmechanisms as black boxes; if an \α-approximate single buyer mechanism\ncan be constructed for each buyer, and if no buyer requires more than\n\(1)/(k) of all units of each item, then our generic multi buyer\nmechanisms are \γk\α-approximation of the optimal multi buyer\nmechanism, where \γk is a constant which is at least\n1-\(1)/(\√(k+3)). Observe that \γk is at least 1/2 (for k=1)\nand approaches 1 as k \→ \∞. As a byproduct of our construction, we\npresent a generalization of prophet inequalities. Furthermore, as applications\nof our framework, we present multi buyer mechanisms with improved approximation\nfactor for several settings from the literature.\n