Contributed Session Wed.3.MA 043

Wednesday, 15:15 - 16:45 h, Room: MA 043

Cluster 8: Game theory [...]

Solving cooperative games


Chair: Kazutoshi Ando



Wednesday, 15:15 - 15:40 h, Room: MA 043, Talk 1

Tri-Dung Nguyen
Finding solutions of large cooperative games


The nucleolus is one of the most important solution concepts in cooperative game theory as a result of its attractive properties - it always exists, is unique, and is always in the core (if the core is non-empty). However, computing the nucleolus is very challenging because this involves lexicographical minimization of an exponentially large number of excess values. We present a method for computing the nucleolus of large games. We formulate the problem as nested LPs and solve them using a constraint generation algorithm. Although the nested LPs formulation has been documented in the literature, it has not been used for large games because of the large LPs involved. In addition, subtle issues such as how to deal with multiple optimal solutions and with large tight constraint sets have not been discussed in the literature. These issues are crucial and need to be resolved in each LP in order to formulate and solve the subsequent ones. We treat them rigorously and show that the nucleolus can be found efficiently as long as the worst coalition can be identified for a given imputation. We demonstrate our methodology with the case of the weighted voting games with up to 100 players.



Wednesday, 15:45 - 16:10 h, Room: MA 043, Talk 2

Ping Zhao
A mixed-integer programming approach to the determination of a core element for an n-person cooperative game with nontransferable utility

Coauthor: Chuangyin Dang


A fundamental issue concerning n-person cooperative game with nontransferable utility is about core existence. Sufficient conditions like balancedness and necessary conditions for nonemptiness of the core have been given. From a complexity theoretic standpoint, the core existence problem has been proved to be NP-complete, which also indicates computation of core element intractable in general case. We transform a core computation problem into a mixed-integer programming problem such that core existence is equivalent to having an integer point in a polytope. The core of a game can be computed directly by this MIP in virtue of approximating characteristic function by a finite numbers of corners. This approach renders sufficient and necessary conditions dispensable and the information about core can be derived directly by solving the mixed-integer programming. Case in large scale can be computed in the MIP through CPLEX.



Wednesday, 16:15 - 16:40 h, Room: MA 043, Talk 3

Kazutoshi Ando
Computation of the Shapley value of minimum cost spanning tree games: #P-hardness and polynomial cases


We show that computing the Shapley value of minimum cost spanning tree games is #P-hard even if the cost functions of underlying networks are restricted to be {0,1}-valued. The proof is by a reduction from counting the number of minimum 2-terminal vertex cuts of an undirected graph, which is #P-complete. We also investigate minimum cost spanning tree games whose Shapley values can be computed in polynomial time. We show that if the cost function of the given network is a subtree distance, which is a generalization of a tree metric, then the Shapley value of the associated minimum cost spanning tree game can be computed in O(n4) time, where n is the number of players.


  To apply for USA Payday Loans you don't have to seek the help of relatives or go to a bank. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.