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 4121–4220 of 6559. Source text is displayed literally.

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 decision4181rule $x^*(\theta)$ maximizes $\sum_iv_i(x,\theta_i)$.4182 4183\begin{theorem}[Vickrey--Clarke--Groves]\label{thm:groves}\Scl[\cite{Vic61,Cla71,Gro73,GL77}]4184For any functions $h_i$ of the others' reports, the payments4185\[ t_i(\theta)=h_i(\theta_{-i})-\sum_{j\neq i}v_j\bigl(x^*(\theta),\theta_j\bigr) \]4186make truthful reporting a dominant strategy for every agent. If the type spaces are smoothly connected,4187every efficient mechanism with truth-telling in dominant strategies has this form. In general no choice of4188the $h_i$ balances the budget.4189\end{theorem}4190 4191\begin{proof}[Proof of the first claim]4192Agent $i$'s payoff from reporting $\theta_i'$ is4193\[ \sum_jv_j\bigl(x^*(\theta_i',\theta_{-i}),\theta_j\bigr)-h_i(\theta_{-i}), \]4194total surplus at the decision her report induces, minus a term she cannot affect. Truth induces the4195surplus-maximizing decision.4196\end{proof}4197 4198Three threads of this book meet in the proof. The payment adds to $v_i$ a function of the others'4199valuations, so that agent $i$'s payoff becomes incentive equivalent, in the sense of4200\cref{def:equivalences}, to the common objective: the mechanism turns the game into one of common interest4201without changing anyone's intrinsic preferences. The uniqueness clause is revenue equivalence4202(\cref{thm:rochet}(d)) applied agent by agent: once the decision rule is fixed, the payments are determined4203up to a constant in own type, that is, up to $h_i$. And the failure of budget balance is the team problem4204of \cref{thm:teams}: each agent is made residual claimant of the whole surplus, and there is only one4205surplus.4206 4207\begin{example}[The pivot mechanism]4208A project costing $10$ is to be financed by equal shares if built. Two agents value it at $\theta_1=9$ and4209$\theta_2=3$, so their net values are $+4$ and $-2$; the efficient decision is to build. Choosing $h_i$ to be4210the others' best attainable net surplus without $i$ gives the \emph{pivot} payments: agent~1, whose presence4211changes the decision and thereby imposes a loss of $2$ on agent~2, pays $2$ on top of her share; agent~24212pays nothing extra. The designer collects a surplus of $2$ that cannot be returned to the agents without4213disturbing their incentives.4214\end{example}4215 4216\section*{Notes}4217 4218The revelation principle is due to Gibbard \cite{Gib73} for dominant strategies and to Myerson4219\cite{Mye79} and others for Bayesian equilibrium. Rochet \cite{Roc87} characterized implementability in4220quasi-linear environments by cyclic monotonicity; the graph-theoretic view was developed by Vohra and