精读笔记
Problem Setting
论文标题：Intermediate Bilevel Optimization: Modeling Endogenous Follower Tie-Breaking Behavior（arXiv preprint / 2026）。
这篇论文解决的是 bilevel optimization 中一个长期被简化掉但实际很关键的问题：当 follower 的 lower-level optimum 非唯一时，leader 不应只假设 follower 选最有利于 leader 的 optimistic solution，或最不利于 leader 的 pessimistic solution，而应允许 follower 在 optimal/ε-optimal response set 中按某种 decision-dependent probability tie-break。
真正困难点在于：follower response 的随机性不是普通外生不确定性。leader 选择 x 后，不仅 follower 的 feasible/optimal response set S(x,ε) 变了，tie-breaking probability μ_x 也变了。因此 expectation E_{y~μ_x}[F(x,y)] 同时含有 moving support 和 moving density。直接 deterministic equivalent 往往会变成高度非凸、嵌套、甚至不可写 closed form 的对象。
以前方法主要卡在两个位置：一是 optimistic/pessimistic 或 fixed strong-weak β 过于刚性，只能描述极端或固定混合；二是 general intermediate bilevel literature 多关注 existence，而不是如何定义合理的 decision-dependent measure 并实际求解。本文的关键矛盾是：想要更真实的 follower behavior model，就必须处理更难的 endogenous uncertainty；而 bilevel 本身已经很难，不能再简单依赖 deterministic equivalent。
Motivation
作者的核心观察是：tie-breaking 行为本身应随 leader decision 改变。若 leader 的决策使 follower 的 lower-level objective 很好，follower 更可能 cooperative；若 leader 的决策让 follower 处境变差，follower 更可能 adversarial。这是一个比 fixed β 更自然的 inductive bias，也避免了 follower 在坏 outcome 下反而更配合 leader 这类不合理行为。
已有路线缺的是两件事。第一，缺少可调但结构化的 endogenous follower behavior measure：不只是说存在一个 μ_x，而是要给出随 φ(x) 和 F(x,y) 变化的概率族。第二，缺少能把这种 endogenous uncertainty 变成可计算形式的方法。传统 DE 对 support-endogenous 和 fully-endogenous uncertainty 都很不友好；在 full-support case，expectation 甚至通常没有 closed form。
因此，这篇论文的出发点不是提出一个更强的 bilevel solver，而是重新组织建模方式：把 follower tie-breaking 作为 stochastic programming with decision-dependent uncertainty 来处理，再借助 random variable transformation 和 SAA 把问题拉回到相对标准的求解框架里。
Core Idea
核心思想可以概括为：不要直接在 μ_x 上优化，而是构造一个固定外生随机源 ζ，并用 transformation t_μ(x,ζ) 生成 follower response。这样 μ_x 的 decision dependence 被转移到 transformation 中，随机源本身变成 exogenous。这个重写很重要，因为 SAA 需要固定的 sample space；一旦 ζ 固定，就可以在同一组 scenario 上比较不同 x，从而避免对每个 x 重新定义随机事件。
这改变了 intermediate bilevel 的信息流。传统 strong-weak model 是先确定 x，再在 optimistic/pessimistic response 上做固定或显式加权；本文则让 x 先决定 follower satisfaction φ(x)，再通过 behavior function 改变 tie-breaking distribution，最终影响 leader expected objective。inductive bias 是“follower cooperativeness monotonically decreases with follower dissatisfaction”。这个 bias 很强，但在 Stackelberg-type 设置中比任意 μ_x 更可解释。
和 prior 的本质区别不是用了 SAA，而是把 tie-breaking probability 的 endogenous nature 明确建模并变换成 exogenous sampling problem。对 dichotomous case，这让非线性 β(φ(x)) 的 DE 被 threshold-based SAA 替代；对 generalized case，这让 full response set 上的 probability density 可以通过 Markov chain implicit transformation 被嵌入优化。
Method
1. Endogenous behavior measures：它解决的是“μ_x 到底怎么定义”的问题。dichotomous measures 只在 optimistic 与 pessimistic ε-optimal responses 上分配概率，β(φ̃(x)) 控制合作程度；generalized measures 在整个 S(x,ε) 上用 π(F̃(x,y),φ̃(x)) 定义 density。核心变化是把 tie-breaking 从 exogenous parameter 变成 leader-decision-induced behavior。
2. Normalization by follower value and leader outcome：φ̃(x) 用来衡量 follower 对 leader decision 的满意度，F̃(x,y) 用来衡量某个 follower response 对 leader 有多有利。这两个 normalization 让行为函数具有跨实例可比性。它不是数学上必须，但对可建模性和实验比较很关键。
3. Inverse transformation for strong-weak decision-dependent case：对 Bernoulli tie-breaking，采样 ζ~U(0,1)，若 ζ≤β(φ̃(x)) 则选择 optimistic response，否则选择 pessimistic response。通过 β^{-1}(ζ) 和 ordered scenarios，可把选择逻辑写成 threshold crossing。它解决的是 DE 中 β(φ(x)) 与 bilevel response 相乘造成的非凸复杂性。
4. SAA formulation for dichotomous measures：SAA 后只需在有限 scenarios 上决定有多少样本落入 cooperative side。该 formulation 仍需求 optimistic/pessimistic follower values，但通过改造 Zeng-style formulation 可避免 correction scheme。核心变化是把连续非线性 probability weight 变成样本阈值计数。
5. Markov-chain transformation for generalized measures：full-support μ_x 无法 closed-form integration，也不能简单 inverse transform。作者用 Hit-and-Run 在 S(x,ε) 上采样，π 决定沿线段的目标密度，Markov chain 的 stationary distribution 对应 μ_x。这解决的是“如何从 moving support 上抽样”的问题。
6. Integer L-shaped embedding：generalized case 中 ˆg_N^μ(x) 只能在给定 x 后通过 MCMC 估计，所以作者用 integer L-shaped cuts 在 binary leader space 中延迟生成 estimator cuts。这里的机制更像 simulation-embedded branch-and-cut，而不是一个 clean deterministic reformulation。
Key Insight / Why It Works
最核心的贡献是 transformation view：把 endogenous follower tie-breaking 变成 exogenous randomness plus decision-dependent map。这个视角有效，是因为 SAA 真正需要固定随机源，而不是固定 response distribution。只要能保证 t_μ(x,ζ) 对每个 x 诱导出正确 μ_x，就可以在固定 sample path 上优化 expectation estimator。
对 dichotomous case，方法尤其干净。β(φ̃(x)) 本来在 DE 中是一个 decision-dependent nonlinear weight；inverse transform 后，它变成样本阈值判断。排序后的 β^{-1}(ζ) 使 objective 中的 SAA 权重可以由少量 binary threshold variables 表示。这里的增益不是 sampling 本身，而是把概率函数的非线性从 objective 中拿掉，换成 MILP-friendly 的 scenario selection structure。实验中 SAA 快于 DE，很可能主要来自这个 formulation advantage，而不只是 Monte Carlo approximation。
对 generalized case，核心机制没有 dichotomous case 那么强。MCMC + integer L-shaped 的本质是把难以显式积分的问题转为 repeated simulation and cut generation。它确实拓展了可处理 measure 的范围，但 scalability 更多依赖 solver、MCMC mixing、polytope rounding 和 binary expansion。这里的贡献更像一个 practical computational pipeline，而不是复杂性层面的根本突破。
本文最值得迁移的 insight 是：在 decision-dependent uncertainty 中，不一定要直接构造 deterministic equivalent；可以构造一个共享外生随机源，使不同 decisions 下的 random outcome 通过 transformation 对齐。这也类似 common random numbers 的思想：同一组 ζ 在不同 x 下诱导不同 y，但 estimator differences 更稳定。
哪些部分可能只是辅助？具体的 β/π behavior families 更像手工设计的 behavioral priors，提供解释性和实验覆盖，但不是唯一选择；Fragile/Sturdy/Threshold 等命名本身不是核心。MCMC Hit-and-Run 是合理工具，但不是本文独有技术。integer L-shaped cuts 也是已有 stochastic integer programming 思想的迁移。真正新增的信息是把这些工具放入 bilevel tie-breaking 的 endogenous probability 框架中。
需要注意：文中并没有证明这些 behavior families 真实刻画 follower 行为；它们是 normative/modeling assumptions。所谓 follower rationality 被压缩为 φ(x) 越好越 cooperative，这在某些应用中合理，但不是一般定律。
Relation To Prior Work
最近的路线有三类：optimistic/pessimistic bilevel、strong-weak intermediate bilevel、decision-dependent stochastic programming。本文处在这三者交叉处。
相对 optimistic/pessimistic bilevel，本文不是求更强的 extreme solution，而是改变 tie-breaking rule 的建模对象：从 adversarial/cooperative selection 变成 probability measure over optimal responses。这个差异是实质性的，因为 leader objective 从 min/max response 变成 expectation under μ_x。
相对 SWI-BO 和 SWDI-BO，本文的新增点在于系统定义 β(φ̃(x)) 这类 endogenous cooperation functions，并进一步推广到 full-support generalized measure π(F̃,φ̃)。SWDI-BO 不是新概念，Jia et al. 已有 satisfaction-dependent cooperation；本文更实质的部分是把这种 behavior model 和 transformation/SAA 求解框架连起来。
相对 Zeng 2020 的 strong-weak/pessimistic reformulation，本文借用并改造其处理 optimistic/pessimistic follower values 的技术，但把 fixed或DE-style weighting 改为 inverse-transform SAA。这里是已有 bilevel reformulation 与 stochastic programming transformation 的重组。
相对 Salas & Svensson 的 neutral/general Bayesian intermediate view，本文不只是 uniform over response set，而是允许 probability density 随 follower satisfaction 和 leader outcome 变动；同时给出 MCMC-based solution path。实质创新在“endogenous measure + computational transformation”，不是在 intermediate bilevel 概念本身。
相对 Bazotte et al. 2025 的 random variable transformation，本文更像把该 paradigm 移植到 follower tie-breaking 这一 bilevel setting。理论思想来源清晰，但应用对象更复杂，因为 support S(x,ε) 是由 lower-level optimality 隐式定义的。
Dataset / Evaluation
实验使用 BOBILib 中 denegre 与 xuwang 实例的改造版本：upper-level integer linear without coupling constraints，lower-level linear，follower variables relaxed continuous，并人为将 follower objective coefficients 部分置零以增加 multiple optima。这对研究 tie-breaking 是合理的 synthetic stress test，但不是现实行为数据。
evaluation 能支持两个 claim：第一，dichotomous endogenous measures 下，inverse-transform SAA 比 closed-form DE 更 practical；第二，不同 follower behavior 会改变 leader/follower outcome，misspecification 会造成 leader loss。尤其 misspecification 分析是本文比较有价值的实验部分，因为它直接验证了“不能随便用 optimistic/pessimistic 代替真实 tie-breaking”的建模主张。
但实验不能充分支持 generalized scalability。generalized measures 只在 convex/linear follower + binary-expanded leader 下测试，且依赖 MCMC Hit-and-Run、rounding、single-chain/thinning 等工程选择。对于高维退化 polytope、integer follower、非凸 lower-level 或真实 strategic response data，结论外推有限。
benchmark 本身也有偏差：为了制造 follower non-uniqueness，对 lower-level objective 做了随机置零；这可能让 response set 的结构与真实应用中的 degeneracy 不同。文中未充分说明这些 synthetic degeneracies 是否代表实际 tie-breaking 场景。增益来源也部分混合了 formulation、SAA approximation、piecewise approximation baseline 和 solver behavior，归因并不完全干净。
Limitation
1. 行为模型是强假设。follower cooperativeness 被假设为 φ(x) 的严格递减函数，generalized density 还依赖 normalized leader outcome F̃。这是一个合理 behavioral prior，但不是从数据识别出来的。若 follower 的 tie-breaking 受 fairness、risk、历史交互、multi-objective preference 或 bounded rationality 影响，该模型可能 misspecified。
2. generalized case 的可扩展性上限明显。它把 closed-form expectation 的困难转移给 MCMC sampling 和 branch-and-cut cut generation。高维 S(x,ε) 上 Hit-and-Run mixing 可能成为瓶颈；若 polytope 很瘦、退化或含大量 equality/active constraints，rounding 和 convergence 会更脆弱。文中未充分说明 MCMC estimator error 如何影响 branch-and-cut 的 optimality claim。
3. 当前方法主要适配 continuous convex follower response set。若 follower variables 是 integer，S(x,ε) 是离散或组合结构，Lebesgue-density-style generalized measure 和 Hit-and-Run 都不直接适用。作者在 conclusion 也承认这是开放方向，但这其实限制了很多 bilevel combinatorial applications。
4. SAA 的 statistical guarantee 在 bilevel/endogenous/moving-support setting 下没有被充分展开。文中使用单个 SAA instance，而不是多 replication lower-bound estimation；这是计算上可以理解，但使 estimator variance 与 solution quality 的关系不够清楚。
5. DE baseline 对 nonlinear β 需要 piecewise linear approximation，而 SAA formulation 避免该近似。因此 SAA 的优势部分来自 formulation 对 baseline 的不对称性，不完全是 stochastic transformation 本身更强。增益来源不清。
6. 实验没有真实 follower behavior 数据，因此“准确建模 follower behavior 很重要”是通过 synthetic assumed behavior 验证的。如果实际 μ_x 需要从数据估计，统计误差、sample selection bias 和 model misspecification 会成为主问题，本文基本没有处理。
Takeaway
- 1. 这篇论文真正推动的是把 follower tie-breaking 从 bilevel convention 变成 endogenous uncertainty model。
- 这个视角比 optimistic/pessimistic 的二分法更接近真实 strategic interaction。
- 2. 最可迁移的技术 insight 是 random variable transformation：当 distribution/support 随 decision 变化时，先固定外生随机源，再让 decision 通过 transformation 生成 outcome，通常比直接写 deterministic equivalent 更可解。
- 3. dichotomous case 是本文最扎实的部分：inverse transform + SAA threshold formulation 是一个清晰、有效、可复用的机制。
一句话总结
这篇论文把 intermediate bilevel optimization 中的 follower tie-breaking 系统地重写为 decision-dependent stochastic response，并用 random-variable transformation + SAA 给出可计算路径，其中 dichotomous inverse-transform formulation 是最实质的算法贡献，generalized MCMC 框架则是向 full-support behavior modeling 的工程化扩展。