纳什均衡与负载均衡博弈

Question

我知道纳什均衡是指我的任何球员都无法通过改变自己的状态来获得更好的局面。我有 m 台机器（速度相同，容量无限）和 n 个代理人（玩家），每个代理人都有一个权重 w，他必须使用机器处理这个权重。每个代理的个人目标是最小化她机器的负载。全局目标是最小化完工时间。我需要证明从任何解决方案开始我都可以收敛到纯纳什均衡。

（假设机器 < 代理）如果我通过减少权重并为每个代理分配一台机器来对我的代理进行排序：

m1
m2

a1 = 3
a2 = 5
a3 = 7

load m1 = 7
load m2 = 5+3 = 8

这是纯纳什均衡吗？我的特工没有一个想改变他的状态。

Answer 1

假设我们已经为机器分配了代理。每个智能体 a_i 有工作 w_i 要做，每个机器 m_j 有一个总负载L_j（分配给它的代理的负载总和）。

如果agent a_i已经分配给机器m_j，并且变更到机器m_k，新负载将是：

L_j' = L_j - w_i
L_k' = L_k + w_i

当且仅当 L_k' < L_{j[=94= 时代理 ai 才会需要这个]}

现在定义一个新的量R，它是L的平方和，看看它是如何变化的：

R' - R = (L_j'² + L_k'²) - (L_j² + L_k²)
= (L_j - w_i)² + (L_k + w_i)² - (L_j² + L_k²)
= (-2L_jw_i + w_i²) + (2L_k w_i + w_i²)
= -2L_jw_i + (2L_k w_i + 2w_i²)
= 2w_i [-L_j + (L_k + w_i)]
= 2w_i [-L_j + L_k']

但是我们已经知道 L_k' < L_j, 所以

R' - R < 0

R是非负的（因为它是平方和），每次变化都会减少，并且会减少一个最小值大于零的量. 因此这个过程无法继续无限多步。因此它将达到没有代理人想要更换机器的状态。