TY - JOUR
T1 - Implementation and computation of a value for generalized characteristic function games
AU - Michalak, Tomasz P.
AU - Szczepański, Piotr L.
AU - Rahwan, Talal
AU - Chrobak, Agata
AU - Brânzei, Simina
AU - Wooldridge, Michael
AU - Jennings, Nicholas R.
N1 - Funding Information:
Tomasz P. Michalak and Michael Wooldridge were supported by the European Research Council under Advanced Grant 291528 ("RACE"). Piotr L. Szczepański and Tomasz P. Michalak were supported the Polish National Science grant DEC-2013/09/D/ST6/03920. Nicholas R. Jennings was supported by the ORCHID Project, funded by an EPSRC (Engineering and Physical Research Council) under the grant EP/I011587/1. Simina Brânzei was supported by the Sino-Danish Center for the Theory of Interactive Computation, funded by the Danish National Research Foundation and the National Science Foundation of China (under the grant 61061130540). Simina also acknowledges support from the Center for research in the Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council. The authors thank the ACM-TEAC anonymous reviewers and editors for their valuable comments, which greatly benefited the article.
Publisher Copyright:
© 2014 ACM.
PY - 2014/10
Y1 - 2014/10
N2 - Generalized characteristic function games are a variation of characteristic function games, in which the value of a coalition depends not only on the identities of its members, but also on the order in which the coalition is formed. This class of games is a useful abstraction for a number of realistic settings and economic situations, such as modeling relationships in social networks. To date, two main extensions of the Shapley value have been proposed for generalized characteristic function games: the Nowak-Radzik [1994] value and the Sánchez-Bergantiños [1997] value. In this context, the present article studies generalized characteristic function games from the point of view of implementation and computation. Specifically, the article makes two key contributions. First, building upon the mechanism by Dasgupta and Chiu [1998], we present a non-cooperative mechanism that implements both the Nowak-Radzik value and the Sánchez-Bergantiños value in Subgame-Perfect Nash Equilibria in expectations. Second, in order to facilitate an efficient computation supporting the implementation mechanism, we propose the Generalized Marginal-Contribution Nets representation for this type of game. This representation extends the results of Ieong and Shoham [2006] and Elkind et al. [2009] for characteristic function games and retains their attractive computational properties.
AB - Generalized characteristic function games are a variation of characteristic function games, in which the value of a coalition depends not only on the identities of its members, but also on the order in which the coalition is formed. This class of games is a useful abstraction for a number of realistic settings and economic situations, such as modeling relationships in social networks. To date, two main extensions of the Shapley value have been proposed for generalized characteristic function games: the Nowak-Radzik [1994] value and the Sánchez-Bergantiños [1997] value. In this context, the present article studies generalized characteristic function games from the point of view of implementation and computation. Specifically, the article makes two key contributions. First, building upon the mechanism by Dasgupta and Chiu [1998], we present a non-cooperative mechanism that implements both the Nowak-Radzik value and the Sánchez-Bergantiños value in Subgame-Perfect Nash Equilibria in expectations. Second, in order to facilitate an efficient computation supporting the implementation mechanism, we propose the Generalized Marginal-Contribution Nets representation for this type of game. This representation extends the results of Ieong and Shoham [2006] and Elkind et al. [2009] for characteristic function games and retains their attractive computational properties.
KW - Algorithms
KW - Economics
KW - Generalized characteristic function games
KW - Implementation
KW - J.4 [social and behavioral sciences]
KW - Representation
KW - Shapley value
KW - Theory
UR - http://www.scopus.com/inward/record.url?scp=85032865026&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85032865026&partnerID=8YFLogxK
U2 - 10.1145/2665007
DO - 10.1145/2665007
M3 - Article
AN - SCOPUS:85032865026
VL - 2
JO - ACM Transactions on Economics and Computation
JF - ACM Transactions on Economics and Computation
SN - 2167-8375
IS - 4
M1 - 16
ER -