Topic 1

Question 1

Outcome

Answer 1

Allocation + Payment

Question 2

Type

Answer 2

The private information withheld by an agent

Question 3

Type Space

Answer 3

The set of all possible types of a player

Question 4

Type Profile

Answer 4

An instance of the set of all type spaces

Question 5

Valuation

Answer 5

An agent’s utility of an allocation under a given type

Question 6

Quasilinear Mechanism

Answer 6

A triple consisting of the set of all actions of each agent, a choice function, and a payment function

Question 7

Choice Function

Answer 7

Maps action profile to outcomes

Question 8

Payment Function

Answer 8

Maps action profiles to payments

Question 9

Direct Mechanism

Answer 9

The only action available for each agent is to announce their private information (their type)

Question 10

Mechanism Properties: Efficiency

Answer 10

The mechanism selects an outcome that maximises each agents valuation i.e. social welfare is maximised

Question 11

Mechanism Properties: Dominant-strategy Truthful

Answer 11

For every agent, declaring valuation truthfully maximises utility e.g. Vickrey Auction

Question 12

Mechanism Properties: Ex-post Individually Rational

Answer 12

The utility of each agent is at least 0 i.e. no agent loses by participating

Question 13

Mechanism Properties: Budget Balanced

Answer 13

The mechanism collects and distributes the same amount of money to and frog agents

Question 14

Mechanism Properties: Weakly Budget Balanced

Answer 14

The mechanism does not lose money

Question 15

Mechanism Properties: Tractable

Answer 15

The allocation and payment functions are computable in polynomial time

Question 16

Groves Mechanisms

Answer 16

A class of mechanism that are efficient and dominant-strategy truthful

Question 17

VCG Mechanisms

Answer 17

A subclass of Groves mechanisms where the payment function’s tax uses the Clarke tax. So each agent pays their social cost i.e. how much benefit they bring to society by their presence

Question 18

Green-Laffont Theorem

Answer 18

With unrestricted quasilinear utilities, Groves mechanisms are the only mechanisms that are both efficient and dominant-strategy truthful

Question 19

Mechanism Properties: Choice-set Monotonicity

Answer 19

Removing an agent never increases the set of outcomes

Question 20

Mechanism Properties: No Negative Externalities

Answer 20

Every agent has a 0 or positive utility for any choice made with their participation

Question 21

Mechanism Properties: No Single-agent Effect

Answer 21

The total welfare of agents other than i, is weakly increased by removing i i.e. other agents are better off without i e.g. in a single-item auction, removing i reduces the competition

Question 22

VCG Properties

Answer 22

• Not Tractable
• Only Ex-post Individually Rational if also Choice-set Monotone and has No Negative Externalities
• Not Budget Balanced
• Not Weakly Budget Balanced. Unless the No Single-agent Effect holds
• As budget balanced as any efficient mechanism can be

Question 23

Direct Revelation

Answer 23

Revealing your private information

Question 24

Revelation Principle

Answer 24

For any outcome achievable by a mechanism in equilibrium, there exists a direct, truthful mechanism that achieves the same outcome.

Question 25

Indirect Mechanism

Answer 25

Agents reveal partial information about their private value

Question 26

Usefulness of Indirect Mechanisms

Answer 26

- Agents may not want to compromise their privacy by revealing their true valuation - Full revelation can place unreasonable burden on communication channels - Each agent’s equilibrium strategy might be difficult to compute, potentially adding a considerable burden to a direct mechanism

Question 27

Direct Characterisation

Answer 27

A mechanism is dominant-strategy truthful if and only if it satisfies the criteria: 1. The payment function does not depend on the agents own valuation 2. For all possible true valuations of an agent, the mechanism selects the outcome that maximises their utility i.e. selects their most preferred choice

Question 28

Optimal Auctions

Answer 28

Maximise the seller's expected revenue