154:
The number of cuts is bounded, though. Austin's procedure requires 2 cuts to divide a cake between 2 people with an exact value of 1/2; each of these pieces should be divided with 2 more cuts to generate the 4 pieces with exact value of 1/4. So in total, 6 cuts are needed for step A. A single cut
142:
Now the trimmings are divided. Assume w.l.o.g. that #3 took the trimmed piece. We use Austin's procedure again with the trimmings and partners #4 and #1, to create 4 pieces each of which equals exactly 1/4 for both of them. Since partners #1 and #2 have an irrevocable advantage over whoever partner
131:
Partner #3 trims one piece to create a two-way tie for the largest; the partners now choose pieces in reverse order (#4, #3, #2, #1). Either #4 or #3 must take the trimmed piece. This creates an envy-free division for the entire cake less the trimmings (This is similar to the
151:
The run-time of the procedure is, technically, infinite, since Austin's procedure involves two knives moving continuously, and this procedure cannot be discretized.
123:
88:
60:
133:
200:
Brams, Steven J.; Taylor, Alan D.; Zwicker, William S. (1997). "A Moving-Knife
Solution to the Four-Person Envy-Free Cake Division".
184:
251:
39:
125:
and partners #1 and #2. So we have 4 pieces that the first two partners believe to be of exactly identical value of 1/4.
143:
that took the trimmed piece, we can let #3 be the first to select a piece from the trimming, then #2, then #4 and #1.
17:
209:
32:
256:
214:
227:
180:
219:
102:
65:
45:
245:
231:
223:
158:
An advanced variant of the Brams–Taylor–Zwicker procedure uses only 11 cuts.
155:
is done in step B and 6 more cuts in step C, for a total of 13 cuts.
42:. That procedure allows two partners to divide an entire cake to
40:
Austin's procedure for two partners and general fractions
177:
Fair division: from cake-cutting to dispute resolution
105:
68:
48:
117:
82:
54:
202:Proceedings of the American Mathematical Society
8:
18:Brams–Taylor–Zwicker moving knives procedure
175:Brams, Steven J.; Taylor, Alan D. (1996).
213:
104:
72:
67:
47:
167:
62:pieces, each of which is worth exactly
93:The main procedure works as follows.
7:
134:Selfridge–Conway discrete procedure
38:The procedure uses a variation of
25:
179:. Cambridge University Press.
29:Brams–Taylor–Zwicker procedure
1:
224:10.1090/s0002-9939-97-03614-9
99:Use Austin's procedure with
273:
252:Fair division protocols
119:
84:
56:
33:envy-free cake-cutting
120:
85:
57:
103:
66:
46:
118:{\displaystyle k=4}
83:{\displaystyle 1/k}
115:
90:for both of them.
80:
52:
35:among 4 partners.
31:is a protocol for
55:{\displaystyle k}
16:(Redirected from
264:
236:
235:
217:
197:
191:
190:
172:
124:
122:
121:
116:
89:
87:
86:
81:
76:
61:
59:
58:
53:
21:
272:
271:
267:
266:
265:
263:
262:
261:
242:
241:
240:
239:
215:10.1.1.104.3390
199:
198:
194:
187:
174:
173:
169:
164:
149:
101:
100:
64:
63:
44:
43:
23:
22:
15:
12:
11:
5:
270:
268:
260:
259:
254:
244:
243:
238:
237:
208:(2): 547–554.
192:
185:
166:
165:
163:
160:
148:
145:
114:
111:
108:
79:
75:
71:
51:
24:
14:
13:
10:
9:
6:
4:
3:
2:
269:
258:
255:
253:
250:
249:
247:
233:
229:
225:
221:
216:
211:
207:
203:
196:
193:
188:
186:0-521-55644-9
182:
178:
171:
168:
161:
159:
156:
152:
146:
144:
141:
137:
135:
130:
126:
112:
109:
106:
98:
94:
91:
77:
73:
69:
49:
41:
36:
34:
30:
19:
257:Cake-cutting
205:
201:
195:
176:
170:
157:
153:
150:
139:
138:
128:
127:
96:
95:
92:
37:
28:
26:
246:Categories
162:References
147:Efficiency
210:CiteSeerX
232:17233874
230:
212:
183:
228:S2CID
181:ISBN
27:The
220:doi
206:125
136:).
248::
226:.
218:.
204:.
140:C.
129:B.
97:A.
234:.
222::
189:.
113:4
110:=
107:k
78:k
74:/
70:1
50:k
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.