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 (https://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$?
 A: Concerning the question of a reference for maximizing $k$:
A polynomial with all coefficients $\pm1$ is called a Littlewood polynomial, see, e.g., https://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 https://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.
A: The following paper apparently addresses exactly the question that you are interested in:
A General Elicitation-free Protocol for Allocating Indivisible Goods,  by: Sylvain Bouveret and Jérôme Lang, International Joint Conference on Artificial Intelligence (2011).
A: 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
A: 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 


*

*both children prefer $A$ over $B$,

*both children prefer $B'$ over $A'$, and

*$(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$.  
