論文の概要: 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$)が上記の下界とほぼ一致しながら、その問題を正しく解くことを証明している。
これらの結果は、対称的なコンセンサス問題(正しい意見の概念を含まない)とは対照的に、確率的意見力学を用いた正しい意見への高速収束は、メモリの使用を必要とする可能性があることを示唆している。
この洞察は、少数の知識のある個人に依存する自然情報の拡散過程を反映している可能性がある。
関連論文リスト
- 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) - Strategic Resource Selection with Homophilic Agents [68.19497461624208]
類似エージェントとの共同資源利用を目指す異種エージェントを用いたリソース選択ゲームを提案する。
モデルでは,異なるタイプのエージェントを考慮し,その決定的特徴はユーザ間の同一型エージェントの割合である。
このような有界な有理性はゲーム理論上有利な性質を持つことを示す。
論文 参考訳(メタデータ) (2023-05-01T14:14:58Z) - Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure
of Costs [65.23158435596518]
チームのマルコフゲームとして、部分的に観測可能なコストでマルチサイクルルーティング問題を解く。
我々のマルチエージェント強化学習アプローチである、いわゆるマルチエージェントニューラルリライタは、1エージェントニューラルリライタを利用して、反復的に書き換えるソリューションによって問題を解決する。
論文 参考訳(メタデータ) (2022-06-13T09:17:40Z) - Collaborative Multi-agent Stochastic Linear Bandits [28.268809091816287]
我々は,ネットワークを構成するN$エージェントが局所的に通信し,全体的な後悔を最小限に抑える,協調的マルチエージェント線形帯域設定について検討する。
すべてのエージェントは、プレイされたアクションの対応する報酬を観察し、加速されたコンセンサス手順を使用して、すべてのエージェントが取得した報酬の平均の見積もりを計算する。
論文 参考訳(メタデータ) (2022-05-12T19:46:35Z) - Robust Allocations with Diversity Constraints [65.3799850959513]
エージェント値の積を最大化するナッシュ福祉規則は,多様性の制約が導入されたとき,一意にロバストな位置にあることを示す。
また, ナッシュ・ウェルズによる保証は, 広く研究されているアロケーション・ルールのクラスにおいて, ほぼ最適であることを示す。
論文 参考訳(メタデータ) (2021-09-30T11:09:31Z) - Fairness in Ranking under Uncertainty [42.51950847766776]
不公平は、より有益なエージェントが、より有益なエージェントよりも悪い結果を得るときに起こる。
私たちの中心的なポイントは、不公平の主な原因は不確実性であるということです。
有効性と有効性とを最適にトレードオフするランキングを、プリンシパルにどのように計算するかを示す。
論文 参考訳(メタデータ) (2021-07-14T14:10:16Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。