論文の概要: Optimizing Multiple Simultaneous Objectives for Voting and Facility
Location
- arxiv url: http://arxiv.org/abs/2212.03467v1
- Date: Wed, 7 Dec 2022 05:12:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-08 15:57:28.840233
- Title: Optimizing Multiple Simultaneous Objectives for Voting and Facility
Location
- Title（参考訳）: 投票と施設立地の同時目的の最適化
- Authors: Yeu Han, Christopher Jerrett, Elliot Anshelevich
- Abstract要約: 我々は古典的な施設位置設定について研究し、任意の距離空間に$n$クライアントと$m$可能な施設位置を与える。
我々は、全距離、最大距離などを含む目的の$l$-centrum族を考える。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 我々は古典的な施設位置設定について研究し、任意の距離空間に$n$クライアントと$m$可能な施設位置を与え、施設を建設する場所を選択したい。
全く同じ設定は、投票者がクライアントであり、投票者からこの結果のコストを表す結果までの距離(例えば、そのイデオロギー的な違いに基づいて)で、候補または結果を選択することを目標とする空間的社会的選択にも生じる。
これまでのほとんどの作業とは異なり、最適化するための単一の目的(クライアントから施設までの総距離、最大距離など)に集中するのではなく、複数の異なる目的を同時に最適化しようと試みています。
より具体的には、合計距離、最大距離、その他多くの目的を含む$l$-centrumファミリーを考える。
そのような目的の任意のペア(例えば、最大と和)が、最適結果と比較して同時に近似できるかどうかについて、厳密な境界を示す。
特に、そのような目的の任意のペアに対して、1+\sqrt{2}$の係数で両方の目的を同時に近似する結果を選択することができ、最適化された2つの目的がよりよくなるにつれて、この因子がどのように改善するかを正確に評価することができる。
例えば、$q>2$異なる遠心目標に対して、これらの目的のすべての$q$を小さな定数で近似することは常に可能であり、この定数は 3 に $q\rightarrow \infty$ として近づく。
これらの結果から,数個の同時目標のみを最適化する場合,これらすべての目標に対する3つの近似よりもはるかに優れた結果が得られることがわかった。
関連論文リスト
- Deep Pareto Reinforcement Learning for Multi-Objective Recommender Systems [60.91599969408029]
複数の目的を同時に最適化することは、レコメンデーションプラットフォームにとって重要なタスクです。
既存の多目的推薦システムは、そのような動的な関係を体系的に考慮していない。
論文 参考訳（メタデータ） (2024-07-04T02:19:49Z) - Decoding-Time Language Model Alignment with Multiple Objectives [116.42095026960598]
既存の手法は主に、1つの報酬関数に対してLMを最適化することに集中し、それらの適応性は様々な目的に制限される。
本稿では,予測の線形結合から次のトークンを出力する復号時間アルゴリズムである$textbfmulti-objective decoding (MOD)$を提案する。
提案手法は, 自然条件下であっても, 既存のアプローチが準最適であることを示すとともに, 提案手法の最適性を保証する。
論文 参考訳（メタデータ） (2024-06-27T02:46:30Z) - Facility Location Games with Scaling Effects [69.28397508730046]
古典的な施設配置問題を考慮し、各エージェントの個々のコスト関数が、スケーリング係数によって乗算された施設からの距離と等しくなる変動を考察する。
戦略と匿名のメカニズムによって達成できる総コストと最大コストの近似比について結果が得られた。
論文 参考訳（メタデータ） (2024-02-29T07:08:18Z) - Eliciting User Preferences for Personalized Multi-Objective Decision
Making through Comparative Feedback [76.7007545844273]
目的に対して異なるユーザの好みに対応する多目的意思決定フレームワークを提案する。
我々のモデルは、ベクトル値の報酬関数を持つマルコフ決定プロセスで構成され、各ユーザが未知の選好ベクトルを持つ。
少数の比較クエリを用いて,ユーザに対してほぼ最適なポリシを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-07T23:58:19Z) - Knowledge Gradient for Multi-Objective Bayesian Optimization with Decoupled Evaluations [0.0]
いくつかのケースでは、目的を個別に評価することができ、異なるレイテンシや評価コストをそれぞれの目標に関連付けることができる。
目的の異なる評価コストを考慮に入れたスカラー化に基づく知識獲得機能を提案する。
論文 参考訳（メタデータ） (2023-02-02T18:33:34Z) - Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining
the Inefficiency For Many Objectives [16.904475483445452]
NSGA-IIは多目的最適化問題を解く最も顕著なアルゴリズムの1つである。
NSGA-IIは多数の目的に対して効果が低いことを示す。
論文 参考訳（メタデータ） (2022-11-23T16:15:26Z) - Alleviating Search Bias in Bayesian Evolutionary Optimization with Many
Heterogeneous Objectives [9.139734850798124]
異種目的(HE-MOP)を用いた多目的最適化問題に対処する。
高速な目的に対して探索バイアスを緩和する新たな獲得関数を提案する。
提案アルゴリズムの有効性を,多目的・多目的のベンチマーク問題で検証することによって実証する。
論文 参考訳（メタデータ） (2022-08-25T17:07:40Z) - Toward Discovering Options that Achieve Faster Planning [15.874687616157056]
本稿では,計画におけるオプションの利用の計算上の優位性を強調するオプション発見の新たな目的を提案する。
我々の新しいアルゴリズムは、人間の設計した選択肢の集合によって達成される値に近い高い目的値を達成する。
論文 参考訳（メタデータ） (2022-05-25T06:10:10Z) - Multi-Target Active Object Tracking with Monte Carlo Tree Search and
Target Motion Modeling [126.26121580486289]
本研究は,マルチターゲットアクティブオブジェクトトラッキング(AOT)に重点を置いており,複数のターゲットと環境に複数のカメラが配置されている。
目標は、全カメラの全体的な対象範囲を最大化することです。
スポーツゲームをシミュレートするマルチターゲット2D環境を構築し,本手法が対象範囲を効果的に改善できることを示す実験結果を得た。
論文 参考訳（メタデータ） (2022-05-07T05:08:15Z) - Adaptive Multi-Goal Exploration [118.40427257364729]
我々は、AdaGoalが$epsilon$-optimal goal-conditioned policyを学習する目的を達成するためにどのように使えるかを示す。
AdaGoalは、ゴール条件の深い強化学習のための既存の手法の高レベルなアルゴリズム構造に固定されている。
論文 参考訳（メタデータ） (2021-11-23T17:59:50Z) - Practical Bayesian Optimization of Objectives with Conditioning
Variables [1.0497128347190048]
ユーザが複数の問題に直面している場合、状態変数に対してそれぞれを条件付きで最適化する必要がある場合を考える。
目的間の類似性は、それぞれの目的を2つの方法で最適化する。
本稿では条件最適化のためのフレームワークであるConBOを提案する。
論文 参考訳（メタデータ） (2020-02-23T22:06:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。