AN ALGORITHMIC VERSION OF KUHN’S LONE–DIVIDER METHOD OF FAIR DIVISION

C. Bryan Dawson

Among the various types of methods for accomplishing a fair division are those commonly called “lone–divider” (we shall not consider other types of methods here). The first such method, for n = 3 participants, is credited to Hugo Steinhaus [4]. In 1967, Harold Kuhn [5] became the first to publish a lone–divider method for arbitrarily many participants. Although Kuhn’s method has become popular and is discussed in the recent texts [1] and [6], and is even mentioned in lower–level undergraduate texts such as [7], it is rarely if ever restated; this is likely due to the facts that (1) Kuhn’s statement of the method is at least partially existential, rather than algorithmic, and (2) Kuhn’s proof relies on the Frobenius–König theorem. It is the purpose of this note to introduce an algorithmic version of Kuhn’s procedure, along with proof of uniqueness of a set for which Kuhn proves existence only.

We begin by stating the method. Strategies of the various individuals involved will be discussed afterward, followed by proofs of claims made in the statement of the method. We make the common assumption that each player’s preferences are determined by a finitely additive, nonatomic measure. All other undefined terms are as in [1].

Lone–Divider Algorithm for n Participants.

Step 0. The n individuals are ordered in a random fashion into rank 1, rank 2, …, rank n. The lower the number, the higher the rank. Rank 1 is highest. The individual in rank n is the divider; the others are choosers. The identity of the divider is revealed, but the ranks of the choosers are not revealed until after Step 2. Step 1. The divider cuts the object into n pieces. Step 2. The choosers mark acceptable pieces; each chooser must mark at least one piece. This must be done in such a manner that no chooser is aware of another chooser’s marks when making their marks. Step 3.

\underline{Definition}. A set of choosers is called decidable if it contains no subset of k choosers who marked a total of k − 1 or fewer different acceptable pieces between them.

(i). If the set of all choosers is decidable, execute the “decidable allocation procedure.”

(ii). If the set of all choosers is not decidable, let p be the largest integer such that there exists a set of k choosers who marked a total of k − p different pieces acceptable among them. Let m be the smallest integer such that there exists a set of m choosers who marked a total of m−p different pieces acceptable among them (m is the smallest k above, with the stipulation that the largest possible p is used). There will be exactly one such set C of choosers. Call C the set of conflicting choosers. The set D consisting of the other choosers (choosers not in C) is called the set of decidable choosers, since this set is decidable.

Case 1. The set of decidable choosers is empty. Then execute the “maximum redivision procedure.” Case 2. The set of decidable choosers is nonempty. Then execute the “partial redivision procedure.”

End of method.

Decidable Allocation Procedure.

Below, “chooser” refers to a chooser in set D (the set of decidable choosers) when coming from the partial redivision procedure. Pieces assigned to a revision by the partial redivision procedure may not be chosen during this procedure. Step 1. If a chooser has marked exactly one piece acceptable, or if there is only one such remaining piece, that piece is assigned to that chooser. Step 1 is repeated. Step 2. If Step 1 has not resulted in a complete assignment of pieces to the choosers, then the highest–ranking chooser without an assigned piece chooses a piece from among those he/she marked acceptable, with the restriction that afterwards the set E of choosers still without an assigned piece remains decidable considering only the remaining pieces. Step 1 is repeated. Step 3. The remaining available piece (not assigned to a chooser or part of a redivision) is assigned to the divider. End of procedure.

Maximum Redivision Procedure.

Note that there are at least two pieces left which have not been marked acceptable. Call these pieces available. Step 1. The highest–ranking chooser who wishes to be the selector trades ranks with the lowest–ranking chooser. If no chooser wishes to be the selector, then the lowest–ranking chooser is the selector. Step 2. The selector chooses one of the available pieces to be given to the divider.

Step 3. All remaining pieces are reassembled, and the entire lone–divider method is re–executed beginning at Step 1, for the remaining individuals. Note that the selector, being in the lowest rank among the remaining individuals for the new division, will be the new divider. End of procedure.

Paritial Redivision Procedure.

Pieces which have not been marked desirable by a chooser in set C are called available. Pieces marked desirable by choosers in set C are called pieces of conflict. Step 1. The highest–ranking chooser in set C who wishes to be the selector trades ranks with the lowest–ranking chooser in set C. If no chooser in set C wishes to be the selector, then the lowest–ranking chooser in set C is the selector. Step 2. The selector selects p pieces from among the available pieces, with the restriction that afterwards the set D of decidable choosers must remain decidable without any of the p selected pieces or the pieces of conflict to choose from. Step 3. The selected pieces and the pieces of conflict are all reassembled together into an object to be divided among the choosers in set C. This is accomplished by re–executing the entire lone–divider method, beginning with Step 1, with ranks in the same order as in set C; hence, the selector, as the lowest–ranking chooser in set C, is the new divider for the new division. Step 4. The remaining available pieces (not assigned to a redivision in Step 3) are allocated to the choosers in set D and to the original divider by using the decidable allocation procedure. Note: Steps 3 and 4 of this procedure may be executed in this order, simultaneously, or in reverse order. End of procedure.

To see that each player has a strategy that guarantees a fair division, we first consider the divider. Note that the divider always receives one of the n pieces into which they divided the object, and that the piece they receive is not of their own choosing. Hence, they have incentive to divide the object into n equal pieces, and such a division guarantees their fair share.

Next, consider a chooser. If a chooser marks a piece acceptable when it is less than a fair share, they run the risk of receiving that piece in the decidable allocation procedure. Hence, they “should not” mark such a piece. Now suppose that a chooser does not mark a piece P acceptable when it is more than a fair share. Because ranks have not been revealed and the chooser might not have highest rank, it is possible that P could be given to the divider in the maximum redivision procedure, with the rest (total worth < (n − 1)/n) redivided among the n − 1 choosers. Since that division could be accomplished equally in the specified chooser’s eyes, that chooser could wind up with less than a fair share. Hence, choosers, “should” mark pieces worth more than a fair share. (One can easily construct examples whereby the highest–ranking chooser would have incentive not to mark a second–largest piece worth more than a fair share, if they are aware of their rank.) Marking or not marking pieces worth exactly a fair share turns out to be neutral, hence, the requirement that each chooser mark at least one piece. To see that a chooser can guarantee themselves a fair share by marking pieces according to the strategy above, not that either (1) the chooser receives a piece they marked or (2) if they are involved in a redivision, all pieces awarded and not part of the redivision are each worth no more than a fair share to that chooser.

One final note on strategy: in the redivision procedures, one would choose to be a selector only if there is a difference between the available pieces. Otherwise, it is to their advantage not to be the divider in the redivision.

Next, we turn our attention to the claims of Step 3 part (ii) of the main procedure. Since the number of choosers k is bounded by n and p is bounded by k −1, our choice of a largest p is justified. Note that since (i) is not executed, p ≥ 1. Similarly, m is bounded below by p + 1. Suppose C_{1} and C_{2} are two distinct sets of m choosers each of whom marked a total of m−p different pieces acceptable among them, where m, p are optimal values as required. If C_{1} ∩ C_{2} = ∅, then C_{1} ∪ C_{2} is a set of 2m choosers who marked no more than 2m − 2p different pieces acceptable among them; but 2p > p, and we violate our choice of p. Hence, C_{1} ∩ C_{2} ≠ ∅. Let k > 0 be the number of members of that set. Since k < m (the two sets are distinct), by our choice of m we see that these k choosers marked k−(p−s) different pieces acceptable among them, where s ≥ 1. Now, C_{2} \ C_{1} contains m − k choosers. If this set of m − k choosers marked fewer than m − k different pieces among them that were not marked by choosers in C_{1}, then C_{1} ∪ (C_{2} \ C_{1}) is a set of 2m − k choosers who marked fewer than m − p + m − k = (2m − k) − p pieces, violating our choice of p. Thus, the choosers in C_{1} \ C_{2} marked at least m − k different pieces that were not marked by choosers in C_{1} ∩ C_{2}. Thus, the m choosers in C_{2} marked at least k − (p − s) + m − k > m − p different pieces, which contradicts our choice of C_{2}. The uniqueness of C is therefore established. It was this set for which Kuhn proved only existence.

Verification of the validity of the three subprocedures involves only the use of the definition of decidable and direct application of Hall’s Theorem [2]. Construction of examples to show that Step 2 of the decidable allocation procedure, the restriction therein, and the restriction (and allowance) of Step 2 of the partial redivision procedure which are all necessary, are left to the reader as exercises. Note that as an alternative one could reassign ranks in Step 1 of each redivision procedure by a “shift” instead of a “trade.” It is also possible to combine the two redivision procedures; the current choice was made for clarity. Finally, note that one can interpret the result of the previous paragraph as giving uniqueness of an optimal Hall’s theorem application in this case.

We now address the claim that the method is an algorithm. Because there exists only one set C of conflicting choosers with the properties of Step 3 part (ii) of the main procedure, and the number of sets of choosers is finite, one may choose their favorite exhaustive search algorithm for that step to uniquely determine set C. Similarly, valid choices in Step 2 of the partial redivision procedure and the decidable allocation procedure may be determined by exhaustive search. Unfortunately, it is from these steps that the efficiency of the algorithm is determined. It is clear that the remainder of the method is algorithmic.

In order to make the method algorithmic rather than somewhat existential, choices were made that actually limit the number of possible outcomes, i.e., the set of possible outcomes from the algorithm presented here is a proper subset of the possible outcomes of Kuhn’s method. It is only with that understanding that the two methods are identical.

We close by discussing the philosophy of redivision. Kuhn’s method (and the algorithm of this note) make a redivision only if necessary, and with as few individuals as possible, in order to minimize the number of cuts necessary from this type of method. That is also true of the lone–divider method for n = 3 as presented in [3] and [7], but is not true of the presentation in [1] of Steinhaus’ method for n = 3, nor the method for n = 4 in [1] that follows it. In fact, [1] even gives a method of Custer for n = 4 which takes the opposite approach, redividing whenever possible and with as many individuals as possible. The lone–divider– type “matching algorithm” of Robertson and Webb [6] for arbitrary n, which also relies on Hall’s theorem, redivides whenever possible (but not always with as many individuals as possible), and thus utilizes more cuts than Kuhn’s method. Although the specific set of individuals involved in a redivision in Robertson and Webb’s method is not necessarily unique, the method can be “algorithmatized” by use of ranks in a similar manner as to what was done here.

\underline{References}

1. S. J. Brams and A. D. Taylor, Fair Division: From Cake–Cutting to Dispute Resolution, Cambridge University Press, Cambridge, 1996.

2. G. Chartrand and L. Lesniak, Graphs and Digraphs, 2nd edition, Wadsworth, Pacific Grove, California, 1986.

3. COMAP, For All Practical Purposes, 4th edition, W. H. Freeman, New York, 1997.

4. B. Knaster, “Sur le Problème du Partage Pragmatique de H. Steinhaus,” Annales de la Societé Polonaise de Mathematique, 19 (1946), 228–230.

5. H. W. Kuhn, “On Games of Fair Division,” in Essays in Mathematical Economics in Honor of Oskar Morgenstern, Martin Shubik, editor, Princeton University Press, Princeton, New Jersey, 1967, 29–37.

6. J. Robertson and W. Webb, Cake Cutting Algorithms: Be Fair If You Can, A. K. Peters, Natick, Massachusetts, 1998.

7. P. Tannenbaum and R. Arnold, Excursions in Modern Mathematics, 3rd edition, Prentice Hall, Upper Saddle River, New Jersey, 1998.

C. Bryan Dawson Department of Mathematics and Computer Science, UU1899 Union University 1050 Union University Dr. Jackson, TN 38305 email: bdawson@uu.edu