Metric Facility Assignment with Partial Information
It provides theoretical guarantees for assignment algorithms under limited information, relevant to algorithmic mechanism design and social choice.
The paper studies metric facility assignment with partial information, establishing tight distortion bounds for various information types, including a tight bound of 1+√2 for APP+DIST and 2 for ORD+APP+DIST, improving over the optimal bound of 3 using only ORD.
We study an assignment problem where a set of agents and a set of facilities lie on a line metric. The goal is to compute an assignment of agents to facilities to approximately minimize the social cost (the total distance of agents from their assigned facilities) given only partial information regarding the metric. Unlike previous work which focused solely on algorithms with access to the ordinal preferences of the agents over the facilities (ORD), we also consider the value of information regarding approval preferences (APP), and inter-facility distances (DIST). For different combinations of these three information types, we establish tight bounds on the distortion of deterministic algorithms, showing that it is possible to improve over the optimal bound of $3$ that can be achieved using only ORD information. Among other results, we show a tight bound of $1+\sqrt{2}$ for APP+DIST which holds even for general metrics, and a tight bound of $2$ for ORD+APP+DIST.