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

3919 3920\section*{Exercises}3921 3922\begin{exercise}3923Let $\theta$ be uniform on $[0,1]$, let sellers value a car at $\theta$ and buyers at $\theta+k$ with $k>0$.3924Find all equilibrium prices as a function of $k$ and the fraction of cars traded.3925\end{exercise}3926\begin{exercise}3927Construct a distribution of quality for which $\Phi$ has three fixed points, and verify that they are3928Pareto-ranked.3929\end{exercise}3930\begin{exercise}3931In \cref{ex:RS}, verify $\alpha^*$, compute both types' expected utilities at the separating pair and at3932full insurance at the pooled fair premium when $\lambda=0.1$, and confirm that the pooling contract would3933attract both.3934\end{exercise}3935\begin{exercise}3936In \cref{ex:GM} let the asset be worth $1$ with prior probability $\pi$. Compute the bid and the ask, and3937the market maker's posterior after two consecutive buy orders.3938\end{exercise}3939\begin{exercise}3940In \cref{ex:kyle}, compute the insider's expected profit and the expected loss of the noise traders, and3941show that they are equal. How do they depend on $\sigma_u$?3942\end{exercise}3943%% ---- end ch/13-adverse.tex ----3944%% ---- begin ch/14-mechanism.tex ----3945\chapter{Mechanism Design}\label{ch:mechanism}3946 3947So far the game has been given and the equilibrium sought. Mechanism design reverses the problem: an3948outcome is wanted, as a function of information the designer does not have, and the question is whether3949some game has it as an equilibrium. The answer is organized by one principle, which reduces the search3950over all games to a system of inequalities, and by the structure of that system, which turns out to be a3951piece of enriched category theory.3952 3953\section{The revelation principle}3954 3955An agent has a type $\theta\in\Theta$, known only to her, and utility $U(y,\theta)$ over outcomes $y\in Y$. A3956\term{mechanism} is a set $M$ of messages with an outcome function $g\colon M\to Y$. A strategy is a map3957$\sigma\colon\Theta\to M$; it is a best response if $U(g\sigma(\theta),\theta)\ge U(g(m),\theta)$ for all3958$\theta$ and $m$. The mechanism then \term{implements} the social choice function $f=g\circ\sigma\colon\Theta\to Y$.3959 3960Fix $f$ and consider the category $\mathsf{Impl}(f)$ whose objects are triples $(M,g,\sigma)$ with $\sigma$ a best3961response in $(M,g)$ and $g\sigma=f$, and whose morphisms $(M,g,\sigma)\to(M',g',\sigma')$ are maps3962$h\colon M\to M'$ with $g'h=g$ and $h\sigma=\sigma'$.3963 3964\begin{theorem}[Revelation principle]\label{thm:revelation}\Srf[\cite{Gib73,Mye79}]3965\begin{enumerate}[label=(\roman*)]3966\item (Best responses pull back.) Let $\sigma$ be a best response in $(M,g)$ and let $h\colon M'\to M$ be any map3967  such that $\sigma=h\sigma'$ for some $\sigma'\colon\Theta\to M'$. Then $\sigma'$ is a best response in $(M',gh)$.3968\item (Direct mechanisms are initial.) If $\mathsf{Impl}(f)$ is nonempty, then $(\Theta,f,\id_\Theta)$ is an3969  object of it, and is initial.3970\end{enumerate}3971Hence $f$ is implementable by some mechanism if and only if it is \term{incentive compatible}:3972\[ U(f(\theta),\theta)\ \ge\ U(f(\theta'),\theta)\qquad\text{for all }\theta,\theta'. \]3973\end{theorem}3974 3975\begin{proof}3976(i) Every deviation in $M'$ maps under $h$ to a deviation in $M$:3977$U(gh(m'),\theta)\le U(g\sigma(\theta),\theta)=U(gh\sigma'(\theta),\theta)$.3978(ii) Given $(M,g,\sigma)$, apply (i) with $M'=\Theta$, $h=\sigma$, $\sigma'=\id$: truth-telling is a best response in3979the direct mechanism $(\Theta,g\sigma)=(\Theta,f)$. The map $\sigma$ is a morphism $(\Theta,f,\id)\to(M,g,\sigma)$, and3980any morphism $k$ from the direct mechanism satisfies $k=k\circ\id=\sigma$.3981\end{proof}3982 3983The two halves have different characters. Initiality is formal: any implementation receives a unique map3984from the direct one. The content is in (i): the equilibrium property is stable under pulling a mechanism3985back along a map through which the equilibrium factors, because restricting the message space can only3986remove deviations. Being an equilibrium is a property that is \emph{contravariant} in the mechanism. With3987several agents the same argument applies to each agent's interim problem (Bayesian implementation) or3988state by state (dominant strategies), and the conclusion is the same.3989 3990It is as well to be clear about what the principle does not say. It says nothing about \emph{other}3991equilibria of the direct mechanism; implementation in all equilibria is a harder problem with its own3992theory. It assumes that the designer can commit to $g$; without commitment the designer is a player and3993the principle fails (\cref{ch:moralhazard2,ch:pricing}). And it treats communication as free.3994 3995\section{Transfers: the incentive metric}\label{sec:incentive-metric}3996 3997Suppose outcomes are pairs of an allocation $x\in X$ and a payment $t\in\R$, and utility is quasi-linear,3998$U=v(x,\theta)-t$. A direct mechanism is an allocation rule $f\colon\Theta\to X$ with a payment rule3999$t\colon\Theta\to\R$, and incentive compatibility reads4000\begin{equation}\label{eq:IC}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}