What's the complexity of this estate-division game? 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.
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