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.