Differentially Private Equilibrium Finding in Polymatrix Games

作者: Mingyang Liu, Gabriele Farina, Asuman Ozdaglar

发布时间: 2025-03-13

来源: arxiv

研究方向: 博弈论与差分隐私

主要内容

本文研究了在差分隐私约束下，如何寻找多矩阵博弈中的均衡点。文章首先分析了在两种设置下，无法同时实现高精度和渐近零差分隐私预算的情况：一是寻求以欧几里得距离来衡量均衡集的近似保证，二是攻击者可以访问所有通信渠道。然后，假设攻击者可以访问有限数量的通信渠道，提出了一种新的分布式算法，该算法在玩家数量增加时，能够同时达到渐近零纳什差距（在预期效用中，也称为可利用性和隐私预算）。

主要贡献

1. 证明了在两种设置下，无法同时实现高精度和渐近零差分隐私预算。

2. 提出了一种新的分布式算法，该算法在玩家数量增加时，能够同时达到渐近零纳什差距。

3. 算法考虑了图的结构，无论是稀疏图还是稠密图，都能有效地减少噪声的影响，从而实现精度和差分隐私的平衡。

研究方法

1. 分布式算法

2. 差分隐私

3. 投影梯度下降

4. 正则化

5. 图的结构分析

实验结果

实验结果表明，在稠密图中，随着玩家数量的增加，可利用性和隐私预算都会降低。而在稀疏图中，只有隐私预算会降低。这表明，算法在不同类型的图上表现良好，能够有效地平衡精度和隐私。

未来工作

未来可以进一步研究如何将算法应用于更复杂的博弈模型，并探索如何进一步提高算法的效率和准确性。