Loading...
Please wait, while we are loading the content...
Similar Documents
Combinatorial walrasian equilibrium
| Content Provider | CiteSeerX |
|---|---|
| Author | Gravin, Nick Feldman, Michal Lucier, Brendan |
| Description | In STOC |
| Abstract | We study a combinatorial market design problem, where a collection of indivisible objects is to be priced and sold to potential buyers subject to equilibrium constraints. The classic solution concept for such problems is Walrasian Equilibrium (WE), which provides a simple and transparent pricing structure that achieves optimal social welfare. The main weakness of the WE notion is that it exists only in very restrictive cases. To overcome this limitation, we introduce the notion of a Combinatorial Walrasian equilibium (CWE), a natural relaxation of WE. The difference between a CWE and a (non-combinatorial) WE is that the seller can package the items into indivisible bundles prior to sale, and the market does not necessarily clear. We show that every valuation profile admits a CWE that obtains at least half of the optimal (unconstrained) social welfare. Moreover, we devise a poly-time algorithm that, given an arbitrary allocation X, computes a CWE that achieves at least half of the welfare of X. Thus, the economic problem of finding a CWE with high social welfare reduces to the algorithmic problem of social-welfare approximation. In addition, we show that every valuation profile admits a CWE that extracts a logarithmic fraction of the optimal welfare as revenue. Finally, these results are complemented by strong lower bounds when the seller is restricted to using item prices only, which motivates the use of bundles. The strength of our results derives partly from their generality — our results hold for arbitrary valuations that may exhibit complex combinations of substitutes and complements. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Combinatorial Walrasian Equilibrium Classic Solution Concept Arbitrary Allocation Potential Buyer Optimal Welfare Natural Relaxation Main Weakness Equilibrium Constraint Social-welfare Approximation Social Welfare Combinatorial Walrasian Equilibium Logarithmic Fraction Combinatorial Market Design Problem Indivisible Bundle Arbitrary Valuation Walrasian Equilibrium Poly-time Algorithm Restrictive Case Valuation Profile Indivisible Object Item Price Optimal Social Welfare Algorithmic Problem Complex Combination Transparent Pricing Structure High Social Welfare Reduces Economic Problem |
| Content Type | Text |
