Il metodo del fibrato dei punti fissi su domini costituiti da prodotti di simplessi derivanti dagli equilibri di gioco

Abstract degli autori

Sviluppare algoritmi generali con garanzie di convergenza asintotica globale per gli equilibri di Nash nei giochi a somma generale resta una sfida di lunga data. Questo articolo estende dai domini costituiti da un simplesso a quelli costituiti da prodotti di simplessi il quadro teorico del fibrato dei punti fissi per le disuguaglianze variazionali (VI) in dimensione finita, consentendone l’applicazione diretta al calcolo degli equilibri di Nash. Il fibrato dei punti fissi così ottenuto presenta una struttura di fibrato composito. L’innovazione principale consiste nel costruire una VI equivalente su un simplesso e nello stabilire l’equivalenza tra i due quadri teorici del fibrato dei punti fissi mediante un isomorfismo di fibrati. Sfruttando questa equivalenza geometrica, dimostriamo che l’algoritmo di inseguimento del percorso per le VI su domini costituiti da prodotti di simplessi eredita le garanzie di convergenza lineare globale del quadro teorico per i domini costituiti da un simplesso. Negli esperimenti numerici, l’algoritmo ha raggiunto una precisione di $10^{-5}$ in tutte le 5.600 istanze di gioco generate casualmente, da quelle con 2 giocatori e 128 azioni a quelle con 128 giocatori e 2 azioni. Codice e dati sono disponibili all’indirizzo https://github.com/shb20tsinghua/FiberBundle_VI.