An Efficient Algorithm for Testing Epsilon-Approximate Core Membership in Negotiation Games. - Bodwin, Gregory M. (Tufts Archival Research Center, 2005)
We study a game theoretic model of many-party negotiations, in which each player can perform work that benefits the rest of the group. We examine the core of the game, which is the set of potential outcomes that leave no group of negotiators with an incentive to break from the agreement and pick a new outcome. More specically, we are interested in whether or not core membership of an arbitrary point can be tested in polynomial time. This is motivated by the recent economic movement towards bounded rationality, which holds that a game theoretic solution concept is poor if its justication relies on economic agents solving computationally infeasible problems. We first show that the problem is NP-Hard in a basic model of negotiations. We then add to our model the standard economic assumption of diminishing marginal returns, and show that this assumption is sufficient to push the problem into P.