The 36th Stony Brook game theory conference features the New Perspectives on Algorithmic Game Theory Workshop. One of the most anticipated talks is Professor Gonczarowski’s “Quantifying Inefficiency,”

Here’s my note:

Setup

A context is a pair $C=\bigl(X,(\succsim_i)_{i=1}^{n}\bigr)$ where $X$ is a nonempty finite set of alternatives, $n\in\mathbb{N}$, and each $\succsim_i$ is a preference over $\Delta(X)$ satisfying the von Neumann–Morgenstern axioms (hence admitting an expected-utility representation $u_i$, unique up to positive affine transformation).

Can the vNM also encompasses risk aversion characterization?

The Pareto frontier $F_C\subseteq\Delta(X)$ is the set of $x\in\Delta(X)$ for which no $x'\in\Delta(X)$ satisfies $x'\succsim_i x$ for all $i$ with $x'\succ_i x$ for some $i$.

Definition (social inefficiency function). A social inefficiency function assigns to every context $C$ and every $x\in\Delta(X)$ a value $I(C,x)\in\mathbb{R}_{\ge 0}\cup\{\infty\}$.

The function $\hat I$

Fix any vNM representations $u_1,\dots,u_n$. Let $u_i^{\max}=\max_{x\in F_C}u_i(x)$ and $u_i^{\min}=\min_{x\in F_C}u_i(x)$, and define

$$V(C,x)=\frac{1}{n}\sum_{i=1}^{n}\frac{u_i(x)-u_i^{\min}}{u_i^{\max}-u_i^{\min}},\qquad \hat I(C,x)=\max_{x'\in X}V(C,x')-V(C,x).$$
u₁u₂u₁ min = 0u₁ max = 110Pareto frontierV maxV at xbest alternative (tangency)xinefficiencyof x
I(C,x) is the gap between the tangent line and the parallel line through x.

Characterizations

Let $C^1\oplus C^2$ denotes the composition of two contexts on $X^1\times X^2$ with disjoint individuals, each caring only about the marginal on their own context.

A1 — Pareto monotonicity. If $x\succsim_i y$ for all $i$, then $I(C,x)\le I(C,y)$; if moreover $x\succ_i y$ for some $i$, then $I(C,x)

A2 — Anonymity. For any permutation $\pi$ of $\{1,\dots,n\}$: $I\bigl((X,(\succsim_{\pi(i)})_{i=1}^n),x\bigr)=I(C,x)$ for all $x\in\Delta(X)$.

A3 — Expected inefficiency. $I\bigl(C,\alpha x+(1-\alpha)y\bigr)=\alpha\, I(C,x)+(1-\alpha)\, I(C,y)$ for all $x,y\in\Delta(X)$, $\alpha\in[0,1]$.

A4 — Independence of irrelevant alternatives. Let $\emptyset\ne X'\subset X$ and $C'=\bigl(X',(\succsim_i|_{\Delta(X')})_{i=1}^n\bigr)$. If $C$ and $C'$ have the same ideal point ($\max_{\succsim_i}X'\sim_i\max_{\succsim_i}X$ for all $i$) and the same point of minimal expectations ($\min_{\succsim_i}F_{C'}\sim_i\min_{\succsim_i}F_C$ for all $i$), then $I(C',x)-I(C',y)=I(C,x)-I(C,y)$ for all $x,y\in\Delta(X')$. (Both reference points are the endogenous ones of Roth, 1977.)

A5 — Independence of irrelevant preferences. For contexts $D=\bigl(Y,(\succsim_i)_{i=1}^m\bigr)$ and $D'=\bigl(Y,(\succsim_i')_{i=1}^m\bigr)$ on the same alternatives and number of individuals: $I\bigl(C\oplus D,(x,y)\bigr)-I\bigl(C\oplus D,(x',y)\bigr)=I\bigl(C\oplus D',(x,y)\bigr)-I\bigl(C\oplus D',(x',y)\bigr)$ for all $x,x'\in\Delta(X)$, $y\in\Delta(Y)$.

A6 — Population-size stability. For every $k\in\mathbb{N}$: $I\bigl(\oplus_{j=1}^{k}C,(x,\dots,x)\bigr)-I\bigl(\oplus_{j=1}^{k}C,(x',\dots,x')\bigr)=I(C,x)-I(C,x')$ for all $x,x'\in\Delta(X)$.

A7 — Feasibility. For every context $C$ there exists $x\in\Delta(X)$ with $I(C,x)=0$.

NOTE: all contributions are by the OG author. All mistakes are mine.

Theorem 1. A social inefficiency function $I$ satisfies A1–A7 if and only if there exists a constant $0

Some thoughts:

The assumption that $X$ needs to be finite generalizes easily to compact $X$ with continuous preference (cause I think the only thing we need from the finiteness is that max and min over the frontier still exist). Axiom 3 is very strong because it imposes vNM style linearity: I(αx + (1−α)y) = αI(x) + (1−α)I(y). This along with vNM on $\Delta(X)$ jointly did a lot of heavy lifting.

This measure is not a replacement for PoA though. PoA is also measure free and only requires two points. This inefficiency measure captures more structure. It should be a pro when alternatives are finite and preference is ordinal. But for well-measured game like auctions PoA should still be a cleaner metric — for now.