Szanowni Państwo,
serdecznie zapraszamy na Seminarium Instytutu Informatyki, które odbędzie się 24 czerwca 2024 r. o godzinie 10:15 w sali 110 INF. Referat pt.: „Attaining Equilibria Using Control Sets” wygłosi dr Gleb Polevoy, prof. UO.
Streszczenie:
Many interactions result in a socially suboptimal equilibrium, or in a non-equilibrium state, from which arriving at the desired equilibrium through simple dynamics is either impossible or will take too long. Aiming to facilitate arriving at the desired equilibrium, we formulate a new theoretically and practically interesting direct control set problem: Given a game, any profile s and a desired equilibrium d, find a minimum subset A of the players, persuading, bribing, or coercing which to play d instead of s makes d a best response for all the other players.
We first show that the desired equilibrium having certain direct control sets implies the strength of that equilibrium, and then we analyse the direct control set optimisation problem itself. We prove this problem is NP-hard, and even inapproximable within factor n^{1−ε}, for any ε > 0. We then solve important subclasses and provide approximation algorithms.
Next, we concentrate on potential games and prove that, while finding a direct control set there, even with a constant-factor approximation, is still NP-hard, we can solve the problem approximately or even precisely in relevant special cases. We solve this problem for singleton congestion games and closely treat specific potential games, such as symmetric games and coordination games on graphs.