*LINK 1*

*as of ’20 february 2020’*

*LINK 1*

*open problems in ‘fair cake cutting’*

Fair cake-cutting is a kind of ‘fair division problem’

The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value.

The resource has to be divided among several partners who have different preferences over different parts of the cake,

i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible.

The division should be subjectively fair, in that each person should receive a piece that he or she believes to be a fair share.

The “cake” is only a metaphor; procedures for fair cake-cutting can be used to divide various kinds of resources, such as land estates, advertisement space or broadcast time

The cake-cutting problem was introduced by Hugo Steinhaus after World War II^[1] and is still the subject of intense research in…

mathematics

computer science

economics

political science

*’query complexity’ of ‘envy-free cake cutting’*

An envy-free cake-cutting is a kind of fair cake-cutting.

It is a division of a heterogeneous resource (“cake”) that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

Unsolved problem in computer science:
What is the runtime complexity of envy-free cake-cutting?(more unsolved problems in computer science)

When there are only two partners, the problem is easy and has been solved in Biblical times by the divide and choose protocol.

When there are three or more partners, the problem becomes much more challenging

List of unsolved problems in fair division

From Wikipedia, the free encyclopediaJump to navigationJump to search

This page lists open problems related to fair division – a field in the intersection of mathematics, computer science, political science and economics.

1Open problems in fair cake-cutting

1.1Query complexity of envy-free cake-cutting

1.2Number of cuts for cake-cutting with different entitlements

1.3Fair division of a partly-burnt cake

1.4Truthful cake-cutting

2Open problems in fair allocation of indivisible items

2.1Approximate maximin-share fairness

2.1.11. Computational complexity

2.1.22. Cardinal approximation

2.1.33. Ordinal approximation

2.2Envy-free up to one item

2.2.1Pareto-optimal EF1 allocation (goods and bads)

2.2.2Contiguous EF1 allocation

2.3Existence of EFx allocation

2.4Existence of Pareto-efficient PROPx allocation of bads

2.5Competitive equilibrium for almost all incomes

3Fair division of partly-divisible items

3.1Runtime complexity of fair allocation with bounded sharing

4References

Open problems in fair cake-cutting

Query complexity of envy-free cake-cutting[edit]

In the problem of envy-free cake-cutting, there is a cake modeled as an interval, and {\displaystyle n} agents with different value measures over the cake. The value measures are accessible only via queries of the form “evaluate a given piece of cake” or “mark a piece of cake with a given value”. WIth {\displaystyle n=2} agents, an envy-free division can be found using two queries, via divide and choose. With {\displaystyle n>2} agents, there are several open problems regarding the number of required queries.

1. First, assume that the entire cake must be allocated (i.e., there is no disposal), and pieces may be disconnected. How many queries are required?

Lower bound: {\displaystyle \Omega (n^{2})};^[1]
Upper bound: {\displaystyle O(n^{n^{n^{n^{n^{n}}}}})}.^[2]

2. Next, assume that some cake may be left unallocated (i.e., there is free disposal), but the allocation must be proportional (in addition to envy-free): each agent must get at least {\displaystyle 1/n} of the total cake value. Pieces may still be disconnected. How many queries are required?

Lower bound: not known (theoretically it may be polynomially solvable).
Upper bound: {\displaystyle (n!)^{2}n^{2}}.^[2]

3. Next, assume there is free disposal, the allocation must still be proportional, but the pieces must be connected. How many queries are required?

For {\displaystyle n=3}, there is an algorithm with 54 queries.^[3]
For {\displaystyle n\geq 4}, no finite algorithm is currently known.

4. Next, assume there is free disposal, the pieces must be connected, but the allocation may be only approximately-proportional (i.e., some agents may get less than {\displaystyle 1/n} of the total cake value). What value can be guaranteed to each agent using a finite envy-free protocol?

For {\displaystyle n=3}, there is an algorithm that attains 1/3, which is optimal.
For {\displaystyle n=4} (the smallest open case), there is an algorithm that attains 1/7.^[3]
For any {\displaystyle n}, there is an algorithm that attains {\displaystyle 1/(3n)}.^[2]

5. Finally, assume the entire cake must be allocated, and pieces may be disconnected, but the number of cuts should be as small as possible. How many cuts do we need in order to find an envy-free allocation in a finite number of queries?

For {\displaystyle n\geq 3}, a finite algorithm does not exist for {\displaystyle n-1} cuts.^[4]
For {\displaystyle n=3}, Selfridge–Conway procedure solves the problem in finite time with 5 cuts.
For {\displaystyle n\geq 4}, the Aziz-Mackenzie procedure solves the problem in finite time, but with many cuts.
Smallest open case: three agents and 3 or 4 cuts. Can we find an envy-free allocation in finite time?

Number of cuts for cake-cutting with different entitlements[edit]

When all agents have equal entitlements, a proportional cake-cutting can be implemented using {\displaystyle n-1} cuts, which is optimal.

How many cuts are required for implementing a proportional cake-cutting among {\displaystyle n} agents with different entitlements?

Lower bound: {\displaystyle 2n-2};^[5]
Upper bound: {\displaystyle 3n-4}.^[6]
Smallest open case: {\displaystyle n=3} agents with all different entitlements: {\displaystyle 1/7}, {\displaystyle 2/7} and {\displaystyle 4/7}.^[5]

How many cuts are required for implementing an envy-free cake-cutting among {\displaystyle n} agents with different entitlements?

Lower bound: {\displaystyle 2n-2}, since envy-free implies proportional.
Upper bound: not known.

Fair division of a partly-burnt cake[edit]

A partly-burnt cake is a metaphor to a cake in which agents may have both positive and negative valuations.^[7]

A proportional division of such a cake always exists.What is the runtime complexity of calculating a connected-proportional allocation of partly-burnt cake?

Known cases:

When all valuations are positive, or all valuations are negative, the Even-Paz protocol finds a connected proportional division using {\displaystyle O(n\log n)} queries, and this is optimal.
When valuations may be mixed, a moving-knife protocol can be used to find a connected proportional division using {\displaystyle O(n^{2})} queries.^[8]^:Thm.5 Can this be improved to {\displaystyle O(n\log n)} ?

An envy-free division of a partly-burnt cake is guaranteed to exist if-and-only-if the number of agents is the power of a prime integer.^[9] However, it cannot be found by a finite protocol – it can only be approximated. Given a small positive number D, an allocation is called D-envy-free if, for each agent, the allocation will become envy-free if we move the cuts by at most D (length units).What is the runtime complexity (as a function of D) of calculating a connected D-envy-free allocation of a partly-burnt cake?^[7]

Truthful cake-cutting[edit]

Truthful cake-cutting is the design of truthful mechanisms for fair cake-cutting. The currently known algorithms and impossibility results are shown here. The main cases in which it is unknown whether a deterministic truthful fair mechanism exists are:^[10]

There are 3 or more agents with piecewise-uniform valuations, without free disposal.
There are 2 or more agents with piecewise-constant valuations, with or without free disposal (and without additional requirements such as connectivity or non-wastefulness).

Open problems in fair allocation of indivisible items[edit]

Approximate maximin-share fairness[edit]

The 1-of-{\displaystyle n} maximin share (MMS) of an agent is the largest utility the agent can secure by partitioning the items into {\displaystyle n} bundles and receiving the worst bundle. For two agents, divide and choose gives each agent at least his/her 1-of-2 MMS. For {\displaystyle n>2} agents, it is almost always, but not always, possible to give each agent his/her 1-of-{\displaystyle n} MMS. This raises several kinds of questions.

1. Computational complexity[edit]

What is the runtime complexity of deciding whether a given instance admits a 1-of-{\displaystyle n} MMS allocation?^[11]^[12]

Upper bound: {\displaystyle {NP}^{NP}} (which is {\displaystyle \Sigma _{2}^{P}} – level 2 in the polynomial hierarchy)
Lower bound: none (so it may be level 2 or 1 or even 0 of the hierarchy).

NOTE: the following related problems are known to be computationally hard:

Calculating the 1-of-{\displaystyle n} MMS of a given agent is NP-hard even if all agents have additive preferences (reduction from partition problem).
Deciding whether a given allocation is 1-of-{\displaystyle n} MMS is co-NP complete for agents with additive preferences.

2. Cardinal approximation[edit]

What is the largest fraction r such that there always exists an allocation giving each agent a utility of at least r times his 1-of-{\displaystyle n} maximin share?

Known cases:

For two agents: {\displaystyle r=1} by divide-and-choose.
For three agents, even with additive valuations: {\displaystyle r<1}. By a carefully-crafted example.^[13]
For any number of agents with additive valuations: {\displaystyle r\geq 3/4}.^[14]
For any number of agents with additive negative valuations (i.e., for chores): {\displaystyle r\geq 9/11}.^[15]

3. Ordinal approximation[edit]

What is the smallest integer {\displaystyle N} (as a function of {\displaystyle n}) such that there always exists an allocation among {\displaystyle n} agents giving each agent at least his 1-of-{\displaystyle N} MMS?

Known cases:

For two agents: {\displaystyle N=2}. By divide-and-choose.
For any number of agents with binary valuations: {\displaystyle N=n}. By round-robin. It gives EF1, which implies 1-of-{\displaystyle n}-MMS.
For {\displaystyle n>2} agents: {\displaystyle N>n}. By a carefully-crafted example.^[13]
For any number of agents with additive valuations: {\displaystyle N\leq 2n-1}, by round-robin. It gives EF1, which implies 1-of-{\displaystyle (2n-1)}-MMS.
For any number of agents with additive valuations: {\displaystyle N\leq 2n-2}, using envy-free matching.^[16]

So the answer can be anything between {\displaystyle n+1} and {\displaystyle 2n-2}, inclusive. Smallest open case:For {\displaystyle n=4} agents with additive valuations, does there always exist a 1-of-5 maximin-share allocation?

Note: there always exists an Approximate Competitive Equilibrium from Equal Incomes that guarantees the 1-of-({\displaystyle n+1}) maximin-share.^[17] However, this allocation may have excess supply, and – more importantly – excess demand: the sum of the bundles allocated to all agents might be slightly larger than the set of all items. Such an error is reasonable when allocating course seats among students, since a small excess supply can be corrected by adding a small number of seats. But the classic fair division problem assumes that items may not be added.

Envy-free up to one item[edit]

An allocation is called EF1 (envy-free up to one item) if, for any two agents {\displaystyle i} and {\displaystyle j}, and for any subset of size at most one contained in the bundle of {\displaystyle j}, if we remove that subset from {\displaystyle j}’s bundle then {\displaystyle i} does not envy. An EF1 allocation always exists and can be found by the envy cycles algorithm. Combining it with other properties raises some open questions.

Pareto-optimal EF1 allocation (goods and bads)[edit]

When all items are good and all valuations are additive, a PO+EF1 always exists: the allocation maximizing the product of utilities is PO+EF1.^[18] Finding this maximizing allocation is NP-hard,^[19] but in theory, it may be possible to find other PO+EF1 allocations (not maximizing the product).

What is the run-time complexity of finding a PO+EF1 allocation of goods?

A PO+EF1 allocation of bads (chores) is not known to exist, even when all valuations are additive.

Does a PO+EF1 allocation of bads always exist?

What is the run-time complexity of finding such allocation, if it exists?

Contiguous EF1 allocation[edit]

Often the goods are ordered on a line, for example, houses in a street. Each agent wants to get a contiguous block.^[20]For three or more agents with additive valuations, does an EF1 allocation always exist?

Known cases:

For two agents with additive valuations, the answer is yes: we can round a connected envy-free cake-cutting (e.g, found by divide and choose).
For {\displaystyle n} agents with additive valuations, we can find an “EF minus 2” allocation by rounding a connected envy-free cake-cutting, and there also exists an EF2 allocation (proof using a variant of Sperner’s lemma).^[21]
For {\displaystyle n} agents with additive binary valuations (every item value is either 0 or 1), an “EF minus 2” allocation is also EF1, so the answer is yes.

Even when a contiguous EF1 allocation exists, the runtime complexity of finding it is unclear:For three or more agents with binary additive valuations, what is the complexity of finding a contiguous EF1 allocation?

A connected envy-free cake-cutting might take infinitely many queries to find. An EF1 allocation can always be found in finite time by checking all possible allocations, but this algorithm requires exponential run-time.

Existence of EFx allocation[edit]

An allocation is called EFx (“envy-free up to any good”) if, for any two agents {\displaystyle i} and {\displaystyle j}, and for any good in the bundle of {\displaystyle j}, if we remove that good from {\displaystyle j}’s bundle then {\displaystyle i} does not envy.^[22]For three agents with additive valuations, does there always exist an EFx allocation?For {\displaystyle n} agents with general monotone valuations, can we prove that there does not exist an EFx allocation?

Known cases:

If at least {\displaystyle n-1} valuations are identical: yes.`
Hence, for two agents: yes. This is true even for general monotone valuations.^[23]

Existence of Pareto-efficient PROPx allocation of bads[edit]

An allocation of bads is called PROPx (aka FSx)^[24]^:Sec.7 if, for any agent {\displaystyle i}, and for any bad owned by {\displaystyle i}, if we remove that bad from {\displaystyle i}’s bundle, then {\displaystyle i}’s disutility is less than {\displaystyle 1/n} the total disutility.

Does there always exist an allocation of bads that is both PROPx and Pareto-efficient?

Related known cases:

A PROPx allocation of goods (even without Pareto-efficiency) may not exist.
A PROPx allocation of bads (without Pareto-efficiency) always exists.
A PROP1 and Pareto-efficient allocation of either goods or bads always exists.

Competitive equilibrium for almost all incomes[edit]

Competitive equilibrium (CE) is a very strong fairness notion – it implies Pareto-optimality and envy-freeness. When the incomes are equal, CE might not exist even when there are two agents and one good. But, in all other income-space, CE exists when there are two agents and one good. In other words, there is a competitive equilibrium for almost all income-vectors.For two agents with additive valuations over any number of goods, does there exist a competitive equilibrium for almost incomes?^[25]

Known cases:

With three or fewer goods: always yes.
With four goods: yes for 2 agents with general valuations, no for 3 agents with general valuations, no for 4 agents, even with additive valuations.^[26]
With five or more goods: no for two agents with general valuations.

Open conjectures:

When there are two agents with additive valuations, CE for almost all incomes exists for any number of goods.
When there are three agents with additive valuations, CE for almost all incomes might not exist.

Fair division of partly-divisible items[edit]

Runtime complexity of fair allocation with bounded sharing[edit]

Given {\displaystyle n\geq 2} agents, {\displaystyle m} items and an integer {\displaystyle k}, suppose at most {\displaystyle k} items can be shared among two or more agents. What is the runtime complexity of deciding whether a proportional / envy-free allocation exists?

Known cases:

With {\displaystyle k=0} and identical valuations, for any {\displaystyle n\geq 2}, the problem is equivalent to the partition problem, and therefore it is NP-complete.
With {\displaystyle k\geq n-1}, the answer is always “yes”, and an allocation can be found in polynomial time.^[27]
With {\displaystyle n=3} and {\displaystyle k=1} and identical valuations, an allocation can be found in polynomial time iff it exists.^[28]

Smallest open cases:

{\displaystyle n=3} and {\displaystyle k=1} and different valuations.
{\displaystyle n=4} and {\displaystyle k\in \{1,2\}} and identical valuations.

References[edit]

^ Procaccia, Ariel (2009). “Thou Shalt Covet Thy Neighbor’s Cake”. IJCAI’09 Proceedings of the 21st International Joint Conference on Artificial Intelligence: 239–244.
^ Jump up to:^a ^b ^c Aziz, Haris; MacKenzie, Simon (2016). “A discrete and bounded envy-free cake cutting protocol for any number of agents”. FOCS 2016. arXiv:1604.03655. Bibcode:2016arXiv160403655A.
^ Jump up to:^a ^b Segal-Halevi, Erel; Hassidim, Avinatan; Aumann, Yonatan (2016-11-19). “Waste Makes Haste”. ACM Transactions on Algorithms. 13 (1): 1–32. arXiv:1511.02599. doi:10.1145/2988232. ISSN 1549-6325.
^ Stromquist, Walter (2008). “Envy-free cake divisions cannot be found by finite protocols” (PDF). Electronic Journal of Combinatorics.
^ Jump up to:^a ^b Segal-Halevi, Erel (2018-03-14). “Cake-Cutting with Different Entitlements: How Many Cuts are Needed?”. Journal of Mathematical Analysis and Applications. 480: 123382. arXiv:1803.05470. doi:10.1016/j.jmaa.2019.123382.
^ Crew, Logan; Narayanan, Bhargav; Spirkl, Sophie (2019-09-16). “Disproportionate division”. arXiv:1909.07141[math.CO].
^ Jump up to:^a ^b Segal-Halevi, Erel (2018). “Fairly Dividing a Cake After Some Parts Were Burnt in the Oven”. Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS ’18. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 1276–1284. arXiv:1704.00726. Bibcode:2017arXiv170400726S.
^ Aziz, Haris; Caragiannis, Ioannis; Igarashi, Ayumi; Walsh, Toby (2018-07-27). “Fair allocation of combinations of indivisible goods and chores”. arXiv:1807.10684 [cs.GT].
^ Avvakumov, Sergey; Karasev, Roman (2019-07-25). “Envy-free division using mapping degree”. arXiv:1907.11183[math.AT].
^ Bei, Xiaohui; Huzhang, Guangda; Suksompong, Warut (2018-04-18). “Truthful Fair Division without Free Disposal”. arXiv:1804.06923 [cs.GT].
^ Bouveret, Sylvain; Lemaître, Michel (2016-03-01). “Characterizing conflicts in fair division of indivisible goods using a scale of criteria”. Autonomous Agents and Multi-Agent Systems. 30 (2): 259–290. doi:10.1007/s10458-015-9287-3. ISSN 1573-7454.
^ Lang, Jérôme; Rothe, Jörg (2016), Rothe, Jörg (ed.), “Fair Division of Indivisible Goods”, Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, Springer Texts in Business and Economics, Springer Berlin Heidelberg, pp. 493–550, doi:10.1007/978-3-662-47904-9_8, ISBN 9783662479049
^ Jump up to:^a ^b Kurokawa, David; Procaccia, Ariel D.; Wang, Junxing (2018-02-01). “Fair Enough: Guaranteeing Approximate Maximin Shares”. J. ACM. 65 (2): 8:1–8:27. doi:10.1145/3140756. ISSN 0004-5411.
^ Ghodsi, Mohammad; Hajiaghayi, Mohammadtaghi; Seddighin, Masoud; Seddighin, Saeed; Yami, Hadi (2018). “Fair Allocation of Indivisible Goods: Improvements and Generalizations”. Proceedings of the 2018 ACM Conference on Economics and Computation. EC ’18. New York, NY, USA: ACM: 539–556. doi:10.1145/3219166.3219238. ISBN 9781450358293.
^ Huang, Xin; Lu, Pinyan (2019-07-10). “An algorithmic framework for approximating maximin share allocation of chores”. arXiv:1907.04505 [cs.GT].
^ Aigner-Horev, Elad; Segal-Halevi, Erel (2019-01-28). “Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division”. arXiv:1901.09527 [cs.DS].
^ Budish, Eric (2011). “The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes”. Journal of Political Economy. 119 (6): 1061–1103. doi:10.1086/664613.
^ Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2019-09-24). “The Unreasonable Fairness of Maximum Nash Welfare” (PDF). ACM Transactions on Economics and Computation. 7 (3): 1–32. doi:10.1145/3355902. ISSN 2167-8375.
^ Darmann, Andreas; Schauer, Joachim (2015-12-01). “Maximizing Nash product social welfare in allocating indivisible goods”. European Journal of Operational Research. 247 (2): 548–559. doi:10.1016/j.ejor.2015.05.071. ISSN 0377-2217.
^ Suksompong, Warut (2019-05-15). “Fairly allocating contiguous blocks of indivisible items”. Discrete Applied Mathematics. 260: 227–236. arXiv:1707.00345. doi:10.1016/j.dam.2019.01.036. ISSN 0166-218X.
^ Bilò, Vittorio; Caragiannis, Ioannis; Flammini, Michele; Igarashi, Ayumi; Monaco, Gianpiero; Peters, Dominik; Vinci, Cosimo; Zwicker, William S. (2018-08-28). “Almost Envy-Free Allocations with Connected Bundles”. arXiv:1808.09406[cs.GT].
^ Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2019-09-24). “The Unreasonable Fairness of Maximum Nash Welfare” (PDF). ACM Transactions on Economics and Computation. 7 (3): 1–32. doi:10.1145/3355902. ISSN 2167-8375.
^ Plaut, Benjamin; Roughgarden, Tim (2018). “Almost Envy-freeness with General Valuations”. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’18. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics: 2584–2603. arXiv:1707.04769. Bibcode:2017arXiv170704769P. doi:10.1137/1.9781611975031.165. ISBN 9781611975031.
^ Moulin, Hervé (2019). “Fair Division in the Internet Age”. Annual Review of Economics. 11 (1): 407–441. doi:10.1146/annurev-economics-080218-025559.
^ Babaioff, Moshe; Nisan, Noam; Talgam-Cohen, Inbal (2017-03-23). “Competitive Equilibrium with Indivisible Goods and Generic Budgets”. arXiv:1703.08150 [cs.GT].
^ Segal-Halevi, Erel (2017-05-11). “Competitive Equilibrium For almost All Incomes”. arXiv:1705.04212 [cs.GT].
^ Sandomirskiy, Fedor; Segal-Halevi, Erel (2019-08-05). “Fair Division with Minimal Sharing”. arXiv:1908.01669 [cs.GT].
^ “np hardness – A partition problem in which some numbers may be cut”. Theoretical Computer Science Stack Exchange. Retrieved 2019-10-21.

hide v t e Unsolved problems by discipline
Astronomy Biology Chemistry Computer science Economics Fair division Geoscience Information theory Linguistics Mathematics Medicine Neuroscience Philosophy Physics Statistics

Categories:

This page was last edited on 8 February 2020, at 17:03 (UTC).
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.

(2 major variants of the problem have been studied…)

Connected pieces,

e.g. if the cake is a 1-dimensional interval then each partner must receive a single sub-interval. If there are {\displaystyle n} partners, only {\displaystyle n-1} cuts are needed

general pieces

e.g. if the cake is a 1-dimensional interval then each partner can receive a union of disjoint sub-intervals.

(at least they’re not cuttin’ up ‘babies’!)

(o wait…)

(they are?)

(circum what?)

“ASTRONOMY DOMINE!”

“TO INFINITY…AND BEYOND!”

*👨‍🔬🕵️‍♀️🙇‍♀️*SKETCHES*🙇‍♂️👩‍🔬🕵️‍♂️*

📚📖|/\-*WIKI-LINK*-/\|📖📚

👈👈👈 ☜ *“FAIR DIVISION”*

*“UNSOLVED MYSTERIES”* ☞ 👉👉👉

💕💝💖💓🖤💙🖤💙🖤💙🖤❤️💚💛🧡❣️💞💔💘❣️🧡💛💚❤️🖤💜🖤💙🖤💙🖤💗💖💝💘

*🌈✨ *TABLE OF CONTENTS* ✨🌷*

🔥🔥🔥🔥🔥🔥*we won the war* 🔥🔥🔥🔥🔥🔥

"fair division"unsolved mysteries

List of unsolved problems in fair division

Contents

Open problems in fair cake-cutting

Query complexity of envy-free cake-cutting[edit]

Number of cuts for cake-cutting with different entitlements[edit]

Fair division of a partly-burnt cake[edit]

Truthful cake-cutting[edit]

Open problems in fair allocation of indivisible items[edit]

Approximate maximin-share fairness[edit]

1. Computational complexity[edit]

2. Cardinal approximation[edit]

3. Ordinal approximation[edit]

Envy-free up to one item[edit]

Pareto-optimal EF1 allocation (goods and bads)[edit]

Contiguous EF1 allocation[edit]

Existence of EFx allocation[edit]

Existence of Pareto-efficient PROPx allocation of bads[edit]

Competitive equilibrium for almost all incomes[edit]

Fair division of partly-divisible items[edit]

Runtime complexity of fair allocation with bounded sharing[edit]

References[edit]

Navigation menu

Search

Interaction

Tools

Print/export

Languages