Mechanism Design, Reverse Game Theory & Implementation Theory

Question

How does differ the area or methods of Mechanism Design, Implementation Theory and Reverse Game Theory? Are there just three names for the same?

Answer 1

I can't speak about the exact definition of "Reverse Game Theory", since the only time I've ever encountered the term was on Wikipedia. I've never actually heard an economist or mathematician say the words "Reverse Game Theory". I can, however, talk about mechanism design vs. implementation theory.

Broadly speaking, mechanism design and implementation theory are similar, in the sense that they start from the same basic environment and use some of the same tools.

Formally, both start with a (typically finite) set of $N$ agents (with $\vert N \vert \ge 1$, though for implementation theory usually $\vert N \vert > 1$) and a set of outcomes $X$. Each agent $i \in N$ has preferences over outcomes in $X$, typically represented by a utility function $u_i:X\to\mathbb R$.

There are often restrictions on the possible utility functions an agent $i$ might have. Let's denote the set of possible utility functions for $i$ by $U_i \subseteq \mathbb R^X$. We assume that agents know (at least) their own utility function.

Both fields are primarily interested in the investigation of social choice functions or social choice correspondences. Let $U = \prod_{i\in N} U_i$. A social choice function is a function

$$f: U \to X,$$

whereas a social choice correspondence is a function

$$ F: U \to 2^X \setminus \{ \emptyset \}. $$

A social choice function (correspondence) takes a profile of preferences $u = (u_i)_{i \in N}$ as given and specifies the outcome $f(u)$ (set of outcomes $F(u)$) that we would like to achieve. In the case of social choice correspondences, $F(u)$ specifies the set of "acceptable" outcomes given the preference profile $u$.

In order to achieve the outcomes specified by $f$ or $F$, we are interested in designing a game form or a mechanism. Both terms mean the same thing, though the former is more common in implementation theory whereas the latter is more common in (surprise) mechanism design. A game form/mechanism is a pair $\Gamma = (S,g)$, where $S=\prod_{i \in N} S_i$ is a collection of strategy spaces for each agent and $g:S\to X$.

A pair $(\Gamma,u)$ specifies a game. (The strategy spaces are given by $S$, and payoffs are given by $u \circ g$.) Fix your preferred equilibrium concept (e.g. Nash, or dominant strategies, but many other equilibrium concepts will also do) and let $E(\Gamma,u)$ be the set of equilibria of the game specified by $(\Gamma,u)$. (Note that $E(\Gamma,u)$ may be empty. In the discussion that follows, I assume that we've imposed enough structure on $\Gamma$ and $U$ so that this is not the case.)

I am now ready to define a few notions of implementation. I will write down the definitions for a social choice correspondence $F$. The exact same definitions apply for social choice functions if we replace $F$ with $f$ in the definitions below. (Notice, however, that some of the definitions simplify in the case of social choice functions. In particular, for social choice functions, weak and full implementation are equivalent.)

$\Gamma$ partially implements $F$ if, for all $u \in U$,

$$ E(\Gamma,u) \cap F(u) \neq \emptyset. $$

$\Gamma$ weakly implements $F$ if, for all $u \in U$,

$$ E(\Gamma,u) \subset F(u). $$

$\Gamma$ fully implements $F$ if, for all $u \in U$,

$$ E(\Gamma,u) = F(u). $$

Both mechanism design and implementation theory are interested in implementation. However, one primary difference is that in mechanism design, we are often only interested in partial implementation. On the other hand, implementation theory is primarily focused on weak and full implementation. It is, at least in part, for this reason that mechanism design tends to focus on social choice functions, whereas implementation theory is also interested in social choice correspondences.

A second major difference is that in implementation theory we often take the social choice correspondence given. (Alternatively, given the basic environment $(N,X,U)$, we are interested in characterising the social choice correspondences that can be implemented given a specified equilibrium concept.)

On the other hand, in mechanism design, often, the social choice function itself is an object of design. In particular, we are interested in characterising social choice functions that can be partially implemented and maximise some pre-specified objective. Examples of common objective functions include some efficiency criterion (e.g. utilitarian social welfare) or, in an auction environment, revenue.

If you'd like to learn more, I recommend this series of lectures on YouTube from the Jerusalem Summer School on Economic Theory, and this survey of implementation theory by John Moore.