Fair Allocation of Items in Multiple Regions

Houyu Zhou; Tianze Wei; Biaoshuai Tao; Minming Li

doi:10.1609/aaai.v38i9.28861

Fair Allocation of Items in Multiple Regions

Houyu Zhou, Tianze Wei^*, Biaoshuai Tao, Minming Li

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

1 Citation (Scopus)

Abstract

We initiate the study of fair allocation with the set of divisible or indivisible items distributed in multiple regions. The key requirement is that each agent can only obtain items from one region. In this work, we consider two kinds of fairness concepts: envy-based notions including envy-freeness (EF) and envy-freeness up to one/any item (EF1/EFX), and share-based notions including proportionality (PROP) and proportionality up to one/any item (PROP1/PROPX). On the negative side, we show NP-hardness and inapproximability results about the aforementioned fairness notions. On the positive side, we propose several algorithms to compute the partial allocations that satisfy envy-based notions and allocations that approximate the above fairness notions.

© 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Original language	English
Title of host publication	Proceedings of the 38th AAAI Conference on Artificial Intelligence
Publisher	AAAI Press
Pages	9985-9992
Number of pages	8
Volume	38
ISBN (Print)	1-57735-887-2, 978-1-57735-887-9
DOIs	https://doi.org/10.1609/aaai.v38i9.28861
Publication status	Published - 2024
Event	38th Annual AAAI Conference on Artificial Intelligence (AAAI-24) - Vancouver Convention Centre – West Building, Vancouver, Canada Duration: 20 Feb 2024 → 27 Feb 2024 https://aaai.org/aaai-conference/

Conference

Conference	38th Annual AAAI Conference on Artificial Intelligence (AAAI-24)
Abbreviated title	AAAI-24
Place	Canada
City	Vancouver
Period	20/02/24 → 27/02/24
Internet address	https://aaai.org/aaai-conference/

Funding

The work described in this paper was partially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. CityU 11213620]. The research of Biaoshuai Tao was supported by the National Natural Science Foundation of China (No. 62102252). We thank the anonymous AAAI-24 reviewers for their very useful feedback.

Research Keywords

GTEP
Fair Division

RGC Funding Information

RGC-funded

Access Output

10.1609/aaai.v38i9.28861

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

GRF: Algorithmic Foundations of Distributed Large-Scale Graph Processing
LI, M. (Principal Investigator / Project Coordinator), Konrad, C. (Co-Investigator) & ROBINSON, P. (Co-Investigator)
1/01/21 → 5/06/25
Project: Research

Cite this

@inproceedings{05e62e225296497aa04eb88ba12680cc,

title = "Fair Allocation of Items in Multiple Regions",

abstract = "We initiate the study of fair allocation with the set of divisible or indivisible items distributed in multiple regions. The key requirement is that each agent can only obtain items from one region. In this work, we consider two kinds of fairness concepts: envy-based notions including envy-freeness (EF) and envy-freeness up to one/any item (EF1/EFX), and share-based notions including proportionality (PROP) and proportionality up to one/any item (PROP1/PROPX). On the negative side, we show NP-hardness and inapproximability results about the aforementioned fairness notions. On the positive side, we propose several algorithms to compute the partial allocations that satisfy envy-based notions and allocations that approximate the above fairness notions.{\textcopyright} 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.",

keywords = "GTEP, Fair Division",

author = "Houyu Zhou and Tianze Wei and Biaoshuai Tao and Minming Li",

year = "2024",

doi = "10.1609/aaai.v38i9.28861",

language = "English",

isbn = "1-57735-887-2",

volume = "38",

pages = "9985--9992",

booktitle = "Proceedings of the 38th AAAI Conference on Artificial Intelligence",

publisher = "AAAI Press",

note = "38th Annual AAAI Conference on Artificial Intelligence (AAAI-24), AAAI-24 ; Conference date: 20-02-2024 Through 27-02-2024",

url = "https://aaai.org/aaai-conference/",

}

TY - GEN

T1 - Fair Allocation of Items in Multiple Regions

AU - Zhou, Houyu

AU - Wei, Tianze

AU - Tao, Biaoshuai

AU - Li, Minming

PY - 2024

Y1 - 2024

N2 - We initiate the study of fair allocation with the set of divisible or indivisible items distributed in multiple regions. The key requirement is that each agent can only obtain items from one region. In this work, we consider two kinds of fairness concepts: envy-based notions including envy-freeness (EF) and envy-freeness up to one/any item (EF1/EFX), and share-based notions including proportionality (PROP) and proportionality up to one/any item (PROP1/PROPX). On the negative side, we show NP-hardness and inapproximability results about the aforementioned fairness notions. On the positive side, we propose several algorithms to compute the partial allocations that satisfy envy-based notions and allocations that approximate the above fairness notions.© 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

AB - We initiate the study of fair allocation with the set of divisible or indivisible items distributed in multiple regions. The key requirement is that each agent can only obtain items from one region. In this work, we consider two kinds of fairness concepts: envy-based notions including envy-freeness (EF) and envy-freeness up to one/any item (EF1/EFX), and share-based notions including proportionality (PROP) and proportionality up to one/any item (PROP1/PROPX). On the negative side, we show NP-hardness and inapproximability results about the aforementioned fairness notions. On the positive side, we propose several algorithms to compute the partial allocations that satisfy envy-based notions and allocations that approximate the above fairness notions.© 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

KW - GTEP

KW - Fair Division

U2 - 10.1609/aaai.v38i9.28861

DO - 10.1609/aaai.v38i9.28861

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 1-57735-887-2

SN - 978-1-57735-887-9

VL - 38

SP - 9985

EP - 9992

BT - Proceedings of the 38th AAAI Conference on Artificial Intelligence

PB - AAAI Press

T2 - 38th Annual AAAI Conference on Artificial Intelligence (AAAI-24)

Y2 - 20 February 2024 through 27 February 2024

ER -

Fair Allocation of Items in Multiple Regions

Abstract

Conference

Funding

Research Keywords

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Fingerprint

Projects

GRF: Algorithmic Foundations of Distributed Large-Scale Graph Processing

Cite this