論文の概要: On Parameterized Complexity of Liquid Democracy

• arxiv url: http://arxiv.org/abs/2011.14192v1
• Date: Sat, 28 Nov 2020 18:48:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-22 18:32:49.511997
• Title: On Parameterized Complexity of Liquid Democracy
• Title（参考訳）: 液状民主主義のパラメータ化複雑性について
• Authors: Palash Dey, Arnab Maiti and Amatya Sharma
• Abstract要約: 流動民主主義では、各投票者は自決するか、他の投票者に投票を委任する。 最終的に投票する有権者を、投票する有権者のサブセットと共に決定するためには、代表団グラフのサイクルを解決する必要がある。 投票者が投票する有権者の数を上限にすることで、システムデザイナーは個々の投票者の権限を制限することができる。
• 参考スコア（独自算出の注目度）: 5.897728689802829
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In liquid democracy, each voter either votes herself or delegates her vote to some other voter. This gives rise to what is called a delegation graph. To decide the voters who eventually votes along with the subset of voters whose votes they give, we need to resolve the cycles in the delegation graph. This gives rise to the Resolve Delegation problem where we need to find an acyclic sub-graph of the delegation graph such that the number of voters whose votes they give is bounded above by some integer {\lambda}. Putting a cap on the number of voters whose votes a voter gives enable the system designer restrict the power of any individual voter. The Resolve Delegation problem is already known to be NP-hard. In this paper we study the parameterized complexity of this problem. We show that Resolve Delegation is para-NP-hard with respect to parameters {\lambda}, number of sink nodes and the maximum degree of the delegation graph. We also show that Resolve Delegation is W[1]-hard even with respect to the treewidth of the delegation graph. We complement our negative results by exhibiting FPT algorithms with respect to some other parameters. We finally show that a related problem, which we call Resolve Fractional Delegation, is polynomial time solvable.
• Abstract（参考訳）: 流動民主主義では、各投票者は自決するか、他の投票者に投票を委任する。 これは代入グラフと呼ばれるものを生み出します。 最終的に投票する有権者を、投票する有権者のサブセットと共に決定するには、代表グラフのサイクルを解決する必要がある。 このことは、デリゲートグラフの非巡回部分グラフを見つける必要があるリゾルフ・デリゲーション問題を引き起こし、投票した有権者の数は、上述の整数 {\lambda} によって制限される。 投票者が投票する有権者の数を上限にすることで、システムデザイナーは個々の投票者の権限を制限することができる。 Resolve Delegation問題はすでにNPハードであることが知られている。 本稿では,この問題のパラメータ化複雑性について検討する。 Resolve Delegation はパラメータ {\lambda} 、シンクノードの数、デリゲートグラフの最大度に関してパラNPハードであることを示す。 また、デリゲートグラフのツリー幅に関しても、Resolve Delegation は W[1]-hard であることを示す。 我々は、他のパラメータに関してFPTアルゴリズムを示すことで、負の結果を補完する。 最終的に、Resolve Fractional Delegationと呼ばれる関連する問題が多項式時間分解可能であることを示す。

関連論文リスト

• Determining Winners in Elections with Absent Votes [26.675597212113658]
  我々は、投票が最上位の場合に、不在の投票問題で決定的な勝者を調査する。 単一の投票でWAV問題はNP完全であることを示す。 本稿では、時間内に問題を計算できるように、位置スコアリングルールの特別な場合を提案する。
  論文  参考訳（メタデータ） (2023-10-11T02:52:16Z)
• As Time Goes By: Adding a Temporal Dimension Towards Resolving Delegations in Liquid Democracy [16.219158909792256]
  我々の研究は、液体民主主義システムにおける意思決定問題に時間的水平線を統合するための第一歩を踏み出します。 我々のアプローチは、計算複雑性解析を通じて、時間グラフ理論から概念とツールを利用する。
  論文  参考訳（メタデータ） (2023-07-24T15:46:45Z)
• Predicting the Silent Majority on Graphs: Knowledge Transferable Graph Neural Network [45.790140824712616]
  声門ノード(声門少数派)とサイレントノード(サイレント多数派)からなるグラフ、すなわちVS-Graphは現実世界に広く存在している。 本稿では,メッセージパッシングと表現学習における分散シフトをモデル化した知識伝達可能なグラフニューラルネットワーク(KT-GNN)を提案する。
  論文  参考訳（メタデータ） (2023-02-02T04:46:21Z)
• Accelerating Voting by Quantum Computation [35.03314687289671]
  本稿では,任意の匿名投票規則に適用可能な量子加速投票アルゴリズムを提案する。 我々のアルゴリズムは、$Thetaleft(fracntextMOVright)$ timeで高い確率で正しい勝者を出力する。
  論文  参考訳（メタデータ） (2023-01-08T07:29:38Z)
• Measuring a Priori Voting Power -- Taking Delegations Seriously [8.12790806321461]
  本稿では,自由民主主義選挙における有権者の事前投票力を測定するための新たな権力指標を紹介し,その基盤となるネットワークが代表を制限している。 投票者の臨界度を計算することは、投票の重みがインスタンスサイズでアスリーバウンドである場合でも、#Pハードであることが示される。 我々は、これらの理論的性質を強調し、投票権の制限が有権者の投票力をどのように変えるかを示す数値的な結果を提供する。
  論文  参考訳（メタデータ） (2023-01-06T11:16:57Z)
• Obvious Manipulability of Voting Rules [105.35249497503527]
  Gibbard-Satterthwaite の定理は、全会一致で非独裁的な投票規則は、戦略的なものではないと述べる。 我々は投票規則を再検討し、明らかでない操作性という戦略的安全性の弱い概念を考察する。
  論文  参考訳（メタデータ） (2021-11-03T02:41:48Z)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  有権者が承認投票(すなわち、承認した候補者の集合)を投じた場合のマルチウィナー選挙における贈収賄の問題を研究する。 我々は、いくつかの承認ベースのマルチウィナールール(AV、SAV、GAV、RAV、承認ベースのチェンバリン--Courant、およびPAV)を検討します。 一般に、我々の問題は、勝利した委員会の候補者の承認数を増やすための贈収賄行為を制限した場合、より容易になる傾向がある。
  論文  参考訳（メタデータ） (2021-04-19T08:26:40Z)
• Computation and Bribery of Voting Power in Delegative Simple Games [12.259540948639327]
  委任的単純ゲームにおける代表的バンジャフ値とシャプリー・シュビク値を計算する擬似多項式時間アルゴリズムを提案する。 次に、代表者の投票力/重みを最大化・最小化することを目的とした贈収賄問題について、定員数を最大にすることで検討する。
  論文  参考訳（メタデータ） (2021-04-08T11:28:50Z)
• Graph-Based Tri-Attention Network for Answer Ranking in CQA [56.42018099917321]
  本稿では,グラフに基づく新しい三者関係ネットワーク,すなわちGTANを提案し,回答ランキングのスコアを生成する。 実世界の3つのCQAデータセットの実験では、GTANは最先端の回答ランキング法よりも大幅に優れていた。
  論文  参考訳（メタデータ） (2021-03-05T10:40:38Z)
• Topology-Aware Graph Pooling Networks [51.9008939769679]
  ポーリング操作はコンピュータビジョンや自然言語処理タスクに有効である。 グラフデータ上でプーリング操作を実行する上での課題のひとつは、グラフ上で明確に定義されていない局所性の欠如である。 本稿では,グラフトポロジを明示的に考慮したトポロジ対応プーリング(TAP)層を提案する。
  論文  参考訳（メタデータ） (2020-10-19T20:14:30Z)
• Representative Graph Neural Network [113.67254049938629]
  いくつかの代表的特徴を動的にサンプリングするために、代表グラフ層を提示する。 すべての位置からメッセージを伝搬する代わりに、RepGraphレイヤは1つのノードの応答を数個の代表ノードで計算します。
  論文  参考訳（メタデータ） (2020-08-12T09:46:52Z)

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

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