{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:02:51Z","timestamp":1750309371466,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:00:00Z","timestamp":1725580800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["431465007"],"award-info":[{"award-number":["431465007"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Deutsche Forschungsgemeinschaft under Germany\u2019s Excellence Strategy\u2014The Berlin Mathematics Research Center MATH+","award":["390685689"],"award-info":[{"award-number":["390685689"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>\n            In the impartial selection problem, a subset of agents up to a fixed size\n            <jats:italic>k<\/jats:italic>\n            among a group of\n            <jats:italic>n<\/jats:italic>\n            is to be chosen based on votes cast by the agents themselves. A selection mechanism is\n            <jats:italic>impartial<\/jats:italic>\n            if no agent can influence its own chance of being selected by changing its vote. It is\n            <jats:italic>\u03b1-optimal<\/jats:italic>\n            if, for every instance, the ratio between the votes received by the selected subset is at least a fraction of \u03b1 of the votes received by the subset of size\n            <jats:italic>k<\/jats:italic>\n            with the highest number of votes. We study deterministic impartial mechanisms in a more general setting with arbitrarily weighted votes and provide the first approximation guarantee, roughly 1\/\u2308 2\n            <jats:italic>n\/k<\/jats:italic>\n            \u2309. When the number of agents to select is large enough compared to the total number of agents, this yields an improvement on the previously best-known approximation ratio of 1\/\n            <jats:italic>k<\/jats:italic>\n            for the unweighted setting. We further show that our mechanism can be adapted to the impartial assignment problem, in which multiple sets of up to\n            <jats:italic>k<\/jats:italic>\n            agents are to be selected, with a loss in the approximation ratio of 1\/2.\n          <\/jats:p>","DOI":"10.1145\/3677177","type":"journal-article","created":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T12:15:07Z","timestamp":1722860107000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic Impartial Selection with Weights"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4389-1398","authenticated-orcid":false,"given":"Javier","family":"Cembrano","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8018-3289","authenticated-orcid":false,"given":"Svenja M.","family":"Griesbach","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0190-2693","authenticated-orcid":false,"given":"Maximilian J.","family":"Stahlberg","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany and Technische Universit\u00e4t Hamburg, Hamburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,9,6]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2000378.2000390"},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","unstructured":"Haris Aziz Omer Lev Nicholas Mattei Jeffrey S. Rosenschein and Toby Walsh. 2019. Strategyproof peer selection using randomization partitioning and apportionment. Artif. Intell. 275 (2019) 295\u2013309.","DOI":"10.1016\/j.artint.2019.06.004"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399456"},{"key":"e_1_3_3_5_2","doi-asserted-by":"crossref","unstructured":"Antje Bjelde Felix Fischer and Max Klimm. 2017. Impartial selection and the power of up to two choices. ACM Trans. Econ. Comput. 5 4 (2017) 1\u201320.","DOI":"10.1145\/3107922"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13129-0_10"},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","unstructured":"Ioannis Caragiannis George Christodoulou and Nicos Protopapas. 2022. Impartial selection with additive approximation guarantees. Theor. Comput. Syst. 66 (2022) 721\u2013742.","DOI":"10.1007\/s00224-022-10081-0"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3543507.3583553"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538294"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22832-2_11"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3580507.3597693"},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","unstructured":"Geoffroy De Clippel Herve Moulin and Nicolaus Tideman. 2008. Impartial division of a dollar. J. Econ. Theor. 139 1 (2008) 176\u2013191.","DOI":"10.1016\/j.jet.2007.06.005"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1609\/hcomp.v10i1.21987"},{"key":"e_1_3_3_14_2","doi-asserted-by":"crossref","unstructured":"Paul H. Edelman and Attila Por. 2021. A new axiomatic approach to the impartial nomination problem. Games Econ. Behav. 130 (2021) 443\u2013451.","DOI":"10.1016\/j.geb.2021.08.014"},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","unstructured":"Felix Fischer and Max Klimm. 2015. Optimal impartial selection. SIAM J. Comput. 44 5 (2015) 1263\u20131285.","DOI":"10.1137\/140995775"},{"key":"e_1_3_3_16_2","doi-asserted-by":"crossref","unstructured":"Ron Holzman and Herv\u00e9 Moulin. 2013. Impartial nominations for a prize. Econometrica 81 1 (2013) 173\u2013196.","DOI":"10.3982\/ECTA10523"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11467"},{"key":"e_1_3_3_18_2","unstructured":"D. K\u0151nig. 1916. Gr\u00e1fok \u00e9s alkalmaz\u00e1suk a determin\u00e1nsok Z\u0306s a halmazok elm\u00e9let\u00e9re (\u201cGraphs and their applications to the theory of determinants and sets\u201d). Matematikai \u00e9s Term\u00e9szettudom\u00e1nyi \u00c9rtes\u00edt\u0151 34 (1916) 104\u2013119."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/2832249.2832330"},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","unstructured":"Omer Lev Nicholas Mattei Paolo Turrini and Stanislav Zhydkov. 2023. PeerNomination: A novel peer selection algorithm to handle strategic and noisy assessments. Artif. Intell. 316 (2023) 103843.","DOI":"10.1016\/j.artint.2022.103843"},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","unstructured":"Andrew Mackenzie. 2020. An axiomatic analysis of the papal conclave. Econ. Theor. 69 (2020) 713\u2013743.","DOI":"10.1007\/s00199-019-01180-0"},{"key":"e_1_3_3_22_2","first-page":"393","volume-title":"Proceedings of the 29th International Conference on International Joint Conferences on Artificial Intelligence","author":"Mattei Nicholas","year":"2021","unstructured":"Nicholas Mattei, Paolo Turrini, and Stanislav Zhydkov. 2021. PeerNomination: Relaxing exactness for increased accuracy in peer selection. In Proceedings of the 29th International Conference on International Joint Conferences on Artificial Intelligence. 393\u2013399."},{"key":"e_1_3_3_23_2","volume-title":"Simple Allocation with Correlated Types","author":"Niemeyer Axel","year":"2022","unstructured":"Axel Niemeyer and Justus Preusser. 2022. Simple Allocation with Correlated Types. Technical Report. Working Paper. University of Bonn."},{"key":"e_1_3_3_24_2","unstructured":"Matthew Olckers and Toby Walsh. 2022. Manipulation and peer mechanisms: A survey. arXiv preprint arXiv: 2210.01984 (2022)."},{"key":"e_1_3_3_25_2","doi-asserted-by":"crossref","unstructured":"Shohei Tamura and Shinji Ohseto. 2014. Impartial nomination correspondences. Soc. Choice Welf. 43 1 (2014) 47\u201354.","DOI":"10.1007\/s00355-013-0772-9"},{"key":"e_1_3_3_26_2","unstructured":"V. G. Vizing. 1964. Ob otsenke khromaticheskogo klassa p-grafa (\u201cOn an estimate of the chromatic class of a p-graph\u201d). Diskretnyy Analiz 3 (1964) 25\u201330."},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/3367032.3367120"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-85947-3_6"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2023\/327"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677177","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3677177","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:06:17Z","timestamp":1750291577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677177"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,6]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3677177"],"URL":"https:\/\/doi.org\/10.1145\/3677177","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2024,9,6]]},"assertion":[{"value":"2023-12-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-26","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}