| Abstract | Weconsiderweightedlinearcongestiongames,andinvestigatehowsocialignorance,namely
lackofinformationaboutthepresenceofsomeotherplayers,affectstheinefficiencyofpureNashequilibria
(PNE)andtheconvergenceofthe -Nashdynamics.Morespecifically,weadoptthemodelofgraphical
linearcongestiongameswithweightedplayers,wheretheindividualcostandthestrategyselectionofeach
playeronlydependsonhisneighboringplayersinthesocialgraph.Weshowthatsuchgamesadmita
potentialfunction,andthusaPNE.OurmainresultisthattheimpactofsocialignoranceonthePriceof
Anarchy(PoA)andthePriceofStability(PoS)isnaturallyquantifiedbythe independencenumber
ofthesocialgraph .Inparticular,weshowthatthePoAgrowsroughlyas ,which
isessentiallytightaslongas doesnotexceedhalfofthenumberofplayers,andthatthePoSlies
between and .Moreover,weshowthatthe -Nashdynamicsreachesan -
approximateconfigurationintimethatispolynomialanddoesnotdirectlydependonthestructureofthe
socialgraph.Forunweightedgraphicallineargameswithsymmetricstrategies,weshowthatthe -Nash
dynamicsconvergestoan -approximatePNEintimethatispolynomialandexceedsthecorresponding
timeforsymmetriclineargamesbyafactoratmostaslargeasthenumberofplayers. |
