Fair Surveillance Assignment Problem

Monitoring a specific set of locations serves multiple purposes, such as infrastructure inspection and safety surveillance. We study a generalization of the surveillance problem, where the monitoring area, represented by a graph, is divided and assigned to a set of agents with personalized cost functions. In this paper, each agent's patrolling cost towards receiving a subgraph is measured by the weight of the minimum vertex cover therein, and our objective is to design algorithms to compute fair assignments of the surveillance tasks. The fairness is assessed using maximin share (MMS) fairness proposed by Budish [J. Political Econ., 2011]. Our main result is an algorithm which ensures a 4.562-approximate MMS allocation for any number of agents with arbitrary vertex weights. We then prove that no algorithm can be better than 2-approximate MMS. For scenarios involving no more than four agents, we improve the approximation ratio to 2, which is thus the optimal achievable ratio.