UC San Diego

The proliferation of large-scale networks like social networks, transportation networks, or smartgrids imposes new demands and challenges on the design of learning algorithms for optimal resource allocation. In a typical scenario, a group of agents decides how to coordinate the use of shared resources to solve a common goal while satisfying operational and communication constraints. The challenge is how to increase the network resilience given myopic agents with access to partial information. Under these settings, there is an emergence for the design of algorithms that are scalable, robust against adversarial or unknown environments, preserve privacy, and that allow the agents to take autonomous decisions on the resource utilization.

A real-world problem leading to such a scenarios arises in computer networks, epidemiology, and viral marketing, where a viral outbreak can be a threat to the security of interconnected infrastructure and the well-being of general population. The implementation of strategies to stop epidemics can be specially challenging when networks are managed by multiple operators who need to preserve the privacy and interests of their constituents.

Motivated by this situation, we consider a resource allocation problem for virus spread minimization. Based on a general contagion dynamics model, we characterize the optimal solution to the problem. We pose the problem objective as the minimization of the spectral radius of the contagion-dynamics matrix subject to operational constraints. We propose four algorithms to find the solution with provable convergence guarantees under different settings. The first algorithm, inspired by the Replicator Dynamics, implements the desired resource allocation for time-varying symmetric matrices. The second algorithm, designed in continuous-time, uses local and anonymous interactions, does not require knowledge of the total resource available to agents in order to converge to the solution, is robust to agents joining or departing the network, and to sporadic changes in the network topology, computation errors, and communication faults. The third algorithm, which is a discrete version of the second one, conserves the robustness properties of the previous one. Finally, we propose a stochastic algorithm, which extends the previous algorithms to scenarios where the closed-form expression of the cost functions is unknown to the agents.