¿Cuál es la complejidad de este juego de división de bienes?

Alice y Bob están dividiendo el patrimonio de su difunto tío Charlie (una colección finita de artículos discretos) de acuerdo con sus deseos. Primero A elige un elemento, luego B, luego A, y así sucesivamente.$X$

Alice y Bob tienen funciones de utilidad aditivas , de modo que si Alice termina con el conjunto Y ⊆ X , su utilidad es ∑ y ∈ Y u A ( y ) .$u_A, u_B$$Y \subseteq X$$\sum_{y \in Y}u_A(y)$

Estas funciones de utilidad son de conocimiento común, como lo es el hecho de que Alice y Bob son maximizadores de utilidad perfectamente racionales. Esto implica que los jugadores no siempre seguirán un enfoque codicioso, agarrando el objeto de mayor valor para ellos; Serán más estratégicos.

Entonces, ¿cuál es la complejidad computacional de implementar las estrategias de los jugadores? Es factible en el espacio polinomial, y eso es todo lo que sé.

Quizás este documento sea de interés, aunque no sé si aborda problemas de complejidad:

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

o

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