Games and Mechanisms

Question 1

Social Choice Settings

Answer 1

Agents with individual preferences and the aim is to aggregate the preferences and select an outcome that reflects the collective preference assuming the agents are truthful

Question 2

Social Choice Function (SCF)

Answer 2

Maps agent’s preferences to outcomes

Question 3

Bayesian Game

Answer 3

Agents are strategic, holding private information about their preferences of outcomes. They cannot be relied on to honestly disclose their preferences

Question 4

Outcome

Answer 4

The result of a game, capturing the allocation of resources and the payments made by each agent

Question 5

Type

Answer 5

Encapsulates the private information withheld by an agent

Question 6

Type Space

Answer 6

The set of all possible types of each player

Question 7

Type Profile

Answer 7

An instance of the set of all type spaces

Question 8

Common-prior probability distribution

Answer 8

The probability distribution over the set of all type spaces, it is known to all players. It represents the probability the players are in a given type space

Question 9

Utility

Answer 9

It is quasilinear and captures their payoff for an an outcome is defined under a given type

Question 10

Mechanism

Answer 10

A pair
<A, M>

Question 11

Direct Mechanism

Answer 11

The only action available for each agent is to announce their private information:

Question 12

Quasilinear mechanism

Answer 12

A triple
<A, \chi, p>

Question 13

Choice Function

Answer 13

Maps from action profiles to outcomes

Question 14

Payment Function

Answer 14

Maps from action profiles to payments

Question 15

Direct Quasilinear Mechanism

Answer 15

A triple
<\Theta, \chi, p>

\Theta = A

Question 16

Efficient Mechanism

Answer 16

In equilibrium, the selected allocation maximises the total social welfare

Question 17

Dominant Strategy Truthful Mechanism

Answer 17

For every possible agent and true valuation, declaring truthfully maximises utility

Question 18

Ex Post Individually Rational Mechanism

Answer 18

In equilibrium the utility of each agent is at least 0
i.e. no agent loses by participating

Question 19

Budget Balanced Mechanism

Answer 19

Regardless of agents’ types, the mechanism collects and disburses the same amount of money to and from agents

Question 20

Weakly Budget Balanced Mechanism

Answer 20

Regardless of agents’ types, the mechanism does not lose money

Question 21

Tractable Mechanism

Answer 21

All declarable values, allocations, and payments can be computed in polynomial times

Question 22

Groves Mechanisms

Answer 22

A class of mechanisms that are both efficient and dominant strategy truthful

Question 23

Groves Mechanisms: Allocation Function

Answer 23

Selects an allocation that maximises the sum of declared values

Question 24

Groves Mechanisms: Payment Function

Answer 24

Consists of two components
- Tax: The amount an agent pays, it must not be dependent on their own declared valuation

Question 25

Groves Mechanisms: Income

Answer 25

The amount an agent is paid, it is the sum of the other agent's declared valuations

Question 26

VCG Mechanism

Answer 26

Direct quasilinear mechanism that is a subclass of Groves mechanisms It maximises social welfare, i.e. maximises total utility

Question 27

Clarke Tax

Answer 27

The sum of the valuations of the allocation given an agent did not participate