Cutting a Pie is Not a Piece of Cake презентация

Cutting a Pie is Not a Piece of Cake Julius B. Barbanel, Steven J. Brams, Walter Stromquist      Mathematicians enjoy cakes for their own sake and as a metaphor for

Слайд 1Cutting a Pie is Not a Piece of Cake
Walter Stromquist
Swarthmore College
mail@walterstromquist.com

Third

World Congress of the Game Theory Society
Evanston, IL
July 13, 2008




Слайд 2Cutting a Pie is Not a Piece of Cake Julius B. Barbanel,

Steven J. Brams, Walter Stromquist


     Mathematicians enjoy cakes for their own sake and as a metaphor for more general fair division problems.

A cake is cut by parallel planes into n pieces, one for each of n players whose preferences are defined by separate measures. It is known that there is always an envy-free division, and that such a division is always Pareto optimal. So for cakes, equity and efficiency are compatible.

   A pie is cut along radii into wedges. We show that envy-free divisions are not necessarily Pareto optimal --- in fact, for some measures, there may be no division that is both envy-free and Pareto optimal. So for pies, we may have to choose between equity and efficiency.




Слайд 3
This is joint work with

Julius B. Barbanel (Union College)












Steven J. Brams (New York University)

Слайд 4

1. Introduction

2. Cakes

3. Pies

4. Summary


Слайд 6Some definitions
Cakes are cut by parallel planes.

The cake is an

interval C = [ 0, m ].
Points in interval = possible cuts.
Subsets of interval = possible pieces.
We want to partition the interval into S1, S2, …, Sn, where
Si = i-th player’s piece.

Player’s preferences are defined by measures v1, v2, …, vn
vi (Sj ) = Player i’s valuation of piece Sj.

These are probability measures.

We always assume that they are non-atomic (single points always have value zero).


Слайд 7“Absolutely continuous”


Sometimes we assume that the measures are absolutely continuous with

respect to each other.

In effect, this assumption means that pieces with positive length also have positive value to every player.



Слайд 8

1. Introduction

2. Cakes

3. Pies

4. Summary


Слайд 9Two players: I cut, you choose


Слайд 10n players: Everybody gets 1/n







Referee slides knife from left to right
Anyone who

thinks the left piece has reached 1/n says “STOP” …and gets the left piece.
Proceed by induction. (Banach - Knaster ca. 1940)



Слайд 11Envy-free divisions

A division is envy-free if no player thinks any other

player’s piece is better than his own:

vi (Si) ≥ vi (Sj) for every i and j.

Can we always find an envy-free division?

Theorem (1980): For n players, there is always an envy-free division in which each player receives a single interval.

Proofs:
(WRS) The “division simplex”
(Francis Edward Su) Sperner’s Lemma

Слайд 12Two moving knives: the “squeeze”
A cuts the cake into thirds (by

his measure).






Suppose B and C both choose the center piece.

A moves both knives in such a way as to keep end pieces equal (according to A)

B or C says “STOP” when one of the ends becomes tied with the middle. (Barbanel and Brams, 2004)






Слайд 13Undominated allocations
A division {Si} = S1, S2, …, Sn is dominated

by a division
{Ti} = T1, T2, …, Tn if

vi(Ti) ≥ vi(Si) for every i
with strict inequality in at least one case.

That is: T makes some player better off, and doesn’t make any player worse off.

{Si} is undominated if it isn’t dominated by any {Ti} .

“undominated” = “Pareto optimal” = “efficient”



Слайд 14Envy-free implies undominated

Is there an envy-free allocation that is also undominated?


Theorem

(Gale, 1993): Every envy-free division of a cake into n intervals for n players is undominated (assuming absolute continuity).




So for cakes: EQUITY ⇒ EFFICIENCY.


Слайд 15Gale’s proof
Theorem (Gale, 1993): Every envy-free division of a cake into

n intervals for n players is undominated.

Proof: Let {Si} be an envy-free division.
Let {Ti} be some other division that we think might
dominate {Si}.

S2 S3 S1

T3 T1 T2

v1(T1) < v1(S3) ≤ v1(S1)

so {Ti} doesn’t dominate {Si} after all. //

Слайд 16Cakes without absolute continuity
First player’s preference: Uniform, EXCEPT on the leftmost

third of the cake. The first player likes only the left half of the leftmost third.



All other players’ preferences are uniform.



The only envy-free divisions involve cutting the pie in thirds.
None of these divisions is undominated.

Without absolute continuity: We may have to choose between envy-free and undominated.

Слайд 17Summary for cakes
With absolute continuity:

There is always an envy-free division.
Every envy-free

division is also undominated.
There is always a division that is both envy-free and undominated.

Without absolute continuity:

There is always an envy-free division.
For some measures, there is NO division that is both envy-free
and undominated. We may have to choose!

Unless n = 2, when there is always an envy-free, undominated division, whatever the measures.

Слайд 18

1. Introduction

2. Cakes

3. Pies

4. Summary


Слайд 19Pies
Pies are cut along radii. It takes n cuts to make

pieces for n players.





A cake is an interval.
A pie is an interval with its endpoints identified.



Слайд 21Pies
1. Are there envy-free divisions for pies?
YES

2. Does Gale’s proof work?


NO
Envy-free does NOT imply undominated

3. Are there pie divisions that are both envy-free and undominated? (“Gale’s question,” 1993)

YES for two players
NO if we don’t assume absolute continuity
NO for the analogous problem with unequal claims
(Brams, Jones, Klamler – next talk!)

Слайд 22Pies

For n ≥ 3, there are measures for which there does

NOT exist an envy-free, undominated allocation.

These measures may be chosen to be absolutely continuous.

So, Gale’s question is answered in the negative.

Слайд 24The example
Partition the pie into 18 tiny sectors.

Each player’s preference is

uniform, except…
Each player dislikes certain sectors (grayed out).
Each player perceives positive or negative bonuses (C)
or mini-bonuses (ε) in certain sectors.

The measures for three players:

Слайд 25Pies for two players


Of all envy-free allocations, pick the one most

preferred by Player 2.

That allocation is both envy-free and undominated.

Слайд 26Summary for pies

With or without absolute continuity:

There is always an envy-free

division.
For some measures, there is NO division that is both envy-free
and undominated. We may have to choose!





Unless n = 2, when there is always an envy-free, undominated division, whatever the measures.

Слайд 27

1. Introduction

2. Cakes

3. Pies

4. Summary


Слайд 28Summary: When must there be an envy-free, undominated allocation?


Слайд 29Cookies
This cookie cutter has blades at fixed 120-degree angles.









But the center

can go anywhere. Is there always an envy-free division of the cookie? Envy-free and undominated?

Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика