Algorytmiczna teoria gier - niestandardowe koncepcje równowagi?

Zaczynam studia nad algorytmiczną teorią gier i wydaje się, że zwykle pojęcie równowagi jest oparte na punkcie stałym na wykresie. Jednak czy ludzie przyglądali się alternatywnym koncepcjom równowagi, takim jak cykle graniczne? Mogę sobie wyobrazić, że „ciasny” cykl graniczny - to znaczy cykl na wykresie o bardzo małej długości - może być uważany za coś „zbliżonego” do standardowej definicji równowagi.

Próbowałem kopać w Google Scholar, ale bezskutecznie.

Ten, który lubię, jest czasem nazywany „równowagą zgrubną skorelowaną”. To właściwie ograniczający zestaw efektywnej dynamiki „bez żalu”.

Mają kilka fajnych właściwości, między innymi fakt, że można je osiągnąć za pomocą wydajnej, odsprzężonej dynamiki, i obejmują równowagę Nasha jako szczególny przypadek (więc są `` bardziej prawdopodobne '' jako prognoza zachowania). Tym, co może uczynić je nieco podobnymi do tego, o co pytasz, jest to, że te dynamiki uczenia się nigdy nie muszą się zbieżne do ustalonego punktu - w rzeczywistości mogą cyklicznie na zawsze. Niemniej jednak często możliwe jest ograniczenie szybkiej konwergencji dobrobytu społecznego w ramach tej dynamiki (tj. Ceny anarchii nad gruboziarnistymi skorelowanymi równowagami), a co więcej, często dobrobyt społeczny nie jest gorszy niż zgrubnie skorelowanych równowag niż w porównaniu z równowagą Nasha.

Niektóre odpowiednie dokumenty:

http://portal.acm.org/citation.cfm?id=1374430

http://portal.acm.org/citation.cfm?id=1536414.1536485

http://portal.acm.org/citation.cfm?id=1536487

Być może szukasz czegoś takiego jak Sink Equilibria (zacznij od np. Http://arxiv.org/abs/0902.0382 ) - ale długość cyklu nie jest brana pod uwagę.

Prawdopodobnie nie tego szukasz, ale możliwe jest zdefiniowanie przybliżonej równowagi Nasha, w której celem jest znalezienie stanów tak, aby narzędzia gracza były zbliżone do tych określonych przez równowagę Nasha. Noam Nisan ma fajny post na ten temat (a ponieważ czasem się tu spotyka, prawdopodobnie będzie miał dla ciebie lepszą odpowiedź).

Joseph Y. Halpern z Cornell wygłosił ostatnio przemówienie w CUNY Graduate Center pod tytułem: Beyond Nash Equilibrium: Solution Concepts for the 21st Century. Być może jego praca byłaby dla ciebie interesująca.

http://web.cs.gc.cuny.edu/~kgb/seminar.html

Mam nadzieję, że nie jest to zbyt pozorne rozwiązanie, ponieważ patrzy na to pytanie z punktu widzenia teorii gier ewolucyjnych (EGT), zamiast AGT.

Teoria gier, jak pierwotnie sformułowali von Neumann i Morgenstern, była teorią statyczną. Stąd wiele popularnych koncepcji równowagi (Nash, Skorelowane itp.) Jest z natury statycznych. Aby mówić o równowagach niestatycznych, musimy wprowadzić pewną dynamikę. AGT często robi to, biorąc pod uwagę określone rozumowanie (algorytmy), które agenci mogą wykorzystać do podjęcia decyzji.

Alternatywnym podejściem, przyjętym przez EGT, jest uwzględnienie dynamiki populacji dużej liczby podmiotów przy bardzo prostym podejmowaniu decyzji. To zwykle tworzy nieliniową dynamikę w populacji i umieszcza EGT jako część układów dynamicznych. Dlatego zaczynacie widzieć wszystkie szalone koncepcje równowagi systemów dynamicznych, takie jak cykle graniczne lub chaotyczne atraktory wyskakujące jako koncepcje równowagi. Te niestacjonarne równowagi są dobrze badane w EGT, chociaż często analiza opiera się wyłącznie na układach dynamicznych, a nie algorytmicznych.

Jeśli interesuje Cię EGT, to standardowym (i dostępnym) punktem wyjścia jest badanie Hofbauer i Sigmund z 2003 r. „ Dynamika gry ewolucyjnej ”