Computing shapley values, manipulating value division schemes, and checking core membership in multi-issue domains

Abstract

Coalition formation is a key problem in automated negotiation among self-interested agents. In order for coalition formation to be successful, a key question that must be answered is how the gains from cooperation are to be distributed. Various solution concepts have been proposed, but the computational questions around these solution concepts have received little attention. We study a concise representation of characteristic functions which allows for the agents to be concerned with a number of independent issues that each coalition of agents can address. For example, there may be a set of tasks that the capacityunconstrained agents could undertake, where accomplishing a task generates a certain amount of value (possibly depending on how well the task is accomplished). Given this representation, we show how to quickly compute the Shapley value—a seminal value division scheme that distributes the gains from cooperation fairly in a certain sense. We then show that in (distributed) marginal-contribution based value division schemes, which are known to be vulnerable to manipulation of the order in which the agents are added to the coalition, this manipulation is NP-complete. Thus, computational complexity serves as a barrier to manipulating the joining order. Finally, we show that given a value division, determining whether some subcoalition has an incentive to break away (in which case we say the division is not in the core) is NP-complete. So, computational complexity serves to increase the stability of the coalition.