Mathematical Programming Approach for Finding Solutions in Cooperative Games

Cooperative games with transferable utilities belong to a branch of game theory where groups of players can form coalitions in order to jointly achieve the groups’ objectives. Cooperative game theory have many applications in economics and business (e.g. for setting insurance premium and for setting interchange fees for ATM bank networks), in law and political science (e.g. for computing voting power), and engineering (e.g. for coalition structure formation in multi-agent systems) among many others. There are two key questions that arise in cooperative game theory:
1. How to optimally form coalitions of players?
2. How to share/distribute the cost/reward among the players?

The first problem on coalition structure formation has recently received a lot of attention from the algorithmic game theory community and the artificial intelligence community. This problem is equivalent to a set covering problem in the operations research literature. The first aim of this project is to exploit the special property of the characteristic functions and develop mathematical programming techniques to solve the problem more efficiently.

The second problem concerns with finding the solutions of cooperative games. The most popular solution concepts proposed are the core, least core, nucleolus and the Shapley value. Although there is an extensive literature on these solutions’ properties, computing them is still very challenging due to their combinatorial structures. The second objective of this project is to develop mathematical models for finding these solutions. These models will be large-scale optimization problems because of their combinatorial nature. For example, finding the least core can be formulated as a large linear programming (LP) problem while finding the nucleolus involves solving nested LPs.