Sequential Resource Allocation for network diffusion control

The dynamic containment of an undesired network diffusion process, such as an epidemic, requires a decision maker (DM) to be able to respond to its evo- lution by taking the right control actions at the right moments. This task can be seen as managing the alloca- tion of a limited amount of resources to the graph nodes, with the objective to reduce the effects of the process.In this thesis we extend the Dynamic Resource Alloca- tion (DRA) problem and propose a multi-round dynamic control framework, which we realize through two derived models: the Restricted and the Sequential DRA (RDRA, SDRA). Contrary to the standard full-information and full-access DRA considerations, these new models take into account possible access restrictions regarding the the available information about the network and/or the ability to act on its nodes. At each intervention round, the DM has limited access to information related to a fraction of the nodes, and is also gaining access to act on them in a sequential fashion. The latter sequential as- pect in the decision process offers a completely new per- spective to the dynamic diffusion process control, making this work the first to cast the dynamic control problem as a series of specially designed sequential selection pro- cesses.In the Sequential Selection Problem (SSP), immediate and irrevocable decisions need to be made by the DM as candidate items arrive randomly and get examined for one of the limited selection slots available. For the needs of network diffusion control, what we propose translatesinto selecting the right nodes to allocate the control re- sources in a multi-round sequential process. However, standard SSP variants, such as the very well-known sec- retary problem, begin with an empty selection set (cold- start) and perform the selection process once over a single candidate set (single-round). These two limita- tions are addressed in this thesis. First, we introduce the novel Warm-starting SSP setting that considers hav- ing at hand a reference set, which is a set of previously selected items of a given quality, and tries to update optimally that set while examining the sequence of ar- riving candidates, constrained by being able to update the assignment to each selection slot (resource) at most once. The Multi-round Sequential Selection Process, the new online-within-online problem, is then introduced as a natural extension of the warm-starting selection.Both rank-based and score-based ob jective functions over the final selection are considered. A cutoff-based approach is proposed for the former, while the optimal strategy based on dynamic thresholding is derived for the latter assuming that the score distribution is known. These strategies are then put in comparison for their efficiency in the traditional selection setting as well as in solving network control problems that motivated this thesis. The generality of the introduced models allow their application to a wide variety of fields and problems; for instance, reoccurring recruiting processes, manage- ment of resources (e.g. beds, staff) in healthcare units, as well as tackling difficult combinatorial problems under constrains, such as the b-diversification problem found in data-stream processing applications (e.g. in robotics).