Coalition Formation Games

When people aggregate in groups, parties, communities.

Agents are partitioned in groups, according to their preferences.

Hedonic Games

In HGs each agent minds only the coalition she is in, regardless of how the others aggregate in other partitions.

Each agent \(i\) has a (reflexive, transitive and complete) preference relation \(\succcurlyeq_i\) defined over the set of all coalitions \(N_i\) of all the coalition containing \(i\).

\(S\succcurlyeq_i T\) if \(i\) prefers coalition \(S\) to coalition \(T\).

If \(S\succcurlyeq_i T\) and \(T\succcurlyeq_i S\), then \(S\) and \(T\) are equivalent for \(i\).

A HG is a pair \((N,\succcurlyeq)\) where

• \(N\) is the set of agents
• \(\succcurlyeq\) is a preference profile \((\succcurlyeq_1,\cdots,\succcurlyeq_n)\)

An outcome of the game is a coalition structure \(\pi\): a partition of \(N\) into disjoint coalitions.

Question: What are the outcomes \(\pi\) that can be considered stable according to the agents' preferences?

Equilibria/Stability in HG

There are different levels.

Individual Deviations

Individual Rationality: Leave their coalition and going alone

• A partition \(\pi\) is IR if no agent has an incentive to become alone, i.e. \(\forall i\in N,\pi(i)\succcurlyeq_i\{i\}\).

Nash Equilibrium: switch to another partition

• A partition \(\pi\) is NE if no agent can benefit by moving from her coalition \(\pi(i)\) to another coalition \(T\).

Individual Stability: switch to another partition not making the new members worse off

• A partition \(\pi\) is IS if no agent can benefit by moving from her coalition to another existing coalition \(T\) while not making the new members of \(T\) worse off.

Contractual Individual Stability: switch to another coalition not making worse off the members of the new coalition, nor the ones on the old one

• A partition is CIS if no agent can benefit by moving from her coalition \(\pi(i)\) to another existing coalition \(T\) while not making the members of \(\pi(i)\) and \(T\) worse off.

Collective Deviations

Core: form a new coalition with another set of colluding agents

• A coalition \(S\subseteq N\) blocks a partition \(\pi\), if each agent \(i\in S\) strictly prefers \(S\) to her current coalition \(\pi(i)\) in the partition \(\pi\).
• A partition with no blocking coalition is said to be in the core.

Strong Nash: switch to another coalition colluding with another set of agents

• A subset \(S\subseteq N\) Strong Nash blocks \(\pi\) if a partition \(\pi'\) exists s.t. 1. for agents in \(N\backslash S\), the \(\pi\) is unchanged; 2. for all \(i\in S\), the new arrangement is strictly preferred.

Core VS Strong Nash: in Core the colluding agents go all together in a new coalition, in strong Nash they can go in different coalitions.

Implications of Stability

\(SN\Rightarrow Core\Rightarrow IR\)

\(SN\Rightarrow NE\Rightarrow IS\)

\(IS\Rightarrow CIS\)

\(IS\Rightarrow IR\)

HGs with Numerical Valuations

By means of valuation function \(v_i\):

• \(v_i(S)\geq v_i(T)\) iff \(S\succcurlyeq_iT\).

According to numerical valuations:

• HG: pair \((N,\{v_1,\cdots,v_n\})\)
• Core: no coalition \(S\subseteq N\) exists s.t. \(v_i(S)>v_i(\pi(i))\forall i\in S\).

Space Complexity for HGs

For each agent, we need the \(2^{n-1}\) valuations, each for a subset of the other \(n-1\) agents.

In research, we consider HGs that can be succinctly represented. (Use polynomial space).

Succinct HG Classes

In succinct HG, every agent \(i\) has a valuation \(v_i(j)\) for every other agent \(j\). \(v_i(S)\) is a sole function of values \(v_i(j)\) of agent \(j\in S\).

Some subclasses:

• Additively Separable (ASHG): the value is the sum of the value \(i\) have for every other agent in the coalition. But coalitions of smaller size are preferred.
• Fractional (FHG): the value is the average of the value \(i\) have for every other agent in the coalition. But coalitions of smaller size are preferred.
• Worst (W): the value is the minimum of the value \(i\) have for every other agent in the coalition. But coalitions of smaller size are preferred.
• Best (B): the value is the maximum of the value \(i\) have for every other agent in the coalition. But coalitions of smaller size are preferred.

Social Welfare in HGs

Utilitarian Social Welfare: sum of all agents' valuations

Egalitarian Social Welfare: min of all agents' valuations

Nash Social Welfare: product of all agents' valuations

Some Results on the Core

HG Class	Existence	Construction	Verification
W games	NP-complete	?	P
W games (no ties)	P	P	P
B games	NP-complete	?	P
B games (no ties)	yes	P	P
ASGH	\(\Sigma_2^p\)-complete	?	coNP-complete
FHG	\(\Sigma_2^p\)-complete	?	coNP-complete
Friends & Enemies (Friend Appreciation)	yes	P	coNP-complete
Friends & Enemies (Enemy Aversion)	yes	NP-hard	coNP-complete

Strategyproofness in HG

When valuation profiles are unknown, we must ask agents.

Once obtained such "declared" valuations, agents should be partitioned by an algorithm/a mechanism.

Such a mechanism is known in advance by the agents

The mechanism should

• encourage truthful behavior (agent won't get benefit from telling the wrong valuation)
• maximize given social welfare
• run in polynomial time

Each agent \(i\in N\)

• has a private valuation function \(v_i\)
• can declare a possibly different valuation function \(d_i\)

A strategyproof mechanism \(M\) computes an outcome \(\pi\) in such a way that:

• truth telling, i.e., \(d_i=v_i\) is a dominant strategy for each \(i\in N\)
• social welfare is maximized (here it is utilitarian)

Goal: provide strategyproof mechanisms \(M\) with a good approximation ratio $$ r_M=\frac{\sum_{i\in N}d_i(\pi^*(i))}{\sum_{i\in N}d_i(\pi(i))}, $$ where \(\pi^*\) is the optimal solution maximizing the social welfare.

Friends and Enemies Games

Each agent classifies the others as friends or enemies.

2 types of valuation: friend appreciation, enemy aversion

• Friend appreciation: each agent prefers the coalition maximizing number of friends while minimizing the number of enemies.
• Enemy aversion: each agent prefers the coalition minimizing number of enemies while maximizing the number of friends.

Friend appreciation: $$ v_i(S)=\sum_{j\in S\backslash{i}}v_i(j)\text{ s.t. } \begin{cases} v_i(j)=n\text{ if }i\text{ consider }j\text{ as a friend}\ v_i(j)=-1\text{ otherwise} \end{cases} $$ Enemy aversion: $$ v_i(S)=\sum_{j\in S\backslash{i}}v_i(j)\text{ s.t. } \begin{cases} v_i(j)=-n\text{ if }i\text{ consider }j\text{ as an enemy}\ v_i(j)=1\text{ otherwise} \end{cases} $$ Observation: A convenient way to represent instances of FE games is by means of a directed unweighted graph \(G\), s.t. there is an edge from \(i\) to \(j\) if \(i\) declares \(j\) a friend.

Friends Appreciation

Mechanism \(M(d)\):

• Construct weakly connected components in \(G\)
• For each component put in \(\pi\) a coalition with corresponding agents.

Theorem: \(M(d)\) is strategyproof and has approximation \(r_M\leq n\).

Strategyproofness: For every agent \(i\),

• declaring a friend \(j\) as an enemy can only risk that \(j\) is not in her coalition
• declaring an enemy as a friend can only increase the number of enemies in her coalition

Enemy Aversion

Mechanism \(M(d)\): For each agent \(i\) from \(1\) up to \(n\):

• If there exists in the order an unmatched agent \(j\) with arcs \((i,j)\) and \((j,i)\) in \(G(d)\), add \(\{i,j\}\) to \(\pi\).
• Otherwise add \(\{i\}\) to \(\pi\).

Theorem: \(M(d)\) is strategyproof and has approximation \(r_M\leq(1+\sqrt 2)n\).

Strategyproofness: For every agent \(i\),

• declaring a friend j as an enemy can only risk to be put in a singleton

• declaring an enemy j as a friend can only risk to be paired with j

Conclusion

Friends Appreciation

\(r_M\)	Deterministic	Randomized
UB	\(n\)	\(4(1+\epsilon)\)
LB	\(2\)	\(>1\)

Enemy Aversion

\(r_M\)	Poly-time	Exp-time
UB	\((1+\sqrt 2)n\)	\((1+\sqrt2)/2\)
LB	\(\Omega(n)\)	\(>1\)