(Ezekiel 47:14) Fair-and-Square: Fair Division of Erel Segal-haLevi Land Advisors: Yonatan Aumann Avinatan Hassidim FAIR DIVISION APPLICATIONS Divide: Public lands to

homeless. Land-plots to settlers. Family estate to heirs. Museum space to presenters. THE GEOMETRIC APPROACH Partitioning: Divide a complex object (polygon) to pieces: triangles,

rectangles, squares, convex pieces, starshapes, spirals, pseudotriangles Polygon Decomposition", " Mark Keil, J., Handbook of .Computational Geometry (2000) THE ECONOMIC APPROACH Divide a divisible resource (cake) to n people with different values. Each person i has a value density: Value = integral of density: Fair = every person i receives piece

such that: No attention to geometric shape of RECTANGLE LAND, RECTANGLE PLOTS 2 PEOPLE: BLUE AND GREEN Each person marks a north-south line dividing land to two parts with subjective value

1/2. Land is cut between the two division For every person playing by thelines. rules: G B

THE COMBINED APPROACH Give each person a usable piece (square) with a value of at least 1/n Value Shape (fair) Geomet ry Econom

ics PEOPLE, RECTANGLE LAND, RECTANGLE PLOTS Shimon Even and Azaria Paz, 1984 For every person playing by the rules: No guarantee on length/width ratio

of rectangles. A person may receive 9 km by 2 PEOPLE, SQUARE LAND, SQUARE PLOTS Is it possible to give each person a value of at least 1/2? Not in this case! Here no more than

1/4 is possible. QUESTIONS Is it always possible to guarantee each person: value at least 1/4 in a square? value of at least 1/2 in a 2-fat

GEOMETRIC PROP FUNCTION Prop(C,S,n):= highest value that can be guaranteed when dividing cake C with pieces of family S to n people. Classic result: Prop(Rectangle, rectangles, n) = 1/n 1 PERSON, ANY LAND, ANY PLOTS

Definition: for a cake C and family S: CoverNum(C,S):= Minimum # of pieces of S, possibly overlapping, whose union is C. C Reuven Bar-Yehuda Example: CoverNum & Eyal Ben-Hanoch, 1996

(C,Squares)=3 Lemma: For every cake C and family S: Prop(C, S, 1) 1/CoverNum(C,S) 2 PEOPLE, SQUARE LAND, SQUARE PLOTS B G Define 4 subsquares. Each person chooses

favorite sub-square. Easy case: different choices: allocate choices and finish. 2 PEOPLE, SQUARE LAND, SQUARE PLOTS GB Define 4 subsquares. Each person chooses

favorite sub-square. Hard case: same choices: 2 PEOPLE, SQUARE LAND, SQUARE PLOTS Define 4 subsquares. Each person chooses favorite sub-square. Hard case: same choices: each person draws corner square

with value exactly 1/4 2 PEOPLE, SQUARE LAND, SQUARE PLOTS G Define 4 subsquares. Each person chooses favorite sub-square. Hard case: same choices: Smaller

square is allocated 2 PEOPLE, SQUARE LAND, SQUARE PLOTS B 3/4 G Define 4 subsquares. Each person chooses favorite sub-square. Hard case: same

choices: Smaller square is allocated. Other person gets favorite square of 3 2 PEOPLE, SQUARE LAND, SQUARE PLOTS B G Value 1/4

Define 4 subsquares. Each person chooses favorite sub-square. Hard case: same choices: Smaller square is allocated. Other person gets favorite square of 3 HALF-FAIR-AND-SQUARE Prop(Square, squares, 2) = 1/4 GENERALIZATIONS:

Other shapes of cakes. Other shapes of pieces. n people. 2 PEOPLE, UNBOUNDED LAND, SQUARE PIECES Unbounde d land: Cut between two parallel

marks; UN/BOUNDED CAKE 2 peo ple 1/4 ?

1/2 n peo ple ? ? ?

2 PEOPLE, PLANE Someone gets at most one out of 3 pools. Prop (1/4-plane, squares, 2) n PEOPLE, PLANE Someone

gets at most one of 2n-1 pools. Prop (1/4-plane, squares, n) 1/(2n-1) n PEOPLE, SQUARE LAND, SQUARE PIECES Someone gets at most one

of 2n pools. Prop (square, squares, n) 1/(2n) Dividing a square to n people Several algorithms details in paper Prop (square, squares, n) 1/(4n-4) UN/BOUNDED CAKE

2 p. 1/4 1/3 n p. 1/ 2n 1/ (4n-4)

1/ (2n-1) 1/ (4n-4) 1/2 1/ n 1/ (4n-4) n PEOPLE, PLANE We want to show an algorithm that proves:

Prop (1/4-plane, squares, n) 1/(2n-1) n PEOPLE, k-STAIRS k=4 We will show a recursive algorithm that proves: For every

staircase with k inner corners: Prop (k-stairs, squares, n) 1/(2n-2+k) n PEOPLE, k-STAIRS Total value = 2n-2+k Each person marks square with value 1 in every corner.

Keep smallest square in each corner. n PEOPLE, k-STAIRS Total value = 2n-2+k Easy case: Some square corner: Allocate 1 of them. Recurse with: n = -1 k = +1 V -1

n PEOPLE, k-STAIRS Total value = 2n-2+k Hard case: All squares > corner: Shadows appear! Lemma: There is a square with shadow other squares. Allocate 1 of them & Recurse.

n PEOPLE, k-STAIRS Total value = 2n-2+k Hard case: All squares > corner: Allocate square with contained shadow. Recurse with: n = -1 k = +1 - #(shadows) V -1 - #(shadows)

n PEOPLE, k-STAIRS Total value 2n-2+k Final step: n=1 Total value k CoverNum = k By CoverNum lemma, there is a square with value at least 1. Q.E.D. SHADOW LEMMA

For each corner , let: = corner coordinates; = length of smallest square Let: ) = square with smallest . = component of shadow of in corner Lemma: every is contained in the square . Hint:

n PEOPLE, k-STAIRS Prop (k-stairs, squares, n) = 1/(2n-2+k) CURRENT BOUNDS 2 p. n p. 1/4

1/ 2n 1/ (4n-4) 1/3 1/ (2n-1) 1/2 1/ n 1/ (2n-1) n PEOPLE, k-LEVELS k=7

Prop (k-levels, squares, n) = 1/(2n-2+k) CURRENT BOUNDS 2 p. n p. 1/4 1/3

1/ 2n 1/ (2n-1) 1/ (4n-4) 1/2 1/1.5n 1/ n 1/ (2n-1) OPEN QUESTIONS Divide: Rectilinear polytope, Cylinder / torus / sphere,

General fat object; To: 45-degree fat polytopes, Finite unions of squares, General fat objects. (Ezekiel 47:14) OPEN QUESTION Can we divide Earth

Fair-and-Square? Collaborations are welcome! [email protected] ACKNOWLEDGEMENTS Insightful discussions: Galya Segal-Halevi , Rav Shabtay Rappaport, Shmuel Nitzan. Helpful answers: Christian Blatter, Ilya Bogdanov, Henno Brandsma, Boris Bukh, Anthony Carapetis, Christopher Culter, David Eppstein, Yuval Filmus, Peter Franek, Nick Gill, John Gowers, Michael Greinecker, Dafin Guzman, Marcus Hum, Robert Israel, Barry Johnson, Joonas Ilmavirta, Tony K., V. Kurchatkin,

Raymond Manzoni, Ross Millikan, Mariusz Nowak, Boris Novikov, Joseph O'Rourke, Emanuele Paolini, Rahul, Raphael Reitzig, David Richerby, Andrs Salamon, Realz Slaw, B. Stoney, Steven Taschuk, Marc van Leeuwen, Collaborations are welcome! [email protected]