Vi studerar kvaliteten på resultaten i upprepade spel när befolkningen av spelare förändras dynamiskt, och där deltagarna använder inlärningsalgoritmer för att anpassa sig till den dynamiska miljön. Priset på anarki har ursprungligen införts för att studera Nash equilibria av en-shot spel. Många spel som studeras i datavetenskap, såsom paket routing eller ad-auctions, spelas upprepade gånger. Med tanke på den beräkningshårdhet Nash equilibria, ett attraktivt alternativ i upprepade spelinställningar är att spelare använder ingen-regret lärande algoritmer. Priset på total anarki beaktar kvaliteten på sådana läranderesultat, förutsatt att en stabil miljö och spelare befolkning, vilket sällan är fallet i online-inställningar. I detta papper analyserar vi effektiviteten hos upprepade spel i dynamiskt föränderliga miljöer. Ett viktigt drag i inlärningsbeteendet är dess mångsidighet till föränderliga miljöer, förutsatt att den inlärningsmetod som används är adaptiv, d.v.s. inte förlitar sig alltför mycket på erfarenhet från det avlägsna förflutna. Vi visar att i stora klasser av spel, om spelarna väljer sina strategier på ett sätt som garanterar låg adaptiv ånger, garanteras hög social välfärd, även under mycket frekventa förändringar. Ett viktigt tekniskt verktyg för vår analys är att det finns en lösning på välfärdsmaximeringsproblem som både är nära optimal och relativt stabil över tid. En sådan lösning fungerar som ett riktmärke i effektivitetsanalysen av läranderesultat. Vi visar att en sådan stabil och nära optimal lösning finns för många problem, även i de fall då den exakta optimala lösningen kan vara mycket instabil. Vi visar vidare att ett tillräckligt villkor på förekomsten av stabila utfall är förekomsten av en differentialt privat algoritm för välfärdsmaximering problem. Därför drar vi en stark koppling mellan differentiell integritet och hög effektivitet i läranderesultat i ofta föränderliga upprepade spel. Vi demonstrerar våra tekniker genom att fokusera på två klasser av spel som exempel: oberoende objektauktioner och trängselspel. I båda tillämpningarna visar vi att adaptiv inlärning garanterar hög social välfärd även med förvånansvärt hög curn i spelarens befolkning.
Därefter till konferensversionen av denna artikel, använde REF förekomsten av gemensamt differentialt privata algoritmer för att lösa vissa optimeringsproblem för att binda priset på anarki i strategiska varianter av dessa problem, där spelaren uppsättningen är dynamiskt förändras.
Learning and Efficiency in Games with Dynamic Population
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}