Ograniczenie tempa wzrostu ceny anarchii w pojęciach równowagi

Znamy i kochamy wiele zagnieżdżonych klas koncepcji rozwiązań:

• PN: Równowaga Pure Nasha
• MN: Mixed Nash Equilibrium
• CE: Skorelowana równowaga
• CCE: kurs skorelowana równowaga.

Związek między tymi zestawami jest następujący:

$$PN \subset MN \subset CE \subset CCE$$ Możemy rozważyć cenę anarchii w stosunku do jednej z tych koncepcji rozwiązania: najgorszy przypadek opieki społecznej dla dowolnego profilu w zestawie, podzielony przez optymalną opiekę społeczną: $$POA(S) = \max_{s \in S}\frac{COST(s)}{OPT}$$ Tak więc, dzięki powyższym ograniczeniom: Moje pytanie: czy znane są granice szybkości wzrostu tej ilości? Można mieć grę ze skończonym , ale nieskończenie duża. Ale jeśli wiem, że jest skończony, czy również musi być skończony? ? Jak duże mogą być? $$POA(PN) \leq POA(MN) \leq POA(CE) \leq POA(CCE)$$ $POA(PN)$$POA(CCE)$$POA(PN)$$POA(MN)$$POA(CE)$

Stosunek między a może być dowolnie duży. Rozważ następującą grę z zatorami; mamy graczy i przedmiotów, a każdy gracz może wybrać dowolny przedmiot. Koszt dla gracza zależy od przeciążenia wybranego przedmiotu; jest jeśli graczy wybierze ten przedmiot. będzie gwałtownie rosnącą funkcją.$POA(MN)$$POA(PN)$$n$$n$$f(x)$$x$$f$

Jedyny czysty Nash sprawia, że ​​każdy gracz wybiera unikalny przedmiot, więc wszyscy płacą . Z drugiej strony, symetrycznie, losową strategią, w której każdy gracz wybiera jednolicie losowy przedmiot, jest mieszany Nash. Jeśli rośnie gwałtownie, całkowity koszt będzie znacznie droższy, ponieważ istnieje szansa, że ​​wielu graczy wybierze ten sam przedmiot.$f(1)$$f$

W tym blogu podany jest przykład, w którym istnieje nieograniczona różnica między ceną stabilności CE i MN; Wierzę, że coś podobnego pokazałoby również nieograniczoną lukę w PoA.