Breaking the 3/4 barrier for approximate maximin share

H Akrami, J Garg - Proceedings of the 2024 Annual ACM-SIAM …, 2024 - SIAM
We study the fundamental problem of fairly allocating a set of indivisible goods among n
agents with additive valuations using the desirable fairness notion of maximin share (MMS) …

Improving approximation guarantees for maximin share

H Akrami, J Garg, E Sharma, S Taki - arXiv preprint arXiv:2307.12916, 2023 - arxiv.org
We consider fair division of a set of indivisible goods among $ n $ agents with additive
valuations using the fairness notion of maximin share (MMS). MMS is the most popular …

Breaking the envy cycle: Best-of-both-worlds guarantees for subadditive valuations

M Feldman, S Mauras, VV Narayan… - Proceedings of the 25th …, 2024 - dl.acm.org
We study best-of-both-worlds guarantees for the fair division of indivisible items among
agents with subadditive valuations. Our main result establishes the existence of a random …

Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously

H Akrami, N Rathi - arXiv preprint arXiv:2409.01963, 2024 - arxiv.org
We study the problem of computing\emph {fair} divisions of a set of indivisible goods among
agents with\emph {additive} valuations. For the past many decades, the literature has …

Best-of-both-worlds fair allocation of indivisible and mixed goods

X Bu, Z Li, S Liu, X Lu, B Tao - arXiv preprint arXiv:2410.06877, 2024 - arxiv.org
We study the problem of fairly allocating either a set of indivisible goods or a set of mixed
divisible and indivisible goods (ie, mixed goods) to agents with additive utilities, taking the …

Randomized Strategyproof Mechanisms with Best of Both Worlds Fairness and Efficiency

A Sun, B Chen - arXiv preprint arXiv:2408.01027, 2024 - arxiv.org
We study the problem of mechanism design for allocating a set of indivisible items among
agents with private preferences on items. We are interested in such a mechanism that is …

Guaranteeing MMS for All but One Agent When Allocating Indivisible Chores

J Qiu, X Wu, C Zhang, S Zhou - arXiv preprint arXiv:2410.12347, 2024 - arxiv.org
We study the problem of allocating $ m $ indivisible chores to $ n $ agents with additive cost
functions under the fairness notion of maximin share (MMS). In this work, we propose a …

Maximin Shares in Hereditary Set Systems

H Hummel - arXiv preprint arXiv:2404.11582, 2024 - arxiv.org
We consider the problem of fairly allocating a set of indivisible items under the criteria of the
maximin share guarantee. Specifically, we study approximation of maximin share allocations …

Epistemic EFX Allocations Exist for Monotone Valuations

H Akrami, N Rathi - arXiv preprint arXiv:2405.14463, 2024 - arxiv.org
We study the fundamental problem of fairly dividing a set of indivisible items among agents
with (general) monotone valuations. The notion of envy-freeness up to any item (EFX) is …

Fair and Truthful Allocations Under Leveled Valuations

G Christodoulou, V Christoforidis - arXiv preprint arXiv:2407.05891, 2024 - arxiv.org
We study the problem of fairly allocating indivisible goods among agents which are
equipped with {\em leveled} valuation functions. Such preferences, that have been studied …