{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:10:34Z","timestamp":1778497834051,"version":"3.51.4"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,4,18]],"date-time":"2013-04-18T00:00:00Z","timestamp":1366243200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2014,3]]},"DOI":"10.1007\/s10458-013-9224-2","type":"journal-article","created":{"date-parts":[[2013,4,17]],"date-time":"2013-04-17T06:54:09Z","timestamp":1366181649000},"page":"256-289","source":"Crossref","is-referenced-by-count":44,"title":["Computational complexity and approximability of social welfare optimization in multiagent resource allocation"],"prefix":"10.1007","volume":"28","author":[{"given":"Nhan-Tam","family":"Nguyen","sequence":"first","affiliation":[]},{"given":"Trung Thanh","family":"Nguyen","sequence":"additional","affiliation":[]},{"given":"Magnus","family":"Roos","sequence":"additional","affiliation":[]},{"given":"J\u00f6rg","family":"Rothe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,4,18]]},"reference":[{"key":"9224_CR1","first-page":"399","volume-title":"Approximation algorithms for NP-hard problems, Chap. 10","author":"S Arora","year":"1996","unstructured":"Arora, S., & Lund, C. (1996). Hardness of approximations. In D. Hochbaum (Ed.), Approximation algorithms for NP-hard problems, Chap. 10 (pp. 399\u2013446). Boston: PWS Publishing Company."},{"issue":"7","key":"9224_CR2","doi-asserted-by":"crossref","first-page":"2970","DOI":"10.1137\/080723491","volume":"39","author":"A Asadpour","year":"2010","unstructured":"Asadpour, A., & Saberi, A. (2010). An approximation algorithm for max-min fair allocation of indivisible goods. SIAM Journal on Computing, 39(7), 2970\u20132989.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"9224_CR3","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/1120680.1120683","volume":"5","author":"I Bez\u00e1kov\u00e1","year":"2005","unstructured":"Bez\u00e1kov\u00e1, I., & Dani, V. (2005). Allocating indivisible goods. SIGecom Exchanges, 5(3), 11\u201318.","journal-title":"SIGecom Exchanges"},{"key":"9224_CR4","unstructured":"Bouveret, S. (2007). Fair allocation of indivisible items: Modeling, computational complexity and algorithmics. Ph.D. thesis, Institut Sup\u00e9rieur de l\u2019A\u00e9ronautique et de l\u2019Espace, Toulouse."},{"key":"9224_CR5","unstructured":"Bouveret, S., Lema\u00eetre, M., Fargier, H., & Lang, J. (2005). Allocation of indivisible goods: A general model and some complexity results (extended abstract). In: Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems, (pp. 1309\u20131310). ACM Press."},{"key":"9224_CR6","doi-asserted-by":"crossref","unstructured":"Cai, J., Gunderman, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., et al. (1988). The boolean hierarchy I: Structural properties. SIAM Journal on Computing, 16(6), 1232\u20131252.","DOI":"10.1137\/0217078"},{"key":"9224_CR7","doi-asserted-by":"crossref","unstructured":"Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., et al. (1989). The boolean hierarchy II: Applications. SIAM Journal on Computing, 18(1), 95\u2013111.","DOI":"10.1137\/0218007"},{"key":"9224_CR8","doi-asserted-by":"crossref","unstructured":"Cai, J., & Meyer, G. (1987). Graph minimal uncolorability is $${\\rm D}^P$$ D P -complete. SIAM Journal on Computing, 16(2), 259\u2013277.","DOI":"10.1137\/0216022"},{"issue":"3","key":"9224_CR9","first-page":"173","volume":"28","author":"R Chang","year":"1995","unstructured":"Chang, R., & Kadin, J. (1995). On computing boolean connectives of characteristic functions. Theory of Computing Systems, 28(3), 173\u2013198.","journal-title":"Theory of Computing Systems"},{"key":"9224_CR10","first-page":"3","volume":"30","author":"Y Chevaleyre","year":"2006","unstructured":"Chevaleyre, Y., Dunne, P., Endriss, U., Lang, J., Lema\u00eetre, M., Maudet, N., et al. (2006). Issues in multiagent resource allocation. Informatica, 30, 3\u201331.","journal-title":"Informatica"},{"key":"9224_CR11","unstructured":"Chevaleyre, Y., Endriss, U., Estivie, S., & Maudet, N. (2004). Multiagent resource allocation with $$k$$ k -additive utility functions. In: Proceedings of the DIMACS-LAMSADE Workshop on Computer Science and Decision Theory, Annales du LAMSADE, vol. 3, ( pp. 83\u2013100)."},{"key":"9224_CR12","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s10479-008-0335-0","volume":"163","author":"Y Chevaleyre","year":"2008","unstructured":"Chevaleyre, Y., Endriss, U., Estivie, S., & Maudet, N. (2008). Multiagent resource allocation in $$k$$ k -additive domains: Preference representation and complexity. Annals of Operations Research, 163, 49\u201362.","journal-title":"Annals of Operations Research"},{"key":"9224_CR13","unstructured":"Conitzer, V., Sandholm, T., & Santi, P. (2005). Combinatorial auctions with $$k$$ k -wise dependent valuations. In: Proceedings of the 20th National Conference on Artificial Intelligence, (pp. 248\u2013254). AAAI Press."},{"issue":"1\u20132","key":"9224_CR14","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.artint.2005.01.006","volume":"164","author":"P Dunne","year":"2005","unstructured":"Dunne, P., Wooldridge, M., & Laurence, M. (2005). The complexity of contract negotiation. Artificial Intelligence, 164(1\u20132), 23\u201346.","journal-title":"Artificial Intelligence"},{"key":"9224_CR15","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., & Johnson, D. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York: W. H. Freeman and Company."},{"issue":"2","key":"9224_CR16","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0165-0114(97)00168-1","volume":"92","author":"M Grabisch","year":"1997","unstructured":"Grabisch, M. (1997). $$k$$ k -order additive discrete fuzzy measures and their representation. Fuzzy Sets and Systems, 92(2), 167\u2013189.","journal-title":"Fuzzy Sets and Systems"},{"issue":"4","key":"9224_CR17","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J. (2001). Some optimal inapproximability results. Journal of the ACM, 48(4), 798\u2013859.","journal-title":"Journal of the ACM"},{"issue":"2","key":"9224_CR18","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E Horowitz","year":"1976","unstructured":"Horowitz, E., & Sahni, S. (1976). Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM, 23(2), 317\u2013327.","journal-title":"Journal of the ACM"},{"key":"9224_CR19","unstructured":"Lehmann, D., O\u2019Callaghan, L., & Shoham, Y. (1999). Truth revelation in approximately efficient combinatorial auctions. In: Proceedings of the 1st ACM Conference on Electronic Commerce, (pp. 96\u2013102). ACM Press."},{"key":"9224_CR20","unstructured":"Lipton, R., Markakis, E., Mossel, E., & Saberi, A. (2004). On approximately fair allocations of indivisible goods. In: Proceedings of the 5th ACM Conference on Electronic Commerce, (pp. 125\u2013131). ACM Press."},{"key":"9224_CR21","volume-title":"Fair division and collective welfare","author":"H Moulin","year":"2004","unstructured":"Moulin, H. (2004). Fair division and collective welfare. Cambridge: MIT Press."},{"key":"9224_CR22","unstructured":"Nguyen, N., Nguyen, T., Roos, M., & Rothe, J. (2012). Complexity and approximability of egalitarian and Nash product social welfare optimization in multiagent resource allocation. In: Proceedings of the 6th European Starting AI Researcher Symposium, (pp. 204\u2013215). IOS Press."},{"key":"9224_CR23","first-page":"335","volume-title":"Proceedings of the 4th International Workshop on Computational Social Choice","author":"N Nguyen","year":"2012","unstructured":"Nguyen, N., Nguyen, T., Roos, M., & Rothe, J. (2012). Complexity and approximability of social welfare optimization in multiagent resource allocation. In F. Brandt & P. Faliszewski (Eds.), Proceedings of the 4th International Workshop on Computational Social Choice (pp. 335\u2013346). Krak\u00f3w, Poland: AGH University of Science and Technology."},{"key":"9224_CR24","unstructured":"Nguyen, N., Nguyen, T., Roos, M., & Rothe, J. (2012). Complexity and approximability of social welfare optimization in multiagent resource allocation (extended abstract). In: Proceedings of the 11th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 1287\u20131288. IFAAMAS."},{"key":"9224_CR25","unstructured":"Nguyen, N., Roos, M., & Rothe, J. (2012). Exact optimization of social welfare by the Nash product is DP-complete. In: Website Proceedings of the 12th International Symposium on Artificial Intelligence and Mathematics."},{"key":"9224_CR26","unstructured":"Nguyen, T., Roos, M., & Rothe, J. (2012). A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation. Annals of Mathematics and Artificial Intelligence. To appear. A preliminary version appeared in the Website Proceedings of the Special Session on Computational Social Choice at the 12th International Symposium on Artificial Intelligence and Mathematics."},{"key":"9224_CR27","unstructured":"Nguyen, T., & Rothe, J. (2013). Envy-ratio and average Nash social welfare optimization in multiagent resource allocation (extended abstract). In: Proceedings of the 12th International Joint Conference on Autonomous Agents and Multiagent Systems. IFAAMAS. To appear."},{"key":"9224_CR28","volume-title":"Computational complexity, second edn","author":"C Papadimitriou","year":"1995","unstructured":"Papadimitriou, C. (1995). Computational complexity, second edn. Boston: Addison-Wesley."},{"issue":"1","key":"9224_CR29","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0022-0000(88)90042-6","volume":"37","author":"C Papadimitriou","year":"1988","unstructured":"Papadimitriou, C., & Wolfe, D. (1988). The complexity of facets resolved. Journal of Computer and System Sciences, 37(1), 2\u201313.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"9224_CR30","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C Papadimitriou","year":"1984","unstructured":"Papadimitriou, C., & Yannakakis, M. (1984). The complexity of facets (and some facets of complexity). Journal of Computer and System Sciences, 28(2), 244\u2013259.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"9224_CR31","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/322123.322138","volume":"26","author":"N Pippenger","year":"1979","unstructured":"Pippenger, N., & Fischer, M. (1979). Relations among complexity measures. Journal of the ACM, 26(2), 361\u2013381.","journal-title":"Journal of the ACM"},{"key":"9224_CR32","unstructured":"Ramezani, S., & Endriss, U. (2010). Nash social welfare in multiagent resource allocation. In: Agent-mediated electronic commerce. Designing trading strategies and mechanisms for electronic markets, (pp.\u00a0117\u2013131). Springer, Lecture Notes in Business Information Processing No. 79."},{"issue":"5","key":"9224_CR33","first-page":"551","volume":"12","author":"T Riege","year":"2006","unstructured":"Riege, T., & Rothe, J. (2006). Completeness in the boolean hierarchy: Exact-four-colorability, minimal graph uncolorability, and exact domatic number problems\u2014a survey. Journal of Universal Computer Science, 12(5), 551\u2013578.","journal-title":"Journal of Universal Computer Science"},{"key":"9224_CR34","unstructured":"Roos, M., & Rothe, J. (2010). Complexity of social welfare optimization in multiagent resource allocation. In: Proceedings of the 9th International Joint Conference on Autonomous Agents and Multiagent Systems, (pp. 641\u2013648). IFAAMAS."},{"issue":"1","key":"9224_CR35","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/S0020-0190(03)00229-1","volume":"87","author":"J Rothe","year":"2003","unstructured":"Rothe, J. (2003). Exact complexity of exact-four-colorability. Information Processing Letters, 87(1), 7\u201312.","journal-title":"Information Processing Letters"},{"key":"9224_CR36","volume-title":"Complexity theory and cryptology. An introduction to cryptocomplexity. EATCS texts in theoretical computer science","author":"J Rothe","year":"2005","unstructured":"Rothe, J. (2005). Complexity theory and cryptology. An introduction to cryptocomplexity. EATCS texts in theoretical computer science. Berlin: Springer."},{"issue":"1","key":"9224_CR37","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni, S. (1976). Algorithms for scheduling independent tasks. Journal of the ACM, 23(1), 116\u2013127.","journal-title":"Journal of the ACM"},{"issue":"1","key":"9224_CR38","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF00265223","volume":"7","author":"C Schnorr","year":"1976","unstructured":"Schnorr, C. (1976). The network complexity and the Turing machine complexity of finite functions. Acta Informatica, 7(1), 95\u2013107.","journal-title":"Acta Informatica"},{"key":"9224_CR39","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation algorithms, second edn","author":"V Vazirani","year":"2003","unstructured":"Vazirani, V. (2003). Approximation algorithms, second edn. Berlin: Springer."},{"key":"9224_CR40","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"K Wagner","year":"1987","unstructured":"Wagner, K. (1987). More complicated questions about maxima and minima, and some closures of NP. Theoretical Computer Science, 51, 53\u201380.","journal-title":"Theoretical Computer Science"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-013-9224-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10458-013-9224-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-013-9224-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T17:28:29Z","timestamp":1559150909000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10458-013-9224-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,18]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["9224"],"URL":"https:\/\/doi.org\/10.1007\/s10458-013-9224-2","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,18]]}}}