(Ezekiel 47:14) Fair-and-Square: Fair Division of Erel Segal-haLevi

(Ezekiel 47:14) Fair-and-Square: Fair Division of Erel Segal-haLevi

(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]

Recently Viewed Presentations

  • relate (verb) - Manville School District

    relate (verb) - Manville School District

    WEEK 8 Word Study WordsDo Now (answer in notebook):What do the root words ASTR and STELLmean?How many words can you think of that containSTELL ASTR. Root WordASTR/STELL- star. Word Study Words astronomy astrologer asteroid aster stellar constellation ...
  • University Disabled Students Experiences of Learning, Teaching and

    University Disabled Students Experiences of Learning, Teaching and

    Disability legislation may prove to be a Trojan horse and in a decade, the learning experiences of all students may be the subject of greater negotiation" (Healey 2003: 26). LTA experiences Far fewer adjustments for disabled students would be required...
  • Cultural Competency Across the Curriculum

    Cultural Competency Across the Curriculum

    Are there models to promote cultural competency across the curriculum? ... The number of people who identify as multi-racial is projected to triple from eight to 26 million by 2060 2. 1 Gollnick, D. M., & Chinn, P. C. (2002)....
  • References for teachers: http://www ... - Courthouse Green

    References for teachers: http://www ... - Courthouse Green

    Happening in Courthouse Green! This Friday we are inviting children to pay 50p to come into school in non-uniform. The money we raise will go to children in need. The BBC created the Children in Need charity in the 1980s...
  • Chapter 3

    Chapter 3

    Table 3.2 Levich: International Financial Markets ... Symbol Arial Default Design Microsoft Photo Editor 3.0 Photo Bitmap Image Microsoft Excel Worksheet Microsoft Equation 3.0 International Financial Markets Overview Overview Overview Overview Importance of Foreign Exchange Market Trading The ...
  • Distance learning and the visually impaired learner

    Distance learning and the visually impaired learner

    DISTANCE LEARNING AND THE VISUALLY IMPAIRED LEARNER Ms. Lerato Sonia Tladi Reasons for Ratings: Assign Blind Had to ask friends and family for assistance Struggled to get proper information. Blind and Partially Sighted Struggled to obtain the assignment form in...
  • J.R.S.O - LT Scotland

    J.R.S.O - LT Scotland

    Some people live to far away to walk to school, so if that is the case then you could ask to walk from the Harvie Avenue shops or the Baptist Church. Never park on double yellow lines or zigzags this...
  • Marketing Channels for Services

    Marketing Channels for Services

    MARKETING CHANNELS FOR SERVICES MARKETING CHANNELS FOR SERVICES (SPECIAL CHARACTERISTICS OF SERVICES) Intangibility Inseparability Difficulty of Standardization Customer Involvement Perishability MARKETING CHANNELS FOR SERVICES Tend to have SHORTER CHANNELS Channel design issues are not so important but target market issues...