Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 4141–4240 of 6559. Source text is displayed literally.
4141\begin{example}[Two types]\label{ex:screening}4142Let $C(x)=\tfrac12x^2$ and $\theta\in\{2,3\}$ with equal probability. With types observable the seller would4143supply $x=\theta$ and extract all the surplus, earning $\tfrac12\cdot2+\tfrac12\cdot4.5=3.25$. With types hidden,4144the constraints that bind are the low type's participation and the high type's incentive constraint (the4145shortest path of \cref{ex:twotype-metric}). The seller's problem reduces to choosing $x_L$ to maximize4146$\tfrac12(2x_L-\tfrac12x_L^2)-\tfrac12(3-2)x_L$, the low type's surplus less the \emph{information rent}4147$(\theta_H-\theta_L)x_L$ that must be left to the high type. The solution is4148\[ x_L=1,\quad t_L=2;\qquad x_H=3,\quad t_H=8, \]4149with profit $2.5$. The high type receives the efficient quantity and a rent of $1$; the low type's4150quantity is distorted downward, from $2$ to $1$, not because serving her is unprofitable but because every4151unit sold to her raises the rent that the high type can claim by imitating her.4152\end{example}4153 4154With a continuum of types distributed with density $\phi$ and distribution function $F$ on4155$[\underline\theta,\overline\theta]$, \cref{cor:myerson} lets payments be eliminated. Expected profit equals4156\[ \int\Bigl[\Bigl(\theta-\frac{1-F(\theta)}{\phi(\theta)}\Bigr)x(\theta)-C(x(\theta))\Bigr]\phi(\theta)\,d\theta \]4157less the utility of the lowest type, to be maximized over nondecreasing $x(\cdot)$. The seller behaves as if4158each type's willingness to pay were the \term{virtual type} $\theta-\frac{1-F}{\phi}$: the true type less4159the marginal rent that an increase in her allocation gives to all higher types. If the virtual type is4160increasing, pointwise maximization gives $C'(x(\theta))=\theta-\frac{1-F(\theta)}{\phi(\theta)}$: no distortion at4161the top, downward distortion everywhere else, exclusion of types whose virtual type is negative. If it is4162not increasing, the monotonicity constraint binds and the solution is obtained by \emph{ironing}:4163replacing the integrated virtual type by its convex hull \cite{Mye81,MR84}---a closure under the Galois4164connection of \cref{prop:nucleus} once more.4165 4166\begin{example}\label{ex:screening-cont}4167With $\theta$ uniform on $[0,1]$ and $C(x)=\tfrac12x^2$, the virtual type is $2\theta-1$ and4168$x(\theta)=\max\{0,2\theta-1\}$. Types below $\tfrac12$ are excluded. The payment is $t(\theta)=\theta^2-\tfrac14$,4169which as a tariff on quantities is $p(x)=\tfrac12x+\tfrac14x^2$, and the profit is $\tfrac1{12}$.4170\end{example}4171 4172The same analysis, with a regulator in the role of the seller and a firm with private cost in the role of4173the buyer, gives the theory of regulation under asymmetric information \cite{BM82,LT86}: the optimal4174policy offers a menu, efficient firms choose high-powered contracts and earn rents, inefficient firms are4175given low-powered contracts and produce too little, and the regulator's problem is the trade-off between4176rent extraction and efficiency expressed by the virtual type.4177 4178\section{Many agents: Groves mechanisms}4179 4180Let agents $i=1,\dots,n$ have valuations $v_i(x,\theta_i)$ for a collective decision $x$. An efficient decision4181rule $x^*(\theta)$ maximizes $\sum_iv_i(x,\theta_i)$.4182 4183\begin{theorem}[Vickrey--Clarke--Groves]\label{thm:groves}\Scl[\cite{Vic61,Cla71,Gro73,GL77}]4184For any functions $h_i$ of the others' reports, the payments4185\[ t_i(\theta)=h_i(\theta_{-i})-\sum_{j\neq i}v_j\bigl(x^*(\theta),\theta_j\bigr) \]4186make truthful reporting a dominant strategy for every agent. If the type spaces are smoothly connected,4187every efficient mechanism with truth-telling in dominant strategies has this form. In general no choice of4188the $h_i$ balances the budget.4189\end{theorem}4190 4191\begin{proof}[Proof of the first claim]4192Agent $i$'s payoff from reporting $\theta_i'$ is4193\[ \sum_jv_j\bigl(x^*(\theta_i',\theta_{-i}),\theta_j\bigr)-h_i(\theta_{-i}), \]4194total surplus at the decision her report induces, minus a term she cannot affect. Truth induces the4195surplus-maximizing decision.4196\end{proof}4197 4198Three threads of this book meet in the proof. The payment adds to $v_i$ a function of the others'4199valuations, so that agent $i$'s payoff becomes incentive equivalent, in the sense of4200\cref{def:equivalences}, to the common objective: the mechanism turns the game into one of common interest4201without changing anyone's intrinsic preferences. The uniqueness clause is revenue equivalence4202(\cref{thm:rochet}(d)) applied agent by agent: once the decision rule is fixed, the payments are determined4203up to a constant in own type, that is, up to $h_i$. And the failure of budget balance is the team problem4204of \cref{thm:teams}: each agent is made residual claimant of the whole surplus, and there is only one4205surplus.4206 4207\begin{example}[The pivot mechanism]4208A project costing $10$ is to be financed by equal shares if built. Two agents value it at $\theta_1=9$ and4209$\theta_2=3$, so their net values are $+4$ and $-2$; the efficient decision is to build. Choosing $h_i$ to be4210the others' best attainable net surplus without $i$ gives the \emph{pivot} payments: agent~1, whose presence4211changes the decision and thereby imposes a loss of $2$ on agent~2, pays $2$ on top of her share; agent~24212pays nothing extra. The designer collects a surplus of $2$ that cannot be returned to the agents without4213disturbing their incentives.4214\end{example}4215 4216\section*{Notes}4217 4218The revelation principle is due to Gibbard \cite{Gib73} for dominant strategies and to Myerson4219\cite{Mye79} and others for Bayesian equilibrium. Rochet \cite{Roc87} characterized implementability in4220quasi-linear environments by cyclic monotonicity; the graph-theoretic view was developed by Vohra and4221coauthors \cite{Voh11}, and revenue equivalence characterized in \cite{HMUV09}. The envelope formula in4222generality is due to Milgrom and Segal \cite{MS02}. Lawvere's enriched reading of metric spaces is4223\cite{Law73} and Willerton's of the Legendre transform \cite{Wil15}; generalized convexity in the4224principal--agent problem is from \cite{Car01}, and the link with optimal transport is exploited in4225\cite{FKM11}. Optimal nonlinear pricing is due to Mussa and Rosen \cite{MR78} and Maskin and Riley4226\cite{MR84}; optimal regulation to Baron and Myerson \cite{BM82} and Laffont and Tirole \cite{LT86}. The4227efficient mechanisms are from \cite{Vic61,Cla71,Gro73}, with uniqueness in \cite{GL77}. The statement of4228the revelation principle as an initial object, and of incentive-compatible payments as enriched4229copresheaves, are reformulations for which we know no reference but which are immediate from the cited4230results.4231 4232\section*{Exercises}4233 4234\begin{exercise}4235State and prove \cref{thm:revelation} for $n$ agents and Bayesian Nash equilibrium, making explicit the4236interim utility functions to which part (i) is applied.4237\end{exercise}4238\begin{exercise}4239For three types $\theta\in\{1,2,3\}$ with $v=\theta x$ and allocation $(x_1,x_2,x_3)=(0,1,3)$, compute the4240incentive category $\Theta_f$ (all nine hom-values), the set of incentive-compatible payment rules with