Quelle est la complexité de ce jeu de division immobilière?

Alice et Bob divisent la succession de leur oncle Charlie décédé (une collection finie d'articles discrets) selon ses souhaits. Tout d'abord, A choisit un élément, puis B, puis A, etc. $X$

Alice et Bob ont chacun des fonctions utilitaires additives , de sorte que si Alice se retrouve avec l'ensemble , son utilité est . $u_A, u_B$ $Y \subseteq X$ $\sum_{y \in Y}u_A(y)$

Ces fonctions d'utilité sont connues de tous, tout comme le fait qu'Alice et Bob sont des optimiseurs d'utilité parfaitement rationnels. Cela implique que les joueurs ne suivront pas toujours une approche gourmande, saisissant l'objet le plus précieux pour eux; ils seront plus stratégiques.

Alors, quelle est la complexité informatique de la mise en œuvre des stratégies des joueurs? C'est faisable dans l'espace polynomial, et c'est tout ce que je sais.

gt.game-theory Andy Drucker
la source

Il y a un peu d'incertitude de modélisation dans ce problème: comment Alice (ou Bob) choisit-elle entre deux résultats dans lesquels son utilité est la même? Une façon d'éviter cela est de supposer que deux sous-ensembles de X n'ont pas la même utilité. Ensuite, je prétends que le résultat du jeu rationnel est uniquement déterminé, même si l'ordre de choix des objets n'est pas. (Preuve simple par induction.)

Andy Drucker

Quelle est la complexité de ce jeu de division immobilière?

Réponses: