Apa kerumitan game divisi-estate ini?

Alice dan Bob membagi harta paman Charlie milik almarhum mereka (koleksi terbatas $X$barang diskrit) sesuai dengan keinginannya. Pertama A memilih item, lalu B, lalu A, dan seterusnya.

Alice dan Bob masing-masing memiliki fungsi utilitas tambahan $u_A, u_B$, sehingga jika Alice berakhir dengan set $Y \subseteq X$, utilitasnya adalah $\sum_{y \in Y}u_A(y)$.

Fungsi utilitas ini adalah pengetahuan umum, seperti halnya fakta bahwa Alice dan Bob adalah pemaksimalan utilitas yang sangat rasional. Ini menyiratkan bahwa para pemain tidak akan selalu mengikuti pendekatan serakah, meraih item bernilai terbesar bagi mereka; mereka akan lebih strategis.

Jadi, apa kompleksitas komputasi dari penerapan strategi para pemain? Itu bisa dilakukan di ruang polinomial, dan hanya itu yang saya tahu.

Mungkin makalah ini akan menarik meskipun saya tidak tahu apakah ini membahas masalah kompleksitas:

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

atau

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