# Congestion Games with Player-Specific Payoff Functions Igal Milchtaich, Department of Mathematics, The Hebrew University of Jerusalem, 1993

Yüklə 492 b.
 tarix 17.01.2019 ölçüsü 492 b.

• ## Theorem 1:

• Congestion games involving only two strategies possess the finite improvement property.
• ## Proof:

• Suppose on the contrary that there is an infinite improvement path then for some
• WLOG
• This implies that player i, the unique deviator in the first step, deviates from 1 to 2; hence
• By Monotonicity
• Hence player i, never deviates back to strategy 1.

• ## Proof:

• Let be the congestion vector of and set .
• Then holds for all j and k.
• Hence by deviation to of the unique deviator in step k brings to its maximum and all other to their minimum.
• By monotonicity of payoff , j(k) remains the best reply for that player in all later steps, thus each player deviates at most once and .

• ## Proof:

• Here too
• By deviating from j(k), the deviator at step k brings to its minimum, this implies that the payoff in is greater than when he deviated to j(k) ,if he did, or that he will get by deviating to j(k) at any later step.
• Therefore a player will not return to a strategy he deviated from; each player deviates at most r-1 times.

• ## ?

• 1.
• 2. Or Both 1,2

• ## If

• The number of strategies is finite
• The order of deviators is chosen randomly
• Deviators do not deviate simultaneously

## Unweighted Vs. Weighed Congestion Games

Yüklə 492 b.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2020
rəhbərliyinə müraciət