Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 4081–4180 of 6559. Source text is displayed literally.
4081monotone $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 less4159the 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 decision