Qual é a complexidade deste jogo de divisão imobiliária?

Alice e Bob estão dividindo a propriedade de seu falecido tio Charlie (uma coleção finita de itens discretos) de acordo com seus desejos. Primeiro, A escolhe um item, depois B, depois A e assim por diante.$X$

Alice e Bob têm funções utilitárias aditivas , de modo que, se Alice terminar com o conjunto , seu utilitário será .$u_A, u_B$$Y \subseteq X$$\sum_{y \in Y}u_A(y)$

Essas funções de utilidade são de conhecimento comum, assim como o fato de Alice e Bob serem maximizadores de utilidade perfeitamente racionais. Isso implica que os jogadores nem sempre seguirão uma abordagem gananciosa, agarrando o item de maior valor para eles; eles serão mais estratégicos.

Então, qual é a complexidade computacional da implementação das estratégias dos jogadores? É factível no espaço polinomial, e é tudo que sei.

Talvez este artigo seja interessante, embora eu não saiba se trata de questões de complexidade:

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

ou

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