# 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. • ## Such games have realizations in economics, traffic flow, and ecology. • ## In the case were individuals possess different competitive ability (weighted games) Nash equilibrium may not exist. • ## However, if the order of deviation is stochastic, convergence is almost surely to occur. • ## corresponding to . • ## Obviously any maximal Finite Improvement Path ends with an equilibrium. • ## 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. • ## If a game has no FIP thus no ordinal potential it still may have a Nash Equilibrium. ## A two player congestion game with no finite improvement path • ## The Finite improvement property (FIP) implies the Finite Best Reply Property (FBRP) but not the converse. • ## It is this second player B which makes the next move, thus only possibly increasing the payoff of the player A (monotonicity), thus the strategy played by A remains a Best Reply strategy and Equilibrium is reached. ## An infinite best-reply improvement path in a 3-player, 3-strategy unweighted congestion game • ## The Strategy-tuples (3,1,2) and (2,3,1) are equilibria of this game • ## First we proof a Lemma (two parts). • ## If is a sequence of strategies, is a best-reply improvement path and results from the deviation of one player from to then . • ## 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 . • ## If the deviation at step k is from j(k) to j(k-1) (k=1,2….M) then • ## 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. • ## Proof omitted, we will see a more interesting result, using the same Lemma. • ## Theorem 3: Given an arbitrary strategy-tuple in a congestion game , there exists a BRIP such that is an equilibrium and • ## and a BRIP connected to it as in Lemma (B) such that N is maximal. If then we set . • ## ?

• 1.
• 2. Or Both 1,2 • ## Therefore must be a best reply for • ## This gives the upper bound of the length of the shortest BRIP connecting an arbitrary point to an equilibrium. • ## If

• The number of strategies is finite
• The order of deviators is chosen randomly
• Deviators do not deviate simultaneously
• ## Then for WA games a best-reply path almost surely reaches an equilibrium. • ## Equilibrium is not reached within the first steps with probability • ## Mistakes can be the result of lack of information, players starts with a priori estimates of associated payoff which are later modified to a posteriori knowledge of actual gain. • ## Up till now the players had similar influence upon the congestion. This model is generalized by introducing weights and modifying the congestion vector • ## Therefore these games possess a Nash equilibrium in pure strategies, and the equilibrium can be reached by constructing a maximal best-reply improvement path • ## Even a three-player, three-strategy weighted congestion game may not possess a pure-strategy Nash equilibrium. ## A three-player, three-strategy congestion game with no pure-strategy Nash Equilibrium ## A three-player, three-strategy congestion game with no pure-strategy Nash Equilibrium ## 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