An Anytime Algorithm for Finding the ∈-Core in Nontransferable Utility Coalitional Games

摘要

We provide the first anytime algorithm for finding the e-core in a nontransferable utility coalitional game. For a given set of possible joint actions, our algorithm calculates e, the maximum utility any agent could gain by deviating from this set of actions. If e is too high, our algorithm searches for a subset of the joint actions which leads to a smaller e. Simulations show our algorithm is more efficient than an exhaustive search by up to 2 orders of magnitude.