User:Erel Segal/Draft

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?

More information cake, pieces ...

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)

Close

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 ^[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

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.

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.^[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.

More information shape, size ...

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

Close

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

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 ^[10] and ^[11].

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

Approximate utilitarian-optimal division

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.