Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 4181–4280 of 6559. Source text is displayed literally.
4181rule $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 and4221coauthors \cite{Voh11}, and revenue equivalence characterized in \cite{HMUV09}. The envelope formula in4222generality is due to Milgrom and Segal \cite{MS02}. Lawvere's enriched reading of metric spaces is4223\cite{Law73} and Willerton's of the Legendre transform \cite{Wil15}; generalized convexity in the4224principal--agent problem is from \cite{Car01}, and the link with optimal transport is exploited in4225\cite{FKM11}. Optimal nonlinear pricing is due to Mussa and Rosen \cite{MR78} and Maskin and Riley4226\cite{MR84}; optimal regulation to Baron and Myerson \cite{BM82} and Laffont and Tirole \cite{LT86}. The4227efficient mechanisms are from \cite{Vic61,Cla71,Gro73}, with uniqueness in \cite{GL77}. The statement of4228the revelation principle as an initial object, and of incentive-compatible payments as enriched4229copresheaves, are reformulations for which we know no reference but which are immediate from the cited4230results.4231 4232\section*{Exercises}4233 4234\begin{exercise}4235State and prove \cref{thm:revelation} for $n$ agents and Bayesian Nash equilibrium, making explicit the4236interim utility functions to which part (i) is applied.4237\end{exercise}4238\begin{exercise}4239For three types $\theta\in\{1,2,3\}$ with $v=\theta x$ and allocation $(x_1,x_2,x_3)=(0,1,3)$, compute the4240incentive category $\Theta_f$ (all nine hom-values), the set of incentive-compatible payment rules with4241$t_1=0$, and the greatest one. Check the triangle inequality.4242\end{exercise}4243\begin{exercise}4244Discretize $[0,1]$ into $n$ equally spaced types and let $x(\theta)=\theta$. Compute $d_f(0,1)+d_f(1,0)$ as a4245function of $n$ and verify that it tends to zero.4246\end{exercise}4247\begin{exercise}4248Show that $p\mapsto p^v$ and $U\mapsto U^v$ are order-reversing and that $p^{vvv}=p^v$. For $v=\theta x$ on4249$X=\Theta=\R$, compute the tariff conjugate to $U(\theta)=\tfrac12\theta^2$.4250\end{exercise}4251\begin{exercise}4252Verify \cref{ex:screening-cont}, and compute the seller's profit if she is restricted to offering a single4253bundle: one quantity $x$ at one price $t$.4254\end{exercise}4255\begin{exercise}4256In the pivot mechanism for a binary public project with $n$ agents, show that the payments are4257nonnegative, that at most the pivotal agents pay, and that truthful reporting remains optimal even if an4258agent knows the others' reports.4259\end{exercise}4260%% ---- end ch/14-mechanism.tex ----4261%% ---- begin ch/15-signalling.tex ----4262\chapter{Signalling}\label{ch:signalling}4263 4264If the informed party moves first, her action can reveal what she knows. Whether it does, and how much, is4265determined in equilibrium: the meaning of a signal is the Bayesian inverse of the strategy that produces4266it. This chapter treats four models of strategic information transmission, ordered by how much the sender4267can commit: costly signals, costless messages, signals whose meaning the sender designs in advance, and4268signals that the sender distorts in secret.4269 4270\section{Signalling games}4271 4272Nature draws a type $\theta\in\Theta$ from a prior $\pi$. The sender observes $\theta$ and chooses a signal $e\in E$;4273the receiver observes $e$ and chooses an action $a$. A sender strategy is a kernel4274$\sigma\colon\Theta\to E$. The receiver's belief after $e$ is $\mu(e)\in\Dist\Theta$, and in a perfect Bayesian4275equilibrium $\mu$ is the Bayesian inverse $\sigma^\dagger_\pi$ wherever that is defined, the receiver best-responds4276to $\mu$, and the sender best-responds to the receiver.4277 4278The classical trichotomy of equilibria is a trichotomy of kernels. In a \term{separating} equilibrium $\sigma$4279is an injective function, so the inverse is deterministic and the receiver learns the type. In a4280\term{pooling} equilibrium $\sigma$ is constant, the inverse is the prior, and the receiver learns nothing. In