Fairly Allocating Goods in Parallel

We initiate the study of parallel algorithms for fairly allocating indivisible goods among agents with additive preferences. We give fast parallel algorithms for various fundamental problems, such as finding a Pareto Optimal and EF1 allocation under restricted additive valuations, finding an EF1 all...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-09
Main Authors: Garg, Rohan, Psomas, Alexandros
Format: Article
Language:English
Subjects:
Algorithms
Allocations
Reagents
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We initiate the study of parallel algorithms for fairly allocating indivisible goods among agents with additive preferences. We give fast parallel algorithms for various fundamental problems, such as finding a Pareto Optimal and EF1 allocation under restricted additive valuations, finding an EF1 allocation for up to three agents, and finding an envy-free allocation with subsidies. On the flip side, we show that fast parallel algorithms are unlikely to exist (formally, \(CC\)-hard) for the problem of computing Round-Robin EF1 allocations.
ISSN:2331-8422