TY - JOUR

T1 - Computing fair and efficient allocations with few utility values

AU - Garg, Jugal

AU - Murhekar, Aniket

N1 - Funding Information:
Supported by NSF Grant CCF-1942321 (CAREER).
Publisher Copyright:
© 2023 Elsevier B.V.

PY - 2023/6/22

Y1 - 2023/6/22

N2 - We study the problem of allocating indivisible goods among agents with additive valuations in a fair and efficient manner, when agents have few utility values for the goods. We consider the compelling fairness notion of envy-freeness up to any good (EFX) in conjunction with Pareto-optimality (PO). Amanatidis et al. [1] showed that when there are at most two utility values, an EFX allocation can be computed in polynomial-time. We improve this result by showing that for such instances an allocation that is EFX and PO can be computed in polynomial-time. This is the first class apart from identical or binary valuations, for which EFX+PO allocations are shown to exist and are polynomial-time computable. In contrast, we show that when there are three utility values, EFX+PO allocations need not exist, and even deciding if EFX+PO allocations exist is NP-hard. Our techniques allow us to obtain similar results for the fairness notion of equitability up to any good (EQX) together with PO. We show that for instances with two positive values an EQX+PO allocation can be computed in polynomial-time, and deciding if an EQX+PO allocation exists is NP-hard when there are three utility values. We also study the problem of maximizing Nash welfare (MNW), and show that our EFX+PO algorithm returns an allocation that approximates the MNW to a factor of 1.061 for two valued instances, in addition to being EFX+PO. In contrast, we show that for three valued instances, computing an MNW allocation is APX-hard. Finally, we give a polynomial-time algorithm for computing an MNW allocation for two-valued instances where the ratio of the two values is greater than a certain threshold.

AB - We study the problem of allocating indivisible goods among agents with additive valuations in a fair and efficient manner, when agents have few utility values for the goods. We consider the compelling fairness notion of envy-freeness up to any good (EFX) in conjunction with Pareto-optimality (PO). Amanatidis et al. [1] showed that when there are at most two utility values, an EFX allocation can be computed in polynomial-time. We improve this result by showing that for such instances an allocation that is EFX and PO can be computed in polynomial-time. This is the first class apart from identical or binary valuations, for which EFX+PO allocations are shown to exist and are polynomial-time computable. In contrast, we show that when there are three utility values, EFX+PO allocations need not exist, and even deciding if EFX+PO allocations exist is NP-hard. Our techniques allow us to obtain similar results for the fairness notion of equitability up to any good (EQX) together with PO. We show that for instances with two positive values an EQX+PO allocation can be computed in polynomial-time, and deciding if an EQX+PO allocation exists is NP-hard when there are three utility values. We also study the problem of maximizing Nash welfare (MNW), and show that our EFX+PO algorithm returns an allocation that approximates the MNW to a factor of 1.061 for two valued instances, in addition to being EFX+PO. In contrast, we show that for three valued instances, computing an MNW allocation is APX-hard. Finally, we give a polynomial-time algorithm for computing an MNW allocation for two-valued instances where the ratio of the two values is greater than a certain threshold.

KW - EFX

KW - EQX

KW - Fair and efficient allocation

KW - Nash welfare

UR - http://www.scopus.com/inward/record.url?scp=85159758346&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85159758346&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2023.113932

DO - 10.1016/j.tcs.2023.113932

M3 - Article

AN - SCOPUS:85159758346

SN - 0304-3975

VL - 962

JO - Theoretical Computer Science

JF - Theoretical Computer Science

M1 - 113932

ER -