Combinatorial Walrasian Equilibrium
Michal Feldman , The Hebrew University of Jerusalem (currently a visiting scholar at the Center for Research on Computation and Society (CRCS) at Harvard University)
| When: | Sep 13, 2012 | 4:00 pm - 5:30 pm |
|---|---|
| Where: | Maxwell Dworkin G125 |
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.
| Speaker Biography: | Michal Feldman received her Ph.D. in 2005 from the University of California at Berkeley. Following a postdoc at the Hebrew University and at Tel-Aviv University, she joined the faculty of the School of Business Administration at the Hebrew University (in 2007). Her research focuses on the intersection of game theory, computer science and microeconomics, a field often termed "Algorithmic Game Theory". She has been recently awarded a Marie Curie grant, and is currently a visiting scholar at the Center for Research on Computation and Society (CRCS) at Harvard University. |
|---|---|
| Host: | Yiling Chen |
| Contact: |
Gioia Sweetland
gioia@seas.harvard.edu 617-495-2919 |
| Add to Calendar: |
 vCal iCal
|
