{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T04:25:31Z","timestamp":1775276731299,"version":"3.50.1"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030859466","type":"print"},{"value":"9783030859473","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-85947-3_23","type":"book-chapter","created":{"date-parts":[[2021,9,14]],"date-time":"2021-09-14T00:45:22Z","timestamp":1631580322000},"page":"345-359","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Computing Fair and Efficient Allocations with Few Utility Values"],"prefix":"10.1007","author":[{"given":"Jugal","family":"Garg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aniket","family":"Murhekar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,9,14]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Hollender, A., Voudouris, A.A.: Maximum Nash welfare and other stories about EFX. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI), pp. 24\u201330 (2020)","DOI":"10.24963\/ijcai.2020\/4"},{"key":"23_CR2","unstructured":"Aziz, H.: The Hylland-Zeckhauser rule under bi-valued utilities. CoRR abs\/2006.15747 (2020)"},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.05.011","volume":"790","author":"H Aziz","year":"2019","unstructured":"Aziz, H., Bir\u00f3, P., Lang, J., Lesca, J., Monnot, J.: Efficient reallocation under additive and responsive preferences. Theor. Comput. Sci. 790, 1\u201315 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Barman, S., Krishnamurthy, S.: On the proximity of markets with integral equilibria. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pp. 1748\u20131755 (2019)","DOI":"10.1609\/aaai.v33i01.33011748"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Barman, S., Krishnamurthy, S.K., Vaish, R.: Finding fair and efficient allocations. In: Proceedings of the 19th ACM Conference on Economics and Computation (EC), pp. 557\u2013574 (2018)","DOI":"10.1145\/3219166.3219176"},{"key":"23_CR6","unstructured":"Barman, S., Krishnamurthy, S.K., Vaish, R.: Greedy algorithms for maximizing Nash social welfare. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp. 7\u201313 (2018)"},{"key":"23_CR7","unstructured":"Berman, P., Karpinski, M., Scott, A.: Approximation hardness of short symmetric instances of MAX-3SAT. Electronic Colloquium on Computational Complexity (ECCC) (Jan 2003)"},{"key":"23_CR8","unstructured":"Bliem, B., Bredereck, R., Niedermeier, R.: Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), pp. 102\u2013108 (2016)"},{"issue":"1","key":"23_CR9","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1111\/j.1468-0262.2004.00483.x","volume":"72","author":"A Bogomolnaia","year":"2004","unstructured":"Bogomolnaia, A., Moulin, H.: Random matching under dichotomous preferences. Econometrica 72(1), 257\u2013279 (2004)","journal-title":"Econometrica"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"Brams, S., Taylor, A.: Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, Cambridge (1996)","DOI":"10.1017\/CBO9780511598975"},{"issue":"6","key":"23_CR11","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1086\/664613","volume":"119","author":"E Budish","year":"2011","unstructured":"Budish, E.: The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Polit. Econ. 119(6), 1061\u20131103 (2011)","journal-title":"J. Polit. Econ."},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A.D., Shah, N., Wang, J.: The unreasonable fairness of maximum Nash welfare. In: Proceedings of the 17th ACM Conference on Economics and Computation (EC), pp. 305\u2013322 (2016)","DOI":"10.1145\/2940716.2940726"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Khanna, S., Li, S.: On (1, e)-restricted assignment makespan minimization. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1087\u20131101 (2015)","DOI":"10.1137\/1.9781611973730.73"},{"key":"23_CR14","unstructured":"Chaudhury, B.R., Cheung, Y.K., Garg, J., Garg, N., Hoefer, M., Mehlhorn, K.: On fair division for indivisible items. In: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 1\u201317 (2018)"},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"Chaudhury, B.R., Garg, J., Mehlhorn, K.: EFX exists for three agents. In: Proceedings of the 21st ACM Conference on Economics and Computation (EC), pp. 1\u201319 (2020)","DOI":"10.1145\/3391403.3399511"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Chaudhury, B.R., Garg, J., Mehlhorn, K., Mehta, R., Misra, P.: Improving EFX guarantees through rainbow cycle number. CoRR abs\/2103.01628 (2021). To appear in ACM EC 2021","DOI":"10.1145\/3465456.3467605"},{"key":"23_CR17","doi-asserted-by":"crossref","unstructured":"Cole, R., Gkatzelis, V.: Approximating the Nash social welfare with indivisible items. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC), pp. 371\u2013380 (2015)","DOI":"10.1145\/2746539.2746589"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"Darmann, A., Schauer, J.: Maximizing Nash product social welfare in allocating indivisible goods. SSRN Electron. J. 247(2), 548\u2013559 (2014)","DOI":"10.1016\/j.ejor.2015.05.071"},{"issue":"1","key":"23_CR19","first-page":"45","volume":"7","author":"D Foley","year":"1967","unstructured":"Foley, D.: Resource allocation and the public sector. Yale Econ. Essays 7(1), 45\u201398 (1967)","journal-title":"Yale Econ. Essays"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Freeman, R., Sikdar, S., Vaish, R., Xia, L.: Equitable allocations of indivisible goods. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp. 280\u2013286 (2019)","DOI":"10.24963\/ijcai.2019\/40"},{"key":"23_CR21","unstructured":"Garg, J., Hoefer, M., Mehlhorn, K.: Satiation in Fisher markets and approximation of Nash social welfare. CoRR abs\/1707.04428 (2017)"},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"Garg, J., Hoefer, M., Mehlhorn, K.: Approximating the Nash social welfare with budget-additive valuations. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2326\u20132340 (2018)","DOI":"10.1137\/1.9781611975031.150"},{"key":"23_CR23","doi-asserted-by":"crossref","unstructured":"Garg, J., Murhekar, A.: On fair and efficient allocations of indivisible goods. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (2021)","DOI":"10.1609\/aaai.v35i6.16703"},{"key":"23_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-02927-1_1","volume-title":"Automata, Languages and Programming","author":"K Mehlhorn","year":"2009","unstructured":"Mehlhorn, K.: Assigning papers to referees. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 1\u20132. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02927-1_1"},{"key":"23_CR25","unstructured":"Golovin, D.: Max-min fair allocation of indivisible goods. Technical report, CMU-CS-05-144 (2005)"},{"key":"23_CR26","unstructured":"Gourv\u00e8s, L., Monnot, J., Tlilane, L.: Near fairness in matroids. In: Proceedings of the 21st European Conference on Artificial Intelligence (ECAI), pp. 393\u2013398 (2014)"},{"key":"23_CR27","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-04428-1_9","volume-title":"Algorithmic Decision Theory","author":"B de Keijzer","year":"2009","unstructured":"de Keijzer, B., Bouveret, S., Klos, T., Zhang, Y.: On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. In: Rossi, F., Tsoukias, A. (eds.) ADT 2009. LNCS (LNAI), vol. 5783, pp. 98\u2013110. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04428-1_9"},{"key":"23_CR28","doi-asserted-by":"crossref","unstructured":"Lee, E.: APX-hardness of maximizing Nash social welfare with indivisible items. Inf. Process. Lett. 122, 17\u201320 (07 2015)","DOI":"10.1016\/j.ipl.2017.01.012"},{"key":"23_CR29","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mossel, E., Saberi, A.: On approximately fair allocations of indivisible goods. In: Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pp. 125\u2013131 (2004)","DOI":"10.1145\/988772.988792"},{"key":"23_CR30","unstructured":"Mas-Colell, A., et al.: Microeconomic Theory. Oxford University Press, Oxford (1995)"},{"key":"23_CR31","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1613\/jair.1.11618","volume":"68","author":"P McGlaughlin","year":"2020","unstructured":"McGlaughlin, P., Garg, J.: Improving Nash social welfare approximations. J. Artif. Intell. Res. 68, 225\u2013245 (2020)","journal-title":"J. Artif. Intell. Res."},{"key":"23_CR32","doi-asserted-by":"crossref","unstructured":"Moulin, H.: Fair Division and Collective Welfare. MIT Press, Cambridge (2004)","DOI":"10.7551\/mitpress\/2954.001.0001"},{"key":"23_CR33","doi-asserted-by":"crossref","unstructured":"Murhekar, A., Garg, J.: On fair and efficient allocations of indivisible goods. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 6, pp. 5595\u20135602 (2021)","DOI":"10.1609\/aaai.v35i6.16703"},{"key":"23_CR34","doi-asserted-by":"crossref","unstructured":"Plaut, B., Roughgarden, T.: Almost envy-freeness with general valuations. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2584\u20132603 (2018)","DOI":"10.1137\/1.9781611975031.165"},{"issue":"4","key":"23_CR35","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1145\/3382131","volume":"63","author":"AD Procaccia","year":"2020","unstructured":"Procaccia, A.D.: Technical perspective: an answer to fair division\u2019s most enigmatic question. Commun. ACM 63(4), 118 (2020)","journal-title":"Commun. ACM"},{"issue":"1","key":"23_CR36","doi-asserted-by":"publisher","first-page":"315","DOI":"10.2307\/1907319","volume":"17","author":"H Steinhaus","year":"1949","unstructured":"Steinhaus, H.: Sur la division pragmatique. Econometrica 17(1), 315\u2013319 (1949)","journal-title":"Econometrica"},{"issue":"1","key":"23_CR37","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0022-0531(74)90075-1","volume":"9","author":"HR Varian","year":"1974","unstructured":"Varian, H.R.: Equity, envy, and efficiency. J. Econ. Theory 9(1), 63\u201391 (1974)","journal-title":"J. Econ. Theory"},{"key":"23_CR38","unstructured":"Vazirani, V.V., Yannakakis, M.: Computational complexity of the Hylland-Zeckhauser scheme for one-sided matching markets. In: Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS) (2021)"},{"issue":"4","key":"23_CR39","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0167-6377(96)00055-7","volume":"20","author":"GJ Woeginger","year":"1997","unstructured":"Woeginger, G.J.: A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett. 20(4), 149\u2013154 (1997)","journal-title":"Oper. Res. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-85947-3_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T03:38:35Z","timestamp":1673235515000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-85947-3_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030859466","9783030859473"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-85947-3_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"14 September 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAGT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmic Game Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Aarhus","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Denmark","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 September 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sagt2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"73","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"36% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7.5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4 abstracts of presented papers are also included.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}