Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 4059–4158 of 6559. Source text is displayed literally.
4059$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,4121 and conversely.4122\end{enumerate}4123When $v(x,\theta)=\langle x,\theta\rangle$ the transform is the Legendre--Fenchel conjugate, $v$-convex means4124convex and lower semicontinuous, and (i) is Rockafellar's theorem that the cyclically monotone4125correspondences are those contained in the subdifferential of a convex function.4126\end{proposition}4127 4128Willerton \cite{Wil15} observed that the Legendre--Fenchel transform is the nucleus of the pairing between4129a vector space and its dual, viewed as a profunctor enriched in $\Rbar$; the proposition says that4130nonlinear pricing is the same construction for the valuation. The dual pair of descriptions---the4131agent's indirect utility on the type space, the designer's tariff on the allocation space---is an instance4132of the duality between presheaves and copresheaves that a profunctor always induces. In the theory of4133optimal transport the same transforms appear under the name of $c$-conjugates, and the modern treatment of4134multidimensional screening exploits the identification \cite{FKM11}.4135 4136\section{Optimal screening}4137 4138The designer now has an objective. A monopolist sells a quantity $x$ produced at cost $C(x)$ to a buyer4139with utility $\theta x-t$, and wants to maximize expected profit.4140 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 less