Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 4159–4258 of 6559. Source text is displayed literally.
4159the 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 with4241$t_1=0$, and the greatest one. Check the triangle inequality.4242\end{exercise}4243\begin{exercise}4244Discretize $[0,1]$ into $n$ equally spaced types and let $x(\theta)=\theta$. Compute $d_f(0,1)+d_f(1,0)$ as a4245function of $n$ and verify that it tends to zero.4246\end{exercise}4247\begin{exercise}4248Show that $p\mapsto p^v$ and $U\mapsto U^v$ are order-reversing and that $p^{vvv}=p^v$. For $v=\theta x$ on4249$X=\Theta=\R$, compute the tariff conjugate to $U(\theta)=\tfrac12\theta^2$.4250\end{exercise}4251\begin{exercise}4252Verify \cref{ex:screening-cont}, and compute the seller's profit if she is restricted to offering a single4253bundle: one quantity $x$ at one price $t$.4254\end{exercise}4255\begin{exercise}4256In the pivot mechanism for a binary public project with $n$ agents, show that the payments are4257nonnegative, that at most the pivotal agents pay, and that truthful reporting remains optimal even if an4258agent knows the others' reports.