Thursday, 5 March 2015

game theory - Fairest way to choose gifts

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

No comments:

Post a Comment