Limiter le taux d'augmentation du prix de l'anarchie à travers les concepts d'équilibre

Nous connaissons et aimons un tas de classes imbriquées de concepts de solution:

• PN: Pure Nash Equilibrium
• MN: équilibre de Nash mixte
• CE: équilibre corrélé
• CCE: cours corrélé à l'équilibre.

La relation entre ces ensembles est: Nous pouvons considérer le prix de l'anarchie sur n'importe lequel de ces concepts de solution: le pire des cas de la protection sociale pour n'importe quel profil de l'ensemble, divisé par le bien-être social optimal : Donc, par les contenants ci-dessus: POA (PN) \ leq POA (MN) \ leq POA (CE) \ leq POA (CCE) Ma question: sont leurs limites connues sur la vitesse à laquelle cette quantité peut augmenter? Il est possible d'avoir un jeu avec POA (PN) fini, mais POA (CCE) sans limites. Mais si je sais que POA (PN) est fini, POA (MN) doit-il également être fini? POA (CE) ? Jusqu'à quel point peuvent-ils être plus grands?

$$PN \subset MN \subset CE \subset CCE$$ $$POA(S) = \max_{s \in S}\frac{COST(s)}{OPT}$$ $$POA(PN) \leq POA(MN) \leq POA(CE) \leq POA(CCE)$$ $POA(PN)$$POA(CCE)$$POA(PN)$$POA(MN)$$POA(CE)$

Le rapport entre et peut être arbitrairement élevé. Considérez le jeu de congestion suivant; nous avons joueurs et objets, et chaque joueur peut choisir n'importe quel objet. Le coût pour un joueur dépend de l'encombrement de l'objet choisi; c'est si joueurs choisissent cet objet. sera une fonction en forte croissance.$POA(MN)$$POA(PN)$$n$$n$$f(x)$$x$$f$

Le seul Nash pur permet à chaque joueur de choisir un objet unique, donc tout le monde paie . D'un autre côté, par symétrie, la stratégie aléatoire où chaque joueur choisit un objet uniformément aléatoire est un Nash mixte. Si croît rapidement, le coût total sera beaucoup plus cher, car il est possible que plusieurs joueurs choisissent le même article.$f(1)$$f$

Dans ce billet de blog, un exemple où il existe un écart illimité entre le prix de la stabilité de CE et MN est donné; Je crois que quelque chose de similaire montrerait également un écart illimité pour le PoA.