Independent scholarship · Open accessThe monthly digest

Indexed text attachment

games-and-information-in-higher-categories.tex

Source for Games and Information in Higher Categories

View paper · Download original file

Lines 4001–4100 of 6559. Source text is displayed literally.

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 with4059$4\le t_H-t_L\le6$. Revenue equivalence fails, since $6+(-4)\ne0$: with finitely many types there is slack.4060A seller who wants the largest payments consistent with the low type's participation, $t_L=\theta_L\cdot1=2$,4061takes the representable: $t_H=t_L+d_f(L,H)=8$. The ``binding downward incentive constraint'' of the4062textbooks is a shortest path from the lowest type.4063\end{example}4064 4065\section{One-dimensional types}4066 4067Let $\Theta=[\underline\theta,\overline\theta]$ and $v(x,\theta)=\theta x$, with $x\in\R$ a quantity or a4068probability of receiving a good.4069 4070\begin{corollary}[Myerson's lemma]\label{cor:myerson}\Scl[\cite{Mye81}]4071An allocation rule $x(\cdot)$ is implementable iff it is nondecreasing. The payment rule is then unique up4072to a constant:4073\[ t(\theta)=t(\underline\theta)+\int_{\underline\theta}^{\theta}s\,dx(s)4074   =\theta x(\theta)-\int_{\underline\theta}^{\theta}x(s)\,ds-\mathrm{const}, \]4075and the agent's indirect utility satisfies the envelope formula $U(\theta)=U(\underline\theta)+\int_{\underline\theta}^\theta x(s)\,ds$.4076\end{corollary}4077 4078\begin{proof}4079Here $\ell(\theta',\theta)=\theta\,(x(\theta)-x(\theta'))$. The two-cycle condition4080$\ell(\theta',\theta)+\ell(\theta,\theta')=(\theta-\theta')(x(\theta)-x(\theta'))\ge0$ is monotonicity, and for4081monotone $x$ longer cycles add nothing. For $\theta'<\theta$, a path that climbs from $\theta'$ to $\theta$4082through a fine partition has length equal to an upper Riemann--Stieltjes sum of $\int s\,dx(s)$, and refining4083decreases it; so $d(\theta',\theta)=\int_{\theta'}^\theta s\,dx(s)$. A descending path gives a lower sum with a4084minus sign, so $d(\theta,\theta')=-\int_{\theta'}^\theta s\,dx(s)$. The two are inverse, and \cref{thm:rochet}(d)4085applies.4086\end{proof}4087 4088The contrast with \cref{ex:twotype-metric} isolates what revenue equivalence needs. With two types there is one path each4089way and the lengths do not cancel. On an interval, paths can be refined without limit, and upper and lower4090sums converge to the same integral. Revenue equivalence is a consequence of the \emph{connectedness} of the4091type space.4092 4093In several dimensions, with $v$ linear in $\theta\in\R^n$, the incentive metric is obtained by integrating4094the vector field $\theta\mapsto f(\theta)$ along paths, and implementability requires two things:4095monotonicity, and that the integral around every closed loop vanish. The second is a4096flatness condition: the allocation rule must be a gradient. On a simply connected domain it can be checked4097locally; this is the content of the local-to-global theorems of mechanism design, in which weak4098monotonicity together with path-independence around small loops implies incentive compatibility4099\cite{JMS99,SY05,AK08,Car12}. The reader will recognize \cref{thm:H1}. Posteriors are local data that glue4100to a common prior when a cocycle is trivial; an allocation rule is local data that glues to a payment rule