User:Erel Segal/Draft

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)

Also: Wyoming

Partially-proportional division

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)	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

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 and , heavily rely on 1-dimensionality.

OPEN: envy-free division for 3 or more agents, which keeps the partial-proportionality guarantee.

Uniform Preference Externalities

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 or MMS - Maxi-Min-Share .

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, 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, 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)

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)

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

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.

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

Utilitarian price of partial-proportionality

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 and .

OPEN: The utilitarian price of full proportionality in 2 dimensions.

Efficient division

Approximate utilitarian-optimal division

The algorithm of 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.