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.
What's the complexity of this estate-division game?
gt.game theory
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/270orhttp://www.jstor.org/pss/169267