Zohar Barak

Zohar Barak

We study the facility location mechanism design problem where $n$ agents report their locations in Euclidean space, and the output is a single facility location. The cost function of each agent is the distance from the returned facility, and the objective is to minimize the social cost function (the sum of agent costs) in a strategyproof way. Our contributions: 1. Breaking the deterministic barrier. For $\mathbb{R}^2$, we give a random strategyproof mechanism (RR-CWM) achieving an expected approximation ratio of $\frac{4}π \approx 1.27$, which strictly improves upon the best deterministic strategyproof mechanism (which has a $\sqrt{2} \approx 1.41$ ratio). This closes the open problem of separating deterministic and random mechanisms for utilitarian facility location mechanism design in $\mathbb{R}^2$. For $\mathbb{R}^d$, we show that the expected approximation ratio of our mechanism is in $[1.41 - O(1/\sqrt{d}), 1.547]$. 2. Improved learning augmented mechanisms through randomization. We show our ideas can achieve better performance in the learning augmented setting in $\mathbb{R}^2$, where in addition to the input the mechanism also receives predictions. For the output prediction model of Agrawal et al. 2022 we show an improved expected consistency-robustness trade-off. Our results also imply improved performance for the input MAC predictions model of Barak et al. 2024. 3. The limitations of Random Dictators. We show a lower bound for the common mechanism class of GRD (Generalized Random Dictator) mechanisms, where only locations reported by the agents may be returned. We show that any GRD mechanism has a larger expected approximation ratio than our RR-CWM mechanism, as our lower bound for $\mathbb{R}^2$ is $\frac{4}π$ (matching the upper bound of RR-CWM, which is not a GRD mechanism). For $\mathbb{R}^d$, we show a lower bound of $\sqrt{2} - O(1/d)$.

Zohar Barak, Anupam Gupta, Inbal Talgam-Cohen

Algorithms with predictions have attracted much attention in the last years across various domains, including variants of facility location, as a way to surpass traditional worst-case analyses. We study the $k$-facility location mechanism design problem, where the $n$ agents are strategic and might misreport their location. Unlike previous models, where predictions are for the $k$ optimal facility locations, we receive $n$ predictions for the locations of each of the agents. However, these predictions are only "mostly" and "approximately" correct (or MAC for short) -- i.e., some $δ$-fraction of the predicted locations are allowed to be arbitrarily incorrect, and the remainder of the predictions are allowed to be correct up to an $\varepsilon$-error. We make no assumption on the independence of the errors. Can such predictions allow us to beat the current best bounds for strategyproof facility location? We show that the $1$-median (geometric median) of a set of points is naturally robust under corruptions, which leads to an algorithm for single-facility location with MAC predictions. We extend the robustness result to a "balanced" variant of the $k$ facilities case. Without balancedness, we show that robustness completely breaks down, even for the setting of $k=2$ facilities on a line. For this "unbalanced" setting, we devise a truthful random mechanism that outperforms the best known result of Lu et al. [2010], which does not use predictions. En route, we introduce the problem of "second" facility location (when the first facility's location is already fixed). Our findings on the robustness of the $1$-median and more generally $k$-medians may be of independent interest, as quantitative versions of classic breakdown-point results in robust statistics.