Cooperative Game Theory: New Mathematical and Algorithmic Approaches.

Cooperative game theory is a branch of game theory that offers a conceptually simple and intuitive mathematical framework to model collaborative settings involving multiple decision makers (players). Solutions of cooperative games offer different ways to share the profit or cost among the players in a way that ensures the fairness and stability of the collaboration, while considering the possibility that any subgroup of players has the option to form their own coalition. The focus of this project is on the most generic class of cooperative games - the integer maximisation games. These games arise in settings where the players in each coalition need to solve an integer maximisation problem to achieve the best interests of their coalition. This proposed research addresses a fundamental question of how to distribute payoff under a new paradigm with the presence of uncertainty and in the context of reasonably large games.

Often, formulating a real-life application as a cooperative game, where relevant, is not a difficult task. The part that discourages the use of cooperative game theory is the difficulty in undertaking numerical computation of the solutions due to their combinatorial structures. This is particularly true in integer maximisation games where the set of inputs of the problem, i.e., the value that each coalition can create, involves solving an exponentially large number of integer linear programs. The first part of the proposed research provides efficient algorithms for payoff allocation in reasonably large integer maximisation games. In addition, an open-source software package for computing these solutions and showcase real-world applications is made available. This promises to extend the impact to wide groups of practitioners and academics who want to apply cooperative game theory to profit-/cost-sharing applications.

The proposed project also aims to study cooperative games with uncertain payoffs. While uncertainty is a natural part of most decision-making problems, the issue has been largely ignored in the literature of cooperative game theory and there is currently no rigorous framework for handling these. We propose a new framework where fundamental concepts such as stability and fairness are redefined in the face of uncertainty.

The proposed research has a direct impact to the UK economy and society and this is demonstrated through a broad range of real-world applications:

* The research might change the way the UK banking system operates regarding their ATM machines and hence might affect the daily activities of millions of customers. Due to the widespread geographical distribution of the customers and the limited number of ATM machines available, many UK people will benefit once the banks collaborate such that customers from one bank can use ATM machines from other banks free-of-charge. The cooperative framework proposed can be used to model the banking systems and provide them with a fair mechanism for setting the interchange fees among banks. This will save the operational costs of a large number of bilateral negotiations among individual pairs of banks. More importantly, it provides a well-proven framework for collaboration and hence can be more easily adopted by the banks. The PI has received a strong support from John Howells, CEO of LINK Scheme Ltd, and his team to apply the research findings to ATM interchange fee-setting. The team is also strengthened by the presence of Stewart Gow, a former practitioner in the ATM industry, who has extensive experience on this area.

* The proposed framework can be directly applied to the fair allocation of baggage service costs among airliners at airports. In fact, Heathrow Airport and Arup have expressed initial interest in using the results of this project. Once a group of airliners collaborates and uses an airport, they will together need to solve an optimal baggage claim allocation problem, which is an integer maximisation problem, and hence the problem fits very well within the proposed framework. With a fair and stable cost-sharing mechanism, the airliners and airports can collaborate more effectively to provide better service to the UK people.

In addition to LINK and Heathrow Airport, other companies such as Carnival UK, Red Scientific, and the RNLI have expressed initial interest in using the results of the project. These examples demonstrate that the proposed research fits well with the recent EPSRC Delivery Plan 2016/17-2019/20 where improving productivity through business innovation has been identified as one of the key priority areas. The collaborative framework that we consider in this proposal concerns stable and fair resources/cost sharing. Therefore, incorporating them into decision-making processes that involve multiple players/stakeholders may contribute to the development of a sustainable society, which is another key deliverable that has been identified in the EPSRC Delivery Plan.

In a broader sense, the impact includes the potential improvements to the UK and the world economy through more efficient usage and sharing of common resources, e.g., the transportation infrastructures and energy systems. As an example, a direct application of this research is on the efficient calculation of the core in combinatorial auctions, i.e., core-selecting solutions, a novel concept recently introduced by world leading economists. Combinatorial auctions have proven to be very useful in efficiently assigning resources to the right users and this in turn has generated revenues for the economy.

Finally, the proposal falls within the remit of the EPSRC's Mathematical Sciences Programme (e.g., the recent calls for `Decision Making under Uncertainty') and it fits very well into the EPSRC's strategic plan to strengthen the field of Operational Research in the UK.