11 marks] The Moving Knife algorithm is used, as described in GTa.12, to divide
ID: 3197849 • Letter: 1
Question
11 marks] The Moving Knife algorithm is used, as described in GTa.12, to divide a cake among n people. Person P is the ith person to call Stop"and hence receives the ith piece cut. No one tries to be greedy (as discussed in GTa.14), and no two players call "Stop at the same time Method GTa.12 (Moving Knife for Proportional Division into n pieces) 1. A knife is passed over the cake from left to right. The first player who assesses the portion to the left of the knife at-says "Stop." is awarded that portion, and drops out. If two players simultaneously say "Stop." one is assigned the piece at random. 2. Repeat Step 1 with the remaining players on the remaining piece of cake. n. There is now one player left, who receives the remaining piece. Dubins and Spanier (cited from Robertson and Webb 1998, 8 Concept GTa.14 (Playing by the Rules) With the Moving Knife algorithm, any player who tries to be greedy risks losing out to a player who is slightly less greedy. Certainly, individuals may have a different tolerance for this risk, and they may feel they have skill at being just greedy enough" relative to others. We assume that players put this aside and go for exactly 7 a) 3 marks If n 3, what is the most we can say for sure about how P2 assesses the size of i. the first piece cut ii. the second piece cut ii the third piece cut? (b) 8 marks) Consider the statement: S,: The player who receive the ith piece assesses her piece as being the ith smallest If n 4, determine with justification whether the statement Si must be true e ust be false, or e could be either true or false. Repeat for S2, S3, S Note that if Christine assesses the pieces as 0.23, 0.25, 0.25, 0.27, then she considers bothe pieces bfno size 0.25 as the second smallest. Go to Settings to aExplanation / Answer
(a) There are 3 people , so the resulting pieces do not have to be contiguous,namely if both players 2 and 3 lable the
middle piece as "bad " and 1 takes it.and if the cut- and-choose is different from 1"s original cut.
Therefore:'
The size of first piece cut is 1/2
The size of second piece cut is usually greater than first piece
and
The size of third piece is greater than first and second piece's.
(2)
S1 cuts the cake into three pieces (which she values equally)
S2 must be true:
If she thinks at least two pieces are >=1/3 (or) labels two them as "bad"
If S2 is true,then S4,S3,S2,S1 each choose a piece (in that order) and we are done.
S2 must be false:
If S2 false, then S3,S4 can also choose between passing and labelling
If S4 is true ,then players S2,S3, S4,S1 each choose a piece(in that order) and we are done.
S2 could be either true or false then S2 has to take (one of the piece(s) labelled as "bad" by S1,S3,S4
The rest reassembled S2 cut -and -choose pieces.
S3must be true:
If she thinks at least two pieces are >=1/3 (or) labels two them as "bad"
If S3 is true,then S4,S3,S2,S1 each choose a piece (in that order) and we are done.
S3 must be false:
If S3 false, then S4 can also choose between passing and labelling
If S4 is true ,then players S2,S3, S4,S1 each choose a piece(in that order) and we are done.
S3 could be either true or false then S3 has to take (one of the piece(s) labelled as "bad" by S1,S2,S4
The rest reassembled S3 cut -and -choose pieces.
S4must be true:
If she thinks at least two pieces are >=1/3 (or) labels two them as "bad"
If S4 is true,then S4,S3,S2,S1 each choose a piece (in that order) and we are done.
S4 must be false:
If S4 false, then the order is same
S4 could be either true or false then S4 has to take (one of the piece(s) labelled as "bad" by S1,S2,S3
The rest reassembled S4 cut -and -choose pieces.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.