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

• 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.) Commented Nov 19, 2010 at 16:43