Internship work at Inria, Rennes in Summer of 2018
under guidance of Prof. Blaise Genest

Setting

Population of agents modelled as finite-state systems - NFAs - need to be synchronized into a sink state

System represented as a game; first player (Controller) chooses actions uniformly - Controller must apply same action to all agents - and second player (Agents) makes non-deterministic choice for each agent

Game with $m$ agents is called the $m$-population game

Population control problem - can Controller synchronize $m$-Agents for arbitrary $m$; irrespective of choice of (non-deterministic) transitions Agents chooses?

Animations

Consider the following system with $m = 2$ (depicted as red and blue).
Press "space" for animations!
Controller chooses $\pi = aba$. The following runs are possible amongst others.

Clearly run 1 was winning for the Controller but run 2 was not. Hence $\pi = aba$ is not a winning strategy for Controller. (Trivially though $\pi = \epsilon$ is.)

Overview of results

The population control problem is $\mathrm{EXPTIME}$-complete

In case the system $\mathcal{A}$ is synchronizable, the synchronization time (worst case number of actions to be performed) is ${\color{blue} {polynomial}}$ in the number of agents and ${\color{red} {exponential}}$ in the size (number of states) of $\mathcal{A}$. These bounds are tight upto a constant factor in the exponent.

Hence the algorithm proposed is optimal

Possible Future Work

Probabilistic extensions of these systems - MDPs- may be used to model agents

NFAs are polynomial-time synchronizable. An interesting problem is to identify MDPs which are sub-polynomial - polylog-time synchronizable