Artificial Computational Intelligence

Multi-Agent Decision Making: Cooperative Game Theory

Published: 2026-08-25

Level: postgraduate

Audience: Postgraduate students in Artificial Intelligence and Machine Learning

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Game Theory: Definition and Purpose — covered in Lecture 15
Elements of a Game — covered in Lecture 15
Cooperative vs Non-Cooperative Games — covered in Lecture 15
Prisoner's Dilemma and Nash Equilibrium — covered in Lecture 15
Pure Strategy vs Mixed Strategy — covered in Lecture 15

Multi-Agent Decision Making: Cooperative Game Theory

16.1 Cooperative Game Theory — Motivation and Definition

16.1.1 Why Cooperative Game Theory Matters

Why should you care? Every time a team project produces something better than any individual could alone, the same hard question appears: who deserves what share of the reward? Cooperative game theory is the mathematical toolkit for answering that question — and it powers everything from startup equity splits to how AI agents decide whether to collaborate.

Modern AI increasingly relies on multi-agent systems where multiple agents must work together. The central question is: when agents collaborate, how do they decide who teams up with whom, and how should the resulting reward be divided fairly? This is the domain of cooperative game theory (a field that studies how rational agents form teams and split joint payoffs), which originated in economics and operations research and has been adopted by AI for designing multi-agent decision-making systems.

Worked example — the startup scenario. Consider three people starting a company: one handles development, one handles marketing, and one secures investors. Each brings a different capability to the table. Individually, each would generate some value. But working together, they can generate far more — say 100 crores in profit. The question then becomes: how should that 100 crores be divided? Equal division sounds idealistic; in practice, organizations have hierarchies because people contribute differently. This is the central problem cooperative game theory addresses.

Intuition — the group-project analogy. Think of a university group assignment. Individually, each student might score around 60 marks. Working together, the project scores 95 marks. How should those 95 marks be divided? The contribution-sheet model used in assignments is a crude approach — it uses a Boolean 0% or 100% — but even among those who contributed 100%, not everyone contributed equally in terms of intellectual capability or time spent. The gap between "everyone gets the same" and "everyone gets what they deserve" is exactly the gap cooperative game theory fills.

AI borrows concepts from many fields — computer science, probability, statistics, psychology, and economics. Cooperative game theory comes from the economics and operations research side. The core idea is that in many real-world situations, working together gives better results than working alone. Cooperative game theory studies how multiple agents (or players — any decision-making entity in the game) cooperate to achieve a common goal and how the earned reward should be shared fairly.

16.1.2 Cooperative vs. Non-Cooperative Games

Hook — what makes a game "cooperative"? The prisoners in the classic dilemma were in separate cells and could not talk. What changes if they could sit down, negotiate, and shake hands on a deal? That single change — the ability to make binding agreements — is the dividing line between two entire branches of game theory.

In non-cooperative games like the prisoner's dilemma, players optimize for their own self-interest with limited communication. The prisoners were in separate cells and could not talk. In cooperative games, agents can communicate, form groups, make binding agreements, and work together. This is the key distinction: cooperative game theory examines scenarios where agents can talk, form groups, and make binding agreements. Agents form coalitions (subsets of players who join forces) to increase the total reward, and value is created through collective action. But once the job is done, challenges of fairness and stability arise.

The textbook (Russell & Norvig, Ch. 17) sharpens this distinction: in a cooperative game, it is possible to have a binding agreement between agents, thereby enabling robust cooperation. In the human world, legal contracts and social norms help establish such binding agreements. In the world of computer programs, it may be possible to inspect source code to make sure it will follow an agreement. If binding agreements are not possible, we have a non-cooperative game — a term that does not mean cooperation is impossible, only that no central agreement guarantees it. Agents in a non-cooperative setting might independently choose to cooperate if it serves their self-interest, but nothing forces them to.

Side-by-side contrast:

Dimension	Non-Cooperative Game	Cooperative Game
Communication	Limited or none	Free communication
Agreements	Not binding (or absent)	Binding — agents can commit
Analysis focus	Individual strategy (Nash equilibrium, dominant strategy)	Coalition formation and payoff division
Classic example	Prisoner's dilemma, matching pennies	Shapley value division, cost sharing
AI application	Adversarial search, auction bidding	Multi-agent collaboration, resource allocation
Key question	"What should I do given what others might do?"	"Who should I team up with, and how do we split the reward?"

Other examples of non-cooperative games include market pricing (two large MNCs planning pricing strategy without communicating), matching pennies, and monopoly. Chess is partially non-cooperative but not a classic example since players can observe each other's moves.

Scope: The boundary is not always clean. Some real-world settings mix both: a delivery company might do centralized cooperative planning for truck routes but leave individual drivers to make non-cooperative decisions about shortcuts in traffic. The key test is: can agents make a deal that a neutral third party could enforce? If yes, the game is cooperative; if each agent must look out for itself, it is non-cooperative.

Recap: Cooperative game theory answers two linked questions: (1) which teams should form, and (2) how should the joint reward be split? The field gives us formal tools — characteristic functions, the core, the Shapley value — to reason about these questions rigorously rather than relying on gut feeling. Cooperative games let agents form binding agreements and share rewards; non-cooperative games leave each agent to fend for itself. We begin by formalizing the building blocks: players and coalitions.

16.2 Players, Coalitions, and Grand Coalition

16.2.1 Definitions

Hook — before you can divide the pie, you need to know who is at the table. Every formal result in cooperative game theory rests on three simple building blocks: who the players are, which groups can form, and what happens when everyone teams up. Get these definitions right and everything else follows.

Before examining how players interact, we must establish how games are defined.

Player set: In any type of game or in agentic AI, you must determine the number of agents. The group of all players in the game is mathematically denoted as $N = {1, 2, 3, \dots, n}$ . A player is any decision-making entity — a person, a software agent, a company, or even a country. The symbol $n$ (lowercase) denotes the total number of players.

Coalition: Any subset of players who choose to join forces. If all players group together, it is called the grand coalition, denoted $N$ . The textbook (Russell & Norvig, Ch. 17) notes that in everyday language "coalition" implies a group with a common cause, but formally any subset of players counts as a coalition — even one that forms purely for strategic reasons.

Counting coalitions. For $n$ players, the total number of possible coalitions (excluding the empty set, since nobody working together is not interesting) is $2^{n} - 1$ . This is because each player is either in or out of a subset, giving $2^{n}$ subsets total, minus the empty set.

For three players A, B, C, the possible coalitions (excluding the empty set) are:

Singletons: ${A}$ , ${B}$ , ${C}$
Pairs: ${A, B}$ , ${A, C}$ , ${B, C}$
Grand coalition: ${A, B, C}$

This gives $2^{3} - 1 = 7$ possible coalitions.

Worked example — four players. For $n = 4$ players ${1, 2, 3, 4}$ , the number of coalitions is $2^{4} - 1 = 15$ . These break down by size as follows:

Size 1 (singletons): $(1 4) = 4$ coalitions
Size 2 (pairs): $(2 4) = 6$ coalitions
Size 3 (triples): $(3 4) = 4$ coalitions
Size 4 (grand coalition): $(4 4) = 1$ coalition

Total: $4 + 6 + 4 + 1 = 15$ . This matches $2^{4} - 1 = 15$ . ✓

Pitfall — confusing coalitions with coalition structures. A coalition is any subset of players. A coalition structure is a partition of all players into non-overlapping coalitions — it describes who is actually grouped with whom in a particular outcome. For three players, there are 7 possible coalitions but only 5 possible coalition structures: ${{A}, {B}, {C}}$ , ${{A}, {B, C}}$ , ${{B}, {A, C}}$ , ${{C}, {A, B}}$ , and ${{A, B, C}}$ . Do not mix up these two concepts.

Recap: The player set $N$ defines who is in the game; a coalition is any subset of $N$ ; the grand coalition is $N$ itself. With $n$ players there are $2^{n} - 1$ possible coalitions. These definitions are the vocabulary for everything that follows — the characteristic function, the core, and the Shapley value all operate on coalitions.

16.3 Characteristic Function

16.3.1 Definition and Example

Hook — how much is a team worth? Before anyone can argue about fair division, they need to know what each possible team can produce. The characteristic function is the answer sheet: it assigns a dollar value to every possible group of players.

The characteristic function $V$ (sometimes written $ν$ in the textbook) assigns to every possible coalition $C \subseteq N$ a numerical value $V (C)$ representing the total value or payoff that group can secure by working together. Formally, a cooperative game is defined as the pair $G = (N, V)$ — a set of players and a characteristic function.

Formal definition. A cooperative game in characteristic function form is $G = (N, V)$ where:

$N = {1, 2, \dots, n}$ is the set of players
$V : 2^{N} \to R$ is the characteristic function that maps every coalition $C \subseteq N$ to a real number $V (C)$

Typically we assume $V (\emptyset) = 0$ (the empty coalition produces nothing) and $V (C) \geq 0$ for all $C$ (coalitions do not destroy value). In some games we further assume $V ({i}) = 0$ for all $i$ — players achieve nothing alone and must cooperate to generate value.

This value is known a priori — the players declare upfront what they bring to the table. Only then can they decide whether to collaborate. The characteristic function does not say what actions the agents will take, nor does it specify how the value will be split — those questions come later.

Worked example — Startup scenario. Three players A, B, C with the following values:

Coalition	Value $V (C)$
${A}$	2,00,000
${B}$	3,00,000
${C}$	1,00,000
${A, B}$	10,00,000
${A, C}$	7,00,000
${B, C}$	8,00,000
${A, B, C}$	15,00,000

Reading the table: If A works alone, A generates 2 lakhs. If A and B team up, they generate 10 lakhs — far more than the sum of their individual values (2 + 3 = 5 lakhs). The extra 5 lakhs is the synergy from collaboration.

Incentive check: If A alone could make 20 lakhs (instead of 2), A would have no incentive to participate in any coalition where A's share is less than 20 lakhs. This illustrates why we collaborate: only if we can get more jointly do we want a cooperative strategy. Even in multi-agent AI, if one agent can do better alone, there is no reason to have multiple agents collaborate.

Sense-check: The grand coalition ${A, B, C}$ produces 15 lakhs, which is more than any pair (max 10 lakhs) or any individual (max 3 lakhs). So all three players have an incentive to form the grand coalition — but the question of how to split 15 lakhs remains open.

Pitfall — the characteristic function is not the payoff. A common mistake is to read $V (C)$ as "what coalition $C$ actually receives." It is not. $V (C)$ is the total value the coalition could generate if they worked together. The actual payoff each player receives depends on which coalition forms and how they divide the value — that is determined by the imputation and the Shapley value, which we cover next.

Recap: The characteristic function $V$ is the foundation of every cooperative game — it tells us what each possible team is worth. Knowing $V$ is a prerequisite for deciding whether to collaborate (super additivity), how to split the reward (imputation, Shapley value), and whether a proposed split is stable (the core). Next, we examine when collaboration actually makes sense.

16.4 Super Additivity

16.4.1 Definition and Intuition

Hook — when does teamwork actually pay off? Just because two groups can merge does not mean they should. Super additivity is the formal condition that tells us when merging is always at least as good as staying apart.

Many cooperative games have a property called super additivity (from Latin super — "above" — and additive). For any two disjoint coalitions $C$ and $D$ (meaning $C \cap D = \emptyset$ ):

$V (C \cup D) \geq V (C) + V (D)$

What the formula says. When two groups merge, they always do at least as well or better than they would have done apart. If $V (C) = 3$ and $V (D) = 5$ independently, their combined value must be at least 8 for collaboration to make sense. If the union produces only 2, the players would realize they are worse off together and would not collaborate.

Why it matters: If a game is superadditive, then the grand coalition receives a value that is at least as high as the total received by any other coalition structure. This gives all players a mathematical reason to join the grand coalition — though, as we will see, superadditivity alone does not guarantee the grand coalition will actually form (the core may still be empty).

The textbook (Russell & Norvig, Ch. 17) adds an important nuance: even in superadditive games, the grand coalition does not always form, for much the same reason that players do not always arrive at a collectively desirable Pareto-optimal outcome in the prisoner's dilemma. The incentive to defect — to break away with a smaller group that offers a better personal share — can override the collective benefit.

Worked example — checking super additivity. Consider a game with three players where:

$V ({A}) = 2$ , $V ({B}) = 3$ , $V ({C}) = 1$
$V ({A, B}) = 10$ , $V ({A, C}) = 7$ , $V ({B, C}) = 8$
$V ({A, B, C}) = 15$

Check: Is $V ({A, B}) \geq V ({A}) + V ({B})$ ? We need $10 \geq 2 + 3 = 5$ . Yes. ✓

Check: Is $V ({A, B, C}) \geq V ({A, B}) + V ({C})$ ? We need $15 \geq 10 + 1 = 11$ . Yes. ✓

Check: Is $V ({A, B, C}) \geq V ({A}) + V ({B}) + V ({C})$ ? We need $15 \geq 2 + 3 + 1 = 6$ . Yes. ✓

This game is superadditive — every merger is at least as good as the parts.

Scope — super additivity is not guaranteed in the real world. In practice, this is not always known a priori. Sometimes agents collaborate, the plan fails, and they learn from that mistake that this pairing is not good. Agents, like people in companies, business, and relationships, discover through experience that combining forces does not always work. The key insight: we collaborate only when the union makes sense — when the combined value is at least as good as the sum of independent values.

Q: Can forming groups reduce total payoff? A: Yes, and if that happens players would not want to collaborate. Players know the characteristic function a priori and will only collaborate if the union generates at least as much as independent work. In the real world, agents sometimes learn this the hard way — a failed collaboration reveals that the pairing was subadditive (the opposite of superadditive).

Q: In super additivity, combined reward may be more, but after distribution will each player definitely get more than individually? A: That is exactly the central question of cooperative game theory — knowing that collaboration generates more, the challenge is whether redistribution ensures each player benefits. Super additivity guarantees the pie is bigger; it says nothing about whether each person's slice is bigger. That is what the core and Shapley value address.

Recap: Super additivity ( $V (C \cup D) \geq V (C) + V (D)$ ) is the condition that makes collaboration rational — merging never hurts. But a bigger pie does not guarantee everyone gets a bigger slice. We need the concepts of imputation and the core to ensure fair and stable division. Next, we define what a valid outcome looks like.

16.5 Outcome and Payoff Vector

16.5.1 Definition

Hook — knowing the pie is big enough is not enough; someone has to write the cheques. The outcome of a cooperative game specifies two things: which teams actually form, and exactly how much cash each player takes home.

An outcome of a cooperative game consists of two things:

The coalition structure chosen (which groups form) — a partition of $N$ into non-overlapping coalitions
A payoff vector $x = (x_{1}, x_{2}, \dots, x_{n})$ specifying exactly how much value goes to each player $i$

Formal definition. Given a cooperative game $(N, V)$ , an outcome is a pair $(C S, x)$ where:

$C S = {C_{1}, C_{2}, \dots, C_{k}}$ is a coalition structure (a partition of $N$ )
$x = (x_{1}, x_{2}, \dots, x_{n})$ is a payoff vector

The payoff must satisfy the constraint that each coalition $C$ splits up all of its value $V (C)$ among its members:

$i \in C \sum x_{i} = V (C) for all C \in C S$

This is the coalition-level efficiency constraint: no value is wasted inside any coalition, and no coalition distributes more than it produces.

The total payoff inside any coalition must perfectly exhaust the value that coalition generates. If a coalition generates 15 lakhs, the sum of individual payoffs within that coalition must equal exactly 15 lakhs — no money is left unallocated, and no more than what was generated is distributed.

Worked example. Given the game $({1, 2, 3}, V)$ where $V ({1}) = 4$ and $V ({2, 3}) = 10$ , a possible outcome is:

$({{1}, {2, 3}}, (4, 5, 5))$

That is, player 1 stays alone and accepts a value of 4, while players 2 and 3 team up to receive a value of 10, which they choose to split evenly (5 each).

Verification:

Coalition ${1}$ : $x_{1} = 4 = V ({1})$ ✓
Coalition ${2, 3}$ : $x_{2} + x_{3} = 5 + 5 = 10 = V ({2, 3})$ ✓
Total distributed: $4 + 5 + 5 = 14$ , which equals $V ({1}) + V ({2, 3}) = 4 + 10 = 14$ ✓

Pitfall — the payoff vector is not unique. For the same coalition structure, there are many valid payoff vectors. In the example above, $(4, 3, 7)$ and $(4, 6, 4)$ are also valid outcomes for the same coalition structure ${{1}, {2, 3}}$ . The question of which payoff vector is fair is what the imputation, core, and Shapley value address.

Recap: An outcome pairs a coalition structure with a payoff vector. The payoff must exactly exhaust each coalition's value — nothing wasted, nothing over-distributed. Many outcomes are possible for the same game; the next concepts (imputation, core, Shapley value) narrow down which outcomes are viable, stable, and fair.

16.6 Imputation — Efficiency and Individual Rationality

16.6.1 The Two Conditions

Hook — not every split is a valid split. If you propose dividing 100 lakhs as (40, 30, 30), that might look reasonable. But what if one player could have earned 50 lakhs alone? Then your split is dead on arrival — that player would walk. An imputation is the formal name for a payoff vector that passes two minimum sanity checks.

A payoff vector is considered viable — called an imputation (from Latin imputare — "to attribute" or "to charge") — if it meets two baseline conditions for the grand coalition. These two conditions define what it means for a payoff to be a valid imputation:

Condition 1 — Efficiency: The payoff vector distributes the entire value of the grand coalition. Formally:

$i \in N \sum x_{i} = V (N)$

No value is thrown away. Whatever is in the payoff vector, when summed, equals the total payoff. This is the "no money left on the table" rule.

Condition 2 — Individual rationality: Every player gets at least what they could have earned working completely alone. Formally:

$x_{i} \geq V ({i}) for every player i \in N$

If player A could have made 10 independently, then A's payoff in the coalition must be at least 10. Otherwise, A would ask: "Why should I join you? I can get 10 myself." This is the "no one is worse off for joining" rule.

The textbook (Russell & Norvig, Ch. 17) defines these identically: an imputation must distribute the total value of the grand coalition (efficiency), and each player must be at least as well off as if they had worked alone (individual rationality). The following examples demonstrate how to check both conditions.

Worked example — valid imputation. Let $V (N) = 100$ and the proposed payoff vector $x = (40, 30, 30)$ , with $V ({A}) = 10$ , $V ({B}) = 15$ , $V ({C}) = 5$ .

Step 1 — Efficiency check: $x_{A} + x_{B} + x_{C} = 40 + 30 + 30 = 100 = V (N) ✓$

Step 2 — Individual rationality check:

Player A: $x_{A} = 40 \geq V ({A}) = 10$ ✓
Player B: $x_{B} = 30 \geq V ({B}) = 15$ ✓
Player C: $x_{C} = 30 \geq V ({C}) = 5$ ✓

Both conditions satisfied. Therefore $x = (40, 30, 30)$ is an imputation. Sense-check: Every player gets more than they would alone, and the full 100 is distributed. No one has a reason to walk away.

Worked example — invalid imputation. Same game, but now $V ({A}) = 50$ and the proposed payoff is $x = (40, 30, 30)$ .

Step 1 — Efficiency check: $40 + 30 + 30 = 100 = V (N)$ ✓

Step 2 — Individual rationality check: $x_{A} = 40 < V ({A}) = 50$ ✗

Player A could have made 50 alone but is only getting 40 in the coalition. This violates individual rationality — it is not an imputation. A would rationally refuse to join.

Pitfall — imputation does not mean fair. An imputation only guarantees two minimum conditions: all value is distributed and no one is worse off than alone. It says nothing about whether the split is fair. The imputation (90, 5, 5) with $V (N) = 100$ and $V ({i}) = 1$ for each $i$ is technically valid — efficiency and individual rationality both hold — but most people would call it outrageously unfair. Fairness is addressed by the Shapley value.

Q: Can forming groups reduce total payoff? A: Yes, and if that happens, players would not want to collaborate. If A alone makes more than A would in any coalition, A has no incentive to participate. This is why the characteristic function is known a priori — players evaluate whether collaboration is worthwhile before committing. The individual rationality condition formalizes this: any proposed split that gives a player less than their standalone value is automatically rejected.

Recap: An imputation is a payoff vector that satisfies efficiency ( $\sum x_{i} = V (N)$ ) and individual rationality ( $x_{i} \geq V ({i})$ ). It is the minimum bar for a viable split — but it does not guarantee stability. A subgroup might still want to break away. That leads us to the core.

16.7 Core — Stability of Coalitions

16.7.1 Definition

Hook — a deal is only as good as its weakest temptation. An imputation passes two sanity checks, but it does not ask the hardest question: is there some subgroup that could walk away and do better? The core is the set of all imputations where nobody has an incentive to defect.

The core is the set of all stable imputations where no sub-coalition has an incentive to defect. An imputation $x$ is in the core if for every possible sub-coalition $C \subseteq N$ :

$i \in C \sum x_{i} \geq V (C)$

What the formula says. The total payoff that any subgroup receives under the proposed split must be at least as much as what that subgroup could generate on its own. If this condition fails for some coalition $C$ — meaning $V (C) > \sum_{i \in C} x_{i}$ — those players will say: "Why are we staying in this grand coalition when we could break away on our own and make more money?"

In plain English: Is the proposed split so good that no subgroup wants to leave? The core is the set of all payoff vectors that pass this test for every possible subgroup.

The textbook (Russell & Norvig, Ch. 17) formalizes this identically: the core consists of all imputations $x$ that satisfy $x (C) \geq V (C)$ for every coalition $C \subset N$ . If the core is empty, then no matter how the grand coalition divides its payoff, some smaller coalition would refuse to join.

Scope — the core tests stability, not fairness. This is a critical distinction. A payoff vector in the core means nobody wants to leave, but the values inside may still be distributed unfairly. For example, the imputation (90, 5, 5) might be in the core if each player's standalone value is low enough — but most people would call it unfair. The core only answers "will everyone stay?" not "is everyone getting a fair deal?" Fairness is a separate concern addressed by the Shapley value.

16.7.2 Worked Example — Core Check

Worked example — the majority game. Three players with characteristic function:

$V (C) = {1& if ∣ C ∣ \geq 2 0& otherwise$

This is a majority game: any pair or the grand coalition produces value 1; a singleton produces nothing.

The proposed split is $x = (\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ .

Step 1 — Efficiency check: $x_{1} + x_{2} + x_{3} = \frac{1}{3} + \frac{1}{3} + \frac{1}{3} = 1 = V (N) ✓$

Step 2 — Individual rationality check: $x_{i} = \frac{1}{3} \geq V ({i}) = 0 for each i ✓$

So $x$ is an imputation. But is it in the core?

Step 3 — Core check (sub-coalitions): Take players 1 and 2. Their combined payoff is: $x_{1} + x_{2} = \frac{1}{3} + \frac{1}{3} = \frac{2}{3}$ But $V ({1, 2}) = 1$ (since $∣ C ∣ = 2 \geq 2$ ). Since $\frac{2}{3} < 1$ , players 1 and 2 can do better by breaking away — they would reject this split.

The same logic applies to every pair: each pair's combined payoff ( $\frac{2}{3}$ ) is less than what they could generate together (1). Therefore, this $x$ is not in the core.

Step 4 — Is the core empty? Consider any imputation $(x_{1}, x_{2}, x_{3})$ with $x_{1} + x_{2} + x_{3} = 1$ . At least one player must have $x_{i} > 0$ ; the other two get a total less than 1. Those two could form a coalition and share the value 1 between them, getting more than their current combined payoff. Since this holds for every imputation, the core is empty.

Sense-check: No matter how you split 1 unit among three players, some pair always gets less than 1 combined — and that pair can break away and get the full 1 for themselves. The grand coalition cannot form sustainably.

Worked example — core is non-empty. Two players with:

$V ({1}) = 5$ , $V ({2}) = 5$ , $V ({1, 2}) = 20$

The surplus from cooperation is $20 - 5 - 5 = 10$ . Any imputation $(x_{1}, x_{2})$ with $x_{1} + x_{2} = 20$ and $x_{1} \geq 5$ , $x_{2} \geq 5$ is in the core, because no single player can do better alone (each gets at least 5) and the only sub-coalition to check besides singletons is the grand coalition itself (which is satisfied by efficiency).

For example, $(6, 14)$ is in the core: player 1 gets 6 (≥ 5), player 2 gets 14 (≥ 5), and $6 + 14 = 20 = V (N)$ . No subgroup can profitably defect.

But is $(6, 14)$ fair? Player 1 might argue that the 10-unit surplus should be split more evenly. The core does not answer this question — it only confirms stability.

16.7.3 Empty Core and Fairness Limitations

Empty core: If no imputation can satisfy the core condition — meaning some subgroup always wants to defect no matter how you split the reward — the core is empty. The grand coalition cannot form sustainably because someone will always want to leave. The textbook notes that for many classes of cooperative games, checking whether the core is empty is co-NP-complete — computationally hard.

Computational note: The core condition naturally leads to a system of linear inequalities. The unknowns are $x_{1}, \dots, x_{n}$ , and the constraints are:

$x_{i} \geq V ({i})$ for all $i \in N$
$\sum_{i \in N} x_{i} = V (N)$
$\sum_{i \in C} x_{i} \geq V (C)$ for all $C \subseteq N$

Any solution defines an imputation in the core. The difficulty is that there are $2^{n}$ coalitions — an exponential number of constraints.

Common mistake — misreading the characteristic function. A frequent exam error is misinterpreting the piecewise definition of $V (C)$ . If $V (C) = 1$ when $∣ C ∣ \geq 2$ and 0 otherwise, then a singleton has value 0, not 1. Read the condition carefully before computing.

16.7.4 Student Questions

Q: If $x ({A, B}) > V ({A, B})$ , can we say they are getting a benefit? A: Yes, they are getting a benefit — their combined payoff exceeds what they could produce alone. But the core does not answer whether that benefit is fairly distributed between A and B. The core only says "you will not leave the group." Fairness is a separate concern addressed by the Shapley value.

Q: Won't C intend to leave if C alone can make more? A: If C's independent value $V ({C})$ exceeds C's payoff $x_{C}$ in the coalition, then yes, C would leave and the payoff is not in the core. This is exactly what the individual rationality condition checks — and the core goes further by checking every subgroup, not just singletons.

Recap: The core is the set of imputations where no subgroup can profitably defect: $\sum_{i \in C} x_{i} \geq V (C)$ for all $C$ . An empty core means the grand coalition cannot hold. But the core only tests stability — it does not guarantee fairness. For a fair division based on marginal contribution, we turn to the Shapley value.

16.8 Shapley Value — Fair Distribution Based on Marginal Contribution

16.8.1 Core Idea

Hook — what is each person really worth? The core tells us whether a deal is stable. But it does not tell us how to split the money. If the grand coalition produces 100 lakhs, should we divide it equally? By seniority? By who talks the loudest? Lloyd Shapley, a Nobel laureate economist, proposed an answer so elegant and unique that it remains the gold standard: pay each person according to their average contribution across every possible way the team could have formed.

While the core determines whether a coalition is stable, the Shapley value tells us exactly how to distribute the payoff fairly based on merit. It was developed by Nobel laureate Lloyd Shapley in the early 1950s.

The core philosophy is simple: a player's reward should be equal to their average marginal contribution. The marginal contribution of a player is the value that player adds when joining an existing coalition. Formally, the marginal contribution of player $i$ to coalition $C$ (where $i \in / C$ ) is:

$M C_{i} (C) = V (C \cup {i}) - V (C)$

Intuition — the empty-room analogy. Think of it as: there is an empty room, and people enter one by one. Every time someone enters, we ask: "How much extra value appeared because this one person entered?" If the room's value was 10 before and becomes 12 after, the marginal contribution is 2. Shapley's insight: do not divide the total reward equally. Compute the marginal contributions of each person — averaged over every possible entry order — and use those to decide the payoff.

The textbook (Russell & Norvig, Ch. 17) frames it this way: Shapley suggested that the only fair way to divide the value $V (N)$ was to do so according to how much each player contributed to creating that value. A first attempt would be to pay each player $i$ their marginal contribution to the grand coalition: $M C_{i} (N ∖ {i})$ . But this implicitly assumes player $i$ is the last to enter. Shapley's solution: consider all possible orderings of players, compute each player's marginal contribution in each ordering, and take the average.

16.8.2 The Four Axioms

Why the Shapley value is unique. The Shapley value is the only distribution method that satisfies four intuitive fairness axioms simultaneously. This is a remarkable result — it means if you accept these four principles as requirements for fairness, you are forced to use the Shapley value.

Efficiency: The total reward is entirely distributed — nothing is left over. Formally: $\sum_{i \in N} ϕ_{i} = V (N)$ .
Dummy player: If a player adds absolutely zero value to every single coalition ( $M C_{i} (C) = 0$ for all $C$ ), their payoff is 0. In assignments, these are the "sleeping partners" who were in the group for the sake of it but did not contribute — they get zero marks.
Symmetry: If two players contribute identical values to all coalitions ( $M C_{i} (C) = M C_{j} (C)$ for all $C \subseteq N ∖ {i, j}$ ), they receive identical payoffs.
Additivity: If players participate in two separate independent games $G$ and $G^{'}$ , their total payout is the sum of their payouts from each individual game: $ϕ_{i} (G + G^{'}) = ϕ_{i} (G) + ϕ_{i} (G^{'})$ .

The textbook notes that the additivity axiom is admittedly rather technical, but if we accept it as a requirement, the Shapley value is the only way to distribute coalitional value so as to satisfy these fairness axioms.

16.8.3 Computing the Shapley Value

The formula. For $n$ players, consider all $n!$ permutations (orderings) of players. For each permutation, compute each player's marginal contribution when they enter. The Shapley value for player $i$ is the average of their marginal contributions across all permutations:

$ϕ_{i} = \frac{1}{n !} all permutations π \sum [V (S_{i} (π) \cup {i}) - V (S_{i} (π))]$

where $S_{i} (π)$ is the set of players who entered before player $i$ in permutation $π$ .

Key properties:

For $n$ players, there are $n!$ permutations to enumerate
Each player's Shapley value is their marginal contribution averaged over all orderings
The Shapley values always sum to $V (N)$ (efficiency is guaranteed)
The result is unique — there is exactly one Shapley value for any cooperative game

Worked example — taxi sharing. Three players share a taxi. Individual costs are $C_{1} = 6$ , $C_{2} = 12$ , $C_{3} = 42$ . The cost for any group is the maximum individual cost in that group:

$V (C) = i \in C max C_{i}$

So the grand coalition cost is $max (6, 12, 42) = 42$ .

All coalition costs:

Coalition	Cost $V (C)$
${1}$	6
${2}$	12
${3}$	42
${1, 2}$	12
${1, 3}$	42
${2, 3}$	42
${1, 2, 3}$	42

There are $3! = 6$ possible orderings. For each ordering, each player pays the difference between their individual cost and what has already been paid, but never more than their individual cost and never less than zero.

Permutation 1: (1, 2, 3)

Player 1 enters: pays 6 (nothing was paid before)
Player 2 enters: already 6 paid, player 2's threshold is 12, so pays $12 - 6 = 6$
Player 3 enters: already 12 paid, player 3's threshold is 42, so pays $42 - 12 = 30$
Marginal contributions: (6, 6, 30)

Permutation 2: (1, 3, 2)

Player 1 enters: pays 6
Player 3 enters: already 6 paid, pays $42 - 6 = 36$
Player 2 enters: already 42 paid, player 2's threshold is 12, which is already exceeded, so pays 0
Marginal contributions: (6, 0, 36)

Permutation 3: (2, 1, 3)

Player 2 enters: pays 12
Player 1 enters: already 12 paid, player 1's threshold is 6, already exceeded, so pays 0
Player 3 enters: already 12 paid, pays $42 - 12 = 30$
Marginal contributions: (0, 12, 30)

Permutation 4: (2, 3, 1)

Player 2 enters: pays 12
Player 3 enters: already 12 paid, pays $42 - 12 = 30$
Player 1 enters: already 42 paid, threshold 6 exceeded, pays 0
Marginal contributions: (0, 12, 30)

Permutation 5: (3, 1, 2)

Player 3 enters: pays 42 (nothing was paid before)
Player 1 enters: already 42 paid, threshold 6 exceeded, pays 0
Player 2 enters: already 42 paid, threshold 12 exceeded, pays 0
Marginal contributions: (0, 0, 42)

Permutation 6: (3, 2, 1)

Player 3 enters: pays 42
Player 2 enters: already 42 paid, threshold 12 exceeded, pays 0
Player 1 enters: already 42 paid, threshold 6 exceeded, pays 0
Marginal contributions: (0, 0, 42)

Shapley value computation:

Player 1: $\frac{6 + 6 + 0 + 0 + 0 + 0}{6} = \frac{12}{6} = 2$

Player 2: $\frac{6 + 0 + 12 + 12 + 0 + 0}{6} = \frac{30}{6} = 5$

Player 3: $\frac{30 + 36 + 30 + 30 + 42 + 42}{6} = \frac{210}{6} = 35$

Shapley value: (2, 5, 35). Total: $2 + 5 + 35 = 42$ , which equals the grand coalition cost. ✓

Fairness check: Player 1 would have paid 6 alone but pays only 2 — better off. Player 2 would have paid 12 alone but pays only 5 — better off. Player 3 would have paid 42 alone but pays only 35 — better off. Everyone saves money compared to going alone. This is an imputation (efficiency and individual rationality both satisfied). ✓

Is this in the core? Yes. If any two players try to break away, they would still pay more than their Shapley values. For example, if players 1 and 2 form a sub-coalition, their cost is $max (6, 12) = 12$ , but their combined Shapley payoff is only $2 + 5 = 7$ . They would pay more by leaving, so they stay. No sub-coalition has an incentive to defect. ✓

Pitfall — Shapley value does not always lie in the core. In this taxi example, the Shapley value happens to be in the core. But this is not guaranteed in general. Whether the Shapley value lies in the core depends on the specific characteristic function. Do not assume it always does.

16.8.5 Student Questions on Shapley Value

Q: Is it not 100% fair for Player 3? Player 3 is paying 35 while the proportion seems unequal. A: Shapley value does not guarantee 100% fairness in the intuitive sense. What it guarantees is that everyone is better off than going alone. Player 3 would have paid 42 alone but pays 35 due to the coalition. It is still better for Player 3. The Shapley value is at least better than the core, which only checks stability without any fairness guarantee. This is one of the major challenges in modern AI — even with Shapley value, perfect fairness is not guaranteed.

Q: Under what situation would this not be part of the core? A: When some sub-coalition can be better off on their own. In this specific problem, the max function ensures that any pair breaking away would pay more, so they stay. But you should not generalize that Shapley value always implies being in the core — that depends on the specific characteristic function.

Q: How is the Shapley value different from simply dividing profit according to each person's individual contribution? A: They are conceptually the same, but the formal calculation of individual contribution through marginal contributions across all orderings was given by Shapley. It might seem intuitive today, but it comes from this economic framework. The marginal contribution approach ensures that the ordering effect is averaged out, giving a unique fair division.

Q: For permutation (2, 1, 3), why does Player 1 pay 0 when only 12 was paid and Player 1's threshold is 6? A: Each player checks their own threshold against what is already paid. Player 1's threshold is 6, but 12 is already paid (exceeds 6), so Player 1 pays nothing. They are not always looking at the total money the cab can earn — they look at their own total threshold and whether that money has already been paid.

Recap: The Shapley value divides $V (N)$ by averaging each player's marginal contribution over all $n!$ orderings. It is the unique solution satisfying efficiency, dummy player, symmetry, and additivity. It guarantees everyone is better off than going alone, but does not always lie in the core and does not guarantee intuitive fairness. Next, we see how players use these concepts strategically.

16.9 Strategic Choices in Cooperative Games

16.9.1 Three Types of Strategies

Hook — knowing the math is not enough; you need to know how to negotiate. The Shapley value tells you what is fair. The core tells you what is stable. But in the real world, players do not passively accept the math — they strategize, bluff, and form secret alliances. This section shows how all the concepts come together in real negotiation scenarios.

Players in cooperative games face several strategic questions:

Coalition strategy: Which group of players should I join to maximize our collective value? This is about choosing the right team — not just the team with the highest $V (C)$ , but the team where your marginal contribution is highest.
Negotiation strategy: How much of the collective payout should I demand to ensure I don't walk away? In salary negotiations, you tell your manager: "Collectively we earned this much, I contributed this much, I demand this raise or I leave the team." The Shapley value gives you the mathematical basis for this claim.
Stability strategy: Is there a secret side deal I can make with a subset of players to get a better outcome? This is about finding imputations outside the core — if the current split is not in the core, some subgroup can profitably defect.

16.9.2 Worked Example — Developer, Marketer, Investor

Worked example — the startup negotiation. Three players: A (developer), B (marketer), C (investor).

Coalition	Value $V (C)$
${A}$	10K (can build a basic app alone)
${B}$	0 (cannot do anything without a product)
${C}$	0 (has capital but no product to invest in)
${A, B}$	40K (can build and sell)
${A, C}$	30K (can build a high-end app but can't sell effectively)
${B, C}$	0 (no product — would only sell slides)
${A, B, C}$	100K (launch a massive venture)

Key observation: Player A is the most valuable player — without A, neither B nor C can generate any value (except the coalitions that include A). A is indispensable.

Strategic threat: Even though the grand coalition ${A, B, C}$ produces the most total value (100K), player A might strategically threaten to stay in the smaller coalition ${A, B}$ (worth 40K) during negotiations to force players B and C to give A a larger share of the 100K. A's argument: "Without me, you two make zero. With just B, I make 40K. Pay me accordingly."

The investor's unfair proposal: Suppose the investor (C) dominates the negotiation and proposes: A gets 15K, B gets 5K, C takes 80K. This is not the Shapley value — it is a power play. The investor claims credit for the 100K.

Core check: Is this proposal in the core? Check coalition ${A, B}$ : $V ({A, B}) = 40 K$ , but under this split, A and B get only $15 K + 5 K = 20 K$ . Since $40 K > 20 K$ , players A and B can do better by defecting. The proposal is not in the core.

Counter strategy: Players A and B look at this proposal and realize that together their sub-coalition ${A, B}$ can make 40K on their own. Under the investor's split, they only receive a combined 20K. So A and B form a secret alliance, reject the investor's proposal, and walk out to form their own company. The investor is left with nothing.

Lesson: This example is a culmination of many concepts: value, payoff, strategy, core, and Shapley value all interact. A proposal that ignores the core condition will be undermined by strategic defection.

16.9.3 Worked Example — Voting and Strategic Power

Worked example — the voting paradox. Three investors hold shares: Investor 1 holds 45%, Investor 2 holds 45%, Investor 3 holds 10%. To pass any corporate resolution, a simple majority (>50%) is needed.

Characteristic function: $V (C) = 1$ if the coalition's total shares exceed 50% (winning coalition), and $V (C) = 0$ otherwise.

Possible winning coalitions: ${1, 2}$ (90%), ${1, 3}$ (55%), ${2, 3}$ (55%), ${1, 2, 3}$ (100%).

Shapley value computation: There are $3! = 6$ permutations:

Permutation	Player 1's MC	Player 2's MC	Player 3's MC
(1, 2, 3)	0 (alone: 0)	1 (joins {1}: 0→1)	0 (joins {1,2}: already 1)
(1, 3, 2)	0 (alone: 0)	0 (joins {1,3}: already 1)	1 (joins {1}: 0→1)
(2, 1, 3)	1 (joins {2}: 0→1)	0 (alone: 0)	0 (joins {1,2}: already 1)
(2, 3, 1)	0 (joins {2,3}: already 1)	0 (alone: 0)	1 (joins {2}: 0→1)
(3, 1, 2)	1 (joins {3}: 0→1)	0 (joins {1,3}: already 1)	0 (alone: 0)
(3, 2, 1)	0 (joins {2,3}: already 1)	1 (joins {3}: 0→1)	0 (alone: 0)

Player 1: $\frac{0 + 0 + 1 + 0 + 1 + 0}{6} = \frac{2}{6} = \frac{1}{3}$

Player 2: $\frac{1 + 0 + 0 + 0 + 0 + 1}{6} = \frac{2}{6} = \frac{1}{3}$

Player 3: $\frac{0 + 1 + 0 + 1 + 0 + 0}{6} = \frac{2}{6} = \frac{1}{3}$

Shapley value: $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ — completely equal, despite the 45-45-10 ownership split.

Why this is striking: Even though Investor 3 only owns 10%, their strategic contribution is identical to the billionaires holding 45%. Why? Because Investor 3 changes a losing coalition into a winning coalition in exactly the same number of permutations as Investors 1 and 2. Investor 1 alone cannot pass anything (45% < 50%). Investor 2 alone cannot pass anything (45% < 50%). But Investor 3 combined with either one creates a majority. Each player is the "swing vote" in exactly 2 out of 6 permutations.

Sense-check: The total is $\frac{1}{3} + \frac{1}{3} + \frac{1}{3} = 1 = V (N)$ . ✓ This result shows that ownership percentage and strategic power are not the same thing — a small player who is frequently the swing vote can have outsized influence.

Recap: Strategic choices in cooperative games involve coalition selection, negotiation leverage, and stability analysis. The developer-marketer-investor example shows how the core catches unfair proposals. The voting example shows that strategic power (Shapley value) can differ dramatically from raw ownership. These concepts are directly applicable to corporate governance, startup equity, and multi-agent AI system design.

16.10 Applications of Coalition Structures

16.10.1 Real-World Applications

Hook — where does this actually matter outside exams? Every concept in this lecture — characteristic functions, the core, the Shapley value — has direct, named applications in industry, governance, and AI system design.

Coalition structures and the concepts learned here are used in:

Multi-agent AI systems: Agents must decide whether to collaborate, who to collaborate with, and how to share rewards. Cooperative game theory provides the formal framework for these decisions. For example, in a fleet of delivery drones, the Shapley value can determine each drone's fair share of the delivery fee based on its marginal contribution to coverage.
Corporate governance and voting systems: The 45-45-10 voting example from Section 16.9 is not just a textbook exercise — it models real shareholder dynamics. A minority holder with the right coalition potential can have outsized strategic power. Corporate boards use similar analyses to understand voting blocs.
Salary and contract negotiation: The negotiation strategy concept maps directly to real-world compensation discussions where employees leverage their marginal contribution. The Shapley value gives a mathematical basis for "what am I worth to this team?"
Startup equity division: The developer-marketer-investor example mirrors real startup founding scenarios where fair equity split is critical. Founders and accelerators increasingly use Shapley-inspired frameworks to negotiate equity.
Shared resource allocation: The taxi-sharing problem models any shared-cost scenario — cloud computing resources, shared infrastructure, ride-sharing platforms. The Shapley value determines fair cost sharing.
Trust and reputation systems: In multi-agent systems, agents build reputations based on their contributions to coalitions. The Shapley value can quantify each agent's contribution to collective outcomes.
Dynamic planning and off-site construction coordination: When multiple contractors must coordinate, coalition analysis helps determine fair payment and optimal team formation.

Recap: Cooperative game theory is not just theory — it powers real decisions in AI agent design, corporate governance, startup equity, shared resources, and negotiation. The mathematical tools (characteristic function, core, Shapley value) give principled answers to questions that were previously resolved by gut feeling or power dynamics.

Exam Guidance Summary

16.11.1 Exam Preparation Advice

Exam note: The exam is application-oriented, not memory-based. There is nothing to mug up — no direct formula recall or "explain what this is" questions. The whole paper tests whether you can apply concepts.

Prepare the course as if it were a closed-book exam. The open-book materials should be treated as cheat sheets for looking up something you forgot, not as primary study material.
A well-designed open-book question paper gives no scope for searching through slides and textbooks during the exam.
Past papers are not a good indicator because the syllabus has changed (e.g., dynamic Bayesian networks were removed). Every time the paper is designed by different ICs and reviewed by different people.

Exam note: Expect questions like: given a characteristic function and a payoff vector, determine if it is an imputation, check if it is in the core, compute the Shapley value. The exam tests whether you can do these computations, not just define them.

Problem-solving recipe for exam questions:

Imputation check: Verify efficiency ( $\sum x_{i} = V (N)$ ) and individual rationality ( $x_{i} \geq V ({i})$ for all $i$ ). Both must hold.
Core check: First confirm the payoff is an imputation. Then check every sub-coalition $C$ : is $\sum_{i \in C} x_{i} \geq V (C)$ ? If any sub-coalition fails, the payoff is not in the core.
Shapley value: Enumerate all $n!$ permutations. For each permutation, compute each player's marginal contribution when they enter. Average each player's marginal contributions across all permutations.

Common exam mistake: The characteristic function definition is critical — read it carefully. If $V (C) = 1$ when $∣ C ∣ \geq 2$ and 0 otherwise, then a singleton has value 0, not 1. Misreading this is a common mistake that cascades through imputation, core, and Shapley value calculations.

Grading structure: EC1 is for 30 marks: Assignment 1 (12 marks), Assignment 2 (13 marks), Quiz (5 marks — best of two quizzes). No rounding off at the 30-mark level; rounding to two decimals happens only at the final 100-mark total.

There will be one more class covering voting mechanisms, bidding, bargaining, and ethics.

Key Industry Applications

16.12.1 Real-World Connections

Multi-agent AI systems: Agents must decide whether to collaborate, who to collaborate with, and how to share rewards — directly modeled by cooperative game theory. The Shapley value is increasingly used to explain AI model contributions in ensemble systems.
Corporate governance: Voting power and shareholder coalitions (the 45-45-10 example shows how a minority holder can have equal strategic power). Board seat allocation and proxy voting follow coalition dynamics.
Salary and contract negotiation: The negotiation strategy concept maps directly to real-world compensation discussions where employees leverage their marginal contribution. The Shapley value provides a mathematical framework for "what am I worth to this team?"
Startup equity division: The developer-marketer-investor example mirrors real startup founding scenarios where fair equity split is critical. Shapley-inspired frameworks are used by accelerators and co-founders.
Shared resource allocation: The taxi-sharing problem models any shared-cost scenario (cloud computing resources, shared infrastructure, ride-sharing platforms like Ola and Uber). Fair cost allocation in cloud computing is an active research area using Shapley values.
Platform economics: Companies like GE splitting entities to maximize individual value illustrate real-world coalition dynamics. Mergers and acquisitions can be analyzed as coalition formation games.

ACI Lecture 16 notes · Multi-Agent Decision Making: Cooperative Game Theory

Artificial Computational Intelligence· postgraduate· 2026-08-25

Sections Breakdown

1Cooperative Game Theory — Motivation and Definition

Introduces cooperative game theory as the study of how agents form teams and fairly divide joint rewards, contrasting it with non-cooperative games.

2Players, Coalitions, and Grand Coalition

Defines the foundational vocabulary: player set N, coalitions as subsets, grand coalition, and the counting formula 2^n - 1.

3Characteristic Function

Defines the characteristic function V that assigns a numerical value to every possible coalition, with startup worked example.

4Super Additivity

Defines super additivity as the condition V(C ∪ D) ≥ V(C) + V(D) for disjoint coalitions, with worked verification.

5Outcome and Payoff Vector

Defines an outcome as a pair (CS, x) of coalition structure and payoff vector with efficiency constraint.

6Imputation — Efficiency and Individual Rationality

Defines imputation as a payoff vector satisfying efficiency and individual rationality, with valid and invalid examples.

7Core — Stability of Coalitions

Defines the core as the set of imputations where no sub-coalition can profitably defect, with majority game and two-player examples.

8Shapley Value — Fair Distribution Based on Marginal Contribution

Defines the Shapley value as the average marginal contribution across all n! orderings, with taxi sharing worked example.

9Strategic Choices in Cooperative Games

Covers coalition selection, negotiation leverage, and stability analysis with developer-marketer-investor and voting examples.

10Applications of Coalition Structures

Real-world applications in multi-agent AI, corporate governance, startup equity, shared resources, and negotiation.

Postgraduate students in Artificial Intelligence and Machine Learning

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Cooperative Game Theory — Motivation and Definition

Must-know: Cooperative game theory studies how agents form coalitions and divide payoffs when binding agreements are possible; the key distinction from non-cooperative games is the ability to make binding commitments.

⚠️ Top pitfall: Confusing 'non-cooperative' with 'competitive' — non-cooperative simply means no binding agreements, not that cooperation is impossible.

Self-check: What is the single key feature that distinguishes a cooperative game from a non-cooperative game?

Connects to: 16.2 Players, Coalitions, and Grand Coalition; 16.3 Characteristic Function

Players, Coalitions, and Grand Coalition

Must-know: A coalition is any subset of players N; the grand coalition is N itself; for n players there are 2^n - 1 possible coalitions (excluding the empty set).

$2^{n} - 1 possible coalitions$

⚠️ Top pitfall: Confusing a coalition (any subset) with a coalition structure (a partition of all players into non-overlapping coalitions).

Self-check: How many possible coalitions exist for 4 players? List them by size.

Connects to: 16.3 Characteristic Function; 16.5 Outcome and Payoff Vector

Characteristic Function

Must-know: The characteristic function V maps every coalition C to a real number V(C) representing the total value that coalition can produce. A cooperative game is the pair G = (N, V). V(empty set) = 0 by convention.

$V : 2^{N} \to R$

⚠️ Top pitfall: Confusing V(C) — what a coalition could produce — with the actual payoff players receive, which depends on which coalition forms and how the value is divided.

Self-check: Given V({A}) = 5, V({B}) = 3, V({A,B}) = 12, what is the synergy from A and B collaborating?

Connects to: 16.4 Super Additivity; 16.6 Imputation

Super Additivity

Must-know: Super additivity means merging two disjoint coalitions never reduces total value: V(C ∪ D) ≥ V(C) + V(D). It guarantees the grand coalition produces at least as much as any other arrangement, but does not guarantee fair division.

$V (C \cup D) \geq V (C) + V (D)$

⚠️ Top pitfall: Assuming super additivity guarantees each player gets more — it only guarantees the total pie is bigger, not that individual slices are larger.

Self-check: If V({A}) = 4, V({B}) = 6, and V({A,B}) = 8, is the game superadditive? Why might A and B still not collaborate?

Connects to: 16.3 Characteristic Function; 16.6 Imputation; 16.7 Core

Outcome and Payoff Vector

Must-know: An outcome is a pair (coalition structure, payoff vector). The payoff vector must satisfy ∑_{i∈C} x_i = V(C) for every coalition C in the structure — no value wasted or over-distributed.

$i \in C \sum x_{i} = V (C) for all C \in C S$

⚠️ Top pitfall: Thinking there is only one valid payoff vector per coalition structure — many different splits satisfy the efficiency constraint.

Self-check: If V({A,B}) = 20, name two different valid payoff vectors for the coalition {A,B}.

Connects to: 16.6 Imputation; 16.7 Core

Imputation — Efficiency and Individual Rationality

Must-know: An imputation must satisfy: (1) efficiency — ∑x_i = V(N), all value distributed; (2) individual rationality — x_i ≥ V({i}), no player worse off than alone. An imputation is necessary but not sufficient for stability.

$i \in N \sum x_{i} = V (N), x_{i} \geq V ({i}) for all i$

⚠️ Top pitfall: Thinking an imputation guarantees fairness — it only guarantees two minimum conditions. A highly unequal split can still be a valid imputation.

Self-check: V(N) = 60, V({A}) = 10, V({B}) = 20, V({C}) = 5. Is (25, 25, 10) an imputation? Show your checks.

Connects to: 16.7 Core; 16.8 Shapley Value

Core — Stability of Coalitions

Must-know: The core is the set of imputations where no sub-coalition can defect: ∑_{i∈C} x_i ≥ V(C) for every C. An empty core means the grand coalition cannot hold. The core tests stability only, not fairness.

$i \in C \sum x_{i} \geq V (C) for all C \subseteq N$

⚠️ Top pitfall: Misreading the piecewise characteristic function — if V(C) = 1 when |C| ≥ 2, singletons have value 0, not 1.

Self-check: V({1}) = V({2}) = V({3}) = 0, V(C) = 1 for |C| ≥ 2. Is the core empty? Explain in one sentence.

Connects to: 16.6 Imputation; 16.8 Shapley Value

Shapley Value — Fair Distribution Based on Marginal Contribution

Must-know: Shapley value φ_i = average of MC_i across all n! permutations. Unique solution satisfying efficiency, dummy player, symmetry, additivity. Everyone is better off than going alone. Does not always lie in the core.

$ϕ_{i} = \frac{1}{n !} π \sum [V (S_{i} (π) \cup {i}) - V (S_{i} (π))]$

⚠️ Top pitfall: Assuming Shapley value always lies in the core — it depends on the characteristic function. Also, confusing marginal contribution with total contribution.

Self-check: For the taxi problem with C1=6, C2=12, C3=42, what is the Shapley value? Verify it sums to 42.

Connects to: 16.7 Core; 16.9 Strategic Choices

Strategic Choices in Cooperative Games

Must-know: Strategic choices involve coalition selection, negotiation leverage (backed by Shapley value), and stability analysis (checking the core). The 45-45-10 voting example shows that strategic power can be completely equal despite unequal ownership — each player is the swing vote in exactly 2/6 permutations.

⚠️ Top pitfall: Assuming ownership percentage equals strategic power — the Shapley value measures marginal contribution, not raw holdings.

Self-check: In the 45-45-10 voting example, why does Investor 3 have the same Shapley value as Investors 1 and 2?

Connects to: 16.7 Core; 16.8 Shapley Value; 16.10 Applications

Applications of Coalition Structures

Must-know: Cooperative game theory applies to multi-agent AI, corporate governance, startup equity, shared resource allocation, and negotiation — anywhere teams form and rewards must be divided.

⚠️ Top pitfall: Treating these applications as afterthoughts — exam questions often ask you to apply concepts to real scenarios.

Self-check: Name two real-world domains where the Shapley value is used for fair division.

Connects to: 16.8 Shapley Value; 16.9 Strategic Choices

Previous LectureLecture 15 · Hidden Markov Model Algorithms and Multi-Agent Decision Making

Next LectureLecture 01 · Big Data Analytics — Course Introduction and Core Foundations

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

Multi-Agent Decision Making: Cooperative Game Theory

16.1 Cooperative Game Theory — Motivation and Definition

16.1.1 Why Cooperative Game Theory Matters

16.1.2 Cooperative vs. Non-Cooperative Games

16.2 Players, Coalitions, and Grand Coalition

16.2.1 Definitions

16.3 Characteristic Function

16.3.1 Definition and Example

16.4 Super Additivity

16.4.1 Definition and Intuition

16.5 Outcome and Payoff Vector

16.5.1 Definition

16.6 Imputation — Efficiency and Individual Rationality

16.6.1 The Two Conditions

16.7 Core — Stability of Coalitions

16.7.1 Definition

16.7.2 Worked Example — Core Check

16.7.3 Empty Core and Fairness Limitations

16.7.4 Student Questions

16.8 Shapley Value — Fair Distribution Based on Marginal Contribution

16.8.1 Core Idea

16.8.2 The Four Axioms

16.8.3 Computing the Shapley Value

16.8.4 Worked Example — Taxi Sharing Problem

16.8.5 Student Questions on Shapley Value

16.9 Strategic Choices in Cooperative Games

16.9.1 Three Types of Strategies

16.9.2 Worked Example — Developer, Marketer, Investor

16.9.3 Worked Example — Voting and Strategic Power

16.10 Applications of Coalition Structures

16.10.1 Real-World Applications

Exam Guidance Summary

16.11.1 Exam Preparation Advice

Key Industry Applications

16.12.1 Real-World Connections

ACI Lecture 16 notes · Multi-Agent Decision Making: Cooperative Game Theory

Sections Breakdown

Exam Revision Notes

Cooperative Game Theory — Motivation and Definition

Players, Coalitions, and Grand Coalition

Characteristic Function

Super Additivity

Outcome and Payoff Vector

Imputation — Efficiency and Individual Rationality

Core — Stability of Coalitions

Shapley Value — Fair Distribution Based on Marginal Contribution

Strategic Choices in Cooperative Games

Applications of Coalition Structures

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat