Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 3959–4058 of 6559. Source text is displayed literally.
3959 3960Fix $f$ and consider the category $\mathsf{Impl}(f)$ whose objects are triples $(M,g,\sigma)$ with $\sigma$ a best3961response in $(M,g)$ and $g\sigma=f$, and whose morphisms $(M,g,\sigma)\to(M',g',\sigma')$ are maps3962$h\colon M\to M'$ with $g'h=g$ and $h\sigma=\sigma'$.3963 3964\begin{theorem}[Revelation principle]\label{thm:revelation}\Srf[\cite{Gib73,Mye79}]3965\begin{enumerate}[label=(\roman*)]3966\item (Best responses pull back.) Let $\sigma$ be a best response in $(M,g)$ and let $h\colon M'\to M$ be any map3967 such that $\sigma=h\sigma'$ for some $\sigma'\colon\Theta\to M'$. Then $\sigma'$ is a best response in $(M',gh)$.3968\item (Direct mechanisms are initial.) If $\mathsf{Impl}(f)$ is nonempty, then $(\Theta,f,\id_\Theta)$ is an3969 object of it, and is initial.3970\end{enumerate}3971Hence $f$ is implementable by some mechanism if and only if it is \term{incentive compatible}:3972\[ U(f(\theta),\theta)\ \ge\ U(f(\theta'),\theta)\qquad\text{for all }\theta,\theta'. \]3973\end{theorem}3974 3975\begin{proof}3976(i) Every deviation in $M'$ maps under $h$ to a deviation in $M$:3977$U(gh(m'),\theta)\le U(g\sigma(\theta),\theta)=U(gh\sigma'(\theta),\theta)$.3978(ii) Given $(M,g,\sigma)$, apply (i) with $M'=\Theta$, $h=\sigma$, $\sigma'=\id$: truth-telling is a best response in3979the direct mechanism $(\Theta,g\sigma)=(\Theta,f)$. The map $\sigma$ is a morphism $(\Theta,f,\id)\to(M,g,\sigma)$, and3980any morphism $k$ from the direct mechanism satisfies $k=k\circ\id=\sigma$.3981\end{proof}3982 3983The two halves have different characters. Initiality is formal: any implementation receives a unique map3984from the direct one. The content is in (i): the equilibrium property is stable under pulling a mechanism3985back along a map through which the equilibrium factors, because restricting the message space can only3986remove deviations. Being an equilibrium is a property that is \emph{contravariant} in the mechanism. With3987several agents the same argument applies to each agent's interim problem (Bayesian implementation) or3988state by state (dominant strategies), and the conclusion is the same.3989 3990It is as well to be clear about what the principle does not say. It says nothing about \emph{other}3991equilibria of the direct mechanism; implementation in all equilibria is a harder problem with its own3992theory. It assumes that the designer can commit to $g$; without commitment the designer is a player and3993the principle fails (\cref{ch:moralhazard2,ch:pricing}). And it treats communication as free.3994 3995\section{Transfers: the incentive metric}\label{sec:incentive-metric}3996 3997Suppose outcomes are pairs of an allocation $x\in X$ and a payment $t\in\R$, and utility is quasi-linear,3998$U=v(x,\theta)-t$. A direct mechanism is an allocation rule $f\colon\Theta\to X$ with a payment rule3999$t\colon\Theta\to\R$, and incentive compatibility reads4000\begin{equation}\label{eq:IC}4001t(\theta)-t(\theta')\ \le\ \ell_f(\theta',\theta)\defeq v(f(\theta),\theta)-v(f(\theta'),\theta)\qquad\text{for all }\theta,\theta'.4002\end{equation}4003The number $\ell_f(\theta',\theta)$ is what type $\theta$ gains from receiving her own allocation rather than4004that of $\theta'$. Read \eqref{eq:IC} as a system of difference constraints on a complete directed graph4005with vertex set $\Theta$ and arc lengths $\ell_f$: payments are a \emph{potential}, a function whose increase4006along each arc is at most the arc's length.4007 4008Recall from \cref{sec:banach} that a category enriched in $([0,\infty],\ge,+)$ is a generalized metric4009space. Lengths here may be negative, so enrich instead in the extended reals4010$\Rbar=([-\infty,\infty],\ge,+)$, as in Lawvere's treatment of the Legendre transform \cite{Law73,Wil15}. An4011$\Rbar$-category is a set with a function $d$ to $\Rbar$ satisfying $d(a,b)+d(b,c)\ge d(a,c)$ and $0\ge d(a,a)$.4012The free $\Rbar$-category on a weighted graph is its shortest-path closure.4013 4014\begin{definition}4015The \term{incentive category} $\Theta_f$ of an allocation rule $f$ is the free $\Rbar$-category on the graph4016$(\Theta,\ell_f)$: its hom-values are4017\[ d_f(\theta',\theta)=\inf\Bigl\{\textstyle\sum_{j=1}^k\ell_f(\theta_{j-1},\theta_j)\ \Bigm|\ \theta'=\theta_0,\theta_1,\dots,\theta_k=\theta\Bigr\}. \]4018\end{definition}4019 4020\begin{theorem}[Implementability and revenue equivalence, enriched]\label{thm:rochet}\Srf[\cite{Roc87,HMUV09,Voh11}]4021Let $f\colon\Theta\to X$ be an allocation rule.4022\begin{enumerate}[label=(\alph*)]4023\item There is a payment rule making $f$ incentive compatible if and only if the graph $(\Theta,\ell_f)$ has4024 no cycle of negative length; equivalently $d_f(\theta,\theta)=0$ for all $\theta$; equivalently $d_f$ never4025 takes the value $-\infty$. (\emph{Cyclic monotonicity.})4026\item The incentive-compatible payment rules for $f$ are exactly the real-valued $\Rbar$-functors4027 $\Theta_f\to\Rbar$, that is, the functions $t$ with $t(\theta)-t(\theta')\le d_f(\theta',\theta)$.4028\item For each $\theta_0$, the corepresentable $d_f(\theta_0,-)$ is the pointwise greatest4029 incentive-compatible payment rule vanishing at $\theta_0$, and $-d_f(-,\theta_0)$ is the least.4030\item (\emph{Revenue equivalence.}) Any two incentive-compatible payment rules for $f$ differ by a constant4031 if and only if $d_f(\theta,\theta')+d_f(\theta',\theta)=0$ for all $\theta,\theta'$: every hom-value of $\Theta_f$ is4032 invertible, with inverse the hom-value in the opposite direction.4033\end{enumerate}4034\end{theorem}4035 4036\begin{proof}4037(b) A function satisfies the constraint on every arc iff it satisfies it along every path, iff it4038satisfies it for the infimum over paths. (a) Summing \eqref{eq:IC} around a cycle shows that a potential4039forces every cycle to have nonnegative length. Conversely if there are no negative cycles then $d_f$ is4040finite, $d_f(\theta,\theta)=0$, and $d_f(\theta_0,-)$ satisfies (b) by the triangle inequality. (c) If $t$4041satisfies (b) and $t(\theta_0)=0$ then $t(\theta)\le d_f(\theta_0,\theta)$ and $-t(\theta)\le d_f(\theta,\theta_0)$;4042both bounds are themselves payment rules by the triangle inequality. (d) By (c) the payment rules4043vanishing at $\theta_0$ fill the interval between $-d_f(-,\theta_0)$ and $d_f(\theta_0,-)$, which is a point4044iff the two coincide.4045\end{proof}4046 4047Parts (a) and (d) are Rochet's theorem \cite{Roc87} and the characterization of revenue equivalence by4048Heydenreich, M\"uller, Uetz and Vohra \cite{HMUV09}; the network formulation is developed at length in4049\cite{Voh11}. What the enriched phrasing contributes is the identification of the objects. An allocation4050rule \emph{is} a generalized metric on the type space. A payment rule \emph{is} a copresheaf. Part (c) is the4051enriched Yoneda lemma: the payment rules are bounded by the representables, and the representable at the4052type whose participation constraint binds is the revenue-maximizing one. Condition (d) says that the4053incentive category is a groupoid in the enriched sense; it then has no room for two different potentials.4054 4055\begin{example}[Two types]\label{ex:twotype-metric}4056Let $v(x,\theta)=\theta x$ with types $\theta_L=2$, $\theta_H=3$ and allocation $f(\theta_L)=1$, $f(\theta_H)=3$.4057Then $\ell_f(L,H)=\theta_H(3-1)=6$ and $\ell_f(H,L)=\theta_L(1-3)=-4$. The only cycle has length $2\ge0$, so $f$ is4058implementable; $d_f(L,H)=6$, $d_f(H,L)=-4$, and the incentive-compatible payments are those with