- Elosztott nehézgolyós Nash-egyensúlyi algoritmus geometriai konvergenciája időben változó digráfokon korlátlan műveletekkel (arXiv)
Szerző: Duong Thuy Anh Nguyen, Duong Tung Nguyen, Angelia Nedich
Absztrakt: Javasolunk egy új elosztott algoritmust, amely egyesíti a nehéz labda lendületét és a konszenzuson alapuló gradiens módszert, hogy megtalálja a Nash-egyensúlyt (NE) a nem kooperatív konvex játékok egy osztályában, korlátlan akciókészletekkel. Ebben a megközelítésben a játék minden ügynöke hozzáfér a saját sima helyi költségfüggvényéhez, és kommunikációs hálózaton keresztül információt cserélhet szomszédaival. A javasolt módszert úgy tervezték, hogy időben változó irányított gráfok általános sorozatán dolgozzon, és lehetővé teszi nem azonos lépésméretek és impulzusparaméterek használatát. Munkánk az első, amely a nehézlabda lendületet beépíti a nem kooperatív játékok kontextusába, és szigorú bizonyítékot adunk annak geometriai konvergenciájára az ÉK-hez, az ügynökök költségfüggvényeinek erős konvexitása és Lipschitz-folytonossága közös feltételezései mellett. Ezen túlmenően a költségfüggvények, a keverési mátrixok és a gráf összekapcsolhatósági struktúrák jellemzői alapján explicit korlátokat állítunk fel a lépésméret-értékekre és az impulzusparaméterekre. A javasolt módszerünk hatékonyságának bemutatása érdekében numerikus szimulációkat végzünk egy Nash-Cournot játékon, hogy bemutassuk annak felgyorsult konvergenciáját a meglévő módszerekhez képest.
2. Bizonyítható részecske-alapú primál-kettős algoritmus kevert Nash-egyensúlyhoz (arXiv)
Szerző: Shihong Ding, Hanze Dong, Cong Fang, Zhouchen Lin, Tong Zhang
Absztrakt: Az általános nemkonvex nemkonkáv minimax problémát folytonos változók felett vizsgáljuk. Ennek a problémának a fő kihívása, hogy nem létezik nyeregpont. Ennek a nehézségnek a megoldása érdekében megvizsgáljuk a kevert Nash-egyensúly megtalálásának kapcsolódó problémáját, amely egy randomizált stratégia, amelyet a folytonos változók közötti valószínűségi eloszlások képviselnek. Javasolunk egy részecske-alapú primál-kettős algoritmust (PPDA) egy gyengén entrópia-szabályozott min-max optimalizálási eljáráshoz a valószínűségi eloszlások felett, amely a részecskék sztochasztikus mozgását alkalmazza a kevert Nash-egyensúly véletlenszerű stratégiáinak frissítésére. A javasolt algoritmus szigorú konvergenciaanalízise megtalálható. Összehasonlítva azokkal a korábbi munkákkal, amelyek a részecskesúlyt mozgások nélkül próbálják frissíteni, a PPDA az első megvalósítható részecske alapú algoritmus, amely nem aszimptotikus kvantitatív konvergencia eredményeket, futási időt és minta összetettségi garanciákat tartalmaz. Keretrendszerünk új betekintést nyújt a részecske alapú algoritmusok tervezésébe a folyamatos min-max optimalizáláshoz az általános nemkonvex nemkonkáv beállításban.
