Cooperative Game Theory: New Mathematical and Algorithmic Approaches.
Lead Research Organisation:
University of Southampton
Department Name: Sch of Mathematical Sciences
Abstract
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.
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.
Planned Impact
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.
* 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.
People |
ORCID iD |
Tri-Dung Nguyen (Principal Investigator / Fellow) |
Publications
Benedek M
(2020)
Finding and verifying the nucleolus of cooperative games
in Mathematical Programming
Bo Chen
(2021)
Coopetition in Linear Production Games
Chen B.
(2023)
A Model of Coopetitive Resource Sharing
Doan X
(2020)
Technical Note-Robust Newsvendor Games with Ambiguity in Demand Distributions
in Operations Research
Fang F
(2021)
Joint pricing and inventory decisions for substitutable and perishable products under demand uncertainty
in European Journal of Operational Research
Gourtani A
(2020)
A distributionally robust optimization approach for two-stage facility location problems
in EURO Journal on Computational Optimization
Le P
(2018)
Efficient computation of the Shapley value for large-scale linear production games
in Annals of Operations Research
M. Benedek
(2020)
On the number of iterations requiredto compute the nucleolus
Description | This research deals with cooperative games; that is, the mathematical models for how players/participants share their cost/profit that are resulted of the collaboration. The key aims of this grant was to develop models for uncertain cooperative game, i.e., when the cost/profits are uncertain, and for games with a large number of participants. Both of these objectives are mostly met with the key published results. |
Exploitation Route | This object has resulted in an open software suit for the public to use. In the future, the PI also hope to include more demonstration software to demonstrate the field. |
Sectors | Communities and Social Services/Policy Education Energy Healthcare Retail Transport |
Description | We have proposed game theory solution for fairer cost sharing among banks and ATM network operators. |
First Year Of Impact | 2018 |
Sector | Financial Services, and Management Consultancy |
Impact Types | Societal Economic |
Description | Collaboration with LINK LTD |
Organisation | Link Scheme Holdings Ltd |
Country | United Kingdom |
Sector | Private |
PI Contribution | The PI has work with LINK to develop a new method using cooperative game theory to share the cost of maintaining the UK ATM network among banks |
Collaborator Contribution | LINK ATM has provided us with valuable real data for the analysis. |
Impact | A software has been developed based on the work. A research paper is being written: T.D. Nguyen (2021) Game of Banks - Keeping Free ATMs Alive?. |
Start Year | 2017 |
Title | Open Source Code for Computing the Nucleolus (Companion Software for Research Paper: https://link.springer.com/article/10.1007/s10107-020-01527-9) |
Description | This software is the result of the PhD work that the PI has supervised. It is also a companion software for the research paper https://link.springer.com/article/10.1007/s10107-020-01527-9. This software is written in C++ and the first that can compute the nucleolus of cooperative games with up to 30 players. |
Type Of Technology | Software |
Year Produced | 2019 |
Open Source License? | Yes |
Impact | This software is the first that can compute the nucleolus of cooperative games with up to 30 players. |
URL | https://github.com/blrzsvrzs/nucleolus |
Description | Career in Operational Research |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | National |
Primary Audience | Undergraduate students |
Results and Impact | Sharing career in Operational Research to prospective students. The event attracted around 50 students attending live and with presentation slides shared to others. |
Year(s) Of Engagement Activity | 2021 |
Description | Coopetition Games |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Professional Practitioners |
Results and Impact | Presentation of research resulted from the grant. Q&A and sharing from both the PI and the audience were conducted. |
Year(s) Of Engagement Activity | 2020 |
Description | Game of Banks: Saving the Free ATM Network! |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Professional Practitioners |
Results and Impact | Presented research resulted from the grant; that is, applying cooperative game theory to novel application |
Year(s) Of Engagement Activity | 2021 |
Description | Organising Conference Stream/Sessions on Game Theory at the Operational Research Society Annual Conference |
Form Of Engagement Activity | Participation in an activity, workshop or similar |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Professional Practitioners |
Results and Impact | The stream attracted both researchers from Universities and practitioners and results on the boundary of game theory and operational research was presented. The PI also presented his work resulted from the grant. |
Year(s) Of Engagement Activity | 2020 |
Description | Sharing Funding Experience |
Form Of Engagement Activity | A formal working group, expert panel or dialogue |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Postgraduate students |
Results and Impact | Sharing experience with funding agencies. The event attracted nearly 500 international MSc/PhD/Postdoct/ERC researchers |
Year(s) Of Engagement Activity | 2021 |