論文の概要: On the Role of Memory in Robust Opinion Dynamics
- arxiv url: http://arxiv.org/abs/2302.08600v1
- Date: Thu, 16 Feb 2023 21:53:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-20 16:35:50.647607
- Title: On the Role of Memory in Robust Opinion Dynamics
- Title（参考訳）: ロバストオピニオンダイナミクスにおける記憶の役割について
- Authors: Luca Becchetti, Andrea Clementi, Amos Korman, Francesco Pasquale, Luca
Trevisan and Robin Vacus
- Abstract要約: 我々は,n$同一エージェントと匿名エージェントからなる完全接続システムにおける意見力学について検討する。
あるソースエージェントは、最初は正しい意見を持ち、実行中は、この意見のままである。
ソースがなければ、エージェントは$ell$ランダムエージェントの意見を引き出し、あるルールに従ってその意見を更新する。
- 参考スコア（独自算出の注目度）: 3.4533036061671973
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate opinion dynamics in a fully-connected system, consisting of
$n$ identical and anonymous agents, where one of the opinions (which is called
correct) represents a piece of information to disseminate. In more detail, one
source agent initially holds the correct opinion and remains with this opinion
throughout the execution. The goal for non-source agents is to quickly agree on
this correct opinion, and do that robustly, i.e., from any initial
configuration. The system evolves in rounds. In each round, one agent chosen
uniformly at random is activated: unless it is the source, the agent pulls the
opinions of $\ell$ random agents and then updates its opinion according to some
rule. We consider a restricted setting, in which agents have no memory and they
only revise their opinions on the basis of those of the agents they currently
sample. As restricted as it is, this setting encompasses very popular opinion
dynamics, such as the voter model and best-of-$k$ majority rules.
Qualitatively speaking, we show that lack of memory prevents efficient
convergence. Specifically, we prove that no dynamics can achieve correct
convergence in an expected number of steps that is sub-quadratic in $n$, even
under a strong version of the model in which activated agents have complete
access to the current configuration of the entire system, i.e., the case
$\ell=n$. Conversely, we prove that the simple voter model (in which $\ell=1$)
correctly solves the problem, while almost matching the aforementioned lower
bound.
These results suggest that, in contrast to symmetric consensus problems (that
do not involve a notion of correct opinion), fast convergence on the correct
opinion using stochastic opinion dynamics may indeed require the use of memory.
This insight may reflect on natural information dissemination processes that
rely on a few knowledgeable individuals.
- Abstract（参考訳）: 完全に接続されたシステムにおける意見のダイナミクスを調査し、$n$の同一エージェントと匿名エージェントで構成され、意見の1つ(正しい)が情報の拡散を表す。
より詳しくは、あるソースエージェントが最初は正しい意見を持ち、実行中もこの意見のままである。
非ソースエージェントの目標は、この正しい意見に迅速に同意し、あらゆる初期設定から堅牢にそれを行うことである。
システムはラウンドで進化する。
各ラウンドにおいて、ランダムに選択された1つのエージェントが起動される: ソースでない限り、エージェントは$\ell$ランダムエージェントの意見をプルし、あるルールに従ってその意見を更新する。
エージェントが記憶を持っておらず、現在サンプルとなっているエージェントの意見に基づいてのみ意見を変更するような制限された設定を考える。
制限されているように、この設定は投票者モデルや多数決ルールなど、非常に一般的な意見のダイナミクスを含んでいる。
定性的に言えば、メモリ不足は効率的な収束を妨げる。
具体的には、活性化されたエージェントがシステム全体の現在の構成、すなわち$\ell=n$を満たしているモデルの強力なバージョンでさえも、n$のサブクアドラルである期待される数ステップにおいて、ダイナミクスが正しい収束を達成できないことを証明します。
逆に、単純な投票者モデル($\ell=1$)が上記の下界とほぼ一致しながら、その問題を正しく解くことを証明している。
これらの結果は、対称的なコンセンサス問題(正しい意見の概念を含まない)とは対照的に、確率的意見力学を用いた正しい意見への高速収束は、メモリの使用を必要とする可能性があることを示唆している。
この洞察は、少数の知識のある個人に依存する自然情報の拡散過程を反映している可能性がある。
関連論文リスト
- Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。
我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。
我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
論文 参考訳（メタデータ） (2024-10-22T19:34:53Z) - On the Hardness of Decentralized Multi-Agent Policy Evaluation under Byzantine Attacks [12.696705862929337]
完全分散型マルチエージェント政策評価問題について,最大$f$の障害エージェントの存在下で検討する。
特に、モデル中毒設定を伴ういわゆるビザンツの欠陥モデルに焦点を当てる。
論文 参考訳（メタデータ） (2024-09-19T16:27:08Z) - Towards Unified Alignment Between Agents, Humans, and Environment [24.731978646069]
本稿では, エージェントと人間の意図, 環境動態, 自己制約の同時調整を提唱する$mathbfUA2$の原則を紹介する。
我々は,WebShopに現実的な機能を導入し,意図を示すユーザプロファイル,複雑な環境力学のパーソナライズされたリランク,自己制約を反映する実行コスト統計などの概念実証を行った。
論文 参考訳（メタデータ） (2024-02-12T16:14:22Z) - Pure Exploration under Mediators' Feedback [63.56002444692792]
マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。
本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。
本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
論文 参考訳（メタデータ） (2023-08-29T18:18:21Z) - On the Convergence of Bounded Agents [80.67035535522777]
境界エージェントは、エージェントの将来の振る舞いを記述するために必要な最小の状態数が減少できない場合に収束する。
第2の見解では、エージェントの内部状態が変更された場合にのみ、エージェントのパフォーマンスが変化するときのみ、境界エージェントが収束した。
論文 参考訳（メタデータ） (2023-07-20T17:27:29Z) - Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure
of Costs [65.23158435596518]
チームのマルコフゲームとして、部分的に観測可能なコストでマルチサイクルルーティング問題を解く。
我々のマルチエージェント強化学習アプローチである、いわゆるマルチエージェントニューラルリライタは、1エージェントニューラルリライタを利用して、反復的に書き換えるソリューションによって問題を解決する。
論文 参考訳（メタデータ） (2022-06-13T09:17:40Z) - Robust Allocations with Diversity Constraints [65.3799850959513]
エージェント値の積を最大化するナッシュ福祉規則は,多様性の制約が導入されたとき,一意にロバストな位置にあることを示す。
また, ナッシュ・ウェルズによる保証は, 広く研究されているアロケーション・ルールのクラスにおいて, ほぼ最適であることを示す。
論文 参考訳（メタデータ） (2021-09-30T11:09:31Z) - Bandit Linear Optimization for Sequential Decision Making and
Extensive-Form Games [102.23975166536326]
tree-form sequential decision making (tfsdm) は、エージェントと潜在的に敵対的な環境の間のツリー形式の相互作用をモデル化することで、古典的なワンショット意思決定を拡張する。
これは、各プレイヤーが幅広い形式のゲームで直面するオンライン意思決定問題、およびマルコフ決定プロセス、およびエージェントが観測された履歴を条件とする部分観察可能なマルコフ決定プロセスをキャプチャする。
本稿では, (i) 線形時間損失と (ii) $o(sqrtt)$ cumulative regret の両方を提供する拡張dmのバンディット線形最適化問題に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-03-08T05:00:13Z) - Robust Multi-Agent Multi-Armed Bandits [26.26185074977412]
最近の研究によると、$Kの武器を持った盗賊の独立した事例に直面しているエージェントが、後悔を減らすために協力できることが示されている。
我々は、悪質なエージェントの振る舞いを仮定することなく、$m$が$K$よりも小さいと仮定すると、このアルゴリズムに対するコラボレーションは本当に後悔を減らせることを示した。
論文 参考訳（メタデータ） (2020-07-07T22:27:30Z) - VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit
Feedback [104.06766271716774]
本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。
まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。
当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
論文 参考訳（メタデータ） (2020-04-19T18:00:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。