9
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Andy Drucker
    Commented Nov 19, 2010 at 16:43

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Wow--you nailed it! This paper gives a very simple, efficient algorithm for exactly the problem above, with a slick proof of correctness. Thanks! $\endgroup$
    – Andy Drucker
    Commented Nov 19, 2010 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.