論文の概要: Competitive Algorithms for Cooperative Multi-Agent Ski-Rental Problems

• arxiv url: http://arxiv.org/abs/2507.15727v1
• Date: Mon, 21 Jul 2025 15:36:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-22 20:51:32.463594
• Title: Competitive Algorithms for Cooperative Multi-Agent Ski-Rental Problems
• Title（参考訳）: 協調型多エージェントスキーレンタル問題の競合アルゴリズム
• Authors: Xuchuang Wang, Bo Sun, Hedyeh Beyhaghi, John C. S. Lui, Mohammad Hajiesmaili, Adam Wierman,
• Abstract要約: 本稿では,従来のスキーレンタルジレンマをグループ設定に一般化する,新しいマルチエージェントスキーレンタル問題を提案する。 我々のモデルでは、各エージェントは固定された日代でレンタルするか、個別のコストでパスを購入することができる。 我々はエージェントのアクティブな時代が異なり、エージェントが意思決定プロセスから抜け出すと動的状態につながるシナリオを考察する。
• 参考スコア（独自算出の注目度）: 35.95355517827071
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces a novel multi-agent ski-rental problem that generalizes the classical ski-rental dilemma to a group setting where agents incur individual and shared costs. In our model, each agent can either rent at a fixed daily cost, or purchase a pass at an individual cost, with an additional third option of a discounted group pass available to all. We consider scenarios in which agents' active days differ, leading to dynamic states as agents drop out of the decision process. To address this problem from different perspectives, we define three distinct competitive ratios: overall, state-dependent, and individual rational. For each objective, we design and analyze optimal deterministic and randomized policies. Our deterministic policies employ state-aware threshold functions that adapt to the dynamic states, while our randomized policies sample and resample thresholds from tailored state-aware distributions. The analysis reveals that symmetric policies, in which all agents use the same threshold, outperform asymmetric ones. Our results provide competitive ratio upper and lower bounds and extend classical ski-rental insights to multi-agent settings, highlighting both theoretical and practical implications for group decision-making under uncertainty.
• Abstract（参考訳）: 本稿では,従来のスキーレンタルジレンマを,エージェントが個人や共有コストを発生させるグループ設定に一般化する,新しいマルチエージェントスキーレンタル問題を提案する。 我々のモデルでは、各エージェントは固定された日代でレンタルするか、個別のコストでパスを購入することができる。 我々はエージェントのアクティブな時代が異なり、エージェントが意思決定プロセスから抜け出すと動的状態につながるシナリオを考察する。 異なる視点からこの問題に対処するために、私たちは3つの異なる競争比率(全体、状態依存、個々人の合理性)を定義します。 各目的に対して、最適決定性およびランダム化ポリシーを設計・分析する。 我々の決定論的政策は、動的状態に適応する状態認識しきい値関数を使用し、一方、ランダム化されたポリシーは、調整された状態認識分布から閾値をサンプリングし、再サンプリングする。 この分析は、全てのエージェントが同じ閾値を使用する対称ポリシーが非対称ポリシーよりも優れていることを示した。 以上の結果から,従来のスキーレンタルの知見を多エージェント設定に拡張し,不確実性を考慮したグループ意思決定における理論的および実践的意味を明らかにした。

関連論文リスト

• On multiagent online problems with predictions [0.0]
  マルチエージェント環境での予測による(競争的な)アルゴリズムのパワーについて検討する。 エージェントが将来の(自己)行動に1つの予測器を、他のプレイヤーの行動に1つの予測器を使用すると仮定する2つの予測器フレームワークを導入する。
  論文  参考訳（メタデータ） (2025-07-15T08:52:12Z)
• On the Hardness of Decentralized Multi-Agent Policy Evaluation under Byzantine Attacks [12.696705862929337]
  完全分散型マルチエージェント政策評価問題について,最大$f$の障害エージェントの存在下で検討する。 特に、モデル中毒設定を伴ういわゆるビザンツの欠陥モデルに焦点を当てる。
  論文  参考訳（メタデータ） (2024-09-19T16:27:08Z)
• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  競売業者が各ラウンドの買い手グループに、合計で$T$で分けない商品を販売している問題を考える。 競売人は、各グループの最低平均配分を保証する公正な制約に固執しつつ、割引された全体の収益を最大化することを目的としている。
  論文  参考訳（メタデータ） (2024-05-31T19:26:05Z)
• On Imperfect Recall in Multi-Agent Influence Diagrams [57.21088266396761]
  マルチエージェント・インフルエンス・ダイアグラム(MAID)はベイズネットワークに基づくゲーム理論モデルとして人気がある。 混合ポリシと2種類の相関平衡を用いて, 忘れ易いエージェントと不注意なエージェントでMAIDを解く方法を示す。 また,不完全なリコールがしばしば避けられないマルコフゲームやチーム状況へのMAIDの適用についても述べる。
  論文  参考訳（メタデータ） (2023-07-11T07:08:34Z)
• 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)
• Fair Incentives for Repeated Engagement [0.46040036610482665]
  我々は、参加決定が受け取ったインセンティブに依存するエージェントに直面する場合、維持のための最適な金融インセンティブスキームを見つけるという課題について検討する。 明示的な差別がなくても、システムの種類構成を変化させることで、ポリシーが無意識に異なるタイプのエージェントを識別できることが示される。
  論文  参考訳（メタデータ） (2021-10-28T04:13:53Z)
• Robust Allocations with Diversity Constraints [65.3799850959513]
  エージェント値の積を最大化するナッシュ福祉規則は,多様性の制約が導入されたとき,一意にロバストな位置にあることを示す。 また, ナッシュ・ウェルズによる保証は, 広く研究されているアロケーション・ルールのクラスにおいて, ほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2021-09-30T11:09:31Z)
• Multiagent Value Iteration Algorithms in Dynamic Programming and Reinforcement Learning [0.0]
  各段階における制御がいくつかの異なる決定から構成される無限水平動的プログラミング問題を考える。 以前の研究では、ポリシーの反復アルゴリズムを導入しました。
  論文  参考訳（メタデータ） (2020-05-04T16:34:24Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。 まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。 当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
  論文  参考訳（メタデータ） (2020-04-19T18:00:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。