論文の概要: Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive

• arxiv url: http://arxiv.org/abs/2002.05156v2
• Date: Tue, 31 Mar 2020 13:26:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-01 20:32:13.764464
• Title: Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive
• Title（参考訳）: ベイズ市民の説得:ほぼ最適であり、ほぼ説得力がある
• Authors: Matteo Castiglioni, Andrea Celli, Nicola Gatti
• Abstract要約: i) 任意の状態空間, (ii) 任意の行動空間, (iii) 任意の送信者のユーティリティ関数を用いて, 一般の状況下での公衆の説得問題を考察する。 任意の公的な説得問題に対して準多項式時間ビクテリア近似アルゴリズムを提案し、特定の設定でQPTASを出力する。
• 参考スコア（独自算出の注目度）: 57.47546090379434
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Persuasion studies how an informed principal may influence the behavior of agents by the strategic provision of payoff-relevant information. We focus on the fundamental multi-receiver model by Arieli and Babichenko (2019), in which there are no inter-agent externalities. Unlike prior works on this problem, we study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender's utility functions. We fully characterize the computational complexity of computing a bi-criteria approximation of an optimal public signaling scheme. In particular, we show, in a voting setting of independent interest, that solving this problem requires at least a quasi-polynomial number of steps even in settings with a binary action space, assuming the Exponential Time Hypothesis. In doing so, we prove that a relaxed version of the Maximum Feasible Subsystem of Linear Inequalities problem requires at least quasi-polynomial time to be solved. Finally, we close the gap by providing a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
• Abstract（参考訳）: 説得は、インフォメーションプリンシパルが、ペイオフ関連情報の戦略的提供によってエージェントの行動にどのように影響するかを研究する。 我々は,arieli と babichenko (2019) による,エージェント間外部性のない基本マルチレシーバモデルに注目した。 この問題の先行研究とは異なり、一般設定における公衆の説得問題について研究する。 (i)任意の状態空間 (ii)任意の作用空間 (iii)任意の送信者のユーティリティ機能。 最適公開信号伝達スキームのバイクリテリア近似を計算する計算複雑性を完全に特徴付ける。 特に、独立性のある投票環境では、指数時間仮説を仮定して、二項作用空間を持つ設定においても、この問題を解決するには少なくとも準多項式のステップ数が必要であることを示す。 これにより、線形不等式問題の最大実現可能なサブシステムの緩和版は、少なくとも準多項時間を必要とすることが証明される。 最後に、任意の公的な説得問題に対して準多項式時間双基準近似アルゴリズムを提供することによりギャップを埋め、特定の設定でQPTASを得る。

関連論文リスト

• Scalable Decentralized Algorithms for Online Personalized Mean Estimation [12.002609934938224]
  本研究は,各エージェントが実数値分布からサンプルを収集し,その平均値を推定する,オーバーアーキシング問題の簡易版に焦点を当てた。 1つは信念の伝播からインスピレーションを得ており、もう1つはコンセンサスに基づくアプローチを採用している。
  論文  参考訳（メタデータ） (2024-02-20T08:30:46Z)
• Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
  不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。 簡便な解と理論的に最適な解との決定論的関係を導出する。
  論文  参考訳（メタデータ） (2023-10-03T04:40:38Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。 本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。 マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
  論文  参考訳（メタデータ） (2023-05-01T06:46:22Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。 この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。 有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
  論文  参考訳（メタデータ） (2022-05-16T15:47:41Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。 性能は不特定な事前条件で優雅に低下することを示す。
  論文  参考訳（メタデータ） (2021-07-03T23:17:26Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• A Distributed Privacy-Preserving Learning Dynamics in General Social Networks [22.195555664935814]
  一般的なソーシャルネットワークにおける分散プライバシ保護学習問題について検討する。 本研究では,4段階の分散ソーシャル学習アルゴリズムを提案する。 アルゴリズムの性能に関する2つの基本的な質問に対する回答を提供する。
  論文  参考訳（メタデータ） (2020-11-15T04:00:45Z)
• Robust Finite-State Controllers for Uncertain POMDPs [25.377873201375515]
  不確実部分可観測決定過程 (uPOMDPs) により、標準POMDPの確率的遷移観測関数は不確実集合に属する。 UPOMDPの有限メモリポリシを計算するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-09-24T02:58:50Z)

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

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