Approximate Nash Equilibria with Near Optimal Social Welfare
Approximate Nash Equilibria with Near Optimal Social Welfare
复制标题
DOI：
--
复制
发表时间：
2015-07
期刊：
影响因子：
--
通讯作者：
A. Czumaj;M. Fasoulakis;M. Jurdzinski
中科院分区：
文献类型：
--
作者：
A. Czumaj;M. Fasoulakis;M. Jurdzinski
众所周知，纳什均衡和近似纳什均衡并不一定优化双矩阵博弈的社会最优解。本文证明了对于每一个固定的e>；0，每个双矩阵对策(取值于[0；1])都有一个e-近似纳什均衡，且博弈双方的总收益至少有一个最优的常数因子(1-√1-e)2。此外，我们的结果可以在如下意义上实现算法：对于每一个固定的0≤e*<；e，如果我们能在多项式时间内找到e*-近似纳什均衡，那么我们可以在多项式时间内找到一个e-近似纳什均衡，且博弈者的总收益至少是最优的一个常数因子。当e-≥为1/2时，我们的分析尤为严格。在这种情况下，我们证明了对于任何双阵博弈，都存在一个具有固定大小支持度的e-近似纳什均衡，它的社会福利至少是最优社会福利的2√e-e≥0：914倍。此外，我们还证明了我们的社会福利的界是紧的，即对于每一个e-≥1/2，存在一个双矩阵对策，其中每个e-近似纳什均衡的社会福利至多为最优社会福利的2√e-e倍。
It is known that Nash equilibria and approximate Nash equilibria not necessarily optimize social optima of bimatrix games. In this paper, we show that for every fixed e > 0, every bimatrix game (with values in [0; 1]) has an e-approximate Nash equilibrium with the total payoff of the players at least a constant factor, (1 - √1 - e)2, of the optimum. Furthermore, our result can be made algorithmic in the following sense: for every fixed 0 ≤ e* < e, if we can find an e*-approximate Nash equilibrium in polynomial time, then we can find in polynomial time an e-approximate Nash equilibrium with the total payoff of the players at least a constant factor of the optimum. Our analysis is especially tight in the case when e ≥ 1/2. In this case, we show that for any bimatrix game there is an e-approximate Nash equilibrium with constant size support whose social welfare is at least 2√e - e ≥ 0:914 times the optimal social welfare. Furthermore, we demonstrate that our bound for the social welfare is tight, that is, for every e ≥ 1/2 there is a bimatrix game for which every e-approximate Nash equilibrium has social welfare at most 2√e - e times the optimal social welfare.