Bayesian-Nash Implementation

Bayesian-Nash Implementation

• The mechanism design problem involves outcomes $X$, $n$ agents, agent types $\theta_i$ from type sets $\Theta_i$, agent utilities $u_i(x, \theta)$, and social choice function $f: \Theta \rightarrow X$.
• The goal of mechanism design is to implement $f$ in a good equilibrium.
• The revelation principle simplifies mechanism design by letting designers focus on truthful direct-revelation mechanisms, where agents directly announce their types $\hat{\theta}_i$ and the mechanism chooses an outcome $x = f(\hat{\theta})$.

Bayesian-Nash Implementation

• Truthful direct-revelation mechanism equates to Bayesian-Nash Incentive Compatibility (BNIC):
  • $\mathbb{E}{\theta{-i}}\left[u_{i}\left(f\left(\theta_{i}, \theta_{-i}\right), \theta_{i}\right)\right] \geq \mathbb{E}{\theta{-i}}\left[u_{i}\left(f\left(\hat{\theta}{i}, \theta{-i}\right), \theta_{i}\right)\right]$ for all $i$, $\theta_i$, $\hat{\theta}_i$.
• Ex-post Incentive Compatibility (EPIC):
  • $u_{i}\left(f\left(\theta_{i}, \theta_{-i}\right), \theta_{i}\right) \geq u_{i}\left(f\left(\hat{\theta}{i}, \theta{-i}\right), \theta_{i}\right)$ for all $i$, $\theta$, $\hat{\theta}_i$.
• Dominant-Strategy Incentive Compatibility (DSIC):
  • $u_{i}\left(f\left(\theta_{i}, \theta_{-i}\right), \theta_{i}\right) \geq u_{i}\left(f\left(\hat{\theta}{i}, \theta{-i}\right), \theta_{i}\right)$ for all $i$, $\theta$, $\hat{\theta}i$, $\theta{-i}$.
  • DSIC $\Rightarrow$ EPIC $\Rightarrow$ BNIC.

Example: Selling a Single Item

• Involves one seller and $n$ buyers.
• Buyer $i$'s valuation is $\theta_i$.
• Valuations are independent and identically distributed (i.i.d.) from distribution $F$ with density $f$.
• Seller has a valuation of 0.
• The social choice function allocates the item to the buyer with the highest valuation.

Myerson's Lemma

• Aims to maximize $\mathbb{E}{\theta}\left[\sum{i} \theta_{i} x_{i}(\theta)\right]$, with $x_i(\theta)$ indicating if buyer $i$ receives the item.
• Ironing/Virtual Valuation:
  • Calculated by: $J(\theta) = \theta - \frac{1-F(\theta)}{f(\theta)}$.
  • Assumes J is increasing (or "ironed" to ensure it increases).
• The optimal auction per Myerson's Lemma is allocating the item to the highest bidder $i$ with $J(\theta_i) \geq 0$ (if one exists) at price $\theta_i$.

Revenue Equivalence

• Relies on the following assumptions:
  • $\Theta_i = [\underline{\theta}, \overline{\theta}]$ for all $i$.
  • $F_i(\theta_i)$ is continuous with density $f_i(\theta_i) > 0$ for all $i$.
  • $x_i(\theta)$ is the probability that agent $i$ receives the object.
  • $\mathbb{E}{\theta{-i}}\left[x_{i}\left(\theta_{i}, \theta_{-i}\right)\right]$ is weakly increasing in $\theta_i$ for all $i$.
  • All agents with type $\underline{\theta}$ have the same expected utility.
• All BNIC mechanisms allocating objects with the same probability relative to $\theta$ have the same expected revenue.

VCG Mechanism

• Vickrey-Clarke-Groves (VCG) Mechanism operates in a quasilinear environment:
  • $u_i(x, \theta_i) = v_i(x, \theta_i) + t_i$, where $v_i$ is the valuation for outcome $x$ and $t_i$ is the monetary transfer.
• Chooses $x^*(\theta) = \operatorname{argmax}_{x \in X} \sum_i v_i(x, \theta_i)$.
• Payments are calculated as: $t_i(\theta) = \sum_{j \neq i} v_j(x^(\theta_{-i}), \theta_j) - \sum_{j \neq i} v_j(x^(\theta), \theta_j)$.
• VCG is DSIC and maximizes social welfare.