A land has to be divided among n agents, such that each agent gets a piece with a certain geometric shape. This problem can be approached in several ways, depending on the shape of the land:
Colorado (Rectangular land) edit
Also: Wyoming
Partially-proportional division edit
How much value should be in the land, so that each of the n agents can get a square with a value of at least 1?
| cake | pieces | lower bound | upper bound - subjective values | upper bound - identical values |
|---|---|---|---|---|
| Square | squares | 2n example: (n=5 n=2 animated)[1] |
6n-8 (obsolete)  |
- |
| 2-fat rectangle with 4 walls |
squares | 2n | 6n-8 (obsolete)  4n-4 (NEW, not verified)  |
2n (NEW, not verified)  |
| 1-by-L rectangle with 4 walls |
R-fat rectangles | 2n-2+⌈L/R⌉ | 6n-10+⌈max(L,2)/R⌉ (obsolete) 4n-6+⌈max(L,2)/R⌉ (generalization of above) |
2n-2+⌈L/R⌉ (generalization of above) |
| Rectangle with 3 walls (long wall open) |
squares | 2n-1 example: (n=5) |
6n-9 (obsolete) 4n-5 (NEW)  |
2n-1 (see 4 walls) |
| Rectangle with 3 walls (long wall open) |
squares; n=3 agents |
5 | 5 (NEW)  |
5 |
| Quarter-plane (2 walls) |
squares | 2n-1 example: (n=5) |
4n-7 for n>=3  |
2n-1 (see 4 walls) |
| Half-plane (1 wall) |
squares | (3n-1)/2 example: (n=4, n=7) NEW: (7n-3)/4 example: (n=5) |
4n-14 for n>=6  |
2n-2 (based on 2 walls) |
| Plane (no walls) |
squares | (5n-1)/4 examples: (n=5; n=10) |
4n-28 for n>=12  |
2n-4 (based on 1 wall) (NEW) |
More details are in a Google spreadsheet.
GAPS:
- 4, 3 and 2 walls - different valuations;
- 1 and 0 walls - different and identical valuations;
- Is a proportional division possible in a cyclic plane, such as a Cylinder? A Torus? A Sphere (Earth)?
Envy-free division edit
For n=2 agents, a slight variation on the recursive-halving rules allows each agent to get a piece that is at least as valuable as the other agent's piece, with the same proportionality guarantee.
Algorithms for envy-free division for n agents, such as [2] and [3], heavily rely on 1-dimensionality.
OPEN: envy-free division for 3 or more agents, which keeps the partial-proportionality guarantee.
Uniform Preference Externalities edit
If an agent can divide its own utility function to n squares with proportion p, how much can we guarantee to that agent when there are other n-1 agents with different utility functions? This kind of fairness is called UPE - Uniform Preference Externalities[4] or MMS - Maxi-Min-Share [5][6].
Currently I have negative examples for small number of agents:
- Square, 2 agents: the red and the blue can both cut 2 squares with subjective value 1/2[7], but together, one of them will get at most 1/4. This is the smallest possible proportion.
- Quarter plane, 2 agents: the red and the blue can both cut 2 squares with subjective value 1/2[8], but together, one of them will get at most 1/3. This is the smallest possible proportion.
- Quarter plane, 3 agents: All 3 agents can cut 3 squares with subjective value 1/3, but together, one of them will get at most 1/4. This is not tight since the smallest possible proportion is 1/5.
- This example can be generalized to n agents, each of whom can cut n squares with subjective value 1/n, but together one of them will get at most 1/(n+1). This is not tight since the smallest possible proportion is 1/(2n-1).
OPEN: tighten the bound.
Antarctica (Polygonal land) edit
Also: Utah, New Mexico, Dubai
The recursive halving algorithm can be generalized to other shapes, as long as they can be divided to smaller copies of themselves, like Rep-tiles or Irrep-tiles. The proportionality factor depends on the order of the rep-tile. The rep-tile with the smallest order is a right-angled isosceles triangle (RAIT), with an order of 2:
| cake | pieces | lower bound | upper bound |
|---|---|---|---|
| RAIT | Generalized RAIT (quadrilateral with a square at least half its area) |
n | 2n-2
|
The next-smallest is the right-angled trapezoid, with an order of 3.
OPEN: Closing the gap for RAITs.
Japan (General land) edit
Also: Chile, Philippines
In general, the absolute proportion for square pieces can be very small (e.g. a circular land when all value is on the perimeter). So for general lands, we consider a relative proportion - the proportion a person can get, relative to the largest proportion of a square.
This involves several sub-questions.
Selection division edit
How many disjoint shapes should each agent draw, such that each agent can get a single shape?
An upper bound for the above question is achieved by the following greedy algorithm:
Repeat n times:
- Select the shape that intersects the least number of disjoint shapes.
- Give that shape to its owner, remove the shapes intersected by it and the other shapes of the same owner.
This is also a constant-factor approximation algorithm for the Maximum disjoint set problem.[9]
An upper bound on its approximation ratio is the max min DIN where:
- DIN(x) = size of largest set of disjoint shapes intersected by shape x.
- min DIN(C) = minimum (over all shapes x) of DIN(x) in a collection C.
- max min DIN = maximum (over all collections C) of min DIN(C).
If M = max min DIN, then an upper bound for selection division is M(n-1)+1.
| shape | size | Selection division lower bound | max min DIN lower bound | max min DIN upper bound | upper bound |
|---|---|---|---|---|---|
| intervals | arbitrary | n | 1 | 1 (rightmost-left intersects at most 1 disjoint) See Interval scheduling. |
n |
| axis-parallel squares | unit | n+O(√n)  |
2 | 2 (topmost intersects at most 2 disjoint) | 2n-1 |
| disks | unit | n+O(√n) | 3 | 3 (topmost intersects at most 3 disjoint) | 3n-2 |
| axis-parallel squares | arbitrary | 2n-1 |
3 | 4 (smallest intersects at most 4 disjoint) | 4n-3 |
| disks | arbitrary | 2n-1 | 3 | 5 (smallest intersects at most 5 disjoint) | 5n-4 |
OPEN (Geometric question): Is there an arrangement of axis-parallel squares in which every square intersects at least 4 disjoint squares?
OPEN: Is it possible to prove an upper bound on the greedy selection-division algorithm, that is smaller than the one guaranteed by max min DIN (4n-3 for squares)?
Price of fairness edit
Utilitarian price of partial-proportionality edit
The utilitarian price of partial-proportionality in 2 dimensions is Θ(√n). The proof uses a redivision protocol which can preserve connectivity, convexity, rectangularity and fat-rectangularity. Therefore the result applies to scenarios in which the pieces in both the optimal and the new division must be connected, convex, rectangular or fat-rectangular, respectively. The results are the same order of magnitude as the 1-dimensional results of [10] and [11].
OPEN: The utilitarian price of full proportionality in 2 dimensions.
Efficient division edit
Approximate utilitarian-optimal division edit
The algorithm of [12] was presented for a 1-dimensional cake but is actually very general. It works for the following model:
- There is a set C of discrete items (“the cake”).
- There are n agents with additive valuations over the items of C, v_1,...,v_n.
- There is a collection Q of subsets of C (“the squares”).
- The goal is to give each agent i a square s_i ∈ Q, such that the sum of v_i(s_i) is maximized.
Notes edit
- ^ Note on lower-bound examples:
- The proportion you can give to (squares+1) agents is at most (1/points) (so the value required for (squares+1) agents is at least (1/points)).
- The proportion you can give to squares agents is at least 1/(points-1) (so the value required for squares agents is at most 1/(points-1)).
- ^ Su, F. E. (1999). "Rental Harmony: Sperner's Lemma in Fair Division". The American Mathematical Monthly. 106 (10): 930. doi:10.2307/2589747. JSTOR 2589747.
- ^ http://arxiv.org/abs/1307.2225
- ^ Moulin, H. (1990). "Uniform externalities". Journal of Public Economics. 43 (3): 305. doi:10.1016/0047-2727(90)90003-z.
- ^ Budish, E. (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy. 119 (6): 1061. doi:10.1086/664613.
- ^ http://www.cs.cmu.edu/~arielpro/papers/mms.pdf
- ^ Each pool has a value of 1/4
- ^ The red agent has 3 pools of 1/3, but for the blue agent I had to use 6 pools of 1/6
- ^ Marathe, M. V.; Breu, H.; Hunt, H. B.; Ravi, S. S.; Rosenkrantz, D. J. (1995). "Simple heuristics for unit disk graphs". Networks. 25 (2): 59. doi:10.1002/net.3230250205.
- ^ Aumann, Y.; Dombb, Y. (2010). "The Efficiency of Fair Division with Connected Pieces". Internet and Network Economics. Lecture Notes in Computer Science. Vol. 6484. p. 26. doi:10.1007/978-3-642-17572-5_3. ISBN 978-3-642-17571-8.
- ^ Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; Kyropoulou, M. (2011). "The Efficiency of Fair Division". Theory of Computing Systems. 50 (4): 589. doi:10.1007/s00224-011-9359-y.
- ^ http://dl.acm.org/citation.cfm?id=2484976