Approximate Strategyproofness in Approval-based Budget Division
Haris Aziz, Patrick Lederer, Jeremy Vollen
IJCAI'26
cs.GT, econ.TH
2026-05-12
公平、有效、策略防操纵三者不可兼得。这篇用激励比放松防操纵,证明Nash乘积规则最坏只让撒谎者效用翻倍,在平均公平份额下已是最优。
参与式预算、捐赠协调这类场景,要把一份可分割的资源按投票人的喜好分给若干项目。这篇研究的是批准式预算分配:每人只圈「喜欢 / 不喜欢」,规则输出每个候选人分到的份额。效用就是自己圈中的项目合计拿到多少。
这个模型上有三条几乎没法同时满足的要求。策略防操纵:撒谎不能让自己更好。效率:不能在不损害任何人的前提下让某人更好。公平:成组的投票人应拿到与人数成比例的保障。Brandl 等人 2021 年证明,策略防操纵加上效率,连最弱的公平(每人效用严格大于 0)都保不住。策略防操纵的规则(功利规则、条件功利规则)在效率或公平上亏得很狠。反过来,公平又有效的规则到底有多好操纵,此前没有定量答案。
这篇把「防操纵」放松成激励比:一个投票人通过改选票,效用最多能变成原来的多少倍。激励比为 1 就是策略防操纵;数字越大,最坏情况下越好骗。
理论侧先给三条坏消息。最大支付规则(MP)和公平功利规则(FUT)的激励比是 \(\Theta(n)\),平等主义规则(EGAL)是 \(\Theta(m)\),最坏情况随投票人数或候选人数线性变差。好消息在 Nash 乘积规则(NASH):它最大化全体效用的乘积,激励比恰好是 2,而且投票人可以报告任意凹效用函数,上界仍然是 2,不只限于批准效用。群体合谋也有同类保证:一伙人没法让每个人的效用都超过原来的两倍。
2 这个数字在若干自然条件下已经是下限。满足平均公平份额(AFS)的规则、严格凹可分福利最大化规则,以及满足效率、群体公平份额再加匿名、中立、与输家无关这三条常规条件的规则,激励比都至少是 2。NASH 同时落在这三类里,所以上界和下界贴在一起。
实验侧在三种选票分布(独立批准概率 0.3 的 impartial culture、三维单位球上距离 0.4 的欧氏模型、色散 \(\phi=0.75\) 的截断 Mallows)上,对 n 从 10 到 100、m=10,每种设定抽 1000 张剖面,穷举单人操纵。
理论结果可以收成一张表:
| 规则 | 激励比 | 效率 | 公平 |
| NASH | 2 | 满足 | AFS 与 core |
| EGAL | \(\Theta(m)\) | 满足 | 仅弱公平 |
| FUT | \(\Theta(n)\) | 满足 | 群体公平份额 |
| MP | \(\Theta(n)\) | 不满足 | 群体公平份额,近似因子 2 |
n=100、m=10 时的平均激励比和可操纵剖面比例:
| 规则 | impartial | 欧氏 | Mallows |
| NASH | 100%, 1.12 | 100%, 1.18 | 100%, 1.11 |
| EGAL | 97%, 1.74 | 100%, 1.74 | 99%, 1.73 |
| FUT | 92%, 1.17 | 75%, 1.14 | 70%, 1.10 |
| MP | 99%, 2.52 | 89%, 1.79 | 90%, 1.29 |
NASH 几乎张张都存在有利谎报,平均增益却一直低于 1.2,实验里最大值大约 1.5。FUT 理论最坏是 \(\Theta(n)\),实验均值跟 NASH 差不多,最大值通常在 2 到 3,比 NASH 高一截。EGAL 靠搭便车(只圈当前份额为 0 的已批准项)把平均激励比顶到约 1.74。MP 的均值被极端实例拉高,实验里见到过 37。
把 NASH 与均匀分配做凸组合,可以把激励比压到 6/5 到 4/3 一带,但要让 \(\lambda\) 很小,NASH 的公平与效率会被冲掉。
如果参与式预算或捐赠平台打算上线一条既公平又有效的规则,NASH 是目前公理上最能站住的选项:撒谎最多把效用翻一倍,而且这个倍数在公平条件下没法再压。对平台设计者,这句话比「NASH 可操纵」有用得多。实验还说明,最坏情况分析会冤枉 FUT:典型剖面里它并不比 NASH 更好骗,只是尾巴更肥。
对机制设计研究者,激励比把 Brandl 不可能定理从「三者不可兼得」推进到「放松防操纵之后,2 是公平条件下的最优常数」。Fisher 市场里线性效用的激励比也是 2,两边对上了。
NASH 几乎总是可操纵。激励比管的是倍数上限,不管操纵好不好算、好不好协调。论文没有分析计算复杂度,也没有把防操纵、效率和公平放进同一个近似框架里同时打折。混合均匀分配能换更低的激励比,代价是把 NASH 的公理性质交出去,作者自己也没把这条路当成主推荐。
实验固定 m=10,选票来自三个合成分布,没有真实参与式预算数据。单人操纵是对每张剖面穷举的,群体操纵只在理论上给了「不能人人都翻倍」的保证,没有实验。FUT 的最坏情况与均值之间那截缺口,还没有结构解释。