Какова сложность этой игры с разделением имущества?

9

Алиса и Боб делят имущество своего покойного дяди Чарли (конечная коллекция отдельных предметов) в соответствии с его пожеланиями. Сначала А выбирает предмет, затем В, затем А и так далее.X

У Алисы и Боба есть аддитивные вспомогательные функции , так что, если Алиса заканчивает набором Y \ subseteq X , ее полезность равна \ sum_ {y \ in Y} u_A (y) .uA,uBY⊆X∑y∈YuA(y)

Эти вспомогательные функции общеизвестны, так как Алиса и Боб являются совершенно рациональными максимизаторами полезности. Это означает, что игроки не всегда будут следовать жадному подходу, хватая предмет, который им дороже; они будут более стратегическими.

Итак, какова вычислительная сложность реализации стратегий игроков? Это выполнимо в полиномиальном пространстве, и это все, что я знаю.

gt.game-theory Энди Друкер
источник
1
В этой проблеме есть некоторая неопределенность моделирования: как Алиса (или Боб) выбирают между двумя результатами, в которых ее полезность одинакова? Один из способов избежать этого - предположить, что никаким двум подмножествам X не назначена одинаковая полезность. Затем я утверждаю, что результат при рациональной игре определяется однозначно, даже если порядок выбора предметов не является. (Простое доказательство по индукции.)
Энди Друкер

Ответы:

6

Возможно, эта статья будет интересна, хотя я не знаю, касается ли она вопросов сложности:

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

или

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

Иосиф Малкевич
источник
Ух ты - ты это прибил! В этой статье приведен очень простой и эффективный алгоритм для решения вышеуказанной задачи, с легким доказательством правильности. Спасибо!
Энди Друкер