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 , with . 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 . 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 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
The stronger convention requiring the inequality for every , including zero-valued goods, is denoted . 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 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 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 [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 , an allocation is -EFX if
Requiring the inequality for every good gives -.
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 - for nonnegative additive valuations.
Amanatidis et al. [14] improve the general additive guarantee to , where . Their 2024 work [15] gives -EFX in restricted additive settings: at most seven agents, at most three distinct item values, or multigraph valuations. It does not establish -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 [11].
Lorenz dominance compares utility vectors [16]. Sort both vectors in nondecreasing order. Vector weakly Lorenz dominates if for every . 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:
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 .
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 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 . 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 ,
The normalized construction produces -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 -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 , and Akrami et al. [21] obtain
The additional term tends to zero with . Akrami and Garg [22] obtain , a fixed improvement over .
Feige et al. [23] give a three-agent instance ruling out a uniform guarantee greater than . 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 . Lexicographically maximize
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 -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 for coprime integers . Polynomial-time algorithms are known for , while computing an optimum is NP-hard for [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
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 , allocation 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
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 ; 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 -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 be the maximum of these benchmarks over coalitions containing . An -GMMS allocation satisfies . The full coalition recovers MMS, so GMMS need not exist.
Barman et al. [30] give a guarantee, Amanatidis et al. [14] improve it to , and Chaudhury et al. [33] give -GMMS for complete additive allocations. Existence guarantees and construction running times must be distinguished.
PMMS
Pairwise maximin share (PMMS) restricts GMMS to pairs:
For -PMMS, multiply each pairwise benchmark by . A known general additive approximation is approximately [34].
For nonnegative additive valuations the hierarchy is
and GMMS also implies MMS [30]. EFX here uses positive-good removal. The implication to fails: the identical-values allocation has two-way share 1, so is GMMS and PMMS, but is not .
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 goods unallocated while no agent envies the pool. Berger et al. [38] obtain partial EFX leaving at most goods for , 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 and require . We use zero-inclusive removal here, so EF1X coincides with . Akrami et al. [39] establish EF2X for restricted additive valuations, where .
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 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 . Let after arrivals. Uniform random assignment gives when , 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 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 : 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 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 satisfies .
Proportionality up to any positively valued good (PROPx) requires either that the agent is already proportional or that adding every outside good with 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
taking the minimum of an empty bundle as 0 and for one agent. PROPm requires . The threshold is only after normalizing .
Fisher Markets
Markets offer another route to fairness and efficiency. A linear Fisher market has divisible goods, positive budgets , and prices . A fractional allocation gives utility
where and . 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:
- Supply clears: for each .
- Budgets are exhausted: for each .
- Agents receive only maximum-bang-per-buck goods: implies .
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