Graph-constrained dynamic choice

Thursday, May 20, 2021 11:00to12:00

Dynamic Games and Applications Seminar

Speaker: Vivek Borkar – Department of Electrical Engineering, IIT Bombay, India

Webinar link
Webinar ID: 881 6070 4034
Passcode: 095916

In this talk, I introduce a model of graph-constrained dynamic choice with reinforcement modeled by positively α-homogeneous rewards. Its empirical process, which can be written as a stochastic approximation recursion with Markov noise, has the same probability law as a certain vertex reinforced random walk. Thus, the limiting differential equation that it tracks coincides with the forward Kolmogorov equation for the latter, which in turn is a scaled version of a special instance of replicator dynamics with potential. This equivalence is exploited to show that for α>0, the asymptotic outcome concentrates around the optimum in a certain limiting sense when 'annealed' by letting α↑∞ slowly. 

(Joint work with Konstantin Avrachenkov, Sharayu Moharir and Suhail Mohmad Shah.)

Back to top