21
$\begingroup$

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 chooses 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$?

Improve this question
$\endgroup$
12
  • 4
    $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Commented Aug 31, 2010 at 17:05
  • 4
    $\begingroup$ What I meant was the divide and choose protocol: en.wikipedia.org/wiki/Divide_and_choose $\endgroup$
    – Sune Jakobsen
    Commented Aug 31, 2010 at 17:35
  • 7
    $\begingroup$ I can't believe MO does not have any "fair division" or "social choice" tags... $\endgroup$
    – Thierry Zell
    Commented Aug 31, 2010 at 20:04
  • 3
    $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Commented Sep 1, 2010 at 1:04
  • 2
    $\begingroup$ I intended to type Meta, I really did, one of those Freudian things. $\endgroup$
    – Will Jagy
    Commented Sep 1, 2010 at 1:05

4 Answers 4

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
11
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ @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. $\endgroup$
    – sleepless in beantown
    Commented Sep 1, 2010 at 8:57
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Commented Sep 1, 2010 at 9:29
  • $\begingroup$ Does your lemma apply only to the case where the two children have the same preference function? $\endgroup$
    – JRN
    Commented Mar 28, 2011 at 14:35
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Tony Huynh
    Commented Mar 29, 2011 at 0:16
  • $\begingroup$ 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? $\endgroup$
    – JRN
    Commented Mar 29, 2011 at 0:29
7
$\begingroup$

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.

Improve this answer
$\endgroup$
0
5
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .