{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:58:30Z","timestamp":1725551910674},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540309000"},{"type":"electronic","value":"9783540322931"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11600930_15","type":"book-chapter","created":{"date-parts":[[2005,11,24]],"date-time":"2005-11-24T14:48:12Z","timestamp":1132843692000},"page":"141-150","source":"Crossref","is-referenced-by-count":2,"title":["Walrasian Equilibrium: Hardness, Approximations and Tractable Instances"],"prefix":"10.1007","author":[{"given":"Ning","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atri","family":"Rudra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","unstructured":"Archer, A., Papadimitriou, C.H., Talwar, K., Tardos, E.: An Approximate Truthful Mechanism For Combinatorial Auctions with Single Parameter Agents. In: SODA 2003, pp. 205\u2013214 (2003)"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Archer, A., Tardos, E.: Truthful Mechanisms for One-Parameter Agents. In: FOCS 2001, pp. 482\u2013491 (2001)","DOI":"10.1109\/SFCS.2001.959924"},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"265","DOI":"10.2307\/1907353","volume":"22","author":"K.K. Arrow","year":"1954","unstructured":"Arrow, K.K., Debreu, G.: Existence of An Equilibrium for a Competitive Economy. Econometrica\u00a022, 265\u2013290 (1954)","journal-title":"Econometrica"},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1006\/jeth.1996.2269","volume":"74","author":"S. Bikhchandani","year":"1997","unstructured":"Bikhchandani, S., Mamer, J.W.: Competitive Equilibrium in an Economy with Indivisibilities. Journal of Economic Theory\u00a074, 385\u2013413 (1997)","journal-title":"Journal of Economic Theory"},{"issue":"4","key":"15_CR5","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1016\/j.jcss.2004.04.012","volume":"69","author":"N. Chen","year":"2004","unstructured":"Chen, N., Deng, X., Sun, X.: On Complexity of Single-Minded Auction. Journal of Computer and System Sciences\u00a069(4), 675\u2013687 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR6","unstructured":"Conen, W., Sandholm, T.: Coherent Pricing of Efficient Allocations in Combinatorial Economies. In: AAAI 2002, Workshop on Game Theoretic and Decision Theoretic Agents, GTDT (2002)"},{"volume-title":"Combinatorial Auctions","year":"2005","key":"15_CR7","unstructured":"Cramton, P., Shoham, Y., Steinberg, R. (eds.): Combinatorial Auctions. MIT Press, Cambridge (2005)"},{"key":"#cr-split#-15_CR8.1","doi-asserted-by":"crossref","unstructured":"Deng, X., Papadimitriou, C.H., Safra, S.: On the Complexity of Equilibria. In: STOC 2002, pp. 67???71 (2002);","DOI":"10.1145\/509907.509920"},{"key":"#cr-split#-15_CR8.2","doi-asserted-by":"crossref","unstructured":"Full version appeared in Journal of Computer and System Sciences 67(2), 311???324 (2003)","DOI":"10.1016\/S0022-0000(03)00011-4"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Devanur, N., Papadimitriou, C.H., Saberi, A., Vazirani, V.V.: Market Equilibrium via a Primal-Dual-Type Algorithm. In: FOCS 2002, pp. 389\u2013395 (2002)","DOI":"10.1109\/SFCS.2002.1181963"},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1137\/0215009","volume":"15","author":"Z. Galil","year":"1986","unstructured":"Galil, Z., Micali, S., Gabow, H.: An O(EV logV) Algorithm for Finding a Maximal Weighted Matching in General Graphs. SIAM Journal on Computing\u00a015, 120\u2013130 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR11","volume-title":"Computers and Intractability: a Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N. Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees. Algorithmica\u00a018, 3\u201320 (1997)","journal-title":"Algorithmica"},{"key":"15_CR13","unstructured":"Goldberg, A.V., Hartline, J.D.: Collusion-Resistant Mechanisms for Single-Parameter Agents. In: SODA 2005, pp. 620\u2013629 (2005)"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1006\/jeth.1999.2531","volume":"87","author":"F. Gul","year":"1999","unstructured":"Gul, F., Stacchetti, E.: Walrasian Equilibrium with Gross Substitutes. Journal of Economic Theory\u00a087, 95\u2013124 (1999)","journal-title":"Journal of Economic Theory"},{"key":"15_CR15","unstructured":"Guruswami, V., Hartline, J.D., Karlin, A.R., Kempe, D., Kenyon, C., McSherry, F.: On Profit-Maximizing Envy-Free Pricing. In: SODA 2005, pp. 1164\u20131173 (2005)"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Hochbaum, D.S. (ed.): Approximation Algorithms for NP-Hard Problems. PWS Publishing Company (1997)","DOI":"10.1145\/261342.571216"},{"key":"15_CR17","unstructured":"Huang, S.L., Li, M.: Approximation of Walrasian Equilibrium in Single-Minded Auctions (submitted)"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Jain, K.: A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities. In: FOCS 2004, pp. 286\u2013294 (2004)","DOI":"10.1109\/FOCS.2004.6"},{"key":"15_CR19","doi-asserted-by":"publisher","first-page":"1483","DOI":"10.2307\/1913392","volume":"50","author":"A.S. Kelso","year":"1982","unstructured":"Kelso, A.S., Crawford, V.P.: Job Matching, Coalition Formation, and Gross Substitutes. Econometrica\u00a050, 1483\u20131504 (1982)","journal-title":"Econometrica"},{"key":"#cr-split#-15_CR20.1","doi-asserted-by":"crossref","unstructured":"Lehmann, D., O???Callaghan, L.I., Shoham, Y.: Truth Revelation in Approximately Efficient Combinatorial Auctions. In: ACM Conference on E-Commerce 1999, pp. 96???102 (1999);","DOI":"10.1145\/336992.337016"},{"key":"#cr-split#-15_CR20.2","doi-asserted-by":"crossref","unstructured":"Full version appeared in JACM 49(5), 577-602 (2002)","DOI":"10.1145\/585265.585266"},{"issue":"3","key":"15_CR21","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1086\/261158","volume":"91","author":"H.B. Leonard","year":"1983","unstructured":"Leonard, H.B.: Elicitation of Honest Preferences for the Assignment of Individual to Positions. Journal of Political Economy\u00a091(3), 461\u2013479 (1983)","journal-title":"Journal of Political Economy"},{"key":"15_CR22","volume-title":"Microeconomic Theory","author":"A. Mas-Collel","year":"1995","unstructured":"Mas-Collel, A., Whinston, W., Green, J.: Microeconomic Theory. Oxford University Press, Oxford (1995)"},{"key":"15_CR23","unstructured":"Mu\u2019alem, A., Nisan, N.: Truthful Approximation Mechanisms for Restricted Combinatorial Auctions. In: AAAI 2002, pp. 379\u2013384 (2002)"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Roughgarden, T.: Computing Equilibria in Multi-Player Games. In: SODA 2005, pp. 82\u201391 (2005)","DOI":"10.1145\/1060590.1060598"},{"key":"15_CR25","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discrete Math\u00a055, 221\u2013231 (1985)","journal-title":"Discrete Math"},{"issue":"3","key":"15_CR26","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1287\/ijoc.15.3.284.16077","volume":"15","author":"S. Vries de","year":"2003","unstructured":"de Vries, S., Vohra, R.: Combinatorial Auctions: A Survey. INFORMS Journal on Computing\u00a015(3), 284\u2013309 (2003)","journal-title":"INFORMS Journal on Computing"},{"key":"#cr-split#-15_CR27.1","unstructured":"Walras, L.: Elements d???economie politique pure; ou, Theorie de la richesse sociale (Elements of Pure Economics, or the Theory of Social Wealth), Lausanne, Paris (1874);"},{"key":"#cr-split#-15_CR27.2","unstructured":"Translated by William Jaff??, Irwin (1954)"}],"container-title":["Lecture Notes in Computer Science","Internet and Network Economics"],"original-title":[],"link":[{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/11600930_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:01:08Z","timestamp":1619506868000},"score":1,"resource":{"primary":{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/link.springer.com\/10.1007\/11600930_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540309000","9783540322931"],"references-count":30,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1007\/11600930_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}