Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 4021–4120 of 6559. Source text is displayed literally.
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 rule4101when a cocycle is trivial and a sign condition holds. In both, the obstruction lives in loops, and4102uniqueness of the potential is a statement about connected components.4103 4104\section{Duality: prices and utilities}4105 4106There is a second description of the same structure, in which the mechanism is a price list rather than a4107direct revelation game. A \emph{tariff} is a function $p\colon X\to\Rbar$; faced with it, type $\theta$ obtains4108\[ p^v(\theta)=\sup_{x}\bigl[v(x,\theta)-p(x)\bigr]. \]4109Conversely a utility profile $U\colon\Theta\to\Rbar$ determines the tariff4110$U^v(x)=\sup_\theta[v(x,\theta)-U(\theta)]$, the lowest prices at which no type would do better than $U$.4111 4112\begin{proposition}[Taxation principle as a nucleus]\label{prop:nucleus}\Srf[\cite{Roc87,Car01,Wil15}]4113The maps $p\mapsto p^v$ and $U\mapsto U^v$ form a Galois connection between tariffs on $X$ and utility4114profiles on $\Theta$: the adjunction induced by the valuation $v$ regarded as an $\Rbar$-profunctor from $X$4115to $\Theta$. Its closed elements on the utility side, the profiles with $U=(U^v)^v$, are the4116\term{$v$-convex} functions, and4117\begin{enumerate}[label=(\roman*)]4118\item an allocation rule $f$ is implementable iff there is a $v$-convex $U$ with $f(\theta)$ in the4119 $v$-subdifferential of $U$ at every $\theta$, that is, $U(\theta')\ge U(\theta)+v(f(\theta),\theta')-v(f(\theta),\theta)$;4120\item every incentive-compatible direct mechanism is equivalent to letting the agent choose from a tariff,