Multiplayer cooperative games

Introduction

In previous chapters of Multiplayer games we have introduced already the topic regarding multiplayer games. In other words many player games or n-player games are part of Game theory, which focuses on games where are more than two players. It is considered as games with n ≥ 2 players, and every player has d ≥ 2 strategies to choose.

In real world the people will confront much more often with multiplayer games, than with pure 2 player games. In some way, the whole life and surviving on this planet could be stated as a multiplayer game, because every living person has to choose the way to act (strategy) and therefore affect the others.

In this chapter we will take a look at the multiplayer cooperative games.

Cooperative games

Cooperative game theory deals with situations where objectives of participants of the game are partially cooperative and partially conflicting. It is in the interest of participants to cooperate in the sense of making binding agreements to achieve the maximum possible benefit. When it comes to distribution of benefit/payoffs, participants have conflicting interests. Such situations are usually modelled as cooperative games.

In game theory, a cooperative game (or coalitional game) is a game with competition between groups of players ("coalitions") due to the possibility of external enforcement of cooperative behavior (e.g. through contract law). Those are opposed to non-cooperative games in which there is either no possibility to forge alliances or all agreements need to be self-enforcing (e.g. through credible threats).

Cooperative game theory provides a high-level approach as it only describes the structure, strategies and payoffs of coalitions, whereas non-cooperative game theory also looks at how bargaining procedures will affect the distribution of payoffs within each coalition. As non-cooperative game theory is more general, cooperative games can be analyzed through the approach of non-cooperative game theory provided that sufficient assumptions are made to encompass all the possible strategies available to players due to the possibility of external enforcement of cooperation. While it would thus be optimal to have all games expressed under a non-cooperative framework, in many instances insufficient information is available to accurately model the formal procedures available to the players during the strategic bargaining process, or the resulting model would be of too high complexity to offer a practical tool in the real world. In such cases, cooperative game theory provides a simplified approach that allows to analyze the game at large without having to make any assumption about bargaining powers.

When constructing a mathematical model of the conflict, a distinction is made between a coalition of action and a coalition of interests. Coalition of action refers to certain groups participating in the game and making decisions. Coalition of interests are collectives that participate in the game and defend some common interests. In addition, the concept of a situation is introduced - the result of all coalitions choosing their strategies.

The game is called cooperative, or coalition, if players can join in groups, taking on some obligations to other players and coordinating their actions. This is different from non-cooperative games in which everyone is obliged to play for themselves. Recreational games are rarely cooperative, but such mechanisms are not uncommon in everyday life.

It is often assumed that cooperative games differ precisely in the ability of players to communicate with each other. In general, this is not true. There are games where communication is allowed, but the players pursue personal goals, and vice versa.

Of the two types of games, non-cooperative games describe situations in great detail and produce more accurate results. Cooperatives consider the process of the game as a whole. Attempts to combine the two approaches have yielded considerable results. The so-called Nash program has already found solutions to some cooperative games as equilibrium situations of noncooperative games.

Hybrid games include elements of co-op and non-co-op games. For example, players can form groups, but the game will be played in a non-cooperative style. This means that each player will pursue the interests of his group, while at the same time trying to achieve personal gain.

Cooperative games are obtained in cases when, in a game of n players, it is allowed to form certain coalitions.

Cooperative Games with Transferable Utility

Games with Transferable Utility are games where the utility can be transferred by one player or coalitions to another, without incurring any losses, then it is called Transferable Utility (TU).

For example:

n farmers can cooperate to grow fruit

• Each group of farmers can grow apples or oranges
• a group of size k can grow Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2k^2} tons of apples and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k^3} tons of oranges
• Fruit can be sold in the market: – if there are x tons of apples and y tons of oranges on the market, the market prices for apples and oranges are max{X - x, 0} and max{Y - y, 0}, respectively
• X, Y are some large enough constants
• The profit of each group depends on the quantity and type of fruit it grows, and the market price

Superadditivity and Cohesiveness

Superadditivity

Definition: a game G = (N, v) is called superadditive if v(C U D) ≥ v(C) + v(D) for any two disjoint coalitions C and D

• Example: v(C) = Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |C|^2} : – Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v(C U D)} = Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (|C|+|D|)^2} ≥ Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |C|^2} +Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |D|^2} = Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v(C) + v(D)}
• In superadditive games, two coalitions can always merge without losing money; hence, we can assume that players form the grand coalition

In superadditive games, two coalitions can always merge without losing money; hence, we can assume that players form the grand coalition

• Convention: in superadditive games, we identify outcomes with payoff vectors for the grand coalition

i.e., an outcome is a vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x = (x1, ..., xn)} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x(N) = v(N)}

Clearly, a superadditive game is cohesive. Cooperative (or coalitional) games simply define what each group of individuals can jointly achieve.

Cohesiveness

Cohesiveness is a special case of the stronger assumption, superadditivity, which requires Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v(S ∪ T) ≥ v(S) + v(T)} for all disjoint coalitions S and T.

A game with transferable utility G = hN, vi is cohesive if v(N) ≥ X S∈S v(S) for every partition S of N. The whole is greater than the sum of its parts. More generally, each whole might be greater than the sum of its parts. This is a condition called superadditivity. Formally:

Multiplayer cooperative games

In multiplayer cooperative games, where number of players more than 2, there is a situation where players should interact and cooperate with each other. But the question remains, with whom to cooperate and against whom. The group of players who choose strategies together is called the coalition from which the coalition games originate.

Multiplayer cooperative game theory deals with situations where objectives of participants of the game are partially cooperative and partially conflicting. It is in the interest of participants to cooperate in the sense of making binding agreements to achieve the maximum possible benefit. When it comes to distribution of benefit/payoffs, participants have conflicting interests. Such situations are usually modelled as cooperative games. While the book mainly discusses transferable utility games, there is also a brief analysis of non-transferable utility games.

Coalitions

A coalition is a group of players cooperating in the choice of strategies, or in the redistribution of winnings.

In fact, coalition games involve a set of players, designated N = {1, ..., N}, who strive to form cooperative groups, i.e. coalitions to strengthen their position in the game. Any coalition S ⊆ N is an agreement between the players in S acting as a unit. Coalition or alliance formation is ubiquitous in many applications.

Let P be a set of players and in a system of N players N is also called a grand coalition. The coalition is marked with capital letters of the alphabet: S, T, U, etc. The formed coalition S ⊆ P and the counter-coalition SC:

• The coalition can be one-member (different from political science).
• A grand coalition is a coalition of all players (different from political science).
• Coalition structure is the set of all formed coalitions. For example here the coalition structure for 6 players ({1,4}, {2,3}, {5},{6}).
• Players {5}, {6} are one-member coalition, it means that these players do not cooperate with anyone. For typical conflict situations, a prerequisite is a game with a free disjunctive coalition structure. This coalition structure indicates that any coalition is allowed and a player can only be a member of one coalition.

Characteristic function

A characteristic function game is a pair (N, v), where:

• N = {1, ..., n} is the set of players and
• v : 2N → R is the characteristic function.
• for each subset of players C ⊆ N, v(C) is the amount that the members of C can earn by working together

Usually it is assumed that v is

• normalized: v(∅) = 0,
• non-negative: v(C) ≥ 0, for any C ⊆ N, and
• monotone: v(C) ≤ v(D), for any C, D such that C ⊆ D

• A coalition is any subset of N. N itself is called the grand coalition.

Voting

A voting game is a specific game that has only a score of 1 (accepted) or 0 (not accepted).

• The voting rule is a number specifying the minimum number of votes for the result 1 (accepted).
• A majority coalition is a coalition of players with more votes than indicated voting rule.
• A minority coalition is a coalition that does not have this number of votes. It is often a theoretical coalition that complements the majority coalition.