Proceedings of the ACM Web Conference 2022 · 2022 · 20 citations · 30 references
Social SciencesDecision SciencesEconomicsGame TheoryMicroeconomicsOptimizationAlgorithmic FairnessInformation AsymmetryResource AllocationUtility FunctionsUtility TheoryWelfare EconomicsAllocation Of Indivisible GoodsAllocative FairnessDecision Theory Under Partial InformationEquitable Resource AllocationExistence Of Efficient AllocationsFair Resource AllocationFairnessOrdinal Optimization
In this paper, we study how to fairly allocate a set of indivisible chores to a number of (asymmetric) agents with additive cost functions. We consider the fairness notion of (weighted) proportionality up to any item (PROPX), and show that a (weighted) PROPX allocation always exists and can be computed efficiently. We also consider the partial information setting, where the algorithms can only use agents’ ordinal preferences. We design algorithms that achieve 2-approximate (weighted) PROPX, and the approximation ratio is optimal. We complement the algorithmic results by investigating the relationship between (weighted) PROPX and other fairness notions such as maximin share and AnyPrice share, and bounding the social welfare loss by enforcing the allocations to be (weighted) PROPX.
30
Resource allocation and the public sector
Delia Foley · Medical Entomology and Zoology · 1967 · 1.1K citations
Dimitris Bertsimas, Vivek F. Farias, Nikolaos Trichakis · Operations Research · 2011 · 646 citations
On approximately fair allocations of indivisible goods
R.J. Lipton, Evangelos Markakis, Elchanan Mossel et al. · 2004 · 530 citations
H. Steihaus · Econometrica · 1948 · 446 citations