Fair Division Survey

This paper was written in fulfillment of the requirements of Independent Study CS 4V95.009 for the fall semester of 2024. Corrected September 2026; the literature and open questions retain their December 2024 scope.

Introduction

Fair division studies how resources can be allocated among agents with different preferences. A simple example is cut-and-choose: one agent divides a resource into two pieces of equal value in their eyes, and the other chooses a preferred piece. The procedure separates the ability to construct the division from the ability to choose, giving both agents a reason to accept the outcome.

Fair division has applications in estate division and food distribution, and its procedures have been studied for international dispute resolution [1], [2], [3], [4]. Steinhaus [5] helped formalize its mathematical study. Both divisible resources and indivisible goods have received considerable attention. For divisible cake, Aziz and Mackenzie [6] resolved the existence of a bounded envy-free protocol in the Robertson-Webb query model.

Indivisibility creates a structural obstacle: a single valuable good cannot be shared in a deterministic allocation. Exact envy-freeness therefore need not exist, and several weaker notions have been proposed. Some always exist but are difficult to compute; for others, even existence remains open. In this survey, we discuss common notions, their computational guarantees, and their relationships. We also give an elementary argument connecting maximum Nash welfare and equitability up to any positively valued good under identical additive valuations.

Preliminaries

Let 𝒩︀ be a set of 𝑛 agents and β„³οΈ€ a set of π‘š goods. Agent π‘–βˆˆπ’©οΈ€ has a valuation 𝑣𝑖:2ℳ︀→ℝβ‰₯0, with 𝑣𝑖(βˆ…)=0. Write 𝑣𝑖(𝑔) for 𝑣𝑖({𝑔}). Valuations are additive if 𝑣𝑖(𝑆)=βˆ‘π‘”βˆˆπ‘†π‘£π‘–(𝑔), and monotone if 𝑣𝑖(𝑆)≀𝑣𝑖(𝑇) whenever π‘†βŠ†π‘‡βŠ†β„³οΈ€.

Unless stated otherwise, valuations are nonnegative and additive. Identical valuations satisfy 𝑣𝑖=𝑣 for all agents, and binary additive valuations satisfy 𝑣𝑖(𝑔)∈{0,1}. We state other restrictions locally. Polynomial-time claims for additive valuations refer to rational or integer item values represented in binary. Pseudopolynomial time may depend on their numerical magnitudes. For general set functions, we use a value oracle and count bundle-value queries.

A complete allocation 𝑋=(𝑋1,…,𝑋𝑛) consists of pairwise disjoint bundles with union β„³οΈ€; bundles may be empty. Agent 𝑖’s utility is 𝑣𝑖(𝑋𝑖). A partial allocation may leave a pool 𝑃=β„³οΈ€βˆ–βˆͺπ‘–βˆˆπ’©οΈ€π‘‹π‘– unallocated. Let Ξ π‘˜(𝑆) denote all ordered partitions of 𝑆 into π‘˜ bundles, allowing empty bundles.

Equitability and Lorenz dominance compare utilities across agents and depend on their cardinal scales. Such comparisons require a specified normalization or common utility units. Envy comparisons evaluate both bundles using the same agent’s valuation.

Envy

An allocation is envy-free (EF) if 𝑣𝑖(𝑋𝑖)β‰₯𝑣𝑖(𝑋𝑗) for all agents 𝑖,𝑗. Otherwise, 𝑖 envies 𝑗. Exact EF need not exist for indivisible goods.

For explicitly represented additive valuations, deciding whether an EF allocation exists is NP-complete [7]. This motivates allowing hypothetical removal of goods to resolve envy.

EFX and zero-valued goods

An allocation is envy-free up to any positively valued good (EFX) if

𝑣𝑖(𝑋𝑖)β‰₯𝑣𝑖(π‘‹π‘—βˆ–{𝑔})βˆ€π‘–,π‘—βˆˆπ’©οΈ€,βˆ€π‘”βˆˆπ‘‹π‘— with 𝑣𝑖(𝑔)>0.

The stronger convention requiring the inequality for every π‘”βˆˆπ‘‹π‘—, including zero-valued goods, is denoted EFX0. We use EFX for the positive-good convention throughout and explicitly identify stronger guarantees. The definitions coincide for strictly positive item values. Different papers use different conventions, so the distinction matters [8].

For two agents with additive valuations, an efficient cut-and-choose procedure is available. The cutter sorts goods by nonincreasing value to itself and repeatedly places the next good in a currently least-valued bundle. The chooser takes a preferred bundle.

For two agents with nonnegative additive valuations, this procedure produces an EFX0 allocation in polynomial time.

Finding a partition with the smallest possible utility difference would also give a useful cut-and-choose construction with suitable tie breaking, but that optimization is generally NP-hard. The descending-order method avoids it. The same method gives EFX0 for any number of agents with identical additive valuations.

For three additive agents, Chaudhury et al. [9] give an EFX construction with pseudopolynomial time. A later work simplifies and improves it [10].

Leximin maximizes the minimum utility, then the second-smallest utility, and so on. The leximin++ refinement also considers bundle size: sort agents by pairs (𝑣𝑖(𝑋𝑖),|𝑋𝑖|), comparing utility first and size second, and lexicographically maximize the resulting list. Thus maximize the lowest utility, then its bundle size, then the next utility and its bundle size, and continue.

Under identical nonnegative additive valuations, every leximin++ allocation is EFX0 [11].

This proves existence, not polynomial-time optimization of leximin++. For identical additive valuations, the descending-order method already gives an efficient construction.

EF1

An allocation is envy-free up to one good (EF1) if, for every 𝑖,𝑗, either 𝑋𝑗=βˆ… or some π‘”βˆˆπ‘‹π‘— satisfies 𝑣𝑖(𝑋𝑖)β‰₯𝑣𝑖(π‘‹π‘—βˆ–{𝑔}). Thus removal of at most one good resolves envy. Budish [12] formally introduced this notion. For additive valuations, removing a good of maximum value to 𝑖 from 𝑋𝑗 suffices. For general monotone valuations, singleton value does not determine the effect of removal.

Round-robin repeatedly lets agents choose their favorite remaining good in a fixed order.

For nonnegative additive valuations, round-robin produces EF1 [4].

Another EF1 procedure is envy-cycle elimination [7]. Its graph has an edge 𝑖→𝑗 when 𝑖 envies 𝑗. An unenvied agent is a source, with indegree zero. If no source exists, there is a directed cycle. Rotate bundles so each participant receives the next participant’s envied bundle, then recompute the graph.

Envy-cycle elimination preserves EF1 for monotone valuations [7].

For general monotone valuations, any remaining good can be allocated to a source. The favorite-good and empty-bundle choices in the displayed additive version give a stronger approximation.

Approximate EFX

For π›Όβˆˆ(0,1], an allocation is 𝛼-EFX if

𝑣𝑖(𝑋𝑖)β‰₯𝛼𝑣𝑖(π‘‹π‘—βˆ–{𝑔})βˆ€π‘–,𝑗,βˆ€π‘”βˆˆπ‘‹π‘— with 𝑣𝑖(𝑔)>0.

Requiring the inequality for every good gives 𝛼-EFX0.

Plaut and Roughgarden [11] and Chan et al. [13] study half-EFX guarantees. Chan et al.β€˜s algorithm uses matchings among unenvied agents. The following argument establishes the guarantee for the single-good version above.

The displayed envy-cycle elimination algorithm produces 12-EFX0 for nonnegative additive valuations.

Amanatidis et al. [14] improve the general additive guarantee to πœ‘βˆ’1β‰ˆ0.618, where πœ‘=1+52. Their 2024 work [15] gives 23-EFX in restricted additive settings: at most seven agents, at most three distinct item values, or multigraph valuations. It does not establish 23-EFX for unrestricted additive or general monotone valuations.

Pareto Optimality

Allocation 𝐴 Pareto dominates 𝐡 if 𝑣𝑖(𝐴𝑖)β‰₯𝑣𝑖(𝐡𝑖) for all agents, strictly for at least one. An allocation is Pareto optimal (PO) if no feasible allocation dominates it. Weak coordinatewise dominance is a partial order on utility vectors, although distinct allocations may have the same vector.

Fairness and efficiency can conflict. The following example concerns the zero-inclusive convention.

Some additive instance admits no allocation that is both PO and EFX0 [11].

Lorenz dominance compares utility vectors [16]. Sort both vectors in nondecreasing order. Vector π‘Ž weakly Lorenz dominates 𝑏 if βˆ‘π‘–=1π‘˜π‘Žπ‘–β‰₯βˆ‘π‘–=1π‘˜π‘π‘– for every π‘˜βˆˆ{1,…,𝑛}. Strict Lorenz dominance requires at least one strict inequality. The comparison depends on interpersonal utility scales.

MMS

Agent 𝑖’s maximin share (MMS) is the greatest minimum bundle value it can ensure by partitioning the goods into 𝑛 bundles:

πœ‡π‘–π‘›(β„³οΈ€)=maxπ΅βˆˆΞ π‘›(β„³οΈ€)minπ‘˜βˆˆ{1,…,𝑛}𝑣𝑖(π΅π‘˜).

An MMS allocation satisfies 𝑣𝑖(𝑋𝑖)β‰₯πœ‡π‘–π‘›(β„³οΈ€) for all agents. Each benchmark uses that agent’s valuation alone; this differs from globally maximizing the worst-off agent’s utility.

The benchmark always exists for a finite instance, but an allocation meeting all benchmarks need not exist [17]. Computing exact MMS is NP-hard. High-probability results require a specified random-valuation model. An 𝛼-MMS allocation satisfies 𝑣𝑖(𝑋𝑖)β‰₯π›Όπœ‡π‘–π‘›(β„³οΈ€), where π›Όβˆˆ(0,1].

A half-MMS construction

For an existence argument, normalize each positive MMS benchmark to 1. Zero-benchmark agents impose no positive requirement and can be set aside; reducing the active-agent count cannot lower other agents’ benchmarks. Exact normalization is conceptual, not an efficient preprocessing step.

First give any good worth at least 12 to an unserved agent who values it that much. Then fill bags with arbitrary remaining goods until an unserved agent values the bag at least 12. Allocate that bag and continue. The last agent receives the remaining goods.

Removing one agent and one good weakly increases remaining agents’ MMS benchmarks when the number of bundles is reduced [18]. For 𝑛β‰₯2,

πœ‡π‘–π‘›βˆ’1(β„³οΈ€βˆ–{𝑔})β‰₯πœ‡π‘–π‘›(β„³οΈ€).

The normalized construction produces 12-MMS [18].

A polynomial-time algorithm must handle unknown benchmarks using suitable estimates or the cited approximation methods. The normalized listing establishes the guarantee, not the running time.

Approximation bounds

Procaccia and Wang [19] establish 23-MMS with efficient computation for a fixed number of agents. Later algorithms handle arbitrary agent counts, including Garg et al. [18]. Garg and Taki [20] give 34, and Akrami et al. [21] obtain

34+min{136,316π‘›βˆ’4}.

The additional term tends to zero with 𝑛. Akrami and Garg [22] obtain 34+33836, a fixed improvement over 34.

Feige et al. [23] give a three-agent instance ruling out a uniform guarantee greater than 3940. This is not a known tight answer.

Maximum Nash Welfare

Maximum Nash welfare (MNW) considers agents’ own utilities together. When all utilities can be positive, maximizing their product is equivalent to maximizing their geometric mean. If some must be zero, the product over all agents would always be zero. We therefore use a support-first definition [4].

Let 𝑁+(𝑋)={π‘–βˆˆπ’©οΈ€:𝑣𝑖(𝑋𝑖)>0}. Lexicographically maximize

(|𝑁+(𝑋)|,βˆπ‘–βˆˆπ‘+(𝑋)𝑣𝑖(𝑋𝑖))over π‘‹βˆˆΞ π‘›(β„³οΈ€),

with an empty product equal to 1. First maximize positive support, then the product of positive utilities. A product rewards balancing when transfers are feasible, but this intuition does not characterize the indivisible optimum.

Every MNW allocation is PO and EF1 for nonnegative additive valuations [4].

MNW also gives 21+4π‘›βˆ’3-MMS [4], but need not give EFX for general additive valuations [8].

Exact MNW is NP-hard even for identical additive valuations [24]. Binary additive MNW is polynomial-time computable [25]. Positive two-value instances require a finer distinction: normalize the values to {1,π‘π‘ž} for coprime integers 𝑝>π‘žβ‰₯1. Polynomial-time algorithms are known for π‘ž=1,2, while computing an optimum is NP-hard for π‘žβ‰₯3 [26]. Arbitrary bivalued instances are therefore not all tractable. Three-value instances can also be NP-hard [8].

These barriers motivate computing fairness and efficiency directly. Barman et al. [27] obtain EF1 and PO in pseudopolynomial time for integer-valued additive instances, and polynomial time when item values are polynomially bounded.

Exact MNW always exists in a finite instance. The meaningful approximation question concerns efficient computation. For instances admitting positive utility for all agents, an 𝛼 approximation to Nash social welfare achieves at least 𝛼 times the optimal geometric mean. A factor for the product differs from a factor for its 𝑛th root. Welfare approximation alone need not preserve EF1 or PO.

EQX

An allocation is equitable (EQ) if 𝑣𝑖(𝑋𝑖)=𝑣𝑗(𝑋𝑗) for all 𝑖,𝑗, on specified cardinal scales. Equality may be impossible with indivisible goods. Equitability up to any positively valued good (EQX) requires

𝑣𝑖(𝑋𝑖)β‰₯𝑣𝑗(π‘‹π‘—βˆ–{𝑔})βˆ€π‘–,𝑗,βˆ€π‘”βˆˆπ‘‹π‘— with 𝑣𝑗(𝑔)>0.

The positivity test uses the owner’s valuation 𝑣𝑗, whereas EFX uses the comparing agent’s 𝑣𝑖. Under identical valuations the notions coincide with matching conventions. Freeman et al. [28] show that strictly positive additive goods admit EQX and PO together, and give a pseudopolynomial EQ1 and PO algorithm.

Barman et al. [29] extend EQX existence to monotone valuations. Exact polynomial-time computation is available for weakly well-layered valuations, including additive valuations; their general monotone efficient guarantee is approximate EQX. Chores use the corresponding nonincreasing valuation model, and mixed manna requires further assumptions.

Under identical nonnegative additive valuations, every MNW allocation is EQX with the positive-good convention.

Positivity is essential for arbitrary MNW tie breaking. With identical item values 2,1,0, allocation ({2,0},{1}) is MNW, but removing the zero-valued good leaves value 2 facing value 1. Thus arbitrary MNW does not guarantee the stronger all-goods EQX analogue. Strictly positive item values remove this distinction.

Between EFX and EF1

Envy-freeness up to a less preferred good (EFL) lies between positive-good EFX and EF1 for additive valuations [30]. For each 𝑖,𝑗, either 𝑋𝑗 contains at most one good positively valued by 𝑖, or there exists π‘”βˆˆπ‘‹π‘— such that

𝑣𝑖(𝑋𝑖)β‰₯max{𝑣𝑖(π‘‹π‘—βˆ–{𝑔}),𝑣𝑖(𝑔)}.

Both comparisons use 𝑖’s valuation. The removed good must resolve envy and itself be worth no more to 𝑖 than its own bundle. EFL can be computed in polynomial time using a suitable envy-cycle procedure.

Envy-freeness up to a random good

Farhadi et al. [31] introduce envy-freeness up to a random good (EFR). For nonempty 𝑋𝑗, let 𝐺 be uniformly distributed over its goods. EFR requires

𝑣𝑖(𝑋𝑖)β‰₯𝔼[𝑣𝑖(π‘‹π‘—βˆ–{𝐺})].

For additive valuations, the right side is (1βˆ’1|𝑋𝑗|)𝑣𝑖(𝑋𝑗); empty-bundle comparisons are immediate. This is a hypothetical deletion from a fixed allocation, not necessarily a randomized allocation mechanism. An 𝛼-EFR allocation multiplies the right side by 𝛼. The cited work gives a polynomial-time 0.73-EFR algorithm.

Strategyproofness of randomized mechanisms is separate. An input-independent uniform allocation is strategyproof and ex ante envy-free but may be inefficient. Impossibility results for strategyproof random assignment include additional requirements, rather than ruling out these two properties alone [32].

Improving the Maximin Share

GMMS

Groupwise maximin share (GMMS) requires MMS fairness within every coalition using only its allocated goods [30]:

𝑣𝑖(𝑋𝑖)β‰₯πœ‡π‘–|𝑆|(βˆͺπ‘—βˆˆπ‘†π‘‹π‘—)βˆ€π‘†βŠ†π’©οΈ€,π‘–βˆˆπ‘†.

Let GMMS𝑖(𝑋) be the maximum of these benchmarks over coalitions containing 𝑖. An 𝛼-GMMS allocation satisfies 𝑣𝑖(𝑋𝑖)β‰₯𝛼⋅GMMS𝑖(𝑋). The full coalition recovers MMS, so GMMS need not exist.

Barman et al. [30] give a 12 guarantee, Amanatidis et al. [14] improve it to 2πœ‘+2, and Chaudhury et al. [33] give 47-GMMS for complete additive allocations. Existence guarantees and construction running times must be distinguished.

PMMS

Pairwise maximin share (PMMS) restricts GMMS to pairs:

𝑣𝑖(𝑋𝑖)β‰₯πœ‡π‘–2(𝑋𝑖βˆͺ𝑋𝑗)βˆ€π‘–β‰ π‘—.

For 𝛼-PMMS, multiply each pairwise benchmark by 𝛼. A known general additive approximation is approximately 0.781 [34].

For nonnegative additive valuations the hierarchy is

EF⇒GMMS⇒PMMS⇒EFX⇒EFL⇒EF1,

and GMMS also implies MMS [30]. EFX here uses positive-good removal. The implication to EFX0 fails: the identical-values allocation ({2,0},{1}) has two-way share 1, so is GMMS and PMMS, but is not EFX0.

An allocation can satisfy both MMS and PMMS while failing GMMS.

Other EFX Notions

Epistemic EFX

Epistemic envy-freeness (EEF) asks whether each agent 𝑖, holding its bundle fixed, can redistribute β„³οΈ€βˆ–π‘‹π‘– among the others to eliminate its envy [35]. Epistemic EFX (EEFX) requires that imagined redistribution to satisfy EFX for 𝑖 [36]. Different agents may use different imagined redistributions. In the general monotone results below, EFX satisfaction uses every single-good removal, rather than testing singleton values.

Caragiannis et al. [36] prove existence and polynomial-time computation for additive valuations. Akrami and Rathi [37] extend existence to general monotone valuations. This does not give general polynomial-time computation: EEFX is PLS-hard and requires exponentially many value queries even for identical submodular valuations.

EEF need not exist. With two agents and one good valued positively by both, the empty-bundle agent has only one possible recipient for the remaining good and cannot remove its envy by redistribution.

Charity

One can relax completeness by leaving a pool 𝑃 unallocated while requiring EFX among allocated bundles. The additional no-envy-of-charity requirement is 𝑣𝑖(𝑋𝑖)β‰₯𝑣𝑖(𝑃) for all agents. Leaving every good unallocated satisfies bundle comparisons vacuously but generally fails this requirement.

Chaudhury et al. [33] give a pseudopolynomial algorithm leaving at most π‘›βˆ’1 goods unallocated while no agent envies the pool. Berger et al. [38] obtain partial EFX leaving at most π‘›βˆ’2 goods for 𝑛β‰₯3, and at most one good for four agents. These latter bounds should not automatically be interpreted as inheriting every additional property of the earlier construction.

Zero unallocated goods recovers complete EFX. A related relaxation is EFkX: for every 𝑖,𝑗, remove any π‘‡βŠ†π‘‹π‘— of size min{π‘˜,|𝑋𝑗|} and require 𝑣𝑖(𝑋𝑖)β‰₯𝑣𝑖(π‘‹π‘—βˆ–π‘‡). We use zero-inclusive removal here, so EF1X coincides with EFX0. Akrami et al. [39] establish EF2X for restricted additive valuations, where 𝑣𝑖(𝑔)∈{0,𝑣(𝑔)}.

Arbitrary completion of partial EFX does not automatically give EF2X. Take three agents with identical values, seven unit goods, and a good β„Ž worth 2. Give the agents two, three, and two unit goods, leaving β„Ž unallocated. This is EFX0 and no agent envies the pool. Giving β„Ž to the three-good bundle leaves value 3 after removing two unit goods, above either other agent’s utility 2. A valid completion guarantee needs a separate argument.

Different Settings

Online Fair Division

Offline division has all goods available in advance. Online models allow agents, goods, or both to arrive over time [40]. Here we focus on irrevocably allocating each arriving good without knowing future goods or valuations.

Benade et al. [41] consider additive item values in [0,1]. Let Envy𝑇=max𝑖,𝑗{𝑣𝑖(𝑋𝑗)βˆ’π‘£π‘–(𝑋𝑖)} after 𝑇 arrivals. Uniform random assignment gives 𝔼[Envy𝑇]=𝑂(𝑇log(𝑇)𝑛) when 𝑇β‰₯𝑛log(𝑇), even against an adaptive adversary. Expected envy per arrival therefore vanishes for fixed 𝑛. Zero expected signed envy of a fixed pair is different from zero expected maximum envy. The paper also develops a deterministic method and lower bounds matching up to logarithmic factors.

Ex ante EF compares expected utilities. Ex ante PO rules out a lottery improving every agent’s expected utility weakly and one strictly. Ex post PO requires every allocation realized with positive probability to be PO.

With general nonnegative additive cardinal utilities, no online mechanism guarantees ex ante EF and ex ante PO on every sequence [42].

Chores and Mixed Manna

For chores, use nonnegative costs 𝑐𝑖, with lower costs preferred. For chores we use the zero-inclusive removal convention. Chores-EFX requires

𝑐𝑖(π‘‹π‘–βˆ–{𝑔})≀𝑐𝑖(𝑋𝑗)βˆ€π‘–,𝑗,βˆ€π‘”βˆˆπ‘‹π‘–.

Removal is from the envying agent’s own bundle. A multiplicative cost approximation uses 𝛽β‰₯1 on the right side.

Christoforidis and Santorinaios [43] give a superadditive-cost instance with no EFX allocation and an unbounded approximation ratio, and establish NP-completeness of deciding existence for three agents with suitably represented superadditive costs. Their removal convention includes zero-cost chores, which matters for the construction. These results do not settle additive chores-EFX existence, which remained open in December 2024, or make fairness and PO incompatible in every instance.

Restricted domains allow stronger guarantees. Ebadian et al. [44] study bivalued additive chores, while Barman et al. [45] study supermodular costs with binary marginal values. These are different classes; their EF1 and PO guarantees must be read with those restrictions. Competitive chore division has its own equilibrium algorithms [46].

Mixed manna permits 𝑣𝑖:2ℳ︀→ℝ: an item can be a good for one agent and a chore for another. Barman et al. [29] show EQX nonexistence even for two agents with additive normalized valuations. Deciding existence is weakly NP-hard for two agents and strongly NP-hard for unrestricted agent counts. When every item has the same sign for all agents, some stronger guarantees are available.

Incentives

A mechanism is strategyproof if an agent cannot improve its utility by misreporting its valuation while other reports stay fixed. For randomized mechanisms the comparison usually uses expected utility. This is a property of the allocation rule, not of a single allocation.

Fairness and truthfulness can conflict. Amanatidis et al. [47] show that for two agents and at least four goods, no deterministic truthful mechanism without payments guarantees 𝛼-MMS for 𝛼>12 on general additive valuations. Such impossibilities concern a conjunction of properties across all inputs; they do not deny truthful mechanisms or fair allocations for a fixed instance. Related characterization results identify achievable guarantees [48].

For binary additive valuations, Halpern et al. [49] construct a group-strategyproof MNW mechanism with lexicographic tie breaking. Arbitrary selection of MNW optima is not enough to conclude truthfulness. Binary additive EF1 implies positive-good EFX because all positively valued goods have equal value. Babaioff et al. [16] study truthful fair mechanisms for dichotomous submodular valuations, whose marginal values are binary, rather than arbitrary submodular valuations.

Proportionality

An allocation is proportional (PROP) if 𝑣𝑖(𝑋𝑖)β‰₯𝑣𝑖(β„³οΈ€)𝑛 for every agent. Indivisibility can prevent PROP. Proportionality up to one good (PROP1) permits adding at most one outside good: some π‘‡βŠ†β„³οΈ€βˆ–π‘‹π‘– with |𝑇|≀1 satisfies 𝑣𝑖(𝑋𝑖βˆͺ𝑇)β‰₯𝑣𝑖(β„³οΈ€)𝑛.

Proportionality up to any positively valued good (PROPx) requires either that the agent is already proportional or that adding every outside good 𝑔 with 𝑣𝑖(𝑔)>0 reaches 𝑣𝑖(β„³οΈ€)𝑛. The zero-value convention should be specified when comparing variants. Aziz, Moulin, and Sandomirskiy [50] give a strongly polynomial PROP1 and PO algorithm for additive valuations.

Identical strictly positive additive valuations need not admit PROPx [50].

Proportionality up to the maximin good (PROPm) is an intermediate notion that always exists and is polynomial-time computable for additive goods [51]. Define

𝑑𝑖(𝑋)=max𝑗≠𝑖minπ‘”βˆˆπ‘‹π‘—π‘£π‘–(𝑔),

taking the minimum of an empty bundle as 0 and 𝑑𝑖(𝑋)=0 for one agent. PROPm requires 𝑣𝑖(𝑋𝑖)+𝑑𝑖(𝑋)β‰₯𝑣𝑖(β„³οΈ€)𝑛. The threshold is 1𝑛 only after normalizing 𝑣𝑖(β„³οΈ€)=1.

Fisher Markets

Markets offer another route to fairness and efficiency. A linear Fisher market has divisible goods, positive budgets ℓ𝑖, and prices 𝑝=(𝑝1,…,π‘π‘š). A fractional allocation gives utility

𝑒𝑖(π‘₯𝑖)=βˆ‘π‘”βˆˆβ„³οΈ€π‘£π‘–(𝑔)π‘₯𝑖,𝑔,

where π‘₯𝑖,𝑔β‰₯0 and βˆ‘π‘–π‘₯𝑖,𝑔≀1. The feasible set differs from integral allocation of indivisible goods.

Assume every agent values some good and every good is valued by someone. An equilibrium satisfies:

  1. Supply clears: βˆ‘π‘–π‘₯𝑖,𝑔=1 for each 𝑔.
  2. Budgets are exhausted: βˆ‘π‘”π‘π‘”π‘₯𝑖,𝑔=ℓ𝑖 for each 𝑖.
  3. Agents receive only maximum-bang-per-buck goods: π‘₯𝑖,𝑔>0 implies 𝑣𝑖(𝑔)𝑝𝑔=maxβ„Žπ‘£π‘–(β„Ž)π‘β„Ž.

These assumptions permit positive prices; goods valued by nobody can be assigned price zero and handled separately. Equal budgets give a competitive equilibrium from equal incomes (CEEI).

Exact equilibria for rational linear divisible-goods Fisher markets are polynomial-time computable, including by the classical combinatorial algorithm of Devanur et al. [52]. Exact CEEI computation is therefore not open for this model. Integral CEEI need not exist: one positive-priced indivisible good cannot exhaust two equal positive budgets in an integral allocation.

An integral allocation is fractionally Pareto optimal (fPO) if no feasible fractional allocation dominates it. Thus fPO implies PO, since integral allocations form a subset of the fractional feasible set. A divisible-goods CEEI is envy-free and efficient within the fractional feasible set under the standard linear assumptions [53]. Producing integral fairness from an equilibrium needs an additional rounding or allocation argument.

Chore markets differ: agents earn payments for taking bads rather than spend budgets on goods. The approximate-equilibrium algorithms of Boodaghians et al. [54] and Chaudhury et al. [55] concern chores. Their definitions and guarantees cannot be transferred directly to the divisible-goods model above.

Empirical Results

Formal guarantees address stated valuations, while perceived fairness may also depend on agents’ information. Hosseini et al. [56] use crowdsourced scenarios to compare preferences for assigned and alternative bundles under different fairness and information conditions. The information presented can affect perceived fairness. This differs from a universal guarantee that agents accept an EF1 allocation.

Cardinal elicitation is another practical issue. Spliddit asks agents to distribute 1,000 points among goods according to their preferences. Positive rescaling preserves envy comparisons. When every agent can receive positive utility, rescaling also preserves MNW optima; interpersonal notions such as EQX depend on the normalization. Caragiannis et al. [4] report sub-three-second MNW computation on each of 1,281 Spliddit instances, whose largest instances had ten agents, with the reported hardware and solver. This is an experimental benchmark, not a worst-case runtime guarantee for all ten-agent inputs.

Discussion

We surveyed common fairness notions for indivisible goods and their connections to efficiency and computation. Indivisibility prevents exact EF and PROP even in simple instances, motivating EF1, EFX, and MMS approximations. Stronger guarantees may require restricted valuations, unallocated goods, or a different computational objective.

MNW illustrates both the usefulness and difficulty of a global objective: it guarantees EF1 and PO under additive valuations but may be hard to compute exactly. With identical additive valuations, it also gives EQX for positively valued goods by the elementary transfer argument above. The qualification about zeros is necessary for stronger removal conventions.

As of December 2024, central questions include complete additive EFX existence, polynomial-time EF1 and PO computation, and tighter MMS and groupwise approximation guarantees. Strategic and online models add different obstacles; their impossibilities concern mechanisms with specified information and incentive requirements. Keeping these models distinct is essential when comparing what is known and what remains unproved.

References

  • [1] S. J. Brams, β€œFair Division in Dispute Resolution,” in The Oxford Handbook of Public Choice, Volume 1, Oxford University Press, 2019. doi: 10.1093/oxfordhb/9780190469733.013.44.
  • [2] M. Aleksandrov, H. Aziz, S. Gaspers, and T. Walsh, β€œOnline Fair Division: analysing a Food Bank problem.” [Online]. Available: https://arxiv.org/abs/1502.07571
  • [3] M. Mertzanidis, A. Psomas, and P. Verma, β€œAutomating Food Drop: The Power of Two Choices for Dynamic and Fair Food Allocation.” [Online]. Available: https://arxiv.org/abs/2406.06363
  • [4] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang, β€œThe Unreasonable Fairness of Maximum Nash Welfare,” ACM Trans. Econ. Comput., vol. 7, no. 3, Sep. 2019, doi: 10.1145/3355902.
  • [5] H. Steinhaus, β€œThe problem of fair division,” Econometrica, vol. 16, pp. 101–104, 1948.
  • [6] H. Aziz and S. Mackenzie, β€œA Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents.” [Online]. Available: https://arxiv.org/abs/1604.03655
  • [7] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi, β€œOn approximately fair allocations of indivisible goods,” in Proceedings of the 5th ACM Conference on Electronic Commerce, 2004, pp. 125–131.
  • [8] G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, A. Hollender, and A. A. Voudouris, β€œMaximum Nash welfare and other stories about EFX,” Theoretical Computer Science, vol. 863, pp. 69–85, 2021, doi: 10.1016/j.tcs.2021.02.020.
  • [9] B. R. Chaudhury, J. Garg, and K. Mehlhorn, β€œEFX Exists for Three Agents,” J. ACM, vol. 71, no. 1, Feb. 2024, doi: 10.1145/3616009.
  • [10] H. Akrami, N. Alon, B. R. Chaudhury, J. Garg, K. Mehlhorn, and R. Mehta, β€œEFX allocations: Simplifications and improvements,” arXiv preprint arXiv:2205.07638, 2022.
  • [11] B. Plaut and T. Roughgarden, β€œAlmost envy-freeness with general valuations,” SIAM Journal on Discrete Mathematics, vol. 34, no. 2, pp. 1039–1068, 2020.
  • [12] E. Budish, β€œThe Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes,” Journal of Political Economy, vol. 119, no. 6, pp. 1061–1103, 2011, doi: 10.1086/664613.
  • [13] H. Chan, J. Chen, B. Li, and X. Wu, β€œMaximin-Aware Allocations of Indivisible Goods.” [Online]. Available: https://arxiv.org/abs/1905.09969
  • [14] G. Amanatidis, E. Markakis, and A. Ntokos, β€œMultiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination,” Theoretical Computer Science, vol. 841, pp. 94–109, 2020, doi: 10.1016/j.tcs.2020.07.006.
  • [15] G. Amanatidis, A. Filos-Ratsikas, and A. Sgouritsa, β€œPushing the Frontier on Approximate EFX Allocations.” [Online]. Available: https://arxiv.org/abs/2406.12413
  • [16] M. Babaioff, T. Ezra, and U. Feige, β€œFair and truthful mechanisms for dichotomous valuations,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2021, pp. 5119–5126.
  • [17] D. Kurokawa, A. Procaccia, and J. Wang, β€œWhen Can the Maximin Share Guarantee Be Guaranteed?,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 30, no. 1, Feb. 2016, doi: 10.1609/aaai.v30i1.10041.
  • [18] J. Garg, P. McGlaughlin, and S. Taki, β€œApproximating Maximin Share Allocations,” in 2nd Symposium on Simplicity in Algorithms (SOSA 2019), J. T. Fineman and M. Mitzenmacher, Eds., in Open Access Series in Informatics (OASIcs), vol. 69. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik, 2019, p. 20:1–20:11. doi: 10.4230/OASIcs.SOSA.2019.20.
  • [19] A. D. Procaccia and J. Wang, β€œFair enough: guaranteeing approximate maximin shares,” in Proceedings of the Fifteenth ACM Conference on Economics and Computation, in EC '14. Palo Alto, California, USA: Association for Computing Machinery, 2014, pp. 675–692. doi: 10.1145/2600057.2602835.
  • [20] J. Garg and S. Taki, β€œAn improved approximation algorithm for maximin shares,” in Proceedings of the 21st ACM Conference on Economics and Computation, 2020, pp. 379–380.
  • [21] H. Akrami, J. Garg, E. Sharma, and S. Taki, β€œSimplification and improvement of MMS approximation,” arXiv preprint arXiv:2303.16788, 2023.
  • [22] H. Akrami and J. Garg, β€œBreaking the 3/4 barrier for approximate maximin share,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024, pp. 74–91.
  • [23] U. Feige, A. Sapir, and L. Tauber, β€œA Tight Negative Example for MMS Fair Allocations,” in Web and Internet Economics, M. Feldman, H. Fu, and I. Talgam-Cohen, Eds., Cham: Springer International Publishing, 2022, pp. 355–372.
  • [24] M. Roos and J. Rothe, β€œComplexity of social welfare optimization in multiagent resource allocation,” in Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1-Volume 1, 2010, pp. 641–648.
  • [25] S. Barman, S. K. Krishnamurthy, and R. Vaish, β€œGreedy algorithms for maximizing Nash social welfare,” arXiv preprint arXiv:1801.09046, 2018.
  • [26] H. Akrami et al., β€œMaximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability.” [Online]. Available: https://arxiv.org/abs/2207.10949v5
  • [27] S. Barman, S. K. Krishnamurthy, and R. Vaish, β€œFinding fair and efficient allocations,” in Proceedings of the 2018 ACM Conference on Economics and Computation, 2018, pp. 557–574.
  • [28] R. Freeman, S. Sikdar, R. Vaish, and L. Xia, β€œEquitable allocations of indivisible goods,” arXiv preprint arXiv:1905.10656, 2019.
  • [29] S. Barman, U. Bhaskar, Y. Pandit, and S. Pyne, β€œNearly Equitable Allocations beyond Additivity and Monotonicity,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2024, pp. 9494–9501.
  • [30] S. Barman, A. Biswas, S. K. Krishnamurthy, and Y. Narahari, β€œGroupwise maximin fair allocation of indivisible goods,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
  • [31] A. Farhadi, M. Hajiaghayi, M. Latifian, M. Seddighin, and H. Yami, β€œAlmost envy-freeness, envy-rank, and Nash social welfare matchings,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2021, pp. 5355–5362.
  • [32] C. Basteck and L. Ehlers, β€œStrategy-proof and envy-free random assignment,” Journal of Economic Theory, vol. 209, p. 105618, 2023.
  • [33] B. R. Chaudhury, T. Kavitha, K. Mehlhorn, and A. Sgouritsa, β€œA little charity guarantees almost envy-freeness,” SIAM Journal on Computing, vol. 50, no. 4, pp. 1336–1358, 2021.
  • [34] D. Kurokawa, β€œFair division in game theoretic settings,” Doctoral dissertation, 2017.
  • [35] H. Aziz, S. Bouveret, I. Caragiannis, I. Giagkousi, and J. Lang, β€œKnowledge, fairness, and social constraints,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
  • [36] I. Caragiannis, J. Garg, N. Rathi, E. Sharma, and G. Varricchio, β€œNew Fairness Concepts for Allocating Indivisible Items,” 2023.
  • [37] H. Akrami and N. Rathi, β€œEpistemic EFX Allocations Exist for Monotone Valuations.” [Online]. Available: https://arxiv.org/abs/2405.14463
  • [38] B. Berger, A. Cohen, M. Feldman, and A. Fiat, β€œ(Almost Full) EFX Exists for Four Agents (and Beyond).” [Online]. Available: https://arxiv.org/abs/2102.10654
  • [39] H. Akrami, R. Rezvan, and M. Seddighin, β€œAn EF2X allocation protocol for restricted additive valuations,” arXiv preprint arXiv:2202.13676, 2022.
  • [40] M. Aleksandrov and T. Walsh, β€œOnline fair division: A survey,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2020, pp. 13557–13562.
  • [41] G. Benade, A. M. Kazachkov, A. D. Procaccia, and C.-A. Psomas, β€œHow to make envy vanish over time,” in Proceedings of the 2018 ACM Conference on Economics and Computation, 2018, pp. 593–610.
  • [42] M. Aleksandrov and T. Walsh, β€œStrategy-proofness, envy-freeness and pareto efficiency in online fair division with additive utilities,” in PRICAI 2019: Trends in Artificial Intelligence: 16th Pacific Rim International Conference on Artificial Intelligence, Cuvu, Yanuca Island, Fiji, August 26–30, 2019, Proceedings, Part I 16, 2019, pp. 527–541.
  • [43] V. Christoforidis and C. Santorinaios, β€œOn The Pursuit of EFX for Chores: Non-Existence and Approximations.” [Online]. Available: https://arxiv.org/abs/2406.10752
  • [44] S. Ebadian, D. Peters, and N. Shah, β€œHow to fairly allocate easy and difficult chores,” arXiv preprint arXiv:2110.11285, 2021.
  • [45] S. Barman, V. V. Narayan, and P. Verma, β€œFair Chore Division under Binary Supermodular Costs.” [Online]. Available: https://arxiv.org/abs/2302.11530
  • [46] S. BrΓ’nzei and F. Sandomirskiy, β€œAlgorithms for competitive division of chores,” arXiv preprint arXiv:1907.01766, 2019.
  • [47] G. Amanatidis, G. Birmpas, and E. Markakis, β€œOn truthful mechanisms for maximin share allocations,” arXiv preprint arXiv:1605.04026, 2016.
  • [48] G. Amanatidis, G. Birmpas, G. Christodoulou, and E. Markakis, β€œTruthful allocation mechanisms without payments: Characterization and implications on fairness,” in Proceedings of the 2017 ACM Conference on Economics and Computation, 2017, pp. 545–562.
  • [49] D. Halpern, A. D. Procaccia, A. Psomas, and N. Shah, β€œFair Division with Binary Valuations: One Rule to Rule Them All.” [Online]. Available: https://arxiv.org/abs/2007.06073
  • [50] H. Aziz, H. Moulin, and F. Sandomirskiy, β€œA polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation,” Operations Research Letters, vol. 48, no. 5, pp. 573–578, 2020.
  • [51] A. Baklanov, P. Garimidi, V. Gkatzelis, and D. Schoepflin, β€œPROPm allocations of indivisible goods to multiple agents,” arXiv preprint arXiv:2105.11348, 2021.
  • [52] N. R. Devanur, C. H. Papadimitriou, A. Saberi, and V. V. Vazirani, β€œMarket Equilibrium via a Primal-Dual Algorithm for a Convex Program,” Journal of the ACM, vol. 55, no. 5, 2008, doi: 10.1145/1411509.1411512.
  • [53] A. Mas-Colell, M. Whinston, and J. Green, Microeconomic Theory. in Microeconomic Theory. Oxford University Press, 1995. [Online]. Available: https://books.google.com/books?id=KGtegVXqD8wC
  • [54] S. Boodaghians, B. R. Chaudhury, and R. Mehta, β€œPolynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores,” in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022, pp. 2285–2302.
  • [55] B. R. Chaudhury, J. Garg, P. McGlaughlin, and R. Mehta, β€œOn the existence of competitive equilibrium with chores,” in 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), 2022.
  • [56] H. Hosseini, J. Kavner, S. Sikdar, R. Vaish, and L. Xia, β€œHide, Not Seek: Perceived Fairness in Envy-Free Allocations of Indivisible Goods.” [Online]. Available: https://arxiv.org/abs/2212.04574v2