I det här dokumentet studerar vi spel med kontinuerliga aktionsytor och icke-linjära payoff-funktioner. Vår nyckelinsikt är att Lipschitz kontinuitet av payoff-funktionen gör att vi kan tillhandahålla algoritmer för att hitta ungefärlig jämvikt i dessa spel. Vi börjar med att studera Lipschitz spel, som omfattar till exempel alla konkava spel med Lipschitz kontinuerlig payoff funktioner. Vi tillhandahåller en effektiv algoritm för att beräkna ungefärlig jämvikt i dessa spel. Sedan vänder vi vår uppmärksamhet till straffspel, som omfattar partiska spel och spel där spelarna tar risker i beaktande. Här visar vi att om strafffunktionen är Lipschitz kontinuerlig, då kan vi ge en kvasi-polynom tid approximation system. Slutligen studerar vi distans partisk spel, där vi presenterar enkla starkt polynom tid algoritmer för att hitta bästa svar i L 1, L 2, och L∞ partisk spel, och sedan använda dessa algoritmer för att ge starkt polynom algoritmer som hittar 2/3, 5/7, och 2/3 approximationer för dessa normer, respektive.
Deligkas m.fl. REF-studie beräkning av ungefärlig jämvikt i allmänna konkava spel med kompakta strategi utrymmen och Lipschitz kontinuerliga kostnadsfunktioner.
Lipschitz Continuity and Approximate Equilibria
{'venue': None, 'journal': 'arXiv: Computer Science and Game Theory', 'mag_field_of_study': ['Mathematics', 'Computer Science']}