Text

Fair Allocation of Indivisible Goods : Improvement

We study the problem of fair allocation for indivisible goods. We use the maximin share paradigm introduced by Budish [Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061–1103.] as a measure of fairness. Kurokawa et al. [Kurokawa D, Procaccia AD, Wang J (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):8.] were the first to investigate this fundamental problem in the additive setting. They showed that in delicately constructed examples, not everyone can obtain a utility of at least her maximin value. They mitigated this impossibility result with a beautiful observation: no matter how the utility functions are made, we always can allocate the items to the agents to guarantee each agent’s utility is at least 2/3 of her maximin value. They left open whether this bound can be improved. Our main contribution answers this question in the affirmative. We improve their approximation result to a 3/4 factor guarantee.

Ketersediaan

Informasi Detail

Judul Seri

MATHEMATICS OF OPERATIONS RESEARCH; Vol.46 No.3 August 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1038 - 1053

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

FAIRNESS
APPROXIMATION
MAXIMIN SHARE

Info Detail Spesifik

https://doi.org/10.1287/moor.2020.1096

Pernyataan Tanggungjawab

Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, Hadi Yami

Versi lain/terkait

Lampiran Berkas

Komentar