Hat Guessing Games

NEW

Problem: Reconstructed statement: in the complete-visibility limited-supply hat game, there are $n\ge1$ labelled players, $k\ge1$ colors, and the adversary may use at most $a_i$ hats of color $i$, where $0<a_i\le n$ and $\sum_i a_i\ge n$. Let $H(n;a_1,\dots,a_k)$ be the maximum, over deterministic strategies, of the minimum number of correct guesses over all colorings $x\in[k]^n$ satisfying $|x^{-1}(i)|\le a_i$. The paper’s Theorem 16(vi) gives the upper bound

$$H(n;\mathbf a)\le \left\lfloor \frac{nV_{n-1}(\mathbf a)}{V_n(\mathbf a)} \right\rfloor ,$$

where

$$V_m(\mathbf a)= \sum_{\substack{b_1+\cdots+b_k=m\\0\le b_i\le a_i}} \binom{m}{b_1,\dots,b_k}.$$

The question asks whether this bound is always tight.

Result: Yes. For all admissible $n,k,\mathbf a$,

$$\boxed{ H(n;a_1,\dots,a_k)= \left\lfloor \frac{nV_{n-1}(\mathbf a)}{V_n(\mathbf a)} \right\rfloor . }$$

Proof sketch. Let $R$ be the set of valid full placements, so $|R|=V_n(\mathbf a)$. Let $L$ be the set of valid player-views: a choice of one hidden position and a valid coloring of the other $n-1$ positions. Then $|L|=nV_{n-1}(\mathbf a)$. A deterministic strategy is exactly an assignment of each $l\in L$ to at most one adjacent $x\in R$. The number of correct guesses on $x$ is the indegree of $x$.

The averaging argument gives the stated upper bound.

For the lower bound, let $\alpha=|L|/|R|$. It suffices, by Hall’s theorem applied to $r=\lfloor\alpha\rfloor$ copies of every $x\in R$, to show

$$|N(X)|\ge \alpha |X| \qquad \forall X\subseteq R.$$

This normalized matching inequality holds. If it failed, minimizing the submodular function

$$F(X)=|N(X)|-\alpha|X|$$

and intersecting over all permutations of the $n$ player positions would give a nonempty minimizing counterexample invariant under all player permutations. Such an $X$ is a union of count layers.

For count layers, write

$$D_m=\{b\in\mathbb N^k:\ |b|=m,\ b_i\le a_i\}, \qquad \mu_m(b)=\binom{m}{b_1,\dots,b_k}/V_m(\mathbf a).$$

We need

$$\mu_{n-1}(\partial C)\ge \mu_n(C)$$

for every $C\subseteq D_n$, where $\partial C=\{b\in D_{n-1}:b+e_i\in C\text{ for some }i\}$.

Let $Z_i$ be independent truncated Poisson-type variables with

$$\Pr(Z_i=t)\propto \frac1{t!},\qquad 0\le t\le a_i.$$

Their laws are log-concave. Conditional on $\sum_i Z_i=m$, the law of $(Z_1,\dots,Z_k)$ is exactly $\mu_m$. By Efron’s monotonicity theorem for independent log-concave variables, $\mu_n$ stochastically dominates $\mu_{n-1}$ in the coordinatewise order. By Strassen’s coupling theorem, there is a coupling $(B,C)$ with $B\sim\mu_{n-1}$, $C\sim\mu_n$, and $B\le C$. Since $|C|=|B|+1$, necessarily $C=B+e_i$ for some $i$. Hence $C\in C_0\Rightarrow B\in\partial C_0$, proving the count-shadow inequality.

Thus Hall’s condition holds, so there is a matching assigning $r$ distinct adjacent views to every valid placement. Orienting those views toward their matched placements gives a legal deterministic strategy with at least $r$ correct guesses on every valid placement. Therefore the upper bound is tight.

Verification audit: the reconstruction uses the paper’s “at most $a_i$” interpretation, matching the sums $b_i\le a_i$ in Theorem 16(vi). Degenerate cases agree: exact supply $\sum a_i=n$ gives $H=n$; unlimited supply $a_i=n$ gives $H=\lfloor n/k\rfloor$; and $H(5;4,3)=3$.

Citation: Butler, Hajiaghayi, Kleinberg, and Leighton, “Hat Guessing Games,” SIAM J. Discrete Math. 22(2), 592–605, 2008. Efron, “Increasing properties of Pólya frequency functions,” Ann. Math. Statist. 36 (1965), 272–279. Strassen, “The existence of probability measures with given marginals,” Ann. Math. Statist. 36 (1965), 423–439.