論文の概要: Facility Reallocation on the Line
- arxiv url: http://arxiv.org/abs/2103.12894v1
- Date: Tue, 23 Mar 2021 23:48:45 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-25 13:51:50.580532
- Title: Facility Reallocation on the Line
- Title(参考訳): 路線上の施設移転
- Authors: Bart de Keijzer and Dominik Wojtczak
- Abstract要約: 我々は,$n$エージェントによって報告された位置に基づいて,施設を時間間隔で移動させる実数線上の多段施設再配置問題を考える。
再配置アルゴリズムの目的は、社会コストを最小化することであり、すなわち、施設と全てのエージェントのあらゆる段階の合計距離の合計と、施設を移動させるコストを最小化することである。
- 参考スコア(独自算出の注目度): 9.40406631624105
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a multi-stage facility reallocation problems on the real line,
where a facility is being moved between time stages based on the locations
reported by $n$ agents. The aim of the reallocation algorithm is to minimise
the social cost, i.e., the sum over the total distance between the facility and
all agents at all stages, plus the cost incurred for moving the facility. We
study this problem both in the offline setting and online setting. In the
offline case the algorithm has full knowledge of the agent locations in all
future stages, and in the online setting the algorithm does not know these
future locations and must decide the location of the facility on a
stage-per-stage basis. We derive the optimal algorithm in both cases. For the
online setting we show that its competitive ratio is $(n+2)/(n+1)$. As neither
of these algorithms turns out to yield a strategy-proof mechanism, we propose
another strategy-proof mechanism which has a competitive ratio of $(n+3)/(n+1)$
for odd $n$ and $(n+4)/n$ for even $n$, which we conjecture to be the best
possible. We also consider a generalisation with multiple facilities and
weighted agents, for which we show that the optimum can be computed in
polynomial time for a fixed number of facilities.
- Abstract(参考訳): 実線上では,n$エージェントが報告した場所に基づいて,施設が時間間隔で移動している,多段階的な施設配置問題を考える。
再配置アルゴリズムの目的は、社会コストを最小化することであり、すなわち、施設と全てのエージェントのあらゆる段階の合計距離の合計と、施設を移動させるコストを最小化することである。
オフライン設定とオンライン設定の両方でこの問題を研究する。
オフラインの場合、アルゴリズムは全ての将来の段階におけるエージェントの位置の完全な知識を持ち、オンライン設定では、アルゴリズムはこれらの将来の位置を知らないので、ステージごとに施設の位置を決定する必要がある。
どちらの場合にも最適アルゴリズムを導出する。
オンライン環境では、その競合比は$(n+2)/(n+1)$である。
いずれのアルゴリズムも戦略防御機構は得られないため、奇数$n$に対して$(n+3)/(n+1)$、偶数$(n+4)/n$が$(n+4)/n$という競合比を持つ別の戦略防御機構を提案する。
また,複数の施設と重み付きエージェントによる一般化についても検討し,一定数の施設で最適値を多項式時間で計算できることを示した。
関連論文リスト
- Decentralized Multi-Task Online Convex Optimization Under Random Link
Failures [5.513958040574729]
我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。
我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
論文 参考訳(メタデータ) (2024-01-04T00:57:33Z) - Can We Find Nash Equilibria at a Linear Rate in Markov Games? [95.10091348976779]
マルチプレイヤーゼロサム割引マルコフゲームにおける分散学習について検討した。
目標は、2つの特性を満たすエージェントのポリシー最適化アルゴリズムを設計することである。
論文 参考訳(メタデータ) (2023-03-03T02:40:26Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳(メタデータ) (2022-07-25T18:29:16Z) - Policy Optimization for Markov Games: Unified Framework and Faster
Convergence [81.3266426402464]
このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。
このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
論文 参考訳(メタデータ) (2022-06-06T14:23:13Z) - Local Stochastic Bilevel Optimization with Momentum-Based Variance
Reduction [104.41634756395545]
具体的には、まず、決定論的勾配に基づくアルゴリズムであるFedBiOを提案する。
FedBiOの複雑性は$O(epsilon-1.5)$である。
本アルゴリズムは数値実験において,他のベースラインと比較して優れた性能を示す。
論文 参考訳(メタデータ) (2022-05-03T16:40:22Z) - Learning Augmented Online Facility Location [11.401250502020503]
最適施設の位置に関する不完全な予測を生かしたオンライン施設位置情報(OFL)のオンラインアルゴリズムを提案する。
競合比は, 要求数から一定までにおいて, 下位対数から円滑に減少することが証明された。
アルゴリズムの競合比の誤差への依存性が最適であることを示す。
論文 参考訳(メタデータ) (2021-07-17T16:44:27Z) - Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。
目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。
ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文 参考訳(メタデータ) (2021-02-13T12:57:51Z) - A Provably Efficient Algorithm for Linear Markov Decision Process with
Low Switching Cost [53.968049198926444]
スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。
このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
論文 参考訳(メタデータ) (2021-01-02T18:41:27Z) - Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。
意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。
この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
論文 参考訳(メタデータ) (2020-12-13T04:47:37Z) - Multiagent Rollout and Policy Iteration for POMDP with Application to
Multi-Robot Repair Problems [1.6939372704265414]
有限状態および制御空間,部分状態観測,マルチエージェント構造を有する無限地平面割引動的プログラミング問題を考える。
本手法は、部分的に観測可能なマルチエージェント問題の計算問題に特に対処する。
論文 参考訳(メタデータ) (2020-11-09T06:51:50Z) - Constrained Multiagent Rollout and Multidimensional Assignment with the
Auction Algorithm [0.0]
本稿では,制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張について考察する。
提案手法では,ベースが実現可能な解を生成する場合,ロールアウトアルゴリズムはコスト改善特性を有することを示す。
コスト改善特性は計算要求を大幅に削減した代替実装で維持されていることを示す。
論文 参考訳(メタデータ) (2020-02-18T07:09:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。