TY - GEN
T1 - Computing a payoff division in the least core for MC-nets coalitional games
AU - Hirayama, Katsutoshi
AU - Hanada, Kenta
AU - Ueda, Suguru
AU - Yokoo, Makoto
AU - Iwasaki, Atsushi
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2014.
PY - 2014
Y1 - 2014
N2 - MC-nets is a concise representation of the characteristic functions that exploits a set of rules to compute payoffs. Given aMC-nets instance, the problem of computing a payoff division in the least core, which is a generalization of the core-non-emptiness problem that is known to be coNP-complete, is definitely a hard computational problem. In fact, to the best of our knowledge, no algorithm can actually compute such a payoff division for MC-nets instances with dozens of agents. We propose a new algorithm for this problem, that exploits the constraint generation technique to solve the linear programming problem that potentially has a huge number of constraints. Our experimental results are striking since, using 8 GB memory, our proposed algorithm can successfully compute a payoff division in the least core for the instances with up to 100 agents, but the naive algorithm fails due to a lack of memory for instances with 30 or more agents.
AB - MC-nets is a concise representation of the characteristic functions that exploits a set of rules to compute payoffs. Given aMC-nets instance, the problem of computing a payoff division in the least core, which is a generalization of the core-non-emptiness problem that is known to be coNP-complete, is definitely a hard computational problem. In fact, to the best of our knowledge, no algorithm can actually compute such a payoff division for MC-nets instances with dozens of agents. We propose a new algorithm for this problem, that exploits the constraint generation technique to solve the linear programming problem that potentially has a huge number of constraints. Our experimental results are striking since, using 8 GB memory, our proposed algorithm can successfully compute a payoff division in the least core for the instances with up to 100 agents, but the naive algorithm fails due to a lack of memory for instances with 30 or more agents.
UR - http://www.scopus.com/inward/record.url?scp=84910144738&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84910144738&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-13191-7_26
DO - 10.1007/978-3-319-13191-7_26
M3 - Conference contribution
AN - SCOPUS:84910144738
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 319
EP - 332
BT - PRIMA 2014
A2 - Dam, Hoa Khanh
A2 - Pitt, Jeremy
A2 - Xu, Yang
A2 - Governatori, Guido
A2 - Ito, Takayuki
PB - Springer Verlag
T2 - 17th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2014
Y2 - 1 December 2014 through 5 December 2014
ER -