Mechanism Design for Facility Location using Predictions

• URL: http://arxiv.org/abs/2508.03818v1
• Date: Tue, 05 Aug 2025 18:05:32 GMT
• Title: Mechanism Design for Facility Location using Predictions
• Authors: Toby Walsh,
• Abstract summary: We study mechanisms for the facility location problem augmented with predictions of the optimal facility location.<n>We consider performance in terms of consistency (worst case when predictions are accurate) and robustness (worst case irrespective of the accuracy of predictions)
• Score: 18.168659230989384
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study mechanisms for the facility location problem augmented with predictions of the optimal facility location. We demonstrate that an egalitarian viewpoint which considers both the maximum distance of any agent from the facility and the minimum utility of any agent provides important new insights compared to a viewpoint that just considers the maximum distance. As in previous studies, we consider performance in terms of consistency (worst case when predictions are accurate) and robustness (worst case irrespective of the accuracy of predictions). By considering how mechanisms with predictions can perform poorly, we design new mechanisms that are more robust. Indeed, by adjusting parameters, we demonstrate how to trade robustness for consistency. We go beyond the single facility problem by designing novel strategy proof mechanisms for locating two facilities with bounded consistency and robustness that use two predictions for where to locate the two facilities.

Related papers

• Prediction-Augmented Mechanism Design for Weighted Facility Location [1.6552489352816389]
  We provide a prediction augmented algorithmic framework for balancing the consistency and robustness over strategic agents with non-uniform weights.<n>We prove that there is no strategyproof deterministic mechanism that reach $1$-consistency and $Oleft( n cdot fracW_maxW_min right)$-robustness in weighted FLP, even with fully predictions of all agents.
  arXiv  Detail & Related papers  (2025-07-09T03:13:52Z)
• Equitable Mechanism Design for Facility Location [18.168659230989384]
  We consider strategy proof mechanisms for facility location which maximize equitability between agents.<n>We first prove a simple but fundamental impossibility result that no strategy proof mechanism can bound the approximation ratio of the optimal Gini index of utilities.
  arXiv  Detail & Related papers  (2025-06-12T08:08:58Z)
• Tuning for Trustworthiness -- Balancing Performance and Explanation Consistency in Neural Network Optimization [49.567092222782435]
  We introduce the novel concept of XAI consistency, defined as the agreement among different feature attribution methods.<n>We create a multi-objective optimization framework that balances predictive performance with explanation.<n>Our research provides a foundation for future investigations into whether models from the trade-off zone-balancing performance loss and XAI consistency-exhibit greater robustness.
  arXiv  Detail & Related papers  (2025-05-12T13:19:14Z)
• Performative Prediction on Games and Mechanism Design [69.7933059664256]
  We study a collective risk dilemma where agents decide whether to trust predictions based on past accuracy.<n>As predictions shape collective outcomes, social welfare arises naturally as a metric of concern.<n>We show how to achieve better trade-offs and use them for mechanism design.
  arXiv  Detail & Related papers  (2024-08-09T16:03:44Z)
• Facility Location Games with Scaling Effects [63.421996606381164]
  We take the classic facility location problem and consider a variation in which each agent's individual cost function is equal to their distance from the facility multiplied by a scaling factor.<n>We focus on the objectives of total and maximum cost, describing the computation of the optimal solution.<n>We characterize the conditions on scaling functions which ensure that agents have single-peaked preferences.
  arXiv  Detail & Related papers  (2024-02-29T07:08:18Z)
• Mechanism Design With Predictions for Obnoxious Facility Location [0.0]
  We study mechanism design with predictions for the facility obnoxious location problem. We present deterministic strategyproof mechanisms that display tradeoffs between robustness and consistency on segments, squares, circles and trees.
  arXiv  Detail & Related papers  (2022-12-19T15:04:11Z)
• Collaborative Uncertainty Benefits Multi-Agent Multi-Modal Trajectory Forecasting [61.02295959343446]
  This work first proposes a novel concept, collaborative uncertainty (CU), which models the uncertainty resulting from interaction modules.<n>We build a general CU-aware regression framework with an original permutation-equivariant uncertainty estimator to do both tasks of regression and uncertainty estimation.<n>We apply the proposed framework to current SOTA multi-agent trajectory forecasting systems as a plugin module.
  arXiv  Detail & Related papers  (2022-07-11T21:17:41Z)
• Joint Forecasting of Panoptic Segmentations with Difference Attention [72.03470153917189]
  We study a new panoptic segmentation forecasting model that jointly forecasts all object instances in a scene. We evaluate the proposed model on the Cityscapes and AIODrive datasets.
  arXiv  Detail & Related papers  (2022-04-14T17:59:32Z)
• Counterfactual Inference of Second Opinions [13.93477033094828]
  Automated decision support systems that are able to infer second opinions from experts can potentially facilitate a more efficient allocation of resources. This paper looks at the design of this type of support systems from the perspective of counterfactual inference. Experiments on both synthetic and real data show that our model can be used to infer second opinions more accurately than its non-causal counterpart.
  arXiv  Detail & Related papers  (2022-03-16T14:40:41Z)
• Test-time Collective Prediction [73.74982509510961]
  Multiple parties in machine learning want to jointly make predictions on future test points. Agents wish to benefit from the collective expertise of the full set of agents, but may not be willing to release their data or model parameters. We explore a decentralized mechanism to make collective predictions at test time, leveraging each agent's pre-trained model.
  arXiv  Detail & Related papers  (2021-06-22T18:29:58Z)
• Near Instance-Optimality in Differential Privacy [38.8726789833284]
  We develop notions of instance optimality in differential privacy inspired by classical statistical theory. We also develop inverse sensitivity mechanisms, which are instance optimal (or nearly instance optimal) for a large class of estimands.
  arXiv  Detail & Related papers  (2020-05-16T04:53:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.