Jaka jest złożoność tej gry o podziale nieruchomości?

Alice i Bob dzielą majątek zmarłego wuja Charliego (zbiór skończony $X$elementów dyskretnych) zgodnie z jego życzeniem. Najpierw A wybiera przedmiot, potem B, potem A i tak dalej.

Alice i Bob mają dodatkowe funkcje narzędziowe $u_A, u_B$, więc jeśli Alice skończy z zestawem $Y \subseteq X$, jej użyteczność to $\sum_{y \in Y}u_A(y)$.

Te funkcje użyteczności są powszechnie znane, podobnie jak fakt, że Alice i Bob są doskonale racjonalnymi maksymalizatorami użyteczności. Oznacza to, że gracze nie zawsze będą postępować zgodnie z zachłannością, chwytając przedmiot o najwyższej wartości; będą bardziej strategiczne.

Jaka jest więc złożoność obliczeniowa wdrażania strategii graczy? Jest to wykonalne w przestrzeni wielomianowej i to wszystko, co wiem.

Być może ten artykuł będzie interesujący, chociaż nie wiem, czy dotyczy problemów ze złożonością:

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

lub

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