{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T01:22:49Z","timestamp":1787361769068,"version":"build-2736575974"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>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 (noncombinatorial) 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 the optimal (unconstrained) social welfare. Moreover, we devise a polynomial time algorithm that, given an arbitrary allocation, computes a CWE that achieves at least half its welfare. 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, to motivate the use of bundles, we establish strong lower bounds when the seller is restricted to using item prices only. 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.<\/jats:p>","DOI":"10.1137\/13094339x","type":"journal-article","created":{"date-parts":[[2016,1,6]],"date-time":"2016-01-06T12:28:21Z","timestamp":1452083301000},"page":"29-48","source":"Crossref","is-referenced-by-count":16,"title":["Combinatorial Walrasian Equilibrium"],"prefix":"10.1137","volume":"45","author":[{"given":"Michal","family":"Feldman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nick","family":"Gravin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brendan","family":"Lucier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,1,6]]},"reference":[{"key":"atypb1","first-page":"482","author":"Archer A.","year":"2001","journal-title":"Proceedings of FOCS"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.2307\/1913073"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"L. M. Ausubel and P. R. Milgrom,\n                      Ascending auctions with package bidding\n                      , B. E. J. Theor. Econ. (2002).","DOI":"10.2202\/1534-5963.1019"},{"key":"atypb4","first-page":"110","volume":"2012","author":"Badanidiyuru A.","journal-title":"Proceedings of EC"},{"key":"atypb5","first-page":"50","volume":"2008","author":"Balcan M.-F.","journal-title":"Proceedings of EC"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"X. Bei and Z. Huang,\n                      Bayesian incentive compatibility via fractional assignments\n                      , in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 720-733.","DOI":"10.1137\/1.9781611973082.57"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1996.2269"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.2001.2957"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/050641181"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2009.10.012"},{"key":"atypb11","first-page":"13","author":"Briest P.","year":"2006","journal-title":"ECCC"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"Y. Cai, C. Daskalakis, and S. M. Weinberg,\n                      Understanding incentives: Mechanism design becomes algorithm design\n                      , in Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, 2013, pp. 618-627.","DOI":"10.1109\/FOCS.2013.72"},{"key":"atypb13","first-page":"35","author":"Cheung M.","year":"2008","journal-title":"Proceedings of FOCS"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"Y. K. Cheung, R. Cole, and N. Devanur,\n                      Tatonnement beyond gross substitutes? Gradient descent to the rescue\n                      , in Proceedings of the 45th Annual ACM Symposium on Theory of Computing, New York, 2013, ACM, pp. 191-200.","DOI":"10.1145\/2488608.2488633"},{"key":"atypb15","first-page":"74","author":"Codenotti B.","year":"2005","journal-title":"MD"},{"key":"atypb16","first-page":"159","volume":"2010","author":"Cohen E.","journal-title":"Proceedings of EC"},{"key":"atypb17","first-page":"315","author":"Cole R.","year":"2008","journal-title":"Victoria, BC, Canada"},{"key":"atypb18","first-page":"15","author":"Dhangwatnotai P.","year":"2008","journal-title":"Proceedings of FOCS"},{"key":"atypb19","first-page":"139","author":"Dobzinski S.","year":"2011","journal-title":"Proceedings of STOC"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"S. Dobzinski, M. Feldman, I. Talgam-Cohen, and O. Weinstein,\n                      Welfare and Revenue Guarantees for Competitive Bundling Equilibrium\n                      , CoRR, abs\/1406.0576, 2014.","DOI":"10.1007\/978-3-662-48995-6_22"},{"key":"atypb21","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1145\/1132516.1132607","author":"Dobzinski S.","year":"2006","journal-title":"Proceedings of STOC"},{"key":"atypb22","first-page":"667","author":"Feige U.","year":"2006","journal-title":"Proceedings of FOCS"},{"key":"atypb23","first-page":"123","author":"Feldman M.","year":"2015","journal-title":"Proceedings of SODA"},{"key":"atypb24","unstructured":"M. Feldman, N. Gravin, and B. Lucier,\n                      On Welfare Approximation and Stable Pricing\n                      , arXiv:1511.02399 [cs.GT], 2015."},{"key":"atypb25","first-page":"158","author":"Feldman M.","year":"2014","journal-title":"Proceedings of SAGT"},{"key":"atypb26","first-page":"498","author":"Fiat A.","year":"2009","journal-title":"Proceedings of WINE"},{"key":"atypb27","first-page":"45","volume":"7","author":"Foley D.","year":"1967","journal-title":"Yale Econom. Essays"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"H. Fu, R. Kleinberg, and R. Lavi,\n                      Conditional equilibrium outcomes via ascending price processes with applications to combinatorial auctions with item bidding\n                      , in Proceedings of EC, 2012, ACM, p. 586.","DOI":"10.1145\/2229012.2229055"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2531"},{"key":"atypb31","first-page":"1164","author":"Guruswami V.","year":"2005","journal-title":"Proceedings of SODA"},{"key":"atypb32","first-page":"734","author":"Hartline J. D.","year":"2011","journal-title":"Proceedings of SODA"},{"key":"atypb33","first-page":"301","author":"Hartline J. D.","year":"2010","journal-title":"Proceedings of STOC"},{"key":"atypb34","first-page":"243","volume":"2011","author":"Hartline J. D.","journal-title":"Proceedings of EC"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/S0899-8256(03)00184-2"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.2307\/1913392"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585266"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1086\/261158"},{"key":"atypb39","first-page":"70","volume":"2008","author":"Mirrokni V.","journal-title":"Proceedings of EC"},{"key":"atypb40","first-page":"120","author":"Mu'alem A.","year":"2009","journal-title":"New York"},{"key":"atypb41","first-page":"250","author":"Papadimitriou C. H.","year":"2008","journal-title":"Proceedings of FOCS"},{"key":"atypb42","first-page":"74","author":"Parkes D. C.","year":"2000","journal-title":"Proceedings of AAAI"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1007\/BF01753437"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(74)90075-1"},{"key":"atypb45","unstructured":"L. Walras,\n                      Elements of Pure Economics: Or the Theory of Social Wealth\n                      , Routledge, London, 2003."},{"key":"atypb46","first-page":"21","volume":"2000","author":"Wurman P. R.","journal-title":"Proceedings of EC"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/13094339X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:54:39Z","timestamp":1787338479000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/13094339X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/13094339X"],"URL":"https:\/\/doi.org\/10.1137\/13094339x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}