{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T02:27:27Z","timestamp":1676946447513},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,10,13]],"date-time":"2007-10-13T00:00:00Z","timestamp":1192233600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,9]]},"DOI":"10.1007\/s00453-007-9103-9","type":"journal-article","created":{"date-parts":[[2007,10,12]],"date-time":"2007-10-12T19:09:41Z","timestamp":1192216181000},"page":"44-64","source":"Crossref","is-referenced-by-count":2,"title":["Walrasian Equilibrium: Hardness, Approximations and Tractable Instances"],"prefix":"10.1007","volume":"52","author":[{"given":"Ning","family":"Chen","sequence":"first","affiliation":[]},{"given":"Atri","family":"Rudra","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,13]]},"reference":[{"key":"9103_CR1","doi-asserted-by":"crossref","unstructured":"Archer, A., Tardos, E.: Truthful mechanisms for one-parameter agents. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 482\u2013491, 2001","DOI":"10.1109\/SFCS.2001.959924"},{"key":"9103_CR2","unstructured":"Archer, A., Papadimitriou, C.H., Talwar, K., Tardos, E.: An approximate truthful mechanism for combinatorial auctions with single parameter agents. In: Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 205\u2013214, 2003"},{"key":"9103_CR3","doi-asserted-by":"crossref","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 22, 265\u2013290 (1954)","journal-title":"Econometrica"},{"key":"9103_CR4","doi-asserted-by":"crossref","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. J. Econ. Theory 74, 385\u2013413 (1997)","journal-title":"J. Econ. Theory"},{"key":"9103_CR5","unstructured":"Chen, X., Deng, X.: 3-NASH is PPAD-complete. ECCC Technical Report No. TR05-134"},{"key":"9103_CR6","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: Settling the complexity of 2-player Nash-equilibrium. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp.\u00a0261\u2013272, 2006","DOI":"10.1109\/FOCS.2006.69"},{"issue":"4","key":"9103_CR7","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 69(4), 675\u2013687 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"9103_CR8","unstructured":"Conen, W., Sandholm, T.: Coherent pricing of efficient allocations in combinatorial economies. In: National Conference on Artificial Intelligence (AAAI), Workshop on Game Theoretic and Decision Theoretic Agents (GTDT), 2002"},{"key":"9103_CR9","volume-title":"Combinatorial Auctions","year":"2005","unstructured":"Cramton, P., Shoham, Y., Steinberg, R. (eds.): Combinatorial Auctions. MIT Press, Cambridge (2005)"},{"key":"9103_CR10","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Three-player games are hard. ECCC Technical Report No. TR05-139"},{"key":"9103_CR11","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. In: Proceedings of the Symposium on the Theory of Computation (STOC), pp. 71\u201378, 2006","DOI":"10.1145\/1132516.1132527"},{"key":"9103_CR12","unstructured":"Deng, X., Papadimitriou, C.H., Safra, S.: On the complexity of equilibria. In: Proceedings of the Symposium on the Theory of Computing (STOC), pp. 67\u201371, 2002. Full version appeared in J. Comput. Syst. Sci. 67(2), 311\u2013324 (2003)"},{"key":"9103_CR13","unstructured":"Devanur, N., Papadimitriou, C.H., Saberi, A., Vazirani, V.V.: Market equilibrium via a primal-dual-type algorithm. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 389\u2013395, 2002"},{"key":"9103_CR14","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1137\/0215009","volume":"15","author":"Z. Galil","year":"1986","unstructured":"Galil, Z., Micali, S., Gabow, H.: An O(EVlog\u2009V) algorithm for finding a maximal weighted matching in general graphs. SIAM J. Comput. 15, 120\u2013130 (1986)","journal-title":"SIAM J. Comput."},{"key":"9103_CR15","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":"9103_CR16","doi-asserted-by":"crossref","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 18, 3\u201320 (1997)","journal-title":"Algorithmica"},{"key":"9103_CR17","unstructured":"Goldberg, A.V., Hartline, J.D.: Collusion-resistant mechanisms for single-parameter agents. In: Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 620\u2013629, 2005"},{"key":"9103_CR18","doi-asserted-by":"crossref","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. J. Econ. Theory 87, 95\u2013124 (1999)","journal-title":"J. Econ. Theory"},{"key":"9103_CR19","unstructured":"Guruswami, V., Hartline, J.D., Karlin, A.R., Kempe, D., Kenyon, C., McSherry, F.: On profit-maximizing envy-free pricing. In: Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 1164\u20131173, 2005"},{"key":"9103_CR20","volume-title":"Approximation Algorithms for NP-Hard Problems","year":"1997","unstructured":"Hochbaum, D.S. (eds.): Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston (1997)"},{"issue":"1\u20133","key":"9103_CR21","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1016\/j.tcs.2005.03.008","volume":"337","author":"S.L. Huang","year":"2005","unstructured":"Huang, S.L., Li, M., Zhang, B.: Approximation of Walrasian equilibrium in single-minded auctions. Theor. Comput. Sci. 337(1\u20133), 390\u2013398 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9103_CR22","doi-asserted-by":"crossref","unstructured":"Jain, K.: A polynomial time algorithm for computing the Arrow-Debreu market equilibrium for linear utilities. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 286\u2013294, 2004","DOI":"10.1109\/FOCS.2004.6"},{"key":"9103_CR23","doi-asserted-by":"crossref","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 50, 1483\u20131504 (1982)","journal-title":"Econometrica"},{"key":"9103_CR24","doi-asserted-by":"crossref","unstructured":"Lehmann, D., O\u2019Callaghan, L.I., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. In: ACM Conference on E-Commerce, pp. 96\u2013102, 1999. Full version appeared in JACM 49(5), 577\u2013602 (2002)","DOI":"10.1145\/585265.585266"},{"issue":"3","key":"9103_CR25","doi-asserted-by":"crossref","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. J. Political Econ. 91(3), 461\u2013479 (1983)","journal-title":"J. Political Econ."},{"key":"9103_CR26","volume-title":"Microeconomic Theory","author":"A. Mas-Collel","year":"1995","unstructured":"Mas-Collel, A., Whinston, W., Green, J.: Microeconomic Theory. Oxford University Press, London (1995)"},{"key":"9103_CR27","unstructured":"Mu\u2019alem, A., Nisan, N.: Truthful approximation mechanisms for restricted combinatorial auctions. In: Proceedings of the National Conference on Artificial Intelligence (AAAI), pp. 379\u2013384, 2002"},{"key":"9103_CR28","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: Computing correlated equilibria in multi-player games. In: Proceedings of the Symposium on the Theory of Computing (STOC), pp. 49\u201356, 2005","DOI":"10.1145\/1060590.1060598"},{"key":"9103_CR29","unstructured":"Papadimitriou, C.H., Roughgarden, T.: Computing equilibria in multi-player games. In: Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 82\u201391, 2005"},{"key":"9103_CR30","doi-asserted-by":"crossref","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. 55, 221\u2013231 (1985)","journal-title":"Discrete Math."},{"issue":"3","key":"9103_CR31","doi-asserted-by":"crossref","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 J. Comput. 15(3), 284\u2013309 (2003)","journal-title":"INFORMS J. Comput."},{"key":"9103_CR32","unstructured":"Walras, L.: Elements d\u2019economie politique pure; ou, theorie de la richesse sociale (Elements of Pure Economics, or the Theory of Social Wealth), Lausanne, Paris, 1874. Translated by William Jaff\u00e9, Irwin, 1954"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9103-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9103-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9103-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:00Z","timestamp":1559137500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9103-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,13]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["9103"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9103-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,13]]}}}