論文の概要: Computation and Bribery of Voting Power in Delegative Simple Games
- arxiv url: http://arxiv.org/abs/2104.03692v1
- Date: Thu, 8 Apr 2021 11:28:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-09 12:54:57.878296
- Title: Computation and Bribery of Voting Power in Delegative Simple Games
- Title（参考訳）: 簡素なゲームにおける投票力の計算と贈収賄
- Authors: Gianlorenzo D'Angelo, Esmaeil Delfaraz and Hugo Gilbert
- Abstract要約: 委任的単純ゲームにおける代表的バンジャフ値とシャプリー・シュビク値を計算する擬似多項式時間アルゴリズムを提案する。
次に、代表者の投票力/重みを最大化・最小化することを目的とした贈収賄問題について、定員数を最大にすることで検討する。
- 参考スコア（独自算出の注目度）: 12.259540948639327
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Weighted voting games is one of the most important classes of cooperative
games. Recently, Zhang and Grossi [53] proposed a variant of this class, called
delegative simple games, which is well suited to analyse the relative
importance of each voter in liquid democracy elections. Moreover, they defined
a power index, called the delagative Banzhaf index to compute the importance of
each agent (i.e., both voters and delegators) in a delegation graph based on
two key parameters: the total voting weight she has accumulated and the
structure of supports she receives from her delegators.
We obtain several results related to delegative simple games. We first
propose a pseudo-polynomial time algorithm to compute the delegative Banzhaf
and Shapley-Shubik values in delegative simple games. We then investigate a
bribery problem where the goal is to maximize/minimize the voting power/weight
of a given voter in a delegation graph by changing at most a fixed number of
delegations. We show that the problems of minimizing/maximizing a voter's power
index value are strongly NP-hard. Furthermore, we prove that having a better
approximation guarantee than $1-1/e$ to maximize the voting weight of a voter
is not possible, unless $P = NP$, then we provide some parameterized complexity
results for this problem. Finally, we show that finding a delegation graph with
a given number of gurus that maximizes the minimum power index value an agent
can have is a computationally hard problem.
- Abstract（参考訳）: 軽量投票ゲームは、協調ゲームにおいて最も重要なクラスの1つである。
最近、張とグロッシ[53]は、流動民主主義選挙における各有権者の相対的重要性を分析するのに好適な、エレガントな単純ゲーム(delegative simple game)と呼ばれる、このクラスの変種を提案した。
さらに、彼らはデリゲートグラフにおける各エージェント(すなわち有権者と議員の両方)の重要性を、彼女が蓄積した総投票重量と、代表者から受け取った支持構造に基づいて計算するために、遅延的バンジャフ指数(delagative Banzhaf index)と呼ばれるパワーインデックスを定義した。
単純ゲームに関するいくつかの結果を得る。
まず,delegative simple gamesにおけるdelegative banzhafとshapley-shubikの値を計算する擬似多項時間アルゴリズムを提案する。
次に、代表者の投票力/重みを最大化・最小化することを目的とした贈収賄問題について、定員数を最大にすることで検討する。
投票者のパワーインデックス値の最小化/最大化の問題はNPハードであることを示す。
さらに、投票者の投票重量を最大化するために1-1/e$よりもよい近似保証を持つことは、$p = np$ でない限り不可能であると証明する。
最後に,エージェントが持つ最小のパワーインデックス値を最大化する,与えられた数のグルを持つデリゲーショングラフを見つけることは計算量的に難しい問題であることを示す。
関連論文リスト
- FastGAS: Fast Graph-based Annotation Selection for In-Context Learning [53.17606395275021]
インコンテキスト学習(ICL)は、大規模言語モデル(LLM)に対して、一連のトレーニングインスタンスをプロンプトとして使用することにより、新しいタスクに対処する権限を与える。
既存の手法では、アノテーションのラベルなし例のサブセットを選択する方法が提案されている。
本稿では,高品質なインスタンスを効率的に識別するグラフベースの選択手法であるFastGASを提案する。
論文 参考訳（メタデータ） (2024-06-06T04:05:54Z) - As Time Goes By: Adding a Temporal Dimension Towards Resolving
Delegations in Liquid Democracy [16.219158909792256]
我々の研究は、液体民主主義システムにおける意思決定問題に時間的水平線を統合するための第一歩を踏み出します。
我々のアプローチは、計算複雑性解析を通じて、時間グラフ理論から概念とツールを利用する。
論文 参考訳（メタデータ） (2023-07-24T15:46:45Z) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳（メタデータ） (2023-03-22T03:28:12Z) - 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) - On the Complexity of Finding a Diverse and Representative Committee
using a Monotone, Separable Positional Multiwinner Voting Rule [0.0]
計算社会選択における研究の線は、選挙における公正性を保証するために制約を使用することを懸念している。
最近の研究は、多様な代表委員会を見つけるためのモデルを提案し、モデルの計算的側面を研究した。
ここでは、単調で分離可能な複数投票ルールを用いて、多彩で代表的な委員会を見つける複雑さを分類する。
論文 参考訳（メタデータ） (2022-11-23T18:56:44Z) - Predicting Winning Regions in Parity Games via Graph Neural Networks
(Extended Abstract) [68.8204255655161]
グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。
これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
論文 参考訳（メタデータ） (2022-10-18T15:10:25Z) - 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) - On Parameterized Complexity of Liquid Democracy [5.897728689802829]
流動民主主義では、各投票者は自決するか、他の投票者に投票を委任する。
最終的に投票する有権者を、投票する有権者のサブセットと共に決定するためには、代表団グラフのサイクルを解決する必要がある。
投票者が投票する有権者の数を上限にすることで、システムデザイナーは個々の投票者の権限を制限することができる。
論文 参考訳（メタデータ） (2020-11-28T18:48:22Z) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。
驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。
提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文 参考訳（メタデータ） (2020-08-12T08:52:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。