# Fairest way to choose gifts

Suppose that a parent brings home from a trip $2n$ gifts of roughly
equal value for his/her two children. The children get to choose one
at a time which gifts they want. What is the fairest way to do this?
For instance, if $n=1$ then clearly one child chooses first
(determined by a coin flip) and the other child chooses second. If we
denote the children by 0 and 1, then this method is described by the
choice sequence 01 (assuming, as I do from now on, that 0 choose
first). Now suppose $n=2$. The choice sequence 0101 is clearly biased
toward 0, since 0 has the first choice at the beginning and after both
have chosen one gift. The fairest sequence by any reasonable criterion
is 0110. What about general $n$? If $n=2^k$, an argument can be made
that the fairest sequence is the first $n$ terms of the Thue-Morse
sequence
(http://mathworld.wolfram.com/Thue-MorseSequence.html). Another
argument can be made that the fairest sequence $a_1,\dots, a_n$ is one
that maximizes the value of $k$ for which the polynomial
$(1-2a_1)x^{n-1} + (1-2a_2)x^{n-2}+\cdots+(1-2a_n)$ and its first $k$
derivatives vanish at $x=1$. (The Thue-Morse sequence does not have
this property, though I cannot recall where I once saw this.)

Has this problem received any attention? What is a reference for the
problem of maximizing $k$?

• For dividing an estate with large items, a house, cars, each heir makes a secret bid or monetary "value" estimate on each indivisible item. Then there is a spreadsheet technique for assigning items, which along with some actual money changing hands has every heir doing at least as well as the others, insofar as their personal estimates of value. No real reference, I taught this in a course for nonmajors with a book by the COMAP project called "For All Practical Purposes." Your problem seems harder, can't expect children to submit written estimates, sequential may be only possible. – Will Jagy Aug 31 '10 at 17:05
• What I meant was the divide and choose protocol: en.wikipedia.org/wiki/Divide_and_choose – Sune Jakobsen Aug 31 '10 at 17:35
• I can't believe MO does not have any "fair division" or "social choice" tags... – Thierry Zell Aug 31 '10 at 20:04
• Thierry, see my post at the very end (third page) of this Meat thread:  tea.mathoverflow.net/discussion/34/3/tag-mergerename-requests/…  There is always a chance the link will take you directly to my post, it has a number at the end.  Meanwhile, you have enough points to create new tags, but there appear to be several posiibilities here. – Will Jagy Sep 1 '10 at 1:04
• I intended to type Meta, I really did, one of those Freudian things. – Will Jagy Sep 1 '10 at 1:05

Hello,

I've been lurking on mathoverflow for a while. I am not a research mathematician, just a rank amateur.

Forgive me if I'm missing any etiquette.

Steven J. Brams and Alan D. Taylor discussed the Morse-Thue solution in their book ''The Win-Win Solution,'' ISBN-10: 0393320812, although it's a popular-math book and I'm not sure if they name it. I think they call it "picking sides picking sides."

Brian Hayes blogged of this problem on his bit-player:

http://bit-player.org/2007/choosing-up-sides-again

Best, Mark

Here's an idea. For any partition $(A,B)$ of $[2n]$, where $|A|=|B|=n$, we can ask each child if they prefer $A$ or $B$. If one prefers $A$ and the other prefers $B$, then we are done. Otherwise, they have the same preference function over all such partitions.

Lemma. There exists partitions $(A,B)$ and $(A',B')$ such that

1. both children prefer $A$ over $B$,

2. both children prefer $B'$ over $A'$, and

3. $(A',B')$ is obtained from $(A,B)$ by performing a single swap.

Proof. Perform swaps until $(A,B)$ becomes $(B,A)$. At some point, each child must switch preferences.

Given the assumption that the gifts are all roughly the same value, it seems fair to offer such an $(A,B)$ as a choice and to flip a coin to decide who gets $A$.

• @Tony, While mathematically, your reasoning is sound, I must state that children (and adults dealing with money) do not behave rationally and do not behave consistently. Their valuation function is not just a function of the parameters of the question at hand, but often also a function of fime and a function of what your opponent wants in these economic games. Younger siblings also tend to want what the older sibling wants, or vice versa, in order to confound their rivals intention. Thus "each child must switch preferences" is not going to work in real life. – sleepless in beantown Sep 1 '10 at 8:57
• I certainly agree that there is a lot of idealization going on. This reminds me of a similar problem I heard back in the day. Namely, suppose 3 friends have just moved into a 3 bedroom house. They are trying to decide who gets which room, and how much rent each should pay. The rooms can be highly heterogeneous, and each person can have different preferences. It turns out that using Sperner's Lemma, one can prove that there exists a partition $(p_1,p_2,p_3)$ of the rent such that for each $i \in [3]$, person $i$ chooses room $i$ (with rent $p_i$) over the other two rooms. – Tony Huynh Sep 1 '10 at 9:29
• Does your lemma apply only to the case where the two children have the same preference function? – Joel Reyes Noche Mar 28 '11 at 14:35
• Yes, but this is the hard case. As I mention if they have different preference functions then we can offer them a choice where they are both 'happy' (or at least not jealous of the other). The lemma is false in general if they have different preference functions. For example it is possible that for all partitions $(A,B)$ one child prefers $A$ and the other prefers $B$. – Tony Huynh Mar 29 '11 at 0:16
• When you (Tony) explain it, it sounds so simple. :) This seems to be a very interesting problem, especially if the gifts have different values, then you would have to consider having different sizes for the two partitions. Does anyone know if this general case has been studied before? – Joel Reyes Noche Mar 29 '11 at 0:29

Concerning the question of a reference for maximizing $k$:

A polynomial with all coefficients $\pm1$ is called a Littlewood polynomial, see, e.g., http://en.wikipedia.org/wiki/Littlewood_polynomial. The question of Littlewood polynomials vanishing to high order at $x=1$ is in the literature. See, e.g., Daniel Berend and Shahar Golan, Littlewood polynomials with high order zeros, Math Comp 75 (2006) 1541-1552, freely available at http://www.ams.org/journals/mcom/2006-75-255/S0025-5718-06-01848-5/S0025-5718-06-01848-5.pdf Executive summary; some numbers are known, some bounds are known, much remains to be done.

The following paper apparently addresses exactly the question that you are interested in: