Mechanism Design With Predictions for Obnoxious Facility Location

• URL: http://arxiv.org/abs/2212.09521v1
• Date: Mon, 19 Dec 2022 15:04:11 GMT
• Title: Mechanism Design With Predictions for Obnoxious Facility Location
• Authors: Gabriel Istrate, Cosmin Bonchis
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study mechanism design with predictions for the obnoxious facility location problem. We present deterministic strategyproof mechanisms that display tradeoffs between robustness and consistency on segments, squares, circles and trees. All these mechanisms are actually group strategyproof, with the exception of the case of squares, where manipulations from coalitions of two agents exist. We prove that these tradeoffs are optimal in the 1-dimensional case.

Related papers

• Mechanism Design for Facility Location using Predictions [18.168659230989384]
  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)
  arXiv  Detail & Related papers  (2025-08-05T18:05:32Z)
• 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)
• Refined Mechanism Design for Approximately Structured Priors via Active Regression [50.71772232237571]
  We consider the problem of a revenue-maximizing seller with a large number of items for sale to $n$ strategic bidders. It is well-known that optimal and even approximately-optimal mechanisms for this setting are notoriously difficult to characterize or compute.
  arXiv  Detail & Related papers  (2023-10-11T20:34:17Z)
• Proportional Fairness in Obnoxious Facility Location [70.64736616610202]
  We propose a hierarchy of distance-based proportional fairness concepts for the problem. We consider deterministic and randomized mechanisms, and compute tight bounds on the price of proportional fairness. We prove existence results for two extensions to our model.
  arXiv  Detail & Related papers  (2023-01-11T07:30:35Z)
• Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism [103.36492220921109]
  We show that although Strong Proportionality is a well-motivated and basic axiom, there is no deterministic strategyproof mechanism satisfying the property. We then identify a randomized mechanism called Random Rank which satisfies Strong Proportionality in expectation. Our main characterizes Random Rank as the unique mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation.
  arXiv  Detail & Related papers  (2022-05-30T00:51:57Z)
• Bridging Differential Privacy and Byzantine-Robustness via Model Aggregation [27.518542543750367]
  This paper aims at addressing conflicting issues in federated learning: differential privacy and Byzantinerobustness. Standard mechanisms add transmitted DP, envelops entangles with robust gradient aggregation to defend against Byzantine attacks. We show that the influence of our proposed mechanisms is deperturbed with that robust model aggregation.
  arXiv  Detail & Related papers  (2022-04-29T23:37:46Z)
• 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)
• Strategyproof and Proportionally Fair Facility Location [77.16035689756859]
  We focus on a simple, one-dimensional collective decision problem (often referred to as the facility location problem) We analyze a hierarchy of proportionality-based fairness axioms of varying strength. For each axiom, we characterize the family of mechanisms that satisfy the axiom and strategyproofness.
  arXiv  Detail & Related papers  (2021-11-02T12:41:32Z)
• Incentives in Two-sided Matching Markets with Prediction-enhanced Preference-formation [3.0204520109309843]
  We show that agents returning to the market can attack future predictions by interacting short-term non-optimally with their matches. We construct a formal economic model that captures the feedback loop between prediction mechanisms designed to assist agents and the matching mechanism used to pair them. We show that, as the trust in and accuracy of predictions increases, schools gain progressively more by initiating an adversarial interaction attack.
  arXiv  Detail & Related papers  (2021-09-16T09:56:41Z)
• Strategy Proof Mechanisms for Facility Location in Euclidean and Manhattan Space [17.68987003293372]
  Moving from one dimension to two (or more) dimensions often makes axiomatic properties more difficult to achieve. We show that approximation ratios may increase when moving to two (or more) dimensions.
  arXiv  Detail & Related papers  (2020-09-17T00:25:55Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)
• A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings [113.15416137912399]
  We propose and analyze a novel theoretical and algorithmic framework for structured prediction. We study a large class of loss functions that implicitly defines a suitable geometry on the problem. When dealing with output spaces with infinite cardinality, a suitable implicit formulation of the estimator is shown to be crucial.
  arXiv  Detail & Related papers  (2020-02-13T10:30:04Z)

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.