Optimizing Multiple Simultaneous Objectives for Voting and Facility
Location
- URL: http://arxiv.org/abs/2212.03467v1
- Date: Wed, 7 Dec 2022 05:12:40 GMT
- Title: Optimizing Multiple Simultaneous Objectives for Voting and Facility
Location
- Authors: Yeu Han, Christopher Jerrett, Elliot Anshelevich
- Abstract summary: We study the classic facility location setting, where we are given $n$ clients and $m$ possible facility locations in some arbitrary metric space.
We consider the $l$-centrum family of objectives, which includes the total distance, max distance, and many others.
- Score: 7.0579376123869935
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the classic facility location setting, where we are given $n$
clients and $m$ possible facility locations in some arbitrary metric space, and
want to choose a location to build a facility. The exact same setting also
arises in spatial social choice, where voters are the clients and the goal is
to choose a candidate or outcome, with the distance from a voter to an outcome
representing the cost of this outcome for the voter (e.g., based on their
ideological differences). Unlike most previous work, we do not focus on a
single objective to optimize (e.g., the total distance from clients to the
facility, or the maximum distance, etc.), but instead attempt to optimize
several different objectives simultaneously. More specifically, we consider the
$l$-centrum family of objectives, which includes the total distance, max
distance, and many others. We present tight bounds on how well any pair of such
objectives (e.g., max and sum) can be simultaneously approximated compared to
their optimum outcomes. In particular, we show that for any such pair of
objectives, it is always possible to choose an outcome which simultaneously
approximates both objectives within a factor of $1+\sqrt{2}$, and give a
precise characterization of how this factor improves as the two objectives
being optimized become more similar. For $q>2$ different centrum objectives, we
show that it is always possible to approximate all $q$ of these objectives
within a small constant, and that this constant approaches 3 as $q\rightarrow
\infty$. Our results show that when optimizing only a few simultaneous
objectives, it is always possible to form an outcome which is a significantly
better than 3 approximation for all of these objectives.
Related papers
- Decoding-Time Language Model Alignment with Multiple Objectives [88.64776769490732]
Existing methods primarily focus on optimizing LMs for a single reward function, limiting their adaptability to varied objectives.
Here, we propose $textbfmulti-objective decoding (MOD)$, a decoding-time algorithm that outputs the next token from a linear combination of predictions.
We show why existing approaches can be sub-optimal even in natural settings and obtain optimality guarantees for our method.
arXiv Detail & Related papers (2024-06-27T02:46:30Z) - Facility Location Games with Scaling Effects [69.28397508730046]
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.
We find results on the total and maximum cost approximation ratios achievable by strategyproof and anonymous mechanisms.
arXiv Detail & Related papers (2024-02-29T07:08:18Z) - Eliciting User Preferences for Personalized Multi-Objective Decision
Making through Comparative Feedback [76.7007545844273]
We propose a multi-objective decision making framework that accommodates different user preferences over objectives.
Our model consists of a Markov decision process with a vector-valued reward function, with each user having an unknown preference vector.
We suggest an algorithm that finds a nearly optimal policy for the user using a small number of comparison queries.
arXiv Detail & Related papers (2023-02-07T23:58:19Z) - Bayesian Optimization of Multiple Objectives with Different Latencies [0.0]
In some cases, it is possible to evaluate the objectives separately, and a different latency or evaluation cost can be associated with each objective.
We propose a scalarization based knowledge gradient acquisition function which accounts for the different evaluation costs of the objectives.
We prove consistency of the algorithm and show empirically that it significantly outperforms a benchmark algorithm which always evaluates both objectives.
arXiv Detail & Related papers (2023-02-02T18:33:34Z) - Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining
the Inefficiency For Many Objectives [16.904475483445452]
The NSGA-II is one of the most prominent algorithms to solve multi-objective optimization problems.
We show that the NSGA-II is less effective for larger numbers of objectives.
arXiv Detail & Related papers (2022-11-23T16:15:26Z) - Alleviating Search Bias in Bayesian Evolutionary Optimization with Many
Heterogeneous Objectives [9.139734850798124]
We deal with multi-objective optimization problems with heterogeneous objectives (HE-MOPs)
A new acquisition function that mitigates search bias towards the fast objectives is suggested.
We demonstrate the effectiveness of the proposed algorithm by testing it on widely used multi-/many-objective benchmark problems.
arXiv Detail & Related papers (2022-08-25T17:07:40Z) - Toward Discovering Options that Achieve Faster Planning [15.874687616157056]
We propose a new objective for option discovery that emphasizes the computational advantage of using options in planning.
Our new algorithm achieves a high objective value, which is close to the value achieved by a set of human-designed options.
arXiv Detail & Related papers (2022-05-25T06:10:10Z) - Multi-Target Active Object Tracking with Monte Carlo Tree Search and
Target Motion Modeling [126.26121580486289]
In this work, we are dedicated to multi-target active object tracking (AOT), where there are multiple targets as well as multiple cameras in the environment.
The goal is maximize the overall target coverage of all cameras.
We establish a multi-target 2D environment to simulate the sports games, and experimental results demonstrate that our method can effectively improve the target coverage.
arXiv Detail & Related papers (2022-05-07T05:08:15Z) - Adaptive Multi-Goal Exploration [118.40427257364729]
We show how AdaGoal can be used to tackle the objective of learning an $epsilon$-optimal goal-conditioned policy.
AdaGoal is anchored in the high-level algorithmic structure of existing methods for goal-conditioned deep reinforcement learning.
arXiv Detail & Related papers (2021-11-23T17:59:50Z) - Rethinking Counting and Localization in Crowds:A Purely Point-Based
Framework [59.578339075658995]
We propose a purely point-based framework for joint crowd counting and individual localization.
We design an intuitive solution under this framework, which is called Point to Point Network (P2PNet)
arXiv Detail & Related papers (2021-07-27T11:41:50Z) - Practical Bayesian Optimization of Objectives with Conditioning
Variables [1.0497128347190048]
We consider the more general case where a user is faced with multiple problems that each need to be optimized conditional on a state variable.
Similarity across objectives boosts optimization of each objective in two ways.
We propose a framework for conditional optimization: ConBO.
arXiv Detail & Related papers (2020-02-23T22:06:26Z)
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.