Robust peer-monitoring on graphs with an application to suicide prevention in social net

We consider the problem of selecting a subset of nodes (individuals) in a (social) network that can act as monitors capable of “watching-out” for their neighbors (friends) when the availability or performance of the chosen monitors is uncertain. Such problems arise for example in the context of “Gatekeeper Trainings” for suicide prevention. We formulate this problem as a two-stage robust optimization problem that aims to maximize the worst-case number of covered nodes. Our model is capable of incorporating domain specific constraints, e.g., fairness constraints. We propose a practically tractable approximation scheme and we provide empirical results that demonstrate the effectiveness of our approach.