{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T21:02:29Z","timestamp":1758402149551,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>\n            In this article, we are interested in general techniques for designing mechanisms that approximate the social welfare in the presence of selfish rational behavior. We demonstrate our results in the setting of Combinatorial Auctions (CA). Our first result is a general deterministic technique to decouple the algorithmic allocation problem from the strategic aspects, by a procedure that converts any\n            <jats:italic>algorithm<\/jats:italic>\n            to a dominant-strategy ascending\n            <jats:italic>mechanism<\/jats:italic>\n            . This technique works for any single value domain, in which each agent has the same value for each desired outcome, and this value is the only private information. In particular, for \u201csingle-value CAs\u201d, where each player desires any one of several different bundles but has the same value for each of them, our technique converts any approximation algorithm to a dominant strategy mechanism that almost preserves the original approximation ratio. Our second result provides the first computationally efficient deterministic mechanism for the case of single-value multi-minded bidders (with private value and private desired bundles). The mechanism achieves an approximation to the social welfare which is close to the best possible in polynomial time (unless P=NP). This mechanism is an\n            <jats:italic>algorithmic implementation in undominated strategies<\/jats:italic>\n            , a notion that we define and justify, and is of independent interest.\n          <\/jats:p>","DOI":"10.1145\/1462153.1462157","type":"journal-article","created":{"date-parts":[[2009,2,4]],"date-time":"2009-02-04T13:01:58Z","timestamp":1233752518000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["Single-value combinatorial auctions and algorithmic implementation in undominated strategies"],"prefix":"10.1145","volume":"56","author":[{"given":"Moshe","family":"Babaioff","sequence":"first","affiliation":[{"name":"Microsoft Research -- Silicon Valley, Mountain View, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ron","family":"Lavi","sequence":"additional","affiliation":[{"name":"The Technion -- Israel Institute of Technology, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elan","family":"Pavlov","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, Massachusetts"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,2,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Akcoglu K. Aspens J. DasGupta B. and Kao M. 2002. An opportunity-cost algorithm for combinatorial auctions. In Applied Optimization: Computational Methods in Decision-Making Economics and Finance E. J. Kontoghiorghes B. Rustem and S. Siokos Eds. Kluwer Academic.  Akcoglu K. Aspens J. DasGupta B. and Kao M. 2002. An opportunity-cost algorithm for combinatorial auctions. In Applied Optimization: Computational Methods in Decision-Making Economics and Finance E. J. Kontoghiorghes B. Rustem and S. Siokos Eds. Kluwer Academic.","DOI":"10.1007\/978-1-4757-3613-7_23"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875583"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780616"},{"volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI), 241--247","author":"Babaioff M.","key":"e_1_2_1_4_1","unstructured":"Babaioff , M. , Lavi , R. , and Pavlov , E . 2005. Mechanism design for single-value domains . In Proceedings of the National Conference on Artificial Intelligence (AAAI), 241--247 . Babaioff, M., Lavi, R., and Pavlov, E. 2005. Mechanism design for single-value domains. In Proceedings of the National Conference on Artificial Intelligence (AAAI), 241--247."},{"volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI).","author":"Babaioff M.","key":"e_1_2_1_5_1","unstructured":"Babaioff , M. , Lavi , R. , and Pavlov , E . 2006. Impersonation-based mechanisms . In Proceedings of the National Conference on Artificial Intelligence (AAAI). Babaioff, M., Lavi, R., and Pavlov, E. 2006. Impersonation-based mechanisms. In Proceedings of the National Conference on Artificial Intelligence (AAAI)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/846241.846250"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064013"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Blumrosen L. and Nisan N. 2007. Combinatorial auctions. In Algorithmic Game Theory N. Nisan T. Roughgarden E. Tardos and V. Vazirani Eds. Cambridge University press Cambridge UK.  Blumrosen L. and Nisan N. 2007. Combinatorial auctions. In Algorithmic Game Theory N. Nisan T. Roughgarden E. Tardos and V. Vazirani Eds. Cambridge University press Cambridge UK.","DOI":"10.1017\/CBO9780511800481.013"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060597"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Clarke E. H. 1971. Multipart pricing of public goods. Public Choice 17--33.  Clarke E. H. 1971. Multipart pricing of public goods. Public Choice 17--33.","DOI":"10.1007\/BF01726210"},{"key":"e_1_2_1_11_1","volume-title":"Eds","author":"Cramton P.","year":"2006","unstructured":"Cramton , P. , Shoham , Y. , and Steinberg , R. , Eds . 2006 . Combinatorial Auctions. MIT Press , Cambridge, MA. Cramton, P., Shoham, Y., and Steinberg, R., Eds. 2006. Combinatorial Auctions. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250842"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060681"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132607"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386798"},{"volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI'99)","author":"Fujishima Y.","key":"e_1_2_1_17_1","unstructured":"Fujishima , Y. , Leyton-Brown , K. , and Shoham , Y . 1999. Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches . In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI'99) . Morgan-Kaufmann, San Francisco, CA. Fujishima, Y., Leyton-Brown, K., and Shoham, Y. 1999. Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI'99). Morgan-Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/352871.352873"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Groves T. 1973. Incentives in teams. Econometrica 617--631.  Groves T. 1973. Incentives in teams. Econometrica 617--631.","DOI":"10.2307\/1914085"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0899-8256(03)00184-2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/2297996"},{"volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Lavi R.","key":"e_1_2_1_22_1","unstructured":"Lavi , R. , Mu'alem , A. , and Nisan , N . 2003. Towards a characterization of truthful combinatorial auctions . In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press , Los Alamitos, CA, 574--583. Lavi, R., Mu'alem, A., and Nisan, N. 2003. Towards a characterization of truthful combinatorial auctions. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 574--583."},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Lavi R.","key":"e_1_2_1_23_1","unstructured":"Lavi , R. , and Nisan , N . 2005. Online ascending auctions for gradually expiring items . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM , New York, 1146--1155. Lavi, R., and Nisan, N. 2005. Online ascending auctions for gradually expiring items. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 1146--1155."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.76"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250947"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585266"},{"volume-title":"Proceedings of the AAAI\/IAAI. 379--384","author":"Mu'alem A.","key":"e_1_2_1_27_1","unstructured":"Mu'alem , A. , and Nisan , N . 2002. Truthful approximation mechanisms for restricted combinatorial auctions . In Proceedings of the AAAI\/IAAI. 379--384 . Mu'alem, A., and Nisan, N. 2002. Truthful approximation mechanisms for restricted combinatorial auctions. In Proceedings of the AAAI\/IAAI. 379--384."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2004.10.007"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/501158.501172"},{"volume-title":"Iterative combinatorial auctions","author":"Parkes D.","key":"e_1_2_1_31_1","unstructured":"Parkes , D. 2005. Iterative combinatorial auctions . In Combinatorial Auctions, P. Cramton, Y. Shoham, and R. Steinberg, Eds. MIT press, Cambridge , MA. Parkes, D. 2005. Iterative combinatorial auctions. In Combinatorial Auctions, P. Cramton, Y. Shoham, and R. Steinberg, Eds. MIT press, Cambridge, MA."},{"key":"e_1_2_1_32_1","first-page":"374","article-title":"Cabob: A fast optimal algorithm for winner determination in combinatorial auctions. Manage","volume":"51","author":"Sandholm T.","year":"2005","unstructured":"Sandholm , T. , Suri , S. , Gilpin , A. , and Levine , D. 2005 . Cabob: A fast optimal algorithm for winner determination in combinatorial auctions. Manage . Sci. 51 , 3, 374 -- 390 . Sandholm, T., Suri, S., Gilpin, A., and Levine, D. 2005. Cabob: A fast optimal algorithm for winner determination in combinatorial auctions. Manage. Sci. 51, 3, 374--390.","journal-title":"Sci."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132612"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462153.1462157","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1462153.1462157","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:14Z","timestamp":1750253414000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462153.1462157"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1145\/1462153.1462157"],"URL":"https:\/\/doi.org\/10.1145\/1462153.1462157","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2009,1]]},"assertion":[{"value":"2006-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}