Minimality of a solution update in conflict resolution: An application of revision programming to the von Neumann-Morgenstern approach

摘要

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. (c) 2005 Wiley Periodicals, Inc.