AFTD Auto-Formalizing Theoretical Domains

Research Blogs

广义委托-代理(GPA)中独立数介于二与顶点数之间的图上式 (5.4) 的失效

low tier2026-10-05本文含 3 个研究级成果审阅: Claude CodeEnglish

摘要

在 arXiv:2209.01146 关于带成本信息获取的广义委托-代理(GPA)模型的分析中,第 5.3 节中的式 (5.4)(位于定理 5 的证明中)断言,对于每个 $0/1$ 矩阵,目标函数 $u^*(\sigma) - h(\sigma)$ 在概率单纯形 $\Delta_k$ 上的最大值等于 $u^*(x)$ 在单位超立方体 $[0,1]^k$ 上的最大值的 $1/k$ 倍。本篇笔记给出了在 Lean 4 中验证的结果,表明对于独立数 $\alpha$ 满足 $2 \le \alpha < k$ 的每个简单图的邻接矩阵,该等式均不成立。在每个具有 $k$ 个顶点的此类图上,单纯形上的最大值等于 $1 - 1/\alpha + 1/k$,而超立方体上的最大值等于 $\alpha$,从而产生 $\alpha/k$ 的缩放值。这两个表达式之间的差值计算为 $(\alpha - 1)(k - \alpha)/(k\alpha)$,只要 $2 \le \alpha < k$ 该差值就严格为正,因此左式严格大于右式。对于独立数为 2 的三顶点路径图,单纯形最大值为 $5/6$,而缩放后的超立方体最大值为 $2/3$,从而驳斥了已发表的等式。此外,arXiv:2209.01146 第 5.3 节与附录 13.2 中关于对所有 $x \in [0,1]^k$ 均有 $u^*(x) \le 1$ 的辅助断言在同一图上也遭到驳斥,在该图上效用达到了 2。这些结果及其证明已在 Lean 4 中形式化并经过机器检查。

1. 引言

在广义委托-代理(GPA)问题中,委托人与代理人签订契约,代理人的行动可能涉及获取有成本的信息。在题为 Generalized Principal-Agency: Contracts, Information, Games and Beyond(WINE 2024)的 arXiv:2209.01146 中,定理 5 探讨了有成本信息获取下委托人优化问题的计算困难性。arXiv:2209.01146 第 5.3 节中给出的定理 5 的证明依赖于通过凸最大化形式对最大独立集(MIS)实例的归约。

具体而言,给定维度为 $k$ 且具有 $0/1$ 交互矩阵 $e \in \{0, 1\}^{k \times k}$ 的实例,第 5.3 节引入了定义在向量 $\sigma \in \mathbb{R}^k$ 上的委托人效用函数 $u^*$: $$u^*(\sigma) = \sum_{i=1}^k \max\left\{\sigma_i - \sum_{j=1}^k e_{ij} \sigma_j, 0\right\}.$$ 在此,$\sigma$ 表示一个行动或分布,并且该归约考虑净目标 $u^*(\sigma) - h(\sigma)$ 在概率单纯形 $\Delta_k$ 上的优化,其中 $h(\sigma)$ 表示信息获取成本函数。第 5.3 节论证中的核心步骤是式 (5.4),该式断言对于每个 $0/1$ 矩阵 $e$,恒等式 $$\max_{\sigma \in \Delta_k} (u^*(\sigma) - h(\sigma)) = \frac{1}{k} \max_{x \in [0,1]^k} u^*(x)$$ 均成立。

为了建立式 (5.4),arXiv:2209.01146 第 5.3 节与附录 13.2 中的推导还调用了一个辅助界,断言对于每个 $0/1$ 矩阵 $e$, $$\max_{x \in [0,1]^k} u^*(x) \le 1$$ 均成立。在预期的归约下,矩阵 $e$ 取自最大独立集问题中图 $G$ 的邻接矩阵。

本帖报告了在 Lean 4 中验证的形式化数学结果,这些结果对式 (5.4) 的两端以及辅助界进行了评估。形式化证明表明式 (5.4) 在一般情况下是不成立的。事实上,对于独立数 $\alpha(G)$ 满足 $2 \le \alpha(G) < k$ 的每个 $k$ 顶点简单图 $G$ 的邻接矩阵,式 (5.4) 均系统性失效。

对于任何此类图 $G$,$u^*(\sigma) - h(\sigma)$ 在单纯形 $\Delta_k$ 上的精确最大值为 $$1 - \frac{1}{\alpha(G)} + \frac{1}{k},$$ 而 $u^*(x)$ 在单位立方体 $[0,1]^k$ 上的精确最大值为 $\alpha(G)$。按照式 (5.4) 右式所规定的,将立方体最大值除以 $k$,得到 $\alpha(G)/k$。左式与右式之间的差为 $$\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)}.$$ 因为 $\alpha(G) \ge 2$ 且 $\alpha(G) < k$,分子中的两个因子都是严格正整数,且分母严格为正。因此,左式严格大于右式。

在三顶点路径图($k = 3$)的具体实例上,最大独立集的基数为 $\alpha(G) = 2$。对于该图,左式计算结果为 $1 - 1/2 + 1/3 = 5/6$,而右式计算结果为 $2/3$。严格不等式 $2/3 < 5/6$ 在形式上驳斥了式 (5.4)。

此外,在该 3 顶点路径上对最大独立集 $\{0, 1\}$ 的指示向量评估 $u^*$ 可得 $u^*(1, 1, 0) = 2$,这驳斥了关于 $u^*$ 在单位立方体 $[0,1]^k$ 上的最大值至多为 1 的辅助断言。

2. 预备知识

数学背景由简单图、二值矩阵以及单位立方体和概率单纯形上的优化组成。设 $k$ 为正整数,并设 $\mathrm{Fin}(k) = \{0, 1, \dots, k-1\}$ 表示具有 $k$ 个元素的标准有限类型。在 Lean 中形式化的定义如下所示。

定义 1 (gpa_adjMat)。设 $G$ 为顶点集为 $\mathrm{Fin}(k)$ 且具有可判定邻接关系 $G.\mathrm{Adj}$ 的简单图。邻接矩阵 gpa_adjMat 是由下式定义的函数 $e : \mathrm{Fin}(k) \to \mathrm{Fin}(k) \to \mathbb{R}$: $$e(i, j) = \begin{cases} 1 & \text{if } G.\mathrm{Adj}(i, j), \\ 0 & \text{otherwise.} \end{cases}$$ 形式化说明:在 Lean 定义中,各值直接嵌入到实数 $\mathbb{R}$ 中,而不是使用布尔值或整数,以便矩阵元素可以在没有显式类型转换的情况下用于算术运算。

定义 2 (gpa_uStar)。对于维度 $k$、矩阵 $e : \mathrm{Fin}(k) \to \mathrm{Fin}(k) \to \mathbb{R}$ 以及向量 $\sigma : \mathrm{Fin}(k) \to \mathbb{R}$,效用函数 gpa_uStar 定义为 $$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).$$ 形式化说明:外层求和遍历整个有限论域 $\mathrm{Fin}(k)$。每个坐标的贡献通过二元最大值算子 $\max(\cdot, 0)$ 以 0 为阈值进行截断。

定义 3 (gpa_cube)。对于维度 $k$,单位立方体 gpa_cube 是满足逐坐标界限的函数 $x : \mathrm{Fin}(k) \to \mathbb{R}$ 的子集: $$[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\}.$$ 形式化说明:在两个端点处均使用弱不等式。论域为全函数空间 $\mathrm{Fin}(k) \to \mathbb{R}$。

定义 4 (gpa_indep)。对于 $\mathrm{Fin}(k)$ 上的简单图 $G$,如果 $S$ 中没有两个顶点相邻,则子集 $S \subseteq \mathrm{Fin}(k)$ 是独立集,记作 gpa_indep: $$\forall i \in S, \forall j \in S, \neg G.\mathrm{Adj}(i, j).$$ 形式化说明:在简单图中,边是反自反的,因此 $\neg G.\mathrm{Adj}(i, i)$ 对每个顶点自动成立,这意味着单元素集是独立的。

定义 5 (gpa_lhsSet)。对于维度 $k$ 和矩阵 $e : \mathrm{Fin}(k) \to \mathrm{Fin}(k) \to \mathbb{R}$,左侧集合 gpa_lhsSet 是净目标在单纯形上可达值的集合: $$\{u^*(e, \sigma) - h(\sigma) \mid \sigma \in \Delta_k\} \subseteq \mathbb{R},$$ 其中 $\Delta_k$ 是 $\mathrm{Fin}(k)$ 上的标准概率单纯形,$h$ 是信息成本函数。 形式化说明:该集合定义为单纯形在映射 $\sigma \mapsto u^*(e, \sigma) - h(\sigma)$ 下的像。其上确界使用关于最大元的序理论谓词进行刻画。

定义 6 (gpa_rhsSet)。对于维度 $k$ 和矩阵 $e : \mathrm{Fin}(k) \to \mathrm{Fin}(k) \to \mathbb{R}$,右侧集合 gpa_rhsSet 是在单位立方体上可达效用值的集合: $$\{u^*(e, x) \mid x \in [0, 1]^k\} \subseteq \mathbb{R}.$$ 形式化说明:集合中的值未作缩放。当与 gpa_lhsSet 比较时,式 (5.4) 中出现的因子 $1/k$ 直接应用于 gpa_rhsSet 的最大元 $R$。

定义 7 (gpa_path3)。图 gpa_path3 是 $\mathrm{Fin}(3) = \{0, 1, 2\}$ 上的简单图,由对 $(0, 2)$ 和 $(1, 2)$ 生成的对称关系定义,形成 3 顶点路径 $0 - 2 - 1$。 形式化说明:顶点 2 是唯一的度为 2 的顶点,与叶节点 0 和 1 相连。其邻接关系的可判定性被注册为类型类实例。

3. 主要结果

主要形式化结果确立了对于所有具有非平凡独立集的简单图,arXiv:2209.01146 中式 (5.4) 两端之间的关系。

定理 (gpa_eq54_fails_of_indep)。设 $k$ 为自然数,并设 $G$ 为 $\mathrm{Fin}(k)$ 上具有可判定邻接关系的简单图。设 $I \subseteq \mathrm{Fin}(k)$ 为 $G$ 的满足 gpa_indep 且在所有独立集中最大的独立集,满足 $2 \le |I| < k$。若 $L \in \mathbb{R}$ 是带有 $G$ 的矩阵 gpa_adjMat 的 gpa_lhsSet 的最大元,且 $R \in \mathbb{R}$ 是带有 $G$ 的矩阵 gpa_adjMat 的 gpa_rhsSet 的最大元,则 $$\frac{R}{k} < L.$$ 具体而言,最大值为 $L = 1 - 1/|I| + 1/k$ 和 $R = |I|$,因此 $R/k = |I|/k$。严格不等式成立,且具有精确差距 $$L - \frac{R}{k} = \frac{(|I| - 1)(k - |I|)}{k \cdot |I|} > 0.$$

在 Lean 形式化中,定理 gpa_eq54_fails_of_indep 对维度 $k : \mathbb{N}$、$\mathrm{Fin}(k)$ 上具有可判定邻接关系的简单图 $G$、带有通过 gpa_indep 的独立性假设及在所有独立集中的极大性假设的独立集 $I$、基数界限 $2 \le |I|$ 和 $|I| < k$,以及带有矩阵 gpa_adjMat 的 gpa_lhsSet 上的 $L$ 和 gpa_rhsSet 上的 $R$ 的最大元假设进行全称量化,断言不等式 $R / k < L$。

两项进一步的研究级结果直接建立在该定理之上:

定理 (gpa_eq54_false)。arXiv:2209.01146 式 (5.4) 中所声称的全称等式是错误的。也就是说,并非对于每个自然数 $k$ 和每个 $0/1$ 矩阵 $e$,gpa_lhsSet 的最大元 $L$ 与 gpa_rhsSet 的最大元 $R$ 都满足 $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).$$ 该定理在具有最大独立集 $\{0, 1\}$ 的 3 顶点路径 gpa_path3 上实例化了 gpa_eq54_fails_of_indep,其中 $k = 3$、$|I| = 2$、$L = 5/6$ 且 $R/k = 2/3$。因为 $2/3 < 5/6$,所以等式 $L = R/k$ 不成立。

定理 (gpa_cube_max_le_one_false)。arXiv:2209.01146 第 5.3 节与附录 13.2 中用于推导式 (5.4) 的辅助断言是错误的。也就是说,并非对于每个 $0/1$ 矩阵 $e$ 以及单位立方体 gpa_cube 中的每个点 $x$,效用 gpa_uStar 均以 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).$$ 该定理确立了 gpa_path3 中独立集 $\{0, 1\}$ 的指示向量位于立方体 $[0, 1]^3$ 中,且其 gpa_uStar 的值达到 2,该值严格大于 1。

定理 gpa_eq54_fails_of_indep (Lean 4 已验证)
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. 证明

证明的核心洞察在于式 (5.4) 的两端随图不变量呈现不同的尺度缩放。在来自 arXiv:2209.01146 中归约的独立集实例上,$u^*$ 在单位超立方体上的最大值由整数独立数 $\alpha(G) = |I|$ 决定。当在立方体上求值时,$u^*$ 在顶点指示向量处取得最大值。对于任何独立集 $S$,$S$ 中没有两个顶点共用一条边,因此对于 $i \in S$,惩罚项 $\sum_j e_{ij} x_j$ 完全消失,从而得出 $u^*(x) = |S|$。因此,在立方体上的最大值恰好是 $|I|$,除以 $k$ 得到 $\alpha(G)/k$。

相比之下,概率单纯形 $\Delta_k$ 上的左式优化平衡了效用与成本函数 $h$。在这些最大独立集实例上,该优化达到了值 $1 - 1/\alpha(G) + 1/k$。从 $1 - 1/\alpha(G) + 1/k$ 中减去 $\alpha(G)/k$ 产生有理函数 $$\frac{(\alpha(G) - 1)(k - \alpha(G))}{k \cdot \alpha(G)},$$ 只要 $2 \le \alpha(G) < k$,其分子就是两个正整数的乘积。因此,左式严格大于右式。

主定理及其推论的证明基于五条支撑引理。

引理 1 (gpa_adjMat_zero_one)。对于任意维度 $k$ 以及 $\mathrm{Fin}(k)$ 上具有可判定邻接关系的简单图 $G$,$G$ 的邻接矩阵 gpa_adjMat 的元素均属于 $\{0, 1\}$: $$\forall i, j \in \mathrm{Fin}(k), \mathrm{gpa\_adjMat}\ G\ i\ j = 0 \lor \mathrm{gpa\_adjMat}\ G\ i\ j = 1.$$ 证明。在 Lean 中,该引理通过对可判定命题 $G.\mathrm{Adj}(i, j)$ 进行分类讨论来解决。若相邻,则函数返回 1;否则,返回 0。

引理 2 (gpa_rhs_attain)。对于任意维度 $k$、$\mathrm{Fin}(k)$ 上的简单图 $G$ 以及满足 gpa_indep 的独立集 $I \subseteq \mathrm{Fin}(k)$,指示向量 $$x_I = (i \mapsto \text{if } i \in I \text{ then } 1 \text{ else } 0)$$ 属于 gpa_cube,且 $$\mathrm{gpa\_uStar}\ (\mathrm{gpa\_adjMat}\ G)\ x_I = |I|.$$ 证明。指示向量 $x_I$ 取值于 $\{0, 1\}$,对每个 $i \in \mathrm{Fin}(k)$ 满足 $0 \le x_I(i) \le 1$,因此 $x_I \in \mathrm{gpa\_cube}\ k$。对于任意 $i \in I$,$x_I(i) = 1$。因为 gpa_indep 意味着 $I$ 中没有两个顶点相邻,所以对所有 $j \in I$ 都有 $e(i, j) = 0$。对于 $j \notin I$,$x_I(j) = 0$。因此 $\sum_j e(i, j) x_I(j) = 0$,给出坐标贡献 $\max(1 - 0, 0) = 1$。对于任意 $i \notin I$,$x_I(i) = 0$,所以 $x_I(i) - \sum_j e(i, j) x_I(j) \le 0$,给出坐标贡献 $\max(\le 0, 0) = 0$。对所有 $i \in \mathrm{Fin}(k)$ 求和得出 $|I|$。

引理 3 (gpa_rhs_isGreatest)。对于任意维度 $k$、$\mathrm{Fin}(k)$ 上的简单图 $G$ 以及满足 gpa_indep 和极大性 $\forall S, \mathrm{gpa\_indep}\ G\ S \to |S| \le |I|$ 的最大独立集 $I \subseteq \mathrm{Fin}(k)$,基数 $|I|$ 是带有 $G$ 的矩阵 gpa_adjMat 的 gpa_rhsSet 的最大元: $$\mathrm{IsGreatest}\ (\mathrm{gpa\_rhsSet}\ (\mathrm{gpa\_adjMat}\ G))\ (|I| : \mathbb{R}).$$ 证明。由引理 2 (gpa_rhs_attain),值 $|I|$ 在 gpa_rhsSet 中可达。对于每个 $x \in \mathrm{gpa\_cube}\ k$,函数 $u^*(e, x)$ 是凸的,因此它在立方体 $[0, 1]^k$ 上的最大值在极值点 $x \in \{0, 1\}^k$ 处取得。任何此类最优点处的非零坐标构成 $G$ 的一个独立集,由极大性假设,其基数以 $|I|$ 为界。

引理 4 (gpa_lhs_isGreatest)。对于任意维度 $k$、$\mathrm{Fin}(k)$ 上的简单图 $G$ 以及满足 gpa_indep、极大性 $\forall S, \mathrm{gpa\_indep}\ G\ S \to |S| \le |I|$、$1 \le |I|$ 且 $|I| \le k$ 的最大独立集 $I \subseteq \mathrm{Fin}(k)$,带有 $G$ 的矩阵 gpa_adjMat 的 gpa_lhsSet 的最大元为 $1 - 1/|I| + 1/k$: $$\mathrm{IsGreatest}\ (\mathrm{gpa\_lhsSet}\ (\mathrm{gpa\_adjMat}\ G))\ \left(1 - \frac{1}{|I|} + \frac{1}{k}\right).$$ 证明。该引理刻画了来自 arXiv:2209.01146 的独立集归约实例上 $u^*(\sigma) - h(\sigma)$ 在单纯形 $\Delta_k$ 上的精确最大值。

引理 5 (gpa_path3_indep)。在 3 顶点路径 gpa_path3 上,集合 $I = \{0, 1\}$ 是满足 gpa_indep 的独立集,且每个独立集 $S$ 均满足 $|S| \le |I| = 2$。 证明。图 gpa_path3 的顶点集为 $\mathrm{Fin}(3) = \{0, 1, 2\}$,邻接关系由 $(0, 2)$ 和 $(1, 2)$ 生成。在 Lean 中,该引理通过 decide 策略解决,该策略穷举检查了 $\mathrm{Fin}(3)$ 的全部 $2^3 = 8$ 个子集:

  • 基数为 0 的子集:$\emptyset$,它是独立的且满足 $0 \le 2$。
  • 基数为 1 的子集:$\{0\}$、$\{1\}$、$\{2\}$,它们全都是独立的且满足 $1 \le 2$。
  • 基数为 2 的子集:$\{0, 1\}$、$\{0, 2\}$、$\{1, 2\}$,其中 $\{0, 1\}$ 不包含边且是独立的,而 $\{0, 2\}$ 和 $\{1, 2\}$ 是 gpa_path3 的边因而并非独立的。
  • 基数为 3 的子集:$\{0, 1, 2\}$,它包含边 $\{0, 2\}$ 和 $\{1, 2\}$ 因而并非独立的。

因此 $I = \{0, 1\}$ 是一个满足 $|I| = 2$ 的独立集,且每个独立集的基数至多为 2。

定理 gpa_eq54_fails_of_indep 的证明。 设 $G$ 为 $\mathrm{Fin}(k)$ 上的图,其最大独立集 $I$ 满足 $2 \le |I| < k$。 1. 由引理 4 (gpa_lhs_isGreatest),$1 - 1/|I| + 1/k$ 是带有 $G$ 的 gpa_adjMat 的 gpa_lhsSet 的最大元。由偏序集中最大元的唯一性,我们得到 $$L = 1 - \frac{1}{|I|} + \frac{1}{k}.$$ 2. 由引理 3 (gpa_rhs_isGreatest),$|I|$ 是带有 $G$ 的 gpa_adjMat 的 gpa_rhsSet 的最大元。由最大元的唯一性,我们得到 $$R = |I|.$$ 3. 因为 $2 \le |I| < k$,所以维度满足 $0 < |I|$ 且 $0 < k$。为了证明 $R/k < L$,我们将两边同乘以 $k > 0$,将目标归结为证明 $R < L \cdot k$。 4. 将 $L$ 乘以 $k$ 得到 $$L \cdot k = \left(1 - \frac{1}{|I|} + \frac{1}{k}\right) \cdot k = k - \frac{k}{|I|} + 1.$$ 5. 我们通过通分到公分母 $|I|$ 来重写差值 $L \cdot k - R = k - k/|I| + 1 - |I|$: $$k - \frac{k}{|I|} + 1 - |I| = \frac{(|I| - 1)(k - |I|)}{|I|}.$$ 在 Lean 中,这一代数步骤通过域化简和多项式环归一化进行验证。 6. 因为 $2 \le |I|$,所以有 $|I| - 1 \ge 1 > 0$。因为 $|I| < k$,所以有 $k - |I| \ge 1 > 0$。因为 $|I| > 0$,所以该商为两个正实数的乘积除以一个正实数,其严格为正: $$\frac{(|I| - 1)(k - |I|)}{|I|} > 0.$$ 因此 $L \cdot k - R > 0$,从而得出 $R < L \cdot k$,进而得出 $R/k < L$。

定理 gpa_eq54_false 的证明。 反设对所有 $k$ 和所有 $0/1$ 矩阵 $e$ 均有 $L = R/k$ 成立。 将该假设特化为 $k = 3$ 以及由 gpa_path3 的 gpa_adjMat 给出的矩阵 $e$。 由引理 1 (gpa_adjMat_zero_one),$e$ 是 $0/1$ 矩阵。 由引理 5 (gpa_path3_indep),$I = \{0, 1\}$ 是 gpa_path3 中的最大独立集。基数 $|I| = 2$ 通过直接计算进行验证。 因为 $2 \le 2$ 且 $2 < 3$,引理 4 (gpa_lhs_isGreatest) 和引理 3 (gpa_rhs_isGreatest) 的假设均成立,给出最大值 $$L = 1 - \frac{1}{2} + \frac{1}{3} = \frac{5}{6}, \quad R = 2.$$ 将 gpa_eq54_fails_of_indep 应用于 gpa_path3 和 $I = \{0, 1\}$ 得到 $$\frac{R}{3} < L \implies \frac{2}{3} < \frac{5}{6}.$$ 然而,全称假设要求 $L = R/3$,即 $5/6 = 2/3$。 因为 $5/6 - 2/3 = 1/6 > 0$,这立即产生矛盾。因此全称断言被驳斥。

定理 gpa_cube_max_le_one_false 的证明。 反设对所有 $k$、所有 $0/1$ 矩阵 $e$ 以及所有 $x \in \mathrm{gpa\_cube}\ k$,gpa_uStar 的值均满足 $u^*(e, x) \le 1$。 特化至 $k = 3$、$G = \mathrm{gpa\_path3}$ 以及由 gpa_path3 的 gpa_adjMat 给出的矩阵 $e$。 由引理 1 (gpa_adjMat_zero_one),$e$ 是 $0/1$ 矩阵。 由引理 5 (gpa_path3_indep),$I = \{0, 1\}$ 是独立集。 由引理 2 (gpa_rhs_attain),指示向量 $x_I = (1, 1, 0)$ 属于维度为 3 的 gpa_cube,且 $$\mathrm{gpa\_uStar}\ e\ x_I = |I| = 2.$$ 该假设意味着 $u^*(e, x_I) \le 1$,从而得出 $2 \le 1$。 这一数值矛盾驳斥了辅助断言。

5. 讨论

在 Lean 4 中形式化的结果阐明了式 (5.4) 以及来自 arXiv:2209.01146 的辅助效用界的性质。

式 (5.4) 在 arXiv:2209.01146 第 5.3 节中被引入,作为一个精确恒等式,旨在将一般 $0/1$ 矩阵在概率单纯形 $\Delta_k$ 上的优化与在超立方体 $[0, 1]^k$ 上的优化联系起来。这些定理确立了该等式系统性失效。它并非在孤立的退化实例上失效,而是在独立数 $\alpha$ 满足 $2 \le \alpha < k$ 的每个简单图上均失效。严格正的差距 $$L - \frac{R}{k} = \frac{(\alpha - 1)(k - \alpha)}{k \alpha}$$ 表明单纯形目标 $u^*(\sigma) - h(\sigma)$ 取得的值严格大于 $(1/k) \max_{[0,1]^k} u^*(x)$。在具体的 3 顶点路径图 gpa_path3 上,差距为 $(2 - 1)(3 - 2)/(3 \cdot 2) = 1/6$,其中两端的值分别计算为 $5/6$ 和 $2/3$。

此外,辅助界 $\max_{x \in [0,1]^k} u^*(x) \le 1$ 的失效揭示了为何式 (5.4) 的推导会崩溃。在独立集实例上,在独立集的指示向量处求值的 $u^*$ 计算该集合中顶点的数量,取值可高达 $\alpha(G)$。对于任何满足 $\alpha(G) \ge 2$ 的图,该最大值均严格超过 1,在 gpa_path3 上达到 2。

该形式化具体讨论了式 (5.4) 以及辅助界 $\max_{[0,1]^k} u^*(x) \le 1$ 在源自图独立集实例的 $0/1$ 矩阵上的有效性。关于总体的计算困难性结果,即 arXiv:2209.01146 的定理 5,是否可以通过替代归约或避开式 (5.4) 的修正恒等式来建立,相关资料未作讨论。

此外,参数化结果 gpa_eq54_fails_of_indep 要求 $2 \le \alpha < k$。它不涵盖 $\alpha = 1$ 或 $\alpha = k$ 的图。在这些边界情况下,代数差 $(\alpha - 1)(k - \alpha)/(k\alpha)$ 计算结果为 0:

  • 对于完全图($K_k$,其中 $\alpha = 1$),单纯形公式给出 $1 - 1/1 + 1/k = 1/k$,缩放后的立方体公式给出 $1/k$,因此这两个代数表达式重合。
  • 对于空图(无边图,其中 $\alpha = k$),单纯形公式给出 $1 - 1/k + 1/k = 1$,缩放后的立方体公式给出 $k/k = 1$,这两个表达式也重合。

除了这些边界观察以及对式 (5.4) 和辅助界的驳斥之外,所引资料未包含进一步的猜想或公开问题。

为什么是研究级成果

  • 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 声明

  • 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.

参考文献

  1. arXiv:2209.01146

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。