Alice i Bob dzielą majątek zmarłego wuja Charliego (zbiór skończony 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 , więc jeśli Alice skończy z zestawem , jej użyteczność to .
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.
1
W tym problemie jest trochę niepewności modelowania: w jaki sposób Alice (lub Bob) wybiera między dwoma wynikami, w których jej użyteczność jest taka sama? Jednym ze sposobów, aby tego uniknąć, jest założenie, że żadnemu z dwóch podzbiorów X nie przypisano jednakowej użyteczności. Następnie twierdzę, że wynik racjonalnej gry jest jednoznacznie określony, nawet jeśli kolejność wyboru przedmiotów nie jest ustalona. (Prosty dowód przez indukcję.)
—
Andy Drucker,