論文の概要: When Can Liquid Democracy Unveil the Truth?
- arxiv url: http://arxiv.org/abs/2104.01828v1
- Date: Mon, 5 Apr 2021 09:45:14 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-06 14:25:49.212767
- Title: When Can Liquid Democracy Unveil the Truth?
- Title（参考訳）: 液体民主主義はいつ真実を明かすのか?
- Authors: Ruben Becker, Gianlorenzo D'Angelo, Esmaeil Delfaraz and Hugo Gilbert
- Abstract要約: Caragiannis と Micha によって策定されたいわゆる ODP-problem を調査します。
有権者の確率やネットワークの接続性に関するいくつかの仮説の下で、我々は1時間1/2$近似アルゴリズムを得る。
この観察は、ソーシャルネットワークの接続が液体民主主義パラダイムの効率にとって重要な特徴であることを正式に証明している。
- 参考スコア（独自算出の注目度）: 12.198420431487731
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In this paper, we investigate the so-called ODP-problem that has been
formulated by Caragiannis and Micha [10]. Here, we are in a setting with two
election alternatives out of which one is assumed to be correct. In ODP, the
goal is to organise the delegations in the social network in order to maximize
the probability that the correct alternative, referred to as ground truth, is
elected. While the problem is known to be computationally hard, we strengthen
existing hardness results by providing a novel strong approximation hardness
result: For any positive constant $C$, we prove that, unless $P=NP$, there is
no polynomial-time algorithm for ODP that achieves an approximation guarantee
of $\alpha \ge (\ln n)^{-C}$, where $n$ is the number of voters. The reduction
designed for this result uses poorly connected social networks in which some
voters suffer from misinformation. Interestingly, under some hypothesis on
either the accuracies of voters or the connectivity of the network, we obtain a
polynomial-time $1/2$-approximation algorithm. This observation proves formally
that the connectivity of the social network is a key feature for the efficiency
of the liquid democracy paradigm. Lastly, we run extensive simulations and
observe that simple algorithms (working either in a centralized or
decentralized way) outperform direct democracy on a large class of instances.
Overall, our contributions yield new insights on the question in which
situations liquid democracy can be beneficial.
- Abstract（参考訳）: 本稿では,caragiannis と micha [10] が定式化したいわゆる odp-problem について検討する。
ここでは、選挙の選択肢が2つあり、そのうちの1つが正しいと仮定されている。
ODPでは、正しい代替案が選出される確率を最大化するために、ソーシャルネットワーク内の代表団を組織することを目的としている。
任意の正の定数 $c$ に対して、$p=np$ でなければ odp の多項式時間アルゴリズムは存在せず、$\alpha \ge (\ln n)^{-c}$ の近似保証を達成し、ここで $n$ は有権者の数である。
この結果のためにデザインされた削減は、一部の有権者が誤った情報に苦しむ、不接続なソーシャルネットワークを使っている。
興味深いことに、有権者のアキュラシエーションやネットワークの接続性に関する仮説の下で、多項式時間1/2$-近似アルゴリズムを得る。
この観察は、ソーシャルネットワークの接続が液体民主主義パラダイムの効率にとって重要な特徴であることを正式に証明している。
最後に、我々は広範なシミュレーションを行い、単純なアルゴリズム(中央集権的または非集中的な方法で動く)が大規模なインスタンスで直接民主主義を上回ることを観察する。
全体として、私たちの貢献は、液体民主主義がどのような状況で役に立つかについての新たな洞察をもたらす。
関連論文リスト
- Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - Elections in the Post-Quantum Era: Is the Complexity Shield Strong
Enough? [0.0]
量子コンピュータは、上述した複雑性シールドに対する新たな脅威だと考えている。
本稿では,選挙に対する攻撃の可能性について概説し,量子コンピューティングの能力について論じるとともに,今後の研究の方向性を図示する。
論文 参考訳（メタデータ） (2024-03-08T12:52:11Z) - When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。
我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。
これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
論文 参考訳（メタデータ） (2023-10-09T19:40:54Z) - Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。
私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。
オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
論文 参考訳（メタデータ） (2023-09-27T04:33:09Z) - A Nearly-Linear Time Algorithm for Minimizing Risk of Conflict in Social
Networks [11.244268226976478]
本研究では,少数のノードの初期意見を変更することで,ソーシャルネットワークにおける競合のリスクを最小限に抑えることの課題について検討する。
特に、高速なネットワークは200万以上のノードを持つ大規模ネットワークにスケールし、最大20タイムのスピードアップを実現している。
論文 参考訳（メタデータ） (2023-01-13T10:32:12Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Provably Efficient Offline Reinforcement Learning with Trajectory-Wise
Reward [66.81579829897392]
我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。
PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。
私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
論文 参考訳（メタデータ） (2022-06-13T19:11:22Z) - Fine-Grained Complexity and Algorithms for the Schulze Voting Method [9.399840807973545]
シュルツ法(schulze method)と呼ばれる,有名な単勝投票ルールの計算的側面について検討した。
私たちの論文は、計算社会的選択の分野に微細な複雑さをもたらす最初のものです。
論文 参考訳（メタデータ） (2021-03-05T22:27:36Z) - Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。
目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。
ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文 参考訳（メタデータ） (2021-02-13T12:57:51Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。