Minimality of a solution update in conflict resolution: An application of revision programming to the von Neumann–Morgenstern approach
✍ Scribed by Inna Pivkina; Vladik Kreinovich
- Publisher
- John Wiley and Sons
- Year
- 2005
- Tongue
- English
- Weight
- 137 KB
- Volume
- 20
- Category
- Article
- ISSN
- 0884-8173
No coin nor oath required. For personal study only.
✦ Synopsis
In a 1944 book that started game theory ~and the mathematical approach to conflict resolution!, von Neumann and Morgenstern proposed the notion of a solution. When the situation changes, the old solution is often no longer a solution, so it needs to be updated. In practical applications, it is usually desirable to keep the solution change "minimal" in some reasonable sense. We show that for a seemingly straightforward formalization of this minimality, checking whether a change is minimal is NP-hard. We also show that by representing the notion of a solution as a collection of revision rules, we can produce a reasonable notion of minimality for which there exists a feasible algorithm for checking the minimality of the update.