An anytime approximation method for the inverse Shapley value problem

ABSTRACT

Coalition formation is the process of bringing together two or more agents so as to achieve goals that individuals on their own cannot, or to achieve them more efficiently. Typically, in such situations, the agents have conflicting preferences over the set of possible joint goals. Thus, before the agents realize the benefits of cooperation, they must find a way of resolving these conflicts and reaching a consensus. In this context, cooperative game theory offers the voting game as a mechanism for agents to reach a consensus. It also offers the Shapley value as a way of measuring the influence or power a player has in determining the outcome of a voting game. Given this, the designer of a voting game wants to construct a game such that a player's Shapley value is equal to some desired value. This is called the inverse Shapley value problem. Solving this problem is necessary, for instance, to ensure fairness in the players' voting powers. However, from a computational perspective, finding a player's Shapley value for a given game is #P-complete. Consequently, the problem of verifying that a voting game does indeed yield the required powers to the agents is also #P-complete. Therefore, in order to overcome this problem we present a computationally efficient approximation algorithm for solving the inverse problem. This method is based on the technique of 'successive approximations'; it starts with some initial approximate solution and iteratively updates it such that after each iteration, the approximate gets closer to the required solution. This is an anytime algorithm and has time complexity polynomial in the number of players. We also analyze the performance of this method in terms of its approximation error and the rate of convergence of an initial solution to the required one. Specifically, we show that the former decreases after each iteration, and that the latter increases with the number of players and also with the initial approximation error.

REFERENCES

• 1: V. Conitzer and T. Sandholm. Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. In Proceedings of the National Conference on Artificial Intelligence, pages 219--225, San Jose, California, 2004.
• 2: Xiaotie Deng , Christos H. Papadimitriou, On the complexity of cooperative solution concepts, Mathematics of Operations Research, v.19 n.2, p.257-266, May 1994 [doi>10.1287/moor.19.2.257]
• 3: I. C. Dragan. The potential basis and the weighted Shapley value. Libertas Mathematica, XI:139--150, 1991.
• 4: E. Elkind, L. A. Goldberg, P. Goldberg, and M. Wooldridge. Computational complexity of weighted threshold games. In Proceedings of AAAI-2007, pages 718--723, 2007.
• 5: Shaheen S. Fatima , Michael Wooldridge , Nicholas R. Jennings, A randomized method for the shapley value for the voting game, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329316]
• 6: A. Francis. Advanced Level Statistics. Stanley Thornes Publishers, 1979.
• 7: Samuel Ieong , Yoav Shoham, Marginal contribution nets: a compact representation scheme for coalitional games, Proceedings of the 6th ACM conference on Electronic commerce, p.193-202, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064030]
• 8: Samuel Ieong , Yoav Shoham, Multi-attribute coalitional games, Proceedings of the 7th ACM conference on Electronic commerce, p.170-179, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134726]
• 9: Dennis Leech, Computing Power Indices for Large Voting Games, Management Science, v.49 n.6, p.831-837, June 2003 [doi>10.1287/mnsc.49.6.831.16024]
• 10: I. Mann and L. S. Shapley. Values for large games iv: Evaluating the electoral college by Monte Carlo techniques. Technical report, The RAND Corporation, Santa Monica, 1960.
• 11: I. Mann and L. S. Shapley. Values for large games iv: Evaluating the electoral college exactly. Technical report, The RAND Corporation, Santa Monica, 1962.
• 12: M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press, 1994.
• 13: G. Owen. A note on the Shapley value. Management Science, 14:731--732, 1968.
• 14: G. Owen. Multilinear extensions of games. Management Science, 18(5):64--79, 1972.
• 15: J. S. Rosenschein and G. Zlotkin. Rules of Encounter. MIT Press, 1994.
• 16: A. E. Roth. Introduction to the Shapley value. In A. E. Roth, editor, The Shapley value, pages 1--27. University of Cambridge Press, Cambridge, 1988.
• 17: L. S. Shapley. A value for n person games. In A. E. Roth, editor, The Shapley value, pages 31--40. University of Cambridge Press, Cambridge, 1988.
• 18: Onn Shehory , Sarit Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence, v.101 n.1-2, p.165-200, May 1998 [doi>10.1016/S0004-3702(98)00045-9]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Experimentation

Keywords:
Shapley value, anytime algorithms, coalitions, game-theory, mechanism design