Jump to content

User:Erel Segal/Draft

From Wikipedia, the free encyclopedia

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) width=40px -
2-fat rectangle
with 4 walls
squares 2n 6n-8 (obsolete) width=40px
4n-4 (NEW, not verified) width=40px
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) width=40px
2n-1 (see 4 walls)
Rectangle
with 3 walls
(long wall open)
squares;
n=3 agents
5 5 (NEW) width=40px 5
Quarter-plane
(2 walls)
squares 2n-1
example:
(n=5)
4n-7 for n>=3 width=40px 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 width=40px 2n-2 (based on 2 walls)
Plane
(no walls)
squares (5n-1)/4
examples:
(n=5; n=10)
4n-28 for n>=12 width=40px 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-2width=40px

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.
OPEN: approximate egalitarian-optimal division.

Notes

[edit]
  1. ^ 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)).
  2. ^ 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.
  3. ^ http://arxiv.org/abs/1307.2225
  4. ^ Moulin, H. (1990). "Uniform externalities". Journal of Public Economics. 43 (3): 305. doi:10.1016/0047-2727(90)90003-z.
  5. ^ Budish, E. (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy. 119 (6): 1061. doi:10.1086/664613.
  6. ^ http://www.cs.cmu.edu/~arielpro/papers/mms.pdf
  7. ^ Each pool has a value of 1/4
  8. ^ The red agent has 3 pools of 1/3, but for the blue agent I had to use 6 pools of 1/6
  9. ^ 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.
  10. ^ 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.
  11. ^ 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.
  12. ^ http://dl.acm.org/citation.cfm?id=2484976