Existence of EFX for two additive valuations

DOI10.1016/J.DAM.2023.06.035MaRDI QIDQ6094718zbMATH OpenFDO

Authors Ryoga Mahara

Publication date 14 September 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.08798

zbMATH Keywords

EFX allocationfair divisionindivisible items

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: Fair division of indivisible items is a well-studied topic in Economics and Computer Science.The objective is to allocate items to agents in a fair manner, where each agent has a valuation for each subset of items. Envy-freeness is one of the most widely studied notions of fairness. Since complete envy-free allocations do not always exist when items are indivisible, several relaxations have been considered. Among them, possibly the most compelling one is envy-freeness up to any item (EFX), where no agent envies another agent after the removal of any single item from the other agent's bundle. However, despite significant efforts by many researchers for several years, it is known that a complete EFX allocation always exists only in limited cases. In this paper, we show that a complete EFX allocation always exists when each agent is of one of two given types, where agents of the same type have identical additive valuations. This is the first such existence result for non-identical valuations when there are any number of agents and items and no limit on the number of distinct values an agent can have for individual items. We give a constructive proof, in which we iteratively obtain a Pareto dominating (partial) EFX allocation from an existing partial EFX allocation.

Recommendations

• On the existence of EFX allocations
• Almost envy-freeness with general valuations
• Almost envy-freeness with general valuations
• Maximum Nash welfare and other stories about EFX
• Computing fair and efficient allocations with few utility values

Cites work

• A Little Charity Guarantees Almost Envy-Freeness
• Almost envy-free allocations with connected bundles
• Almost envy-freeness with general valuations
• Approximating the Nash Social Welfare with Indivisible Items
• Approximation Algorithms for Computing Maximin Share Allocations
• APX-hardness of maximizing Nash social welfare with indivisible items
• Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation
• Extension of Additive Valuations to General Valuations on the Existence of EFX.
• Fair allocation of indivisible goods: improvement
• Fair enough: guaranteeing approximate maximin shares
• Maximum Nash welfare and other stories about EFX
• Nash social welfare for indivisible items under separable, piecewise-linear concave utilities
• Nash social welfare, matrix permanent, and stable polynomials
• On fair division for indivisible items

Cited in

(14)

• On the existence of EFX allocations
• Maximum Nash welfare and other stories about EFX
• Almost envy-freeness with general valuations
• Almost envy-freeness with general valuations
• EFX allocations exist for binary valuations
• The frontier of intractability for EFX with two agents
• Extension of additive valuations to general valuations on the existence of EFX
• Note on the existence of EFX allocations for negative additive valuations
• Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods
• Fair and truthful allocations under leveled valuations
• Proportional allocation of indivisible goods up to the least valued good on average
• Best-of-both-worlds fair allocation of indivisible and mixed goods
• Approximating EFX through a new notion of fairness
• Extending EFX allocations to further multi-graph classes

This page was built for publication: Existence of EFX for two additive valuations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6094718)