Mathilde FEKOM : Sequential Resource Allocation for network diffusion control

Résumé :

In this thesis we extend the Dynamic Resource Allocation (DRA) problem and propose a multi-round dynamic control framework, which we realize through the derived Sequential DRA model (SDRA). Contrary to the standard full-information and full-access DRA considerations, at each intervention round, the DM gains information and access only a fraction of the nodes, in a sequential fashion. Standard SSP variants, such as the very well-known secretary problem, begin with an empty selection set (cold-start) and perform the selection process once over a single candidate set (single-round). These two limitations are addressed in this thesis. First, we introduce the novel Warm-starting SSP setting that considers having at hand a reference set, which is a set of previously selected items, and tries to update optimally that set while examining the sequence of arriving candidates. 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 objective 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 or management of resources (e.g. beds, staff) in healthcare units.