“Brams–Taylor–Zwicker procedure”的意思、由来-开放百科全书

The Brams–Taylor–Zwicker procedure is a protocol for envy-free cake-cutting among 4 partners.^[1]{{rp|126–128}}

The procedure uses a variation of Austin's procedure for two partners and general fractions. That procedure allows two partners to divide an entire cake to

pieces, each of which is worth exactly

for both of them.

A. Use Austin's procedure with

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.

B. 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 Selfridge–Conway discrete procedure).

C. 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 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.

Efficiency

The run-time of the procedure is, technically, infinite, since Austin's procedure involves two knives moving continuously, and this procedure cannot be discretized.

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 is done in step B and 6 more cuts in step C, for a total of 13 cuts.

An advanced variant of the Brams–Taylor–Zwicker procedure uses only 11 cuts.^[2]

References

1. ^{{Cite Brams Taylor 1996}}
2. ^{{cite journal | url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.3390 | title=A Moving-Knife Solution to the Four-Person Envy-Free Cake Division | journal=Proceedings of the American Mathematical Society | year=1997 | volume=125 | issue=2 | pages=547–554 | doi = 10.1090/s0002-9939-97-03614-9 }}