Computer Science/Discrete Mathematics Seminar I

We study algorithms for combinatorial market design problems, where a collection of objects are priced and sold to potential buyers subject to equilibrium constraints. We introduce the notion of a combinatorial Walrasian equilibrium (CWE) as a natural relaxation of Walrasian equilibrium, an appealing and robust notion of market pricing equilibrium. The only difference between a CWE and a (non-combinatorial) WE is the ability for the seller to pre-bundle the items prior to sale. This innocuous and natural bundling operation opens up a plethora of algorithmic challenges and opportunities. Unlike WE, which is guaranteed to exist only for a very restricted class of valuations, a CWE always exists. The main algorithmic challenge, therefore, is to design computationally efficient mechanisms that generate CWE outcomes that approximately maximize social welfare. We provide some results on CWE from both the economic and the algorithmic standpoints. If we are not required to sell all of the items, then we show that any market outcome can be converted (in polynomial time) into a CWE that obtains at least half of the original social welfare. Also, there always exists a CWE that extracts at least a logarithmic fraction of the optimal social welfare as revenue, and this bound is tight. If we also insist that all items be sold, then these results continue to hold for a variety of valuation classes, including super-additive and certain budget-additive valuations. Joint work with Brendan Lucier and Nick Gravin.