Library

No glossary terms available for this book.

No discussion questions available for this book.

Chapter 1: Introduction

Who introduced the Shapley value in cooperative game theory?

Oskar Morgenstern
John Nash
Lloyd Shapley
John von Neumann

What does the Shapley value measure for each player in a cooperative game?

The player's position in the grand coalition
The average marginal contribution across all possible orders of participation
The total payoff received by the player
The number of coalitions the player is part of

Which of the following is NOT a property of the characteristic function in cooperative game theory?

It represents the minimum total payoff that the coalition can achieve
It represents the maximum total payoff that the coalition can achieve
It encapsulates the essential cooperative aspects of the game
It assigns a value to each coalition

What is the efficiency axiom in the context of the Shapley value?

The payoff distribution should be random
The payoff to each player should be based on their individual effort
The sum of the payoffs to all players should equal the total value of the grand coalition
Each player should receive a payoff proportional to their total contribution

Which of the following is a method used to compute the Shapley value?

Banzhaf power index
Direct computation approach
Harsanyi dividend method
Monte Carlo method

What is the complexity class of the problem of computing the Shapley value?

P
NP-complete
NP-hard
#P-complete

In a weighted voting game, what does the Shapley value measure for each player?

The total payoff received by the player
The marginal contribution of a player
The number of coalitions the player is part of
The player's position in the grand coalition

What is the characteristic function in a Transferable Utility (TU) game?

A function that assigns a single value to each coalition
A function that assigns a real number to each coalition representing the maximum utility that the coalition can achieve by cooperating
A function that assigns a vector of payoffs to each coalition
A function that assigns a set of feasible payoff vectors to each coalition

Which of the following is a challenge in calculating the Shapley value in Non-Transferable Utility (NTU) games?

Calculating the marginal contribution of each player
Calculating the average marginal contribution of each player
Ensuring that the payoff vectors are feasible and satisfy the individual rationality and collective rationality constraints
Determining the total surplus generated by cooperation

What is the Banzhaf power index used for in cooperative game theory?

Measuring the power of players in a game based on the number of coalitions that a player can swing from losing to winning or vice versa
Calculating the average marginal contribution of a player
Determining the total payoff received by each player
Calculating the marginal contribution of each player in a dynamic game

Chapter 2: Foundations of Cooperative Game Theory

What is the characteristic function in cooperative game theory?

It represents the minimum payoff that a coalition can achieve.
It defines the rules for forming coalitions.
It is a method for distributing the total payoff among the coalition members.
It assigns a value to each coalition, representing the maximum total payoff that the coalition can achieve by working together.

In cooperative games, what is a coalition?

A method for distributing the total payoff among the coalition members.
The maximum total payoff that a group of players can achieve.
The rules for forming coalitions.
A subset of players who decide to work together to achieve a common objective.

What is superadditivity in the context of cooperative games?

The payoff of any coalition is less than or equal to the sum of the payoffs of its subsets.
The maximum total payoff that a group of players can achieve.
The payoff of any two disjoint coalitions is less than or equal to the sum of their individual payoffs.
The rules for forming coalitions.

What does convexity guarantee in cooperative games?

The payoff of any two disjoint coalitions is less than or equal to the sum of their individual payoffs.
The maximum total payoff that a group of players can achieve.
The rules for forming coalitions.
The payoff of a coalition is not excessively high compared to the sum of the payoffs of its subsets, promoting a more balanced distribution of power among players.

What is the Shapley value in the context of cooperative game theory?

The rules for forming coalitions.
A subset of players who decide to work together to achieve a common objective.
A method for distributing the total payoff among the coalition members.
The maximum total payoff that a group of players can achieve.

Chapter 3: Axiomatic Approach to Shapley Value

Which axiom states that the sum of the payoffs to all players should equal the total value of the grand coalition?

Null Player
Additivity
Efficiency
Symmetry

According to the Symmetry axiom, what should be true for players i and j who have the same marginal contribution to every coalition?

Ï_i(v) > Ï_j(v)
Ï_i(v) ≠ Ï_j(v)
Ï_i(v) < Ï_j(v)
Ï_i(v) = Ï_j(v)

The Additivity axiom requires that the payoff allocation for the sum of two games should be:

Ï(v + w) = min(Ï(v), Ï(w))
Ï(v + w) = Ï(v) + Ï(w)
Ï(v + w) = Ï(v) - Ï(w)
Ï(v + w) = max(Ï(v), Ï(w))

What is the payoff for a null player i, who does not contribute to any coalition's value?

Ï_i(v) = v(i)
Ï_i(v) = 0
Ï_i(v) = v(N)
Ï_i(v) is undefined

Which of the following is NOT a key axiom that defines the Shapley value?

Symmetry
Efficiency
Individual Rationality
Additivity

Chapter 5: Applications of Shapley Value

In which field is the Shapley value most commonly used for cost allocation?

Economics
Political Science
Computer Science
Environmental Science

What does the Shapley value consider when distributing costs in a cooperative game?

Each player's initial investment
Each player's marginal contribution to the coalition
Each player's total contribution
Each player's final contribution

In political science, the Shapley value is used to analyze which aspect of committees and legislatures?

Member attendance
Committee structure
Legislative agenda
Voting power

Which of the following is a relevant application of the Shapley value in political science?

Analyzing the effectiveness of political campaigns
Understanding the influence of different factions or parties in a parliamentary system
Assessing the popularity of political leaders
Predicting election outcomes

In computer science, the Shapley value is used for which type of resource allocation problem?

Distributed systems and cloud computing
Mainframe computing
Embedded systems
Centralized systems

What does the Shapley value help to determine in a cloud computing environment?

The priority of each task
The fair share of resources for each task
The total amount of resources available
The cost of each resource

Which discipline is the Shapley value NOT primarily used for?

Environmental Science
Computer Science
Economics
Political Science

In a weighted voting system, the Shapley value helps to understand how weights translate into actual voting power by considering which aspect?

The frequency of meetings
Strategic interactions between members
The number of votes each member has
The importance of each member's decision

What is the primary goal of using the Shapley value in resource allocation problems in computer science?

Maximizing the system's overall delay
Minimizing the system's overall power consumption
Optimizing the system's overall efficiency
Minimizing the system's overall cost

Which of the following is NOT a benefit of using the Shapley value in cost allocation problems?

Ensuring that all participants contribute equally
Preventing free-riding
Ensuring that all participants contribute according to their abilities
Incentivizing participation

Chapter 7: Shapley Value in Non-Transferable Utility Games

In non-transferable utility (NTU) games, what does the characteristic function map each coalition to?

A list of player actions
A range of possible outcomes
A single value
A set of feasible payoff vectors

What is the key challenge in ensuring that payoff vectors are feasible in NTU games?

Satisfying individual rationality and collective rationality constraints
Ensuring the payoff vectors are achievable through external intervention
Calculating the marginal contribution of each player
Dividing the payoff among coalition members

How is the marginal contribution of a player defined in NTU games?

A change in the set of feasible payoff vectors
A simple difference in payoffs
The player's utility level
The number of players in the coalition

What property ensures that no player in a coalition receives a payoff worse than what they could achieve alone?

Individual rationality
Convexity
Feasibility
Collective rationality

What does the coalitional function map each coalition to in NTU games?

A single payoff value
A range of player actions
The number of players in the coalition
A set of payoff vectors that represent possible outcomes

What method provides a fair and efficient way to divide payoffs among players in NTU games?

The core
The nucleolus
The bargaining set
The Shapley value

What does collective rationality guarantee in NTU games?

The payoff to each player is equal
The payoff to the coalition is fixed
The total payoff to the coalition is at least as good as any subset of players acting alone
The payoff to the coalition is maximized

What property ensures that the set of feasible payoff vectors is convex in NTU games?

Convexity
Collective rationality
Individual rationality
Feasibility

In NTU games, what is the role of the coalitional function?

To ensure the payoff vectors are achievable through external intervention
To divide the payoff among coalition members
To calculate the marginal contribution of each player
To determine the feasible payoff vectors for each coalition

What is the final Shapley value for each player in NTU games?

The player's utility level
The sum of the player's payoffs
The number of players in the coalition
The average marginal contribution of that player across all permutations

Chapter 9: Computational Complexity of Shapley Value

What is the computational complexity class to which the problem of computing the Shapley value belongs?

#P-complete
NP-complete
EXP
P

What does it mean if a problem is #P-complete?

It is solvable by a deterministic Turing machine
It can be solved in polynomial time
It is at least as hard as any problem in the class #P
It is easier than NP-complete problems

What is the time complexity of the direct computation approach for the Shapley value?

O(n^2)
O(2^n)
O(n * 2^n)
O(n)

Which of the following is NOT a method for computing the Shapley value?

Monte Carlo method
Linear programming relaxations
Banzhaf power index
Direct computation approach

What is the time complexity of the Monte Carlo method for approximating the Shapley value?

O(2^n)
O(n^2)
O(n * 2^n)
O(m * n^2)

What is the time complexity of the sampling-based approximation scheme for the Shapley value?

O(n * 2^n)
O(n^2)
O(2^n)
O(k * n^2)

What is the primary goal of approximation schemes for the Shapley value?

To find the most efficient algorithm
To reduce the number of players in the game
To provide near-optimal solutions with reduced computational time
To exactly compute the Shapley value

Readings

No readings available.

Gallery

No Image Available

Harvard University

No Image Available

Institute for Advanced Study

No Image Available

John F. Banzhaf III

No Image Available

John Nash

No Image Available

John von Neumann

No Image Available

Lloyd Shapley

No Image Available

MIT

No Image Available

Oskar Morgenstern

No Image Available

Princeton University

No Image Available

RAND Corporation

No Image Available

The International Game Theory Society

No Image Available

The National Science Foundation

You must log in to view news articles.

Game Theory: Shapley Value

Chapter 1: Introduction

Chapter 2: Foundations of Cooperative Game Theory

Chapter 3: Axiomatic Approach to Shapley Value

Chapter 5: Applications of Shapley Value

Chapter 7: Shapley Value in Non-Transferable Utility Games

Chapter 9: Computational Complexity of Shapley Value

Readings

Gallery

Harvard University

Institute for Advanced Study

John F. Banzhaf III

John Nash

John von Neumann

Lloyd Shapley

MIT

Oskar Morgenstern

Princeton University

RAND Corporation

The International Game Theory Society

The National Science Foundation