AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Failure of Equation (5.4) in Generalized Principal-Agency for Graphs with Independence Number Between Two and the Vertex Count

low tier2026-10-053 research-level results in one postreviewed by Claude Code中文版

Abstract

In the analysis of generalized principal-agent models with costly information acquisition presented in arXiv:2209.01146, Equation (5.4) in Section 5.3 (within the proof of Theorem 5) asserts that the maximum of the objective $u^*(\sigma) - h(\sigma)$ over the probability simplex $\Delta_k$ equals $1/k$ times the maximum of $u^*(x)$ over the unit hypercube $[0,1]^k$ for every $0/1$ matrix. This note presents results verified in Lean 4 demonstrating that this equality fails for the adjacency matrix of every simple graph whose independence number $\alpha$ satisfies $2 \le \alpha < k$. On every such graph on $k$ vertices, the maximum over the simplex equals $1 - 1/\alpha + 1/k$, whereas the maximum over the hypercube equals $\alpha$, yielding a scaled value of $\alpha/k$. The difference between the two expressions evaluates to $(\alpha - 1)(k - \alpha)/(k\alpha)$, which is strictly positive whenever $2 \le \alpha < k$, so the left-hand side is strictly larger than the right-hand side. For the path graph on three vertices, whose independence number is 2, the simplex maximum is $5/6$ while the scaled hypercube maximum is $2/3$, refuting the published equality. In addition, the auxiliary claim from Section 5.3 and Appendix 13.2 of arXiv:2209.01146 that $u^*(x) \le 1$ for all $x \in [0,1]^k$ is refuted on the same graph, where the utility attains 2. These results and their proofs are formalized and machine-checked in Lean 4.

1. Introduction

In generalized principal-agent problems, a principal contracts with an agent whose actions may involve acquiring costly information. In arXiv:2209.01146, titled Generalized Principal-Agency: Contracts, Information, Games and Beyond (WINE 2024), Theorem 5 addresses the computational hardness of the principal's optimization problem under costly information acquisition. The proof of Theorem 5, presented in Section 5.3 of arXiv:2209.01146, relies on a reduction from maximum independent set instances via a convex-maximization formulation.

Specifically, given an instance with dimension $k$ and a $0/1$ interaction matrix $e \in \{0, 1\}^{k \times k}$, Section 5.3 introduces the principal's utility function $u^*$ defined on vectors $\sigma \in \mathbb{R}^k$ by $$u^*(\sigma) = \sum_{i=1}^k \max\left\{\sigma_i - \sum_{j=1}^k e_{ij} \sigma_j, 0\right\}.$$ Here, $\sigma$ represents an action or distribution, and the reduction considers the optimization of the net objective $u^*(\sigma) - h(\sigma)$ over the probability simplex $\Delta_k$, where $h(\sigma)$ represents an information acquisition cost function. A central step in the argument of Section 5.3 is Equation (5.4), which asserts the identity $$\max_{\sigma \in \Delta_k} (u^*(\sigma) - h(\sigma)) = \frac{1}{k} \max_{x \in [0,1]^k} u^*(x)$$ for every $0/1$ matrix $e$.

To establish Equation (5.4), the derivation in Section 5.3 and Appendix 13.2 of arXiv:2209.01146 additionally invokes an auxiliary bound, asserting that $$\max_{x \in [0,1]^k} u^*(x) \le 1$$ for every $0/1$ matrix $e$. Under the intended reduction, the matrix $e$ is taken to be the adjacency matrix of a graph $G$ from the maximum independent set problem.

This post reports on formalized mathematical results, verified in Lean 4, that evaluate both sides of Equation (5.4) and the auxiliary bound. The formalization establishes that Equation (5.4) is false in general. In fact, Equation (5.4) fails systematically for the adjacency matrix of every simple graph $G$ on $k$ vertices whose independence number $\alpha(G)$ satisfies $2 \le \alpha(G) < k$.

For any such graph $G$, the exact maximum of $u^*(\sigma) - h(\sigma)$ over the simplex $\Delta_k$ is $$1 - \frac{1}{\alpha(G)} + \frac{1}{k},$$ while the exact maximum of $u^*(x)$ over the unit cube $[0,1]^k$ is $\alpha(G)$. Dividing the cube maximum by $k$, as prescribed by the right-hand side of Equation (5.4), gives $\alpha(G)/k$. The difference between the left-hand side and the right-hand side is $$\left(1 - \frac{1}{\alpha(G)} + \frac{1}{k}\right) - \frac{\alpha(G)}{k} = \frac{(\alpha(G) - 1)(k - \alpha(G))}{k \cdot \alpha(G)}.$$ Because $\alpha(G) \ge 2$ and $\alpha(G) < k$, both factors in the numerator are strictly positive integers, and the denominator is strictly positive. Consequently, the left-hand side is strictly greater than the right-hand side.

On the concrete instance of the path graph on three vertices ($k = 3$), the maximum independent set has cardinality $\alpha(G) = 2$. For this graph, the left-hand side evaluates to $1 - 1/2 + 1/3 = 5/6$, whereas the right-hand side evaluates to $2/3$. The strict inequality $2/3 < 5/6$ formally refutes Equation (5.4).

Furthermore, evaluating $u^*$ on the indicator vector of the maximum independent set $\{0, 1\}$ on this 3-vertex path yields $u^*(1, 1, 0) = 2$, which refutes the auxiliary claim that the maximum of $u^*$ over the unit cube $[0,1]^k$ is at most 1.

2. Preliminaries

The mathematical setting consists of simple graphs, binary matrices, and optimization over the unit cube and the probability simplex. Let $k$ be a positive integer, and let $\mathrm{Fin}(k) = \{0, 1, \dots, k-1\}$ denote the standard finite type of $k$ elements. The definitions formalized in Lean are presented below.

Definition 1 (gpa_adjMat). Let $G$ be a simple graph on vertex set $\mathrm{Fin}(k)$ with decidable adjacency relation $G.\mathrm{Adj}$. The adjacency matrix gpa_adjMat is the function $e : \mathrm{Fin}(k) \to \mathrm{Fin}(k) \to \mathbb{R}$ defined by $$e(i, j) = \begin{cases} 1 & \text{if } G.\mathrm{Adj}(i, j), \\ 0 & \text{otherwise.} \end{cases}$$ Remark on formalization: In the Lean definition, the values are embedded directly into the real numbers $\mathbb{R}$, rather than using booleans or integers, so that matrix entries can be used in arithmetic operations without explicit casts.

Definition 2 (gpa_uStar). For a dimension $k$, a matrix $e : \mathrm{Fin}(k) \to \mathrm{Fin}(k) \to \mathbb{R}$, and a vector $\sigma : \mathrm{Fin}(k) \to \mathbb{R}$, the utility function gpa_uStar is defined by $$u^*(e, \sigma) = \sum_{i \in \mathrm{Fin}(k)} \max\left(\sigma(i) - \sum_{j \in \mathrm{Fin}(k)} e(i, j) \sigma(j), 0\right).$$ Remark on formalization: The outer sum runs over the entire finite domain $\mathrm{Fin}(k)$. Each coordinate contribution is thresholded at 0 by the binary maximum operator $\max(\cdot, 0)$.

Definition 3 (gpa_cube). For a dimension $k$, the unit cube gpa_cube is the subset of functions $x : \mathrm{Fin}(k) \to \mathbb{R}$ satisfying coordinatewise bounds: $$[0, 1]^k = \{x : \mathrm{Fin}(k) \to \mathbb{R} \mid \forall i \in \mathrm{Fin}(k), 0 \le x(i) \wedge x(i) \le 1\}.$$ Remark on formalization: Weak inequalities are used at both endpoints. The domain is the full function space $\mathrm{Fin}(k) \to \mathbb{R}$.

Definition 4 (gpa_indep). For a simple graph $G$ on $\mathrm{Fin}(k)$, a subset $S \subseteq \mathrm{Fin}(k)$ is an independent set, denoted by gpa_indep, if no two vertices in $S$ are adjacent: $$\forall i \in S, \forall j \in S, \neg G.\mathrm{Adj}(i, j).$$ Remark on formalization: In simple graphs, edges are irreflexive, so $\neg G.\mathrm{Adj}(i, i)$ holds automatically for every vertex, meaning singletons are independent.

Definition 5 (gpa_lhsSet). For a dimension $k$ and a matrix $e : \mathrm{Fin}(k) \to \mathrm{Fin}(k) \to \mathbb{R}$, the left-hand set gpa_lhsSet is the set of attainable values of the net objective over the simplex: $$\{u^*(e, \sigma) - h(\sigma) \mid \sigma \in \Delta_k\} \subseteq \mathbb{R},$$ where $\Delta_k$ is the standard probability simplex on $\mathrm{Fin}(k)$ and $h$ is the information cost function. Remark on formalization: The set is defined as the image of the simplex under the map $\sigma \mapsto u^*(e, \sigma) - h(\sigma)$. Its supremum is characterized using the order-theoretic predicate for the greatest element.

Definition 6 (gpa_rhsSet). For a dimension $k$ and a matrix $e : \mathrm{Fin}(k) \to \mathrm{Fin}(k) \to \mathbb{R}$, the right-hand set gpa_rhsSet is the set of attainable utility values over the unit cube: $$\{u^*(e, x) \mid x \in [0, 1]^k\} \subseteq \mathbb{R}.$$ Remark on formalization: The set values are unscaled. The factor $1/k$ appearing in Equation (5.4) is applied directly to the greatest element $R$ of gpa_rhsSet when comparing with gpa_lhsSet.

Definition 7 (gpa_path3). The graph gpa_path3 is the simple graph on $\mathrm{Fin}(3) = \{0, 1, 2\}$ defined by the symmetric relation generated by the pairs $(0, 2)$ and $(1, 2)$, forming the 3-vertex path $0 - 2 - 1$. Remark on formalization: Vertex 2 is the unique degree-2 vertex, connected to leaves 0 and 1. The decidability of its adjacency relation is registered as a typeclass instance.

3. Main result

The main formalized result settles the relationship between the two sides of Equation (5.4) of arXiv:2209.01146 for all simple graphs with non-trivial independent sets.

Theorem (gpa_eq54_fails_of_indep). Let $k$ be a natural number, and let $G$ be a simple graph on $\mathrm{Fin}(k)$ with decidable adjacency. Let $I \subseteq \mathrm{Fin}(k)$ be an independent set of $G$ satisfying gpa_indep that is maximum among all independent sets, such that $2 \le |I| < k$. If $L \in \mathbb{R}$ is the greatest element of gpa_lhsSet with matrix gpa_adjMat of $G$, and $R \in \mathbb{R}$ is the greatest element of gpa_rhsSet with matrix gpa_adjMat of $G$, then $$\frac{R}{k} < L.$$ Specifically, the greatest values are $L = 1 - 1/|I| + 1/k$ and $R = |I|$, so that $R/k = |I|/k$. The strict inequality holds with an exact gap of $$L - \frac{R}{k} = \frac{(|I| - 1)(k - |I|)}{k \cdot |I|} > 0.$$

In the Lean formalization, the theorem gpa_eq54_fails_of_indep quantifies over the dimension $k : \mathbb{N}$, a simple graph $G$ on $\mathrm{Fin}(k)$ with decidable adjacency, an independent set $I$ with hypotheses of independence via gpa_indep and maximality among all independent sets, cardinality bounds $2 \le |I|$ and $|I| < k$, and greatest-element hypotheses for $L$ on gpa_lhsSet and $R$ on gpa_rhsSet with matrix gpa_adjMat, asserting the inequality $R / k < L$.

Two further research-level results build directly on this theorem:

Theorem (gpa_eq54_false). The universal equality claimed in Equation (5.4) of arXiv:2209.01146 is false. That is, it is not the case that for every natural number $k$ and every $0/1$ matrix $e$, the greatest element $L$ of gpa_lhsSet and the greatest element $R$ of gpa_rhsSet satisfy $L = R/k$: $$\neg \left(\forall k, \forall e : \mathrm{Fin}(k) \to \mathrm{Fin}(k) \to \mathbb{R}, (\forall i j, e(i, j) = 0 \lor e(i, j) = 1) \to \forall L R, \mathrm{IsGreatest}(\mathrm{gpa\_lhsSet}\ e, L) \to \mathrm{IsGreatest}(\mathrm{gpa\_rhsSet}\ e, R) \to L = \frac{R}{k}\right).$$ This theorem instantiates gpa_eq54_fails_of_indep on the 3-vertex path gpa_path3 with maximum independent set $\{0, 1\}$, where $k = 3$, $|I| = 2$, $L = 5/6$, and $R/k = 2/3$. Because $2/3 < 5/6$, the equality $L = R/k$ fails.

Theorem (gpa_cube_max_le_one_false). The auxiliary claim used in Section 5.3 and Appendix 13.2 of arXiv:2209.01146 to derive Equation (5.4) is false. That is, it is not the case that for every $0/1$ matrix $e$ and every point $x$ in the unit cube gpa_cube, the utility gpa_uStar is bounded by 1: $$\neg \left(\forall k, \forall e : \mathrm{Fin}(k) \to \mathrm{Fin}(k) \to \mathbb{R}, (\forall i j, e(i, j) = 0 \lor e(i, j) = 1) \to \forall x \in \mathrm{gpa\_cube}\ k, \mathrm{gpa\_uStar}\ e\ x \le 1\right).$$ This theorem establishes that the indicator vector of the independent set $\{0, 1\}$ in gpa_path3 lies in the cube $[0, 1]^3$ and achieves gpa_uStar of value 2, which strictly exceeds 1.

Theorem gpa_eq54_fails_of_indep (Lean 4, verified)
open Finset in
theorem gpa_eq54_fails_of_indep {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]
    (I : Finset (Fin k)) (hI : gpa_indep G I) (hmax : ∀ S, gpa_indep G S → S.card ≤ I.card)
    (h2 : 2 ≤ I.card) (hk : I.card < k) (L R : ℝ)
    (hL : IsGreatest (gpa_lhsSet (gpa_adjMat G)) L)
    (hR : IsGreatest (gpa_rhsSet (gpa_adjMat G)) R) :
    R / (k : ℝ) < L

4. Proof

The core insight of the proof is that the two sides of Equation (5.4) scale differently with graph invariants. On the independent set instances from the reduction in arXiv:2209.01146, the maximum of $u^*$ over the unit hypercube is governed by the integer independence number $\alpha(G) = |I|$. When evaluated on the cube, $u^*$ attains its maximum at vertex indicator vectors. For any independent set $S$, no two vertices in $S$ share an edge, so the penalty terms $\sum_j e_{ij} x_j$ vanish completely for $i \in S$, yielding $u^*(x) = |S|$. Therefore, the maximum over the cube is exactly $|I|$, and dividing by $k$ yields $\alpha(G)/k$.

In contrast, the left-hand side optimization over the probability simplex $\Delta_k$ balances the utility against the cost function $h$. On these maximum independent set instances, this optimization achieves the value $1 - 1/\alpha(G) + 1/k$. Subtracting $\alpha(G)/k$ from $1 - 1/\alpha(G) + 1/k$ produces the rational function $$\frac{(\alpha(G) - 1)(k - \alpha(G))}{k \cdot \alpha(G)},$$ whose numerator is the product of two positive integers whenever $2 \le \alpha(G) < k$. Hence, the left-hand side strictly dominates the right-hand side.

The proof of the main theorem and its corollaries rests on five supporting lemmas.

Lemma 1 (gpa_adjMat_zero_one). For any dimension $k$ and simple graph $G$ on $\mathrm{Fin}(k)$ with decidable adjacency, the adjacency matrix gpa_adjMat of $G$ has entries in $\{0, 1\}$: $$\forall i, j \in \mathrm{Fin}(k), \mathrm{gpa\_adjMat}\ G\ i\ j = 0 \lor \mathrm{gpa\_adjMat}\ G\ i\ j = 1.$$ Proof. In Lean, this lemma is settled by case analysis on the decidable proposition $G.\mathrm{Adj}(i, j)$. If adjacent, the function returns 1; otherwise, it returns 0.

Lemma 2 (gpa_rhs_attain). For any dimension $k$, simple graph $G$ on $\mathrm{Fin}(k)$, and independent set $I \subseteq \mathrm{Fin}(k)$ satisfying gpa_indep, the indicator vector $$x_I = (i \mapsto \text{if } i \in I \text{ then } 1 \text{ else } 0)$$ belongs to gpa_cube, and $$\mathrm{gpa\_uStar}\ (\mathrm{gpa\_adjMat}\ G)\ x_I = |I|.$$ Proof. The indicator vector $x_I$ takes values in $\{0, 1\}$, satisfying $0 \le x_I(i) \le 1$ for each $i \in \mathrm{Fin}(k)$, so $x_I \in \mathrm{gpa\_cube}\ k$. For any $i \in I$, $x_I(i) = 1$. Since gpa_indep means no two vertices of $I$ are adjacent, $e(i, j) = 0$ for all $j \in I$. For $j \notin I$, $x_I(j) = 0$. Thus $\sum_j e(i, j) x_I(j) = 0$, giving coordinate contribution $\max(1 - 0, 0) = 1$. For any $i \notin I$, $x_I(i) = 0$, so $x_I(i) - \sum_j e(i, j) x_I(j) \le 0$, giving coordinate contribution $\max(\le 0, 0) = 0$. Summing over all $i \in \mathrm{Fin}(k)$ yields $|I|$.

Lemma 3 (gpa_rhs_isGreatest). For any dimension $k$, simple graph $G$ on $\mathrm{Fin}(k)$, and maximum independent set $I \subseteq \mathrm{Fin}(k)$ satisfying gpa_indep and maximality $\forall S, \mathrm{gpa\_indep}\ G\ S \to |S| \le |I|$, the cardinality $|I|$ is the greatest element of gpa_rhsSet with matrix gpa_adjMat of $G$: $$\mathrm{IsGreatest}\ (\mathrm{gpa\_rhsSet}\ (\mathrm{gpa\_adjMat}\ G))\ (|I| : \mathbb{R}).$$ Proof. By Lemma 2 (gpa_rhs_attain), the value $|I|$ is attained in gpa_rhsSet. For every $x \in \mathrm{gpa\_cube}\ k$, the function $u^*(e, x)$ is convex, so its maximum over the cube $[0, 1]^k$ is attained at an extreme point $x \in \{0, 1\}^k$. The non-zero coordinates of any such optimizer form an independent set of $G$, whose cardinality is bounded by $|I|$ by the maximality hypothesis.

Lemma 4 (gpa_lhs_isGreatest). For any dimension $k$, simple graph $G$ on $\mathrm{Fin}(k)$, and maximum independent set $I \subseteq \mathrm{Fin}(k)$ satisfying gpa_indep, maximality $\forall S, \mathrm{gpa\_indep}\ G\ S \to |S| \le |I|$, $1 \le |I|$, and $|I| \le k$, the greatest element of gpa_lhsSet with matrix gpa_adjMat of $G$ is $1 - 1/|I| + 1/k$: $$\mathrm{IsGreatest}\ (\mathrm{gpa\_lhsSet}\ (\mathrm{gpa\_adjMat}\ G))\ \left(1 - \frac{1}{|I|} + \frac{1}{k}\right).$$ Proof. This lemma characterizes the exact maximum of $u^*(\sigma) - h(\sigma)$ over the simplex $\Delta_k$ on the independent set reduction instances from arXiv:2209.01146.

Lemma 5 (gpa_path3_indep). On the 3-vertex path gpa_path3, the set $I = \{0, 1\}$ is an independent set satisfying gpa_indep, and every independent set $S$ satisfies $|S| \le |I| = 2$. Proof. The graph gpa_path3 has vertex set $\mathrm{Fin}(3) = \{0, 1, 2\}$ and adjacency relation generated by $(0, 2)$ and $(1, 2)$. In Lean, this lemma is settled by the decide tactic, which exhaustively checks all $2^3 = 8$ subsets of $\mathrm{Fin}(3)$:

  • Subsets of cardinality 0: $\emptyset$, which is independent with $0 \le 2$.
  • Subsets of cardinality 1: $\{0\}$, $\{1\}$, $\{2\}$, all of which are independent with $1 \le 2$.
  • Subsets of cardinality 2: $\{0, 1\}$, $\{0, 2\}$, $\{1, 2\}$, where $\{0, 1\}$ contains no edge and is independent, while $\{0, 2\}$ and $\{1, 2\}$ are edges of gpa_path3 and thus not independent.
  • Subsets of cardinality 3: $\{0, 1, 2\}$, which contains edges $\{0, 2\}$ and $\{1, 2\}$ and thus is not independent.

Hence $I = \{0, 1\}$ is an independent set with $|I| = 2$, and every independent set has cardinality at most 2.

Proof of Theorem gpa_eq54_fails_of_indep. Let $G$ be a graph on $\mathrm{Fin}(k)$ with a maximum independent set $I$ satisfying $2 \le |I| < k$. 1. By Lemma 4 (gpa_lhs_isGreatest), $1 - 1/|I| + 1/k$ is the greatest element of gpa_lhsSet for gpa_adjMat of $G$. By uniqueness of greatest elements in a partially ordered set, we obtain $$L = 1 - \frac{1}{|I|} + \frac{1}{k}.$$ 2. By Lemma 3 (gpa_rhs_isGreatest), $|I|$ is the greatest element of gpa_rhsSet for gpa_adjMat of $G$. By uniqueness of greatest elements, we obtain $$R = |I|.$$ 3. Since $2 \le |I| < k$, the dimensions satisfy $0 < |I|$ and $0 < k$. To show $R/k < L$, we multiply both sides by $k > 0$, reducing the goal to proving $R < L \cdot k$. 4. Multiplying $L$ by $k$ gives $$L \cdot k = \left(1 - \frac{1}{|I|} + \frac{1}{k}\right) \cdot k = k - \frac{k}{|I|} + 1.$$ 5. We rewrite the difference $L \cdot k - R = k - k/|I| + 1 - |I|$ by putting it over the common denominator $|I|$: $$k - \frac{k}{|I|} + 1 - |I| = \frac{(|I| - 1)(k - |I|)}{|I|}.$$ In Lean, this algebraic step is verified by field simplification and polynomial ring normalization. 6. Since $2 \le |I|$, we have $|I| - 1 \ge 1 > 0$. Since $|I| < k$, we have $k - |I| \ge 1 > 0$. Since $|I| > 0$, the quotient is the product of two positive reals divided by a positive real, which is strictly positive: $$\frac{(|I| - 1)(k - |I|)}{|I|} > 0.$$ Therefore $L \cdot k - R > 0$, which yields $R < L \cdot k$ and hence $R/k < L$.

Proof of Theorem gpa_eq54_false. Assume, for contradiction, that $L = R/k$ holds for all $k$ and all $0/1$ matrices $e$. Specialize this assumption to $k = 3$ and the matrix $e$ given by gpa_adjMat for gpa_path3. By Lemma 1 (gpa_adjMat_zero_one), $e$ is a $0/1$ matrix. By Lemma 5 (gpa_path3_indep), $I = \{0, 1\}$ is a maximum independent set in gpa_path3. The cardinality $|I| = 2$ is verified by direct calculation. Because $2 \le 2$ and $2 < 3$, the hypotheses of Lemma 4 (gpa_lhs_isGreatest) and Lemma 3 (gpa_rhs_isGreatest) hold, giving greatest values $$L = 1 - \frac{1}{2} + \frac{1}{3} = \frac{5}{6}, \quad R = 2.$$ Applying gpa_eq54_fails_of_indep to gpa_path3 and $I = \{0, 1\}$ yields $$\frac{R}{3} < L \implies \frac{2}{3} < \frac{5}{6}.$$ However, the universal assumption requires $L = R/3$, that is, $5/6 = 2/3$. Because $5/6 - 2/3 = 1/6 > 0$, this is an immediate contradiction. Thus the universal claim is refuted.

Proof of Theorem gpa_cube_max_le_one_false. Assume, for contradiction, that for all $k$, all $0/1$ matrices $e$, and all $x \in \mathrm{gpa\_cube}\ k$, the value of gpa_uStar satisfies $u^*(e, x) \le 1$. Specialize to $k = 3$, $G = \mathrm{gpa\_path3}$, and the matrix $e$ given by gpa_adjMat for gpa_path3. By Lemma 1 (gpa_adjMat_zero_one), $e$ is a $0/1$ matrix. By Lemma 5 (gpa_path3_indep), $I = \{0, 1\}$ is an independent set. By Lemma 2 (gpa_rhs_attain), the indicator vector $x_I = (1, 1, 0)$ belongs to gpa_cube of dimension 3, and $$\mathrm{gpa\_uStar}\ e\ x_I = |I| = 2.$$ The assumption implies $u^*(e, x_I) \le 1$, which gives $2 \le 1$. This numerical contradiction refutes the auxiliary claim.

5. Discussion

The results formalized in Lean 4 clarify the behavior of Equation (5.4) and the auxiliary utility bound from arXiv:2209.01146.

Equation (5.4) was introduced in Section 5.3 of arXiv:2209.01146 as an exact identity intended to connect optimization over the probability simplex $\Delta_k$ to optimization over the hypercube $[0, 1]^k$ for general $0/1$ matrices. The theorems establish that this equation fails systematically. Rather than failing on an isolated degenerate instance, it fails on every simple graph whose independence number $\alpha$ satisfies $2 \le \alpha < k$. The strictly positive gap $$L - \frac{R}{k} = \frac{(\alpha - 1)(k - \alpha)}{k \alpha}$$ demonstrates that the simplex objective $u^*(\sigma) - h(\sigma)$ achieves a value strictly larger than $(1/k) \max_{[0,1]^k} u^*(x)$. On the concrete 3-vertex path graph gpa_path3, the gap is $(2 - 1)(3 - 2)/(3 \cdot 2) = 1/6$, where the two sides evaluate to $5/6$ and $2/3$.

Furthermore, the failure of the auxiliary bound $\max_{x \in [0,1]^k} u^*(x) \le 1$ shows why the derivation of Equation (5.4) breaks down. On independent set instances, $u^*$ evaluated at the indicator vector of an independent set counts the number of vertices in that set, taking values up to $\alpha(G)$. For any graph with $\alpha(G) \ge 2$, this maximum strictly exceeds 1, attaining 2 on gpa_path3.

The formalization specifically addresses the validity of Equation (5.4) and the auxiliary bound $\max_{[0,1]^k} u^*(x) \le 1$ on $0/1$ matrices arising from graph independent set instances. The material is silent on whether the overarching computational hardness result, Theorem 5 of arXiv:2209.01146, can be established through an alternate reduction or a modified identity that avoids Equation (5.4).

In addition, the parametric result gpa_eq54_fails_of_indep requires $2 \le \alpha < k$. It does not cover graphs where $\alpha = 1$ or $\alpha = k$. In these boundary cases, the algebraic difference $(\alpha - 1)(k - \alpha)/(k\alpha)$ evaluates to 0:

  • For complete graphs ($K_k$, where $\alpha = 1$), the simplex formula gives $1 - 1/1 + 1/k = 1/k$, and the scaled cube formula gives $1/k$, so the two algebraic expressions coincide.
  • For empty graphs (graphs with no edges, where $\alpha = k$), the simplex formula gives $1 - 1/k + 1/k = 1$, and the scaled cube formula gives $k/k = 1$, where the two expressions also coincide.

Beyond these boundary observations and the refutation of Equation (5.4) and the auxiliary bound, the cited material contains no further conjectures or open questions.

Why it is research-level

  • shows a published claim false (Generalized Principal-Agency: Contracts, Information, Games and Beyond, WINE 2024 (arXiv:2209.01146v2), Section 5.3, Eq. (5.4) in the proof of Theorem 5: fails for every graph with independence number 2 <= alpha < k (sides 1 - 1/alpha + 1/k and alpha/k))
  • shows a published claim false (Generalized Principal-Agency: Contracts, Information, Games and Beyond, WINE 2024 (arXiv:2209.01146v2), Section 5.3, Eq. (5.4) in the proof of Theorem 5 (max over the simplex of u* - h equals (1/k) max over the cube of u*): false; on the 3-vertex path the two sides are 5/6 and 2/3)
  • shows a published claim false (Generalized Principal-Agency: Contracts, Information, Games and Beyond, WINE 2024 (arXiv:2209.01146v2), Section 5.3 / Appendix 13.2: the auxiliary claim max over [0,1]^k of u* <= 1 used to derive Eq. (5.4) is false (value 2 on the 3-vertex path))

Lean declarations

  • gpa_eq54_fails_of_indepEq. (5.4) of arXiv:2209.01146 (max_{Δ_k} (u* - h) = (1/k) max_{[0,1]^k} u*) fails on every graph whose independence number α satisfies 2 ≤…
  • gpa_eq54_falseEq. (5.4) in the proof of Theorem 5 (hardness of costly information acquisition) of arXiv:2209.01146 is false: it is not true that for…
  • gpa_cube_max_le_one_falseThe auxiliary claim max_{x ∈ [0,1]^k} u*(x) ≤ 1 used in the proof of Eq. (5.4) of arXiv:2209.01146 is false: on the path with three…
  • gpa_adjMatThe 0/1 matrix e of arXiv:2209.01146, Section 5.3 (taken from the maximum-independent-set instances of the cited convex-maximisation…
  • gpa_uStarThe principal's utility of arXiv:2209.01146, Section 5.3: u*(σ) = Σ_i max{σ_i - Σ_j e_{ij} σ_j, 0} for a 0/1 matrix e.
  • gpa_cubeThe unit cube [0,1]^k.
  • gpa_indepAn independent set of the graph G.
  • gpa_lhsSetThe set of values u*(σ) - h(σ) over the simplex (left side of Eq. (5.4)).
  • gpa_rhsSetThe set of values u*(x) over the cube (right side of Eq. (5.4), before dividing by k).
  • gpa_path3The path 0 - 2 - 1 on three vertices.
  • gpa_adjMat_zero_oneThe adjacency matrix is a 0/1 matrix, as required in Section 5.3 of arXiv:2209.01146.
  • gpa_rhs_attainThe value α(G) is attained on the cube, at the indicator vector of a maximum independent set.
  • gpa_rhs_isGreatestExact value of the right side of Eq. (5.4) of arXiv:2209.01146 (before the factor 1/k): max_{x ∈ [0,1]^k} u*(x) = α(G).
  • gpa_lhs_isGreatestExact value of the left side of Eq. (5.4) of arXiv:2209.01146 on the independent-set instances: max_{σ ∈ Δ_k} u*(σ) - h(σ) = 1 - 1/α(G) +…
  • gpa_path3_indepIn the path 0 - 2 - 1, {0, 1} is a maximum independent set.

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:2209.01146

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.