A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation

被引：46
作者：
Aziz, Haris [1 ,2 ]
Moulin, Herve [3 ,4 ]
Sandomirskiy, Fedor [4 ,5 ]
机构：
[1] UNSW Sydney, Sydney, NSW, Australia
[2] Data61 CSIRO, Sydney, NSW, Australia
[3] Univ Glasgow, Glasgow, Lanark, Scotland
[4] Higher Sch Econ, St Petersburg, Russia
[5] Technion, Haifa, Israel
来源：
OPERATIONS RESEARCH LETTERS | 2020年 / 48卷 / 05期
基金：
俄罗斯基础研究基金会; 欧洲研究理事会;
关键词：
Fair division; Pareto optimality; Proportionality;
D O I：
10.1016/j.orl.2020.07.005
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We consider fair allocation of indivisible items under additive utilities. We show that there exists a strongly polynomial-time algorithm that always computes an allocation satisfying Pareto optimality and proportionality up to one item even if the utilities are mixed and the agents have asymmetric weights. The result does not hold if either of Pareto optimality or PROP1 is replaced with slightly stronger concepts. (C) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页码：573 / 578
页数：6
相关论文
共 15 条
[1]  
[Anonymous], 2017, CORR
[2]  
Aziz H., 2019, P 28 INT JOINT C ART
[3]  
Aziz H., 2019, P 28 INT JOINT C ART
[4]  
Aziz H., 2019, CoRR
[5]   Efficient reallocation under additive and responsive preferences [J].
Aziz, Hans ;
Biro, Peter ;
Lang, Jerome ;
Lesca, Julien ;
Monnot, Jerome .
THEORETICAL COMPUTER SCIENCE, 2019, 790 :1-15
[6]  
Barman S, 2019, AAAI CONF ARTIF INTE, P1748
[7]  
Branzei S., 2019, CORR
[8]   The Unreasonable Fairness of Maximum Nash Welfare [J].
Caragiannis, Ioannis ;
Kurokawa, David ;
Moulin, Herve ;
Procaccia, Ariel D. ;
Shah, Nisarg ;
Wang, Junxing .
EC'16: PROCEEDINGS OF THE 2016 ACM CONFERENCE ON ECONOMICS AND COMPUTATION, 2016, :305-322
[9]   Fair Public Decision Making [J].
Conitzer, Vincent ;
Freeman, Rupert ;
Shah, Nisarg .
EC'17: PROCEEDINGS OF THE 2017 ACM CONFERENCE ON ECONOMICS AND COMPUTATION, 2017, :629-646
[10]  
de Keijzer B., 2009, P 1 ADT C
12