⚡ electrical engineering

Asymmetric-Information Resource Allocation Games: An LP Approach to Purposeful Deception

本文介绍了欺骗性资源分配博弈（DRAG）框架，并证明目的性欺骗的完美贝叶斯纳什均衡可通过非迭代线性规划公式高效计算，从而使防御者能够最优地平衡资源分配与信念操纵，以将攻击者引离真实资产。

原作者： Longxu Pan, Yue Guan, Daigo Shishika, Panagiotis Tsiotras

发布于 2026-04-29

📖 1 分钟阅读☕ 轻松阅读

原作者： Longxu Pan, Yue Guan, Daigo Shishika, Panagiotis Tsiotras

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一场高风险的捉迷藏游戏，但防御者试图隐藏的不是一个人，而是一件珍贵的宝物（“真实资产”），而攻击者则试图找到它。

转折在于：防御者确切知道宝藏的位置，但攻击者不知道。攻击者只能看到防御者部署守卫（资源）的位置。防御者的目标不仅仅是守护宝藏；而是要诱骗攻击者，使其误以为宝藏位于他处，从而浪费时间去追逐一个虚假目标。

本文提出了一种计算该游戏完美策略的新方法，作者称之为DRAG（欺骗性资源分配游戏）。以下是用通俗语言进行的分解：

1. 核心问题：欺骗的“双刃剑”

通常，人们想到欺骗时，会认为只是为了欺骗而撒谎。但在这场游戏中，撒谎是有代价的。

两难困境：如果防御者将所有守卫都放在真正的宝藏上，攻击者可能会立即识破。如果防御者在虚假的“诱饵”宝藏上部署守卫以迷惑攻击者，真正的宝藏就会变得脆弱。
目标：防御者需要找到“金发姑娘”区域：何时撒谎是值得的？ 本文认为，只有当欺骗实际上能提高防御者的获胜几率时，才应进行欺骗。这被称为**“有目的的欺骗”**。

2. 旧方法 vs. 新方法

旧方法（欺骗性路径规划）：先前的研究集中在一个移动代理（如机器人）试图悄悄绕过守卫。该代理控制自己的移动，并能完美地就其去向撒谎。
新方法（DRAG）：在本文中，“说谎者”（防御者）并不控制整个游戏。防御者决定在哪里部署守卫，但攻击者决定走向哪里。“谎言”（攻击者看到的信号）是双方移动的结果。这就像一场舞蹈，其中一方试图将另一方引离舞池，而另一方也在试图将对方引向别处。这使得数学计算变得复杂得多，因为“谎言”和“策略”纠缠在一起。

3. 解决方案：“魔法计算器”（线性规划）

作者面临一个巨大的数学问题：当玩家根据彼此的行动不断更新猜测时，如何计算完美策略？通常，这需要缓慢的、试错式的计算机模拟。

然而，作者发现了一个巧妙的技巧。他们证明，这个复杂且纠缠的问题可以通过**线性规划（LP）**来解开并求解。

类比：想象试图解决一个巨大的、不断变形的 3D 拼图。作者找到了一种方法，将拼图压平到一张 2D 表格上。一旦压平，这就不再是猜谜游戏；而是一项计算机可以瞬间解决的直接计算。
结果：他们创建了一个数学公式，告诉防御者应该以何种频率守护真实宝藏与诱饵，以最大化其胜率。

4. 游戏中发生了什么？（结果）

作者在网格游戏（如简化的棋盘）上测试了他们的数学模型。

技巧：防御者并非随机撒谎。他们策略性地制造“战争迷雾”。例如，防御者可能会在虚假目标上部署刚好足够的守卫，以使攻击者犹豫不决。
“无差异”时刻：最有趣的发现是，防御者试图让攻击者感到无差异。防御者操纵局势，使得在关键节点，攻击者认为：“无论我走哪条路都无所谓；两条路看起来风险相当。”
为何有效：当攻击者感到困惑且无法决定时，他们可能会偶然选择错误的路线。这为防御者争取了额外时间来加强真实宝藏的防御。

5. 为何重要

本文证明了这种“聪明的撒谎”是有效的。

得分：在他们的测试中，使用这种基于数学新策略的防御者，比仅仅诚实行事或攻击者从一开始就知道真相的情况，表现好 19%。
教训：欺骗不是为了混乱或无端地制造困惑。它是关于在对手需要做出决定的确切时刻，精心塑造对手的信念，将其引向错误，而防御者无需牺牲自身安全。

总结：本文提供了一份供捉迷藏游戏中防御者使用的数学“作弊表”。它展示了如何利用有限资源制造恰到好处的困惑，诱骗对手犯错，证明了最好的谎言是那些为了获胜而精心计算的谎言，而不仅仅是为了迷惑。

以下是论文《非对称信息资源分配博弈：一种用于蓄意欺骗的线性规划方法》的详细技术总结。

1. 问题定义：欺骗性资源分配博弈 (DRAG)

本文引入了DRAG，这是一个在图 $G=(S, E)$ 上进行的离散时间动态博弈，由防御者（知情方）和攻击者（不知情方）参与。

设置：自然根据先验分布 $b_0$ 从候选资产集合 $\Theta$ 中选择一个“真实资产” $\theta_{true}$ 。该信息对防御者是私有的。
动态过程：
- 攻击者在图上移动，试图到达真实资产，以最小化该处累积的资源。
- 防御者在每个时间步将有限的防御资源分配给一个候选资产。
- 攻击者观察防御者的分配历史，但不知道真实资产。
目标：
- 防御者：最大化真实资产处累积的总资源。为此，防御者必须在保护真实资产与欺骗攻击者之间取得平衡，即通过将资源分配给诱饵来操纵攻击者的信念。
- 攻击者：通过从观察到的分配历史中推断 $\theta_{true}$ 并导航至该资产，以最小化真实资产处的资源。
关键区别：与以往“欺骗性路径规划”（DPP）工作中知情方控制可观测信号（轨迹）不同，在 DRAG 中，信号（分配历史）源于双方的交互。防御者通过分配影响信念，但攻击者控制状态演化，从而形成了信念与策略的耦合相互依赖性。

2. 方法论：用于 PBNE 的线性规划

核心挑战在于计算完美贝叶斯纳什均衡 (PBNE)，即参与者在通过贝叶斯规则更新信念的同时优化策略。防御者策略与攻击者信念更新之间的耦合通常使该问题非凸且难以求解。

作者提出了一种高效的、非迭代的线性规划 (LP) 公式来求解 PBNE。

A. 动态规划 (DP) 公式

作者首先建立了博弈值的动态规划表示。他们利用了博弈值关于信念 $b_t$ 的期望前值（ex-ante value）的线性性质。

他们将均衡值 $V^*(h_t, b_t)$ 定义为攻击者策略 $\sigma$ 和防御者策略 $\tau$ 上的极小极大问题。
关键在于，他们表明未来值取决于缩放信念 $\alpha b_{t+1}$ ，其中缩放因子 $\alpha$ 取决于防御者的当前策略。

B. 线性规划变换

为了消除信念与策略之间的非线性耦合，作者引入了辅助变量来编码类型与历史的联合分布：

防御者的 LP：他们定义了变量 $z^\theta_{h_t}$ $z_{h_{t}}^{θ}$ ，表示防御者类型为 $\theta$ $θ$ 且历史 $h_t$ $h_{t}$ 实现（结合所采取的行动）的联合概率。
- 这种变换将涉及信念和策略乘积的双线性约束转化为线性约束。
- 由此产生的 LP（公式 18）在满足以下约束的条件下最大化防御者的期望收益：
  1. 最优性：该策略是对所有攻击者行动的最佳响应。
  2. 一致性：联合概率根据博弈动态和贝叶斯更新正确传播。
攻击者的 LP：攻击者的均衡策略由防御者 LP 的对偶导出。攻击者最小化期望收益，使用变量 $\eta$ 来编码沿轨迹的行动概率。

C. 策略重构

一旦求解 LP，即可通过归一化重构均衡策略：

防御者策略： $\tau^\theta_{ht} = z^\theta_{ht} / \sum z^\theta_{ht}$ 。
攻击者策略： $\sigma_{ht} = \eta_{ht} / \sum \eta_{ht}$ 。

3. 主要贡献

新颖的博弈公式 (DRAG)：引入了欺骗性路径规划的对偶问题，其中知情方（防御者）操纵信号（分配）但不完全控制博弈状态演化。
结构洞察：证明了知情方可以通过塑造可观测分配历史的分布来影响不知情方的信念更新，即使没有对状态的完全控制权。
高效计算：证明了尽管存在复杂的信念 - 策略耦合，PBNE 仍可通过单个、非迭代的线性规划计算。这将先前的工作（仅限于 2 个目标和完全信号控制）扩展到了具有多个候选目标的任意图。
蓄意欺骗：定义并刻画了“蓄意欺骗”，即仅在欺骗能提升防御者性能时才使用欺骗，而非为了模糊性而欺骗。

4. 数值结果

作者在具有两个候选资产且先验 $b_0 = [0.2, 0.8]$ 的 $4 \times 4$ 网格博弈上验证了该方法。

涌现的欺骗行为：
- LP 解显示，防御者最初随机化分配，以在攻击者中创造特定的“模糊”信念（ $b_1 \approx [0.53, 0.47]$ ）。
- 这种信念使攻击者在关键决策点对于移向资产 0 还是资产 1 无差异。
- 一旦攻击者无差异，防御者便停止欺骗，并将资源集中于真实资产。这证实了欺骗的“蓄意”性质：它仅被用于达到攻击者决策被中和的状态。
欺骗价值 (VoD)：
- 完全信息基线：如果真实资产已知，防御者的期望收益将为 $-20.6$。
- DRAG 均衡：通过欺骗，防御者实现了 $-16.68$ 的期望收益。
- 结果：这代表了19% 的性能提升，量化了防御者信息优势和战略欺骗的价值。
均衡验证：
- 作者验证了任何一方单方面偏离都不会获益。
- 忽略欺骗的策略（例如，始终将资源分配给真实资产）被证明会被攻击者利用，导致防御者结果更差。

5. 意义

这项工作 bridging 了理论博弈论与对抗环境中的实际资源分配之间的差距。

理论方面：它解决了在具有耦合信念 - 策略动态的博弈中求解 PBNE 的计算困难，提供了一种可扩展的 LP 方法。
实践方面：它提供了一个框架，用于设计防御系统（如网络安全、军事后勤），其中资源有限，必须不仅用于保护，还要用于主动误导对手。
概念方面：它将范式从“为了模糊性的欺骗”转变为“蓄意欺骗”，其目标是将对手的信念引导至特定状态，以最大化防御者的效用。

建议的未来工作包括将框架扩展到双向信息不对称，并将基于学习的方法应用于更大规模的环境。