Multi-label classifiers predict a set of labels per input, such as "dog, leash, park" for a photo. They get better when each label's prediction can depend on the others. The most natural way to learn such dependencies is also the least principled. One trains a separate classifier per label that sees the input plus the other labels' predictions. "Leash" can then lean heavily on "dog" without "dog" leaning equally on "leash." These directed, asymmetric conditionals are easy to fit. They do not, however, define any joint probability distribution. Iterating them at test time can therefore oscillate, settle on whichever fixed point happens to be closest, or stop at an inconsistent label set with no warning. Symmetric graphical models avoid this by forcing every dependency to be mutual. Doing so throws away exactly the directional information, such as hierarchy, implication, and one-sided co-occurrence, that motivates dependency modeling in the first place.
We propose to treat each label as a player in a game. A label's "move" is its predicted probability, and its "payoff" comes from its own learned conditional classifier. A coherent prediction is then an equilibrium: a set of label probabilities in which no label wants to change, given the others. Because the game generally has no shared objective, standard MAP solvers do not apply. Algorithmic game theory, however, offers a tool designed for this situation. Dual discretization rounds both the strategies and the accumulated neighbor influence onto finite grids. It then solves the resulting constraint problem exactly by dynamic programming on a tree, with a provable approximation error. We adapt this tool to per-instance label graphs. The result is an inference procedure that comes with a checkable certificate of coherence, can enumerate every approximate equilibrium, and can choose among them deliberately.
Core Claim
Multi-label inference with asymmetric pairwise dependencies is best posed as finding a logit (quantal-response) equilibrium of a polymatrix game. In a polymatrix game, each player's payoff is a sum of pairwise terms with its graph neighbors. We claim that this equilibrium can be computed with a guaranteed residual on sparse per-instance trees by adapting the dual payoff–strategy discretization of Ortiz and Irfan. Concretely, label $j$ receives a score $$s_j(x, p) = b_j(x) + \sum_{i \in N(j)} W_{ji}(x)\, p_i,$$ where $b_j(x)$ is its own evidence from input $x$, $p_i \in [0,1]$ is the current probability of neighbor label $i$, $N(j)$ is $j$'s neighbor set, and $W_{ji}(x)$ is a learned, input-dependent influence of $i$ on $j$ that need not equal $W_{ij}(x)$. An equilibrium is a vector $p$ satisfying $p_j = \sigma(s_j(x,p))$ for all $j$, where $\sigma$ is the sigmoid.
When $W$ is symmetric, this reduces to the mean-field fixed-point equations of a conditional Ising model. That is the setting of Conditional Graphical Lasso, which learns feature-dependent pairwise potentials and solves them by mean-field iteration. Asymmetry is therefore the precise ingredient that separates our model from prior work, and the symmetrized model is our central ablation.
The novelty is not "game theory for multi-label learning" in general. NBCG already casts groups of labels as bargaining players. In that work, however, the game allocates training gradients across label coalitions in continuous parameter space and never touches test-time label assignment. Our game is played at inference time, over label probabilities, and is solved with discretization guarantees.
Research Program
Model and training. We freeze a feature extractor: CLIP ResNet-50 and ViT-B/16 for images, and bag-of-words or RoBERTa features for text. On top of it we train unary heads $b_j$ and low-rank, input-conditioned influence matrices $W(x)$. Training minimizes the binary cross-entropy of $\sigma(s_j(x, \tilde y))$, where $\tilde y$ is the ground-truth label vector corrupted by neighbor dropout and label flips. The corruption ensures the conditionals are trained on imperfect neighbor inputs, like those they will see at test time. A sparsity penalty on $W$ keeps the per-instance graphs prunable.
Per-instance tree backbone. For each test input, we follow the sparsity argument of Miyao and Tsujii. That work showed document-specific label graphs often have treewidth around 4 to 6, and it ran exact junction-tree inference on them. We first fix labels with negligible unary evidence to off. We then keep a maximum-weight spanning tree over the remaining labels, weighting each edge by $|W_{ji}|+|W_{ij}|$. A bounded-treewidth extension is a stretch goal. Dropped edges are not ignored: they reappear in the certificate described below.
Dual-discretized solver. Each $p_j$ is restricted to the grid $\{0, 1/k, \dots, 1\}$. This is the $k$-uniform restriction used throughout the equilibrium literature, for example by Deligkas, Fearnley and Savani for polymatrix games. Each node's partial sum of neighbor influence is also rounded to a grid of width $\eta$. Rounding these partial sums is the Ortiz–Irfan move that removes the exponential dependence on node degree. With both roundings in place, the equilibrium condition becomes a constraint satisfaction problem on the tree. Each node's constraint is $|p_j - \sigma(s_j)| \le \epsilon$, and it is checked as messages accumulate partial sums from children.
Since $\sigma$ is $1/4$-Lipschitz, rounding every $p_i$ by at most $1/(2k)$ perturbs $s_j$ by at most $\|W_{j\cdot}\|_1/(2k)$. This gives a feasibility tolerance of roughly $$\epsilon \approx \tfrac{1}{4}\left(\|W_{j\cdot}\|_1/(2k) + \deg(j)\,\eta\right),$$ and it tells us how fine the grids must be for a target residual. Ortiz and Irfan analyze multilinear payoffs, not the sigmoid fixed-point condition. Re-deriving their error bound for this condition is part of the theoretical work.
Certificate and selection. Every solution is re-scored on the full, unpruned graph by computing $\max_j |p_j - \sigma(s_j(x,p))|$. This costs one pass over the labels and is a model-level coherence certificate that iterative methods do not provide. The dynamic program can return all feasible grid equilibria, not just one. Among them we select by a welfare-style objective: total log-likelihood under the conditionals, or minimum full-graph residual. The constrained-equilibrium tree dynamic program of Deligkas et al. supports such objectives when they decompose per player. Their NP-hardness results for general graphs are the reason we stay on trees. We will also report how many equilibria each instance has, as a candidate signal of label ambiguity.
A note on dynamics. Choice Paralysis in Evolutionary Games proves that finite strategy grids can track continuous dynamics over fixed horizons yet diverge from them in the long run. That result constrains designs that simulate dynamics on a grid. Our solver computes fixed points directly by dynamic programming rather than running dynamics, so the paralysis mechanism does not apply. We still measure sensitivity to $k$ explicitly rather than assuming the grid is harmless.
Baselines
The naive reference is Binary Relevance: the unary heads $b_j$ alone, thresholded independently, on the same frozen features. SPEN reports beating this baseline on Bibtex and Bookmarks. Any method here must clear it by a wide margin.
The most important competitor uses the same asymmetric model with standard inference: damped fixed-point iteration $p \leftarrow (1-\alpha)p + \alpha\,\sigma(s(x,p))$ with multiple random restarts. It receives the same learned $W$, an equal wall-clock budget per instance, and a tuned $\alpha$ and restart count. If it matches the dynamic-programming solver, the solver is unnecessary. Beating it means higher subset accuracy or example-based F1 on the instances where iteration fails to converge, plus lower full-graph residuals overall.
The key ablation symmetrizes $W$ to $(W+W^\top)/2$. This yields a conditional Ising model in the spirit of Conditional Graphical Lasso. We run exact MAP on the same per-instance trees with max-product and on the full graph with junction tree where feasible. This isolates whether asymmetry, rather than the solver, carries any gain.
On the text benchmarks, the strongest prior structured method is the sparse exact-inference model of Miyao and Tsujii. It reports subset accuracy rising from 77.91% to 80.52% on reuters90 as its correlation threshold grows, with runtimes reaching 116,535 seconds on reuters10 at the highest threshold. Beating it means exceeding 80.52% subset accuracy on reuters90 at a small fraction of that cost.
We also compare against end-to-end unrolled SPEN on Bibtex, Bookmarks and Delicious, using the same features and tuning budget. No reported number was found on Lacuna for SPEN on these datasets, because the file says results appear only in a figure, so we will rerun it.
On images, we include Bayesian Conditional Priors. BCP adjusts zero-shot CLIP logits using pairwise mutual information relative to a single anchor label. It reports average mAP improving from 57.31 to 69.22 with ResNet-50 and from 62.61 to 71.79 with ViT-B/16, aggregated across VOC, COCO and NUS-WIDE. For a matched comparison, our training-free variant sets $W_{ji}$ to directed conditional log-odds estimated from training co-occurrences. Beating BCP means exceeding those aggregated mAPs on the same backbones and the same benchmark mix.
Ma et al. trains full visual prompts. It reports COCO mAP gains of 1.2% to 8.7% over its own baselines but no absolute figure in the file. We treat it as a fine-tuning upper reference rather than a matched competitor.
Why not just…?
Why not just iterate the conditionals until they converge? This is the real threat. If damped iteration converges on nearly every instance to the best equilibrium, our solver adds only a certificate. Our experiments settle the question by reporting three quantities for the iterative baseline: the fraction of test instances where it fails to reach a residual below $\epsilon$ within budget, accuracy on that subset, and how often its fixed point differs from the dynamic program's best-scoring equilibrium. If non-convergence stays under about 1% and the chosen equilibria agree, we will report that the asymmetric model is the contribution and the discretized solver is a diagnostic tool.
Why not just fit a symmetric graphical model and run exact MAP? Symmetric models have a proper joint distribution and mature exact solvers, including junction trees on the low-treewidth graphs Miyao and Tsujii observed. A symmetric potential can represent "A without B is bad." It cannot represent "A's presence should raise B's score strongly while B barely affects A" as two separate learned strengths. The symmetrization ablation measures whether that difference matters. We expect it to matter most on hierarchical and long-tailed label sets, where NBCG documents head labels dominating tail labels. If symmetrization costs nothing, the proposal's premise fails.
Why not just use pairwise test-time priors like BCP? BCP needs no training and is fast. However, it conditions every label on a single anchor, so it cannot express chains such as A raising B, which in turn raises C. Its authors note this restriction to pairwise anchor relations. Our training-free variant uses the same co-occurrence statistics but lets influence propagate through the tree. The comparison therefore tests propagation at matched information.
Why not just use an energy network with gradient-descent inference? SPENs model higher-order dependencies that our pairwise model cannot. Their inference, however, has no optimality guarantee on non-convex energies, and the end-to-end version degraded on the out-of-domain Brown corpus. We expect SPENs may win on in-domain F1 for Delicious with its 983 labels. We will test whether certified equilibria are more robust under a train/test domain split.
Proposed Experiments
The decisive experiments run on reuters90, Bibtex, Bookmarks and Delicious for text, and on VOC07, COCO and NUS-WIDE for images using frozen CLIP features. Metrics are subset accuracy, example-based F1, Hamming loss and mAP, where equilibrium probabilities serve as ranking scores. We also report the full-graph equilibrium residual and the rate of hierarchy or exclusion violations against label co-occurrence rules.
Three checks decide the proposal. The first is the asymmetric-versus-symmetrized ablation under identical solvers. The second is a head-to-head against damped iteration, stratified by whether iteration converges. The third is an accuracy-versus-$k$ curve, with $k \in \{4, 8, 16, 32\}$, plotted against the predicted Lipschitz tolerance, to test whether the error analysis predicts empirical residuals.
A secondary test checks whether the number of equilibria per instance predicts error, measured by AUROC for detecting wrong subset predictions. If it does, multiplicity serves as an uncertainty signal that thresholded classifiers lack. We will also report runtime against tree size, to confirm that the per-instance cost scales polynomially in the number of active labels.
References
- Tractable Algorithms for Approximate Nash Equilibria in Generalized Graphical Games with Tree Structure
- Conditional Graphical Lasso for Multi-label Image Classification
- NBCG: Nash-Bargained Causal Game for Long-Tailed Multi-Label NLP
- Exact Inference for Multi-label Classification using Sparse Graphical Models
- Computing Constrained Approximate Equilibria in Polymatrix Games
- Choice Paralysis in Evolutionary Games
- Structured Prediction Energy Networks
- End-to-End Learning for Structured Prediction Energy Networks
- Multi-Label Test-Time Adaptation with Bayesian Conditional Priors
- Correlative and Discriminative Label Grouping for Multi-Label Visual Prompt Tuning