PaperlayerView exact revision on arXiv

Source-linked AI summary

What You Earn from What You Learn: Characterization and Complexity of the Value of Information

Ratip Emin Berker, Ioannis Anagnostides, Emanuel Tewolde, Brian Hu Zhang, Tuomas Sandholm, Vincent Conitzer

arXiv:2610.19488v1cs.GT

TL;DR

The paper asks how to measure the structural value of information without fixing a payoff environment. It characterizes that value using fractional chromatic numbers of conflict graphs, then shows that perfect information and recall have different computational complexity, with recall’s value also able to be fractional.

  • Problem

    Information structures may be the primary object of interest while payoff specifications are uncertain, ephemeral, or application-dependent.

    Source: §1 · p. 3

  • Method

    The paper defines value as the largest gain ratio over payoff environments and characterizes it using maximum fractional chromatic numbers over associated conflict graphs.

    Source: §1 · p. 3

  • Results

    Perfect-information value is NP-complete to compute under perfect recall and polynomial-time computable when information-set size is bounded; recall value is Σp2-complete and can be fractional without absentmindedness.

    Source: §1.1 · p. 4, §4.3 · p. 13

  • Takeaways & Limitations

    Different information refinements have fundamentally different computational properties.

    Source: §6 · p. 17

    The recall-complexity result assumes decision problems are free of absentmindedness.

    Source: §1.1 · pp. 4–5

Abstract

from arXiv · show

We examine the value of information in extensive-form decision problems: the largest multiplicative gain that a decision maker can obtain from an information refinement, taken over all payoff environments. This measures the structural importance of information disentangled from any particular payoff specification, and generalizes the notion of value of recall recently introduced by Berker et al. (AAAI'25). We establish a unifying characterization of the value of information under any information refinement, uncovering an intriguing connection to the maximum fractional chromatic number over a certain family of conflict graphs. We then employ our characterization to elucidate the complexity of two central information refinements. First, for the value of perfect information in perfect-recall decision problems, we find that the relevant conflict graphs are cographs, so the fractional chromatic number collapses to the clique number. Even though the clique number is tractable for a given cograph, we show that the additional layer of optimization (over the family of graphs) makes computing the value of perfect information NP-complete. On the positive side, we prove fixed-parameter tractability in terms of the degree of imperfect information. Second, for the value of recall in imperfect-recall decision problems (with no absentmindedness), we first show that the value of recall can realize the fractional chromatic number of any graph. Interestingly, this implies that, unlike the value of perfect information, the value of recall can take fractional values. Building on this reduction, we then establish S2P-completeness. This addresses questions left open by Berker et al. (AAAI'25)---both on the characterization and the complexity of the value of recall---and shows that computing the value of recall is strictly harder than the value of perfect information.

1 Introduction

The paper measures the structural value of information independently of a particular payoff specification, motivated by settings where the information structure is more stable than the payoff environment. It characterizes information refinements through conflict graphs and uses that framework to establish different complexity results for perfect information and recall.

1 Introduction

  • The value of information is the largest gain ratio over nonnegative payoff environments for a refinement that splits information sets and improves distinguishability.This separates the structure of the information partition from any particular payoff specification.Source: §1 · p. 3

1.1 Our results

  • The characterization expresses the value of any information refinement as a maximum fractional chromatic number over an associated family of conflict graphs.It provides a unified graph-theoretic view of information refinements.Source: §1.1 · pp. 4–5
  • For perfect information under perfect recall, conflict graphs are cographs, making the value an integer, yet computing it is NP-complete.The hardness comes from optimizing over the family of graphs, despite tractability of the clique number for an individual cograph.Source: §1.1 · p. 4
  • When every information set has bounded size, the value of perfect information is computable in polynomial time by dynamic programming.The paper interprets information-set size as the degree of imperfect information.Source: §1.1 · p. 4
  • For recall without absentmindedness, the value can equal the fractional chromatic number of any graph, so it can be non-integer.This contrasts with the integer-valued perfect-information case.Source: §1.1 · p. 4
  • Computing the value of recall is Σp2-complete, resolving a characterization and complexity gap left by Berker et al. [11] for the case with chance nodes.Their earlier work provided only a loose bound for that case.Source: §1.1 · pp. 4–5
  • The results establish hardness even for single decision makers, while bounded imperfect information yields a tractable regime; recall is strictly harder than perfect information unless the polynomial hierarchy collapses.The paper notes that NP problems are amenable to effective SAT-solver tools, whereas such techniques are not applicable to value of recall.Source: §1.1 · p. 5

1.2 Related work

  • Berker et al. [11] introduced value of recall; related algorithmic work typically evaluates information relative to fixed payoffs, unlike this paper’s payoff-wide ratio.Related settings include influence diagrams, information selection in graphical models, and information design for AI proxies.Source: §1.2 · p. 6

2 Decision problems and information refinements

The section formalizes extensive-form decision problems and the information refinements studied in the paper. It defines their value as the largest payoff gain over all payoff environments.

2.1 Extensive-form decision problems

  • An extensive-form decision problem is a finite tree of chance and player nodes, with information sets grouping player nodes the decision maker cannot distinguish.Chance probabilities and the tree specify the problem; payoffs are considered separately.Source: §2.1 · p. 7
  • No absentmindedness means a path visits each information set at most once; perfect recall additionally requires matching histories of the player's own information sets and actions.Perfect recall implies no absentmindedness, but no absentmindedness still permits forgetting earlier information or actions.Source: §2.1 · p. 7

2.2 Perfect-information and perfect-recall refinements

  • A refinement splits information sets without changing the tree, leaves, action labels, or chance probabilities; perfect information makes every player node a singleton.The coarsest perfect-recall refinement splits original information sets according to the player's earlier information sets and actions.Source: §2.2 · p. 8

2.3 Value ratios

  • The value ratio is the supremum payoff gain from a refinement over all payoff vectors; VoPI and VoR use the perfect-information and coarsest perfect-recall refinements, respectively.Splitting information sets cannot reduce the attainable payoff, so the ratios are at least one.Source: §2.3 · p. 9

3 A unifying characterization through fractional coloring

The section characterizes the value ratio of any information refinement through fractional coloring of conflict graphs. These graphs encode which leaves a strategy in the original problem cannot reach together.

3 A unifying characterization through fractional coloring

  • A conflict graph has reached leaves as vertices, with an edge when two leaves require different actions at a shared original information set.An independent set is exactly a set of leaves compatible with some pure strategy in the original problem.Source: §3 · p. 10
  • For any refinement of a decision problem with no absentmindedness, its value ratio is the maximum fractional chromatic number over conflict graphs induced by refined strategies.This gives a graph-theoretic characterization for any information refinement, not only perfect information or recall.Source: §3 · p. 10
  • Fractional coloring captures the maximum multiplicative gap because the refined strategy can collect weight across its reached leaves while an original strategy can collect only a compatible subset.Those compatible subsets are the conflict graph's independent sets.Source: §3 · p. 10
  • The paper uses the characterization to study the computational complexity of the value of perfect information and the value of recall.The section's stated next step is to investigate these two refinements.Source: §3 · p. 10

4 Value of perfect information

For perfect-recall problems, the paper characterizes the value of perfect information using clique numbers, proves its computation NP-complete, and identifies a fixed-parameter tractable regime.

4.1 Cographs and an integer formula

  • Under perfect recall, every fixed-strategy conflict graph is a cograph, so VoPI is the maximum clique number over these graphs and is always an integer.For cographs, the fractional chromatic number equals the clique number.Source: §4.1 · p. 11

4.2 NP-completeness of VoPI: reduction from MaximumCoverage

  • In the reduction, first-stage actions serve as coverage slots, while perfect information lets the player assign each element to a chosen set.The original strategy cannot condition that assignment on the element.Source: §4.2 · p. 12, Figure 2 · p. 12
  • VoPI-Threshold is NP-complete, via an exact reduction from MaximumCoverage that transfers its approximation hardness to VoPI.The reduction makes the value of perfect information equal the optimum coverage value; unless P = NP, no polynomial-time (1 − 1/e + ϵ)-approximation exists for any constant ϵ > 0.Source: §4.2 · pp. 11–13

4.3 Fixed-parameter tractability

  • VoPI is fixed-parameter tractable in the largest information-set size and largest action-set size; bounded information-set size makes the algorithm polynomial in the problem description.The algorithm uses dynamic programming and the cograph structure of the conflict graph.Source: §4.3 · p. 13

5 Value of recall

The value of recall is characterized through fractional chromatic numbers of conflict graphs, and graph embeddings show that it can be fractional. Its threshold problem is Σp2-complete, even without absentmindedness.

5 Value of recall

  • VoR(Γ) is the maximum fractional chromatic number among conflict graphs induced by perfect-recall refinements of Γ.The section studies VoR-Threshold: whether VoR(Γ) is at least a given rational threshold.Source: §5 · p. 13, §5.1 · p. 13

5.1 Membership in Σp

  • The threshold problem is NP-hard via a transformation equating value of recall with value of perfect information, but the latter’s NP-membership proof does not transfer.For a supplied refined strategy, testing whether an arbitrary graph’s fractional chromatic number meets a threshold is coNP-hard.Source: §5.1 · p. 13

5.2 Fractional coloring embedding

  • For every graph G, decision problem ΓG is free of absentmindedness, has size O(|V| + |E|), and satisfies VoR(ΓG) = χf(G).Source: §5.2 · p. 14

5.2.1 Fractional example of VoR: embedding the 5-cycle

  • The 5-cycle yields a no-absentmindedness decision problem with VoR = 5/2, so value of recall need not be an integer.The fractional-coloring certificate matches a dual lower bound of 5/2 with five independent sets weighted 1/2 each.Source: §5.2.1 · pp. 15–16, Figure 4 · p. 15

5.1 Membership in Σp

  • VoR-Threshold is Σp2-complete, even for decision problems with a single initial chance node and no absentmindedness.The reduction encodes existential assignments with selector information sets and connects optional-edge 3-colorability to fractional coloring.Source: §5.2.1 · pp. 16–17

6 Conclusion and future research

The paper introduces a general value-of-information measure and characterizes it using conflict graphs. It establishes different complexity results for perfect information and recall, and identifies open directions.

6 Conclusion and future research

  • The value of information measures the largest possible utility gain from an information refinement and is characterized by a maximum fractional chromatic number over associated conflict graphs.The characterization provides a unified combinatorial view of different information refinements.Source: §6 · p. 17
  • Computing value of perfect information is NP-complete, while computing value of recall is Σp2-complete without absentmindedness.The paper concludes that the two refinements have different computational properties.Source: §6 · p. 17
  • Future directions include other refinements, imperfect-recall value of perfect information, absentmindedness, and extending value or cost of information beyond single-player problems.Source: §6 · p. 17

Statement on AI use

The authors report using GPT 5.5 Pro in proof development and throughout the paper’s editing, while retaining responsibility for its content.

Statement on AI use

  • GPT 5.5 Pro helped develop some proofs, including finding the construction that led to Theorem 4.5.Source: Statement on AI use · p. 17
  • Theorem 5.10’s Σp2-hardness emerged through repeated interaction with GPT, building on an approach the authors had developed.Source: Statement on AI use · p. 18
  • The authors also used GPT for edits throughout the paper and take full responsibility for its content.Source: Statement on AI use · p. 18

A Algorithms for the value of perfect information

The appendix presents a dynamic-programming algorithm for value of perfect information with bounded information-set size. It also gives a fixed-strategy sequence-form LP and an enumeration-based algorithm.

A Algorithms for the value of perfect information

A.1 Linear program in perfect-recall decision problems

  • For a fixed refined strategy in a perfect-recall problem, a sequence-form linear program computes the relevant quantity in polynomial time.Proposition A.1 identifies ρ(bx_bπ) with 1/λ(bπ), where λ is the LP optimum.Source: §A.1 · p. 23
  • Enumerating all pure perfect-information strategies and solving a polynomial-size LP for each takes poly(|Γ|) times the product of the player-node action-set sizes.In the perfect-information refinement, this product is the number of pure strategies.Source: §A.1 · p. 24

A.2 Bounded information-set size

The algorithm computes the value of perfect information by a dynamic program over information sets and subsets of their nodes. Its running time is polynomial when the largest information set has constant size.

A.2 Bounded information-set size

  • F(I, S) is the largest clique size obtainable among leaves descending from S, optimized over perfect-information choices at and below those nodes.Perfect recall ensures nodes in I share the same previous player sequence, so the state needs no additional history.Source: §A.2 · p. 24
  • For a fixed action map on S, action classes are joined, while chance-separated terminal and successor-information-set pieces are disjoint.Pieces entering distinct next information sets cannot conflict later without violating perfect recall.Source: §A.2 · pp. 24–25
  • The recurrence is acyclic, evaluates in reverse topological order, and its dummy-root state equals VoPI(Γ).For each information set, the algorithm considers maps over all subsets; successor pieces can be precomputed by traversing chance edges.Source: §A.2 · pp. 24–25
  • The algorithm runs in (1 + A)^w poly(|Γ|), where w is the largest information-set size and A the largest action-set size, hence polynomial for fixed w.Since A ≤ |Γ|, the bound is |Γ|^O(w).Source: §A.2 · pp. 24–25

B Proofs

The appendix proves a geometric characterization of the value ratio. It expresses the ratio as the smallest scaling factor needed for original outcome distributions to dominate all refined outcomes.

B.1 Geometric formulation

  • The original and refined outcome distributions form convex polytopes generated by their respective pure-strategy leaf distributions.The downward closure of the original polytope is DΓ := XΓ − R^L_≥0.Source: §B.1 · pp. 25–26
  • The value ratio is the smallest factor α such that every refined outcome distribution can be coordinatewise dominated by α times some original randomized outcome distribution.This is the downward-containment characterization of Proposition B.2.Source: §B.1 · p. 26
  • It suffices to test every pure refined strategy: the value ratio is the maximum of their individual ratios.Convexity of the downward-closed set makes containment of the refined polytope equivalent to containment of each pure-strategy distribution.Source: §B.1 · p. 27

B.2 Conflict graphs and fractional coloring

For decision problems without absentmindedness, the value ratio equals the maximum fractional chromatic number among the refined strategies’ conflict graphs. The proof connects graph independence to compatibility with an original strategy.

B.2 Conflict graphs and fractional coloring

  • A leaf set is independent in a refined strategy’s conflict graph exactly when one original pure strategy is compatible with every leaf in that set.Independence means leaves never require different actions at the same original information set.Source: §B.2 · p. 27
  • Without absentmindedness, the value ratio is the maximum fractional chromatic number over pure refined strategies’ conflict graphs.The proof relates payoff weights to the dual linear program for fractional chromatic number.Source: §B.2 · pp. 27–28
  • The value ratio is rational, its payoff supremum is attained, and it lies between 1 and the number of leaves.The theorem’s maximum is finite, and each fractional chromatic number is the optimum of a rational linear program.Source: §B.2 · p. 28

B.3 Value of perfect information

With perfect recall, each relevant conflict graph is a cograph, making its fractional chromatic number equal to its clique number. The appendix also supplies the structural and reduction arguments underlying the value-of-perfect-information results.

B.3 Value of perfect information

  • For every pure perfect-information strategy in a perfect-recall problem, the conflict graph is a cograph.The induction uses joins across action classes and disjoint unions across chance-separated successor components; perfect recall prevents cross-conflicts between distinct next information sets.Source: §B.3 · pp. 28–29
  • For cographs, the fractional chromatic number equals the clique number, so VoPI(Γ) is the maximum clique number over pure perfect-information strategies.Cographs are built using disjoint union and join, operations that preserve the equality.Source: §B.3 · p. 29
  • VoPI-Threshold is in NP because a perfect-information strategy certifies a threshold-sized clique that can be checked in polynomial time.The graph is a cograph, so its clique number is polynomial-time computable.Source: §B.3 · p. 30
  • VoPI-Threshold is NP-complete: a polynomial reduction from MaximumCoverage constructs a perfect-recall problem whose VoPI equals the instance’s optimum.The constructed problem satisfies VoPI(ΓC) = OPT, preserving the threshold decision.Source: §B.3 · pp. 30–32

B.4 Value of recall

The omitted value-of-recall proofs establish a compact threshold witness and describe verification through existential and universal guesses followed by polynomial-time checks.

B.4 Value of recall

  • If the value of recall is at least τ, a refined pure strategy and normalized nonnegative rational payoff vector satisfy the threshold inequality against every original pure strategy.The witness encoding length is polynomial in the input size and the encoding length of τ.Source: §B.4 · p. 33
  • A polynomial-bit payoff witness exists because, for a fixed refined strategy, the feasible payoffs form a nonempty rational polytope with a basic feasible solution.The proof bounds the solution's bit length using Cramer's rule and the chance-probability coefficients.Source: §B.4 · p. 33
  • The verifier existentially guesses the refined strategy and payoff vector, then universally checks each original pure strategy's inequality in polynomial time.The induced leaf-distribution vectors are computed by traversing the explicit tree and multiplying rational chance probabilities.Source: §B.4 · p. 33

B.4.1 NP-hardness through fractional coloring embedding

This section develops graph-coloring reductions showing that the value of recall can encode fractional chromatic numbers, yielding NP-hardness of exact computation and Σp2-completeness of the threshold problem, even with one initial chance node and no absentmindedness.

B.4.1 NP-hardness through fractional coloring embedding

  • For every graph G, a linear-size decision problem ΓG with no absentmindedness satisfies VoR(ΓG) = χf(G).Every refined strategy induces a conflict graph isomorphic to a spanning subgraph of G, and some strategy realizes G itself.Source: §B.4.1 · pp. 34–35
  • Exact computation of value of recall is NP-hard, since deciding whether χf(G) ≤ r is NP-complete and ΓG is constructible in polynomial time.The reduction uses VoR(ΓG) = χf(G).Source: §B.4.1 · p. 35
  • A polynomial-time conversion to 3-CNF preserves satisfiability under every partial assignment to a specified variable set.The construction adds missing variables with tautologies and replaces clauses using fresh auxiliary variables.Source: §B.4.1 · pp. 35–36
  • For each assignment a to X, the constructed graph Ga is 3-colorable iff there exists an assignment Y with Φ(a,Y)=FALSE; equivalently, Ga is not 3-colorable iff ∀Y Φ(a,Y).Source: §B.4.1 · pp. 36–37
  • For an r-vertex graph G, χf(F(G)) = 3 when G is 3-colorable, while χf(F(G)) ≥ 3 + 3/(r−1) otherwise.The lower bound follows because non-3-colorability limits every independent set of F(G) to at most r−1 vertices.Source: §B.4.1 · pp. 37–38
  • A decision problem Γ with no absentmindedness realizes max_bπ χf(Gbπ) = max_a χf(Fa), with selector bits choosing a and refined conflict-test choices independent.Private tags separate conflict-test histories in the perfect-recall refinement, while shared tests induce the intended graph edges.Source: §B.4.1 · pp. 38–39, Figure 7 · p. 39
  • The constructed problem satisfies max_bπ∈Π(ΓPR) χf(G_bπ) = max_a∈{0,1}^n χf(F_a), embedding the graph-family optimization in value of recall.For each selector vector, the conflict graph matches F_a; for any refined strategy, its conflict graph is a spanning subgraph of the corresponding F_a.Source: §B.4.1 · pp. 39–40
  • The construction realizes optional edge {(λ(b)_i, c), (T, c)} exactly when selector action a_i=b, while selector information sets create no conflicts.Source: §B.4.1 · pp. 39–40
  • For hardness, the proof starts from an instance ∃X ∀Y Φ(X,Y) of ExistsForallDNFSAT, which is Σp 2-complete, and assumes every term of Φ is nonempty.If an empty term is present, the source instance is trivially YES and can be mapped to a one-branch chance-only decision problem with threshold 1, a fixed YES instance of VoR-Threshold.Source: §B.4.1 · p. 40
  • For the constructed F_a, χf(F_a) ≥ τ exactly when G_a is not 3-colorable, making the VoR threshold condition equivalent to the source instance’s YES condition.The reduction is polynomial; when G_a is 3-colorable, χf(F_a)=3<τ, and otherwise χf(F_a)≥3+3/(r−1)>τ.Source: §B.4.1 · p. 40
Loading 2610.19488v1…