Mixed-integer programming representation for symmetrical partition function form games

Abstract

In contexts involving multiple agents (players), determining how they can cooperate through the formation of coalitions and how they can share surplus benefits coming from the collaboration is crucial. This can provide decision-aid to players and analysis tools for policy makers regulating economic markets. Such settings belong to the field of cooperative game theory. A critical element in this area has been the size of the representation of these games: for each possible partition of players, the value of each coalition on it must be provided.

Symmetric partition function form games (SPFGs) belong to a class of cooperative games with two important characteristics. First, they account for externalities provoked by any group of players joining forces or splitting into subsets on the remaining coalitions of players. Second, they consider that players are indistinct, meaning that only the number of players in each coalition is relevant for the SPFG. Using mixed-integer programming, we present the first representation of SPFGs that is polynomial on the number of players in the game. We also characterize the family of SPFGs that we can represent. In particular, the representation is able to encode exactly all SPFGs with five players or less. Furthermore, we provide a compact representation approximating SPFGs when there are six players or more and the SPFG cannot be represented exactly. We also introduce a flexible framework that uses stability methods inspired from the literature to identify a stable social-welfare maximizing game outcome using our representation. We showcase the value of our compact (approximated) representation and approach to determine a stable partition and payoff allocation to a competitive market from the literature.

Dans tout contexte impliquant plusieurs agents (joueurs), il est impératif de déterminer comment les agents coopéreront par la formation de coalitions et comment ils partageront les bénéfices supplémentaires issus de la collaboration. Ceci peut fournir une aide à la décision aux joueurs, ou encore des outils d'analyse pour les responsables en charge de réguler les marchés économiques. De telles situations relèvent de la théorie des jeux coopérative. Un élément crucial de ce domaine est la taille de la représentation de ces jeux : pour chaque partition de joueurs possible, la valeur de chaque coalition qu'on y retrouve doit être donnée.

Les jeux symétriques à fonction de partition (SPFG) appartiennent à une classe de jeux coopératifs possédant deux caractéristiques principales. Premièrement, ils sont sensibles aux externalités, provoquées par n'importe quel groupe de joueurs qui s'allient ou défont leurs alliances, qui sont ressenties par les autres coalitions de joueurs. Deuxièmement, ils considèrent que les joueurs sont indistincts, et donc que seul le nombre de joueurs dans chaque coalition est à retenir pour représenter un SPFG. Par l'utilisation d'outils de programmation mixte en nombres entiers, nous présentons la première représentation de SPFG qui est polynomiale en nombre de joueurs dans le jeu. De surcroît, nous caractérisons la famille des SPFG qu'il est possible de représenter, qui inclut notamment tous les SPFG de cinq joueurs ou moins. De plus, elle dispose d'une approximation compacte pour le cas où, dans un jeu à six joueurs ou plus, le SPFG ne peut pas être représenté de façon exacte. Également, nous introduisons un cadre flexible qui utilise des méthodes visant la stabilité inspirées par la littérature pour identifier, à l'aide de notre représentation, une issue stable qui maximise le bien-être social des joueurs. Nous démontrons la valeur de notre représentation (approximée) compacte et de notre approche pour sélectionner une partition stable et une allocation des profits dans une application de marché compétitif provenant de la littérature.