<p>Perhaps this paper will be of interest though I don't know if it addresses complexity issues:</p>

<p><a href="http://or.journal.informs.org/cgi/content/abstract/19/2/270" rel="nofollow">http://or.journal.informs.org/cgi/content/abstract/19/2/270</a></p>

<p>or</p>

<p><a href="http://www.jstor.org/pss/169267" rel="nofollow">http://www.jstor.org/pss/169267</a></p>

CC BY-SA 2.5
2010-11-19T21:26:53.393Z
Wow--you nailed it!  This paper gives a very simple, efficient algorithm for exactly the problem above, with a slick proof of correctness.  Thanks!
Andy Drucker
CC BY-SA 2.5
2010-11-19T18:27:09.697Z
2010-11-19T18:27:09.697Z
Joseph Malkevitch
<p>Alice and Bob are splitting their deceased uncle Charlie's estate (a finite collection $X$ of discrete items) according to his wishes.  First A picks an item, then B, then A, and so on.</p>

<p>Alice and Bob each have additive utility functions $u_A, u_B$, so that if Alice ends up with the set $Y \subseteq X$, her utility is $\sum_{y \in Y}u_A(y)$.</p>

<p>These utility functions are common knowledge, as is the fact that Alice and Bob are perfectly rational utility-maximizers.  This implies that the players will <em>not</em> always follow a greedy approach, grabbing the item of greatest worth to them; they will be more strategic.</p>

<p>So, what is the computational complexity of implementing the players' strategies?  It's doable in polynomial space, and that's all I know.</p>

CC BY-SA 2.5
2010-11-19T16:43:41.033Z
There is a bit of a modeling uncertainty in this problem: how does Alice (or Bob) choose between two outcomes in which her utility is the same?  One way to avoid this is to assume that no two subsets of X are assigned equal utility.  Then I claim that the outcome under rational play is uniquely determined, even if the order of item choice is not.  (Simple proof by induction.)
Andy Drucker
<gt.game-theory>
What's the complexity of this estate-division game?
Andy Drucker
# What's the complexity of this estate-division game?

(Asked by: username_0 on 2010-11-19)

Alice and Bob are splitting their deceased uncle Charlie's estate (a finite collection $X$ of discrete items) according to his wishes. First A picks an item, then B, then A, and so on.

Alice and Bob each have additive utility functions $u\_A, u\_B$, so that if Alice ends up with the set $Y \subseteq X$, her utility is $\sum\_{y \in Y}u\_A(y)$.

These utility functions are common knowledge, as is the fact that Alice and Bob are perfectly rational utility-maximizers. This implies that the players will *not* always follow a greedy approach, grabbing the item of greatest worth to them; they will be more strategic.

So, what is the computational complexity of implementing the players' strategies? It's doable in polynomial space, and that's all I know.

**Tags:** gt.game-theory
> **Comments:**
> **username_0**: There is a bit of a modeling uncertainty in this problem: how does Alice (or Bob) choose between two outcomes in which her utility is the same?  One way to avoid this is to assume that no two subsets of X are assigned equal utility.  Then I claim that the outcome under rational play is uniquely determined, even if the order of item choice is not.  (Simple proof by induction.)  

---

## 1 answers

### Answer by username_1 on 2010-11-19. Score: 6 | Accepted answer

Perhaps this paper will be of interest though I don't know if it addresses complexity issues:

<http://or.journal.informs.org/cgi/content/abstract/19/2/270>

or

<http://www.jstor.org/pss/169267>

> **Comments:**
> **username_0**: Wow--you nailed it!  This paper gives a very simple, efficient algorithm for exactly the problem above, with a slick proof of correctness.  Thanks!  

---

