How Much Welfare Does Private Information Really Cost? Certified Measurement of the Strategy Representability Gap

When self-interested agents each hold private information, which the literature calls their "type," total welfare is lost for two separate reasons. Agents act selfishly, and agents act without knowing what the others know. Recent theory puts an exact price on the second loss. Fujii's strategy representability gap compares two numbers: the best welfare a planner could reach if it saw everyone's type, and the best welfare reachable when each agent's action may depend only on its own type (The power of mediators; conference version here). Welfare is assumed monotone submodular, meaning each extra agent adds less when others already cover the same ground, as in facility location or influence spreading. Under that assumption the gap is exactly $1-1/e\approx 0.632$ when types are independent. When types are correlated it collapses as $\Theta(1/\sqrt{n})$ in the number of players $n$. That collapse would mean no mediator, however clever, can keep coordination efficient in large populations whose private information is linked. The result is only a worst-case construction, though, and nobody has ever computed the gap on a real instance.

This note proposes to measure the gap on realistic instances, with a guarantee attached to each measurement. The key technical point is that the second quantity in the ratio, the best "local-information" welfare, is a hard team-decision problem. A heuristic search can only underestimate it. That makes the gap look worse than it is, which is exactly the wrong direction when the question is whether the collapse is real. We therefore bracket the gap from both sides. A search over type-contingent strategies gives a lower bound. A linear-programming relaxation gives an upper bound: it allows any joint behavior whose per-agent statistics are consistent with local information. With certified intervals in hand, we can decompose observed welfare loss on standard facility-location and social-network benchmarks into an information part and an incentive part. We can then test when, if ever, realistic correlation produces the predicted $1/\sqrt{n}$ decay.

Core Claim

We claim three things. First, the strategy representability gap can be bracketed tightly enough to be useful on benchmark-scale submodular games with tens of players and small type spaces. Second, on such instances the gap is far closer to 1 than either proven bound. Third, whether it degrades with $n$ is predicted by a measurable property of the instance: how strongly a common factor drives many players' types, combined with how much those players compete over the same elements. Raw correlation alone should not predict it.

The contribution is threefold: the bracketing method, a reusable evaluation protocol, and a decomposition of welfare loss that separates "not knowing" from "not cooperating." The broader literature on unvalidated theory identifies exactly this missing piece: theoretical work that ships no code, no instance generator, and no data (Spielman et al. is the file's example of proofs whose conservative parameters diverge from practice).

Research Program

The object of study is a Bayesian game with $n$ players, a prior $p$ over type profiles $t=(t_1,\dots,t_n)$, and a welfare function $f(a,t)$ that is monotone submodular in the joint action $a$.

The full-information optimum is $\mathrm{OPT}_{FI}=\mathbb{E}_t[\max_a f(a,t)]$. Computing it is ordinary submodular maximization, applied per type profile. Greedy gives a lower bound. A standard LP or an exact integer program on small instances gives an upper bound.

The local-information optimum is $\mathrm{OPT}_{loc}=\max_{\sigma}\mathbb{E}_t[f(\sigma_1(t_1),\dots,\sigma_n(t_n),t)]$, where each $\sigma_i$ maps player $i$'s own type to an action. The gap is $\mathrm{OPT}_{loc}/\mathrm{OPT}_{FI}$.

We lower-bound $\mathrm{OPT}_{loc}$ by coordinate ascent over strategy tables with random restarts: each player in turn picks its best type-contingent rule given the others' rules. For the upper bound we use a "no-signaling" relaxation. Its variables are a joint distribution $\mu(t,a)$ and per-player conditional rules $q_i(a_i\mid t_i)$, constrained so that

$$\sum_{a_{-i}}\mu(t,a)=p(t)\,q_i(a_i\mid t_i)\quad\text{for all } i,t,a_i.$$

Here $a_{-i}$ denotes the other players' actions. The constraint says each player's action statistics depend only on its own type. It is linear because $p$ is fixed. Every true decentralized profile satisfies it, so maximizing $\sum_{t,a}\mu(t,a)f(a,t)$ over it upper-bounds $\mathrm{OPT}_{loc}$.

Enumerating joint actions would make this relaxation exponential in $n$. The benchmark welfare functions, however, are coverage sums over customers or network nodes, and each element is touched only by the few players who can reach it. We therefore write the relaxation per element over its local neighborhood, with consistency constraints on shared players, much as local polytopes are used in graphical models.

Combining the two sides gives a certified interval:

$$\frac{\text{lower bound on }\mathrm{OPT}_{loc}}{\text{upper bound on }\mathrm{OPT}_{FI}}\le \text{gap}\le\frac{\text{upper bound on }\mathrm{OPT}_{loc}}{\text{lower bound on }\mathrm{OPT}_{FI}}.$$

The width of this interval is itself a reported quantity. How tight the no-signaling relaxation is on these instances is an open empirical question, and a result of the project either way.

To separate information loss from incentive loss, we also compute the welfare reached by learning dynamics. We implement Fujii's untruthful swap regret minimization, which provably converges to communication equilibria and agent-normal-form correlated equilibria (Bayes correlated equilibria, no-regret dynamics). Equilibrium welfare divided by $\mathrm{OPT}_{loc}$ is the incentive loss. $\mathrm{OPT}_{loc}$ divided by $\mathrm{OPT}_{FI}$ is the information loss. The paper claims polynomial time, but its cost can blow up with the number of types. Recording wall-clock time and convergence gives the first empirical data point for that algorithm, which the file flags as untested.

Priors come from a generator with explicit knobs. Types are private demand estimates or cost shocks in facility location, and private interest or budget signals in influence games. They are driven by a latent-factor model whose factor loadings follow geography (distance between candidate sites) or community structure (communities detected on the graph). The knobs set the strength of a single common factor, the number of independent factors, and the per-player marginals. We also reimplement the paper's lower-bound construction as a calibration instance.

Baselines

The naive reference point is uncoordinated play: each player picks the action that is best against the prior, ignoring any coordination. Its welfare ratio to $\mathrm{OPT}_{FI}$ shows how much there is to gain at all. It runs on the same instances and priors with no tuning.

The strongest existing competitor for the numerator is centralized greedy on the realized type profile. It is the workhorse of Distributed Submodular Maximization and Consistent Submodular Maximization, and it is the natural "just ignore the game" estimator. On small instances we check it against exact integer programming. Exact methods of the kind in Competitive Facility Location under Random Utilities and Routing Constraints are feasible at this scale: that paper reports optimal solutions for 586 of 600 ORlib instances for a single firm.

For the quantity we actually target, a measured strategy representability gap, there is no reported result on Lacuna. The strongest baseline for estimating $\mathrm{OPT}_{loc}$ is therefore the obvious one: best-response or coordinate-ascent search alone, reported as a point estimate with no upper bound. Every method gets the same instances, the same restart budget, and the same wall-clock budget.

We count the method as beating this baseline if the certified interval rules out conclusions the point estimate would suggest. The clearest case is an instance where the point estimate shows $1/\sqrt{n}$ decay but the upper bound proves the true gap stays flat.

The key ablation removes correlation while keeping every player's type marginals identical, so any change in the gap is attributable to the correlation structure. A second ablation replaces the local relaxation with the trivial upper bound $\mathrm{OPT}_{loc}\le\mathrm{OPT}_{FI}$, which shows how much the relaxation contributes.

Why not just…?

Why not just simulate best-response dynamics and report the welfare ratio? That number mixes selfishness with missing information, and it is a heuristic lower bound. A bad local optimum would look like an information collapse. The no-signaling ablation measures exactly how misleading the point estimate is. If intervals turn out to be as wide as the point-estimate error, we will say so, and the method has not earned its cost.

Why not just use a mean-field model, which scales effortlessly? On Sioux Falls with 14,000 vehicles, online mirror descent for the mean-field game brought the average deviation incentive down to 1.55, against an average travel time of about 27.5 (Solving N-player dynamic routing games). But mean-field models treat players as anonymous, and in their simplest form they assume independent infinitesimal agents. They cannot express a common factor linking many players' private types, and that is precisely the ingredient behind the correlated-prior collapse. Mean-field routing is a data point that large populations can look benign. It does not test the question.

Why not just broadcast full information and skip mediation? Full information does remove the representability problem, but only when types can actually be revealed. In the facility and influence settings modeled here, types are private cost shocks or demand estimates held by rival firms and advertisers. Beyond that, Nachbar et al. prove that full revelation gives only a price-of-anarchy-sized approximation to the best signaling scheme. We report $\mathrm{OPT}_{FI}$ as the ceiling full revelation would reach, but it is not an achievable policy in the games studied.

Why not just note that real instances have low curvature, so the gap is trivially near 1? This is a genuine threat, because nearly-additive welfare would make every gap look fine. We therefore report each instance's curvature (how far welfare is from additive) and vary reach overlap deliberately. A uniformly flat gap near 1 that curvature fully explains would be a legitimate negative finding: the collapse would then be irrelevant on these benchmarks.

Proposed Experiments

Facility-location games use the ORlib and HM14 instances from Competitive Facility Location. Players are firms choosing sites, and customer coverage defines welfare. We scale $n$ from 2 to about 64 with two to four types per player.

Competitive influence games use the Facebook graph from Consistent Submodular Maximization, the DM co-authorship graph from Online Competitive Influence Maximization, and graphs loaded through SNAP, under a coverage-style welfare. Metrics are the certified gap interval and its width, the information/incentive decomposition, and wall-clock time for the relaxation and for the swap-regret dynamics.

The decisive checks come in order. First, calibration: on the reimplemented worst-case construction, the intervals must reproduce a $1/\sqrt{n}$ trend. On independent-prior instances, every interval must lie at or above $0.632$. If either fails, the measurement tool is wrong and nothing downstream counts.

Second, the scientific test: on real instances with correlated priors, we regress the gap on $n$, common-factor strength, and reach overlap. We predict that the gap declines with $n$ only when a strong single factor and heavy overlap co-occur, and stays flat otherwise. A flat gap under strong realistic correlation, or a decline explained by $n$ alone, would each falsify part of that prediction.

Third, the incentive loss measured from untruthful swap regret should sit well above Fujii's $1/2$ bound. The decomposition then tells practitioners whether the loss on their instances comes mainly from missing information or from selfish behavior.