論文の概要: On the Complexity of Winner Determination and Strategic Control in
Conditional Approval Voting
- arxiv url: http://arxiv.org/abs/2202.01660v2
- Date: Wed, 29 Nov 2023 14:32:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-01 04:23:15.436729
- Title: On the Complexity of Winner Determination and Strategic Control in
Conditional Approval Voting
- Title（参考訳）: 条件付承認投票における勝者決定の複雑さと戦略統制について
- Authors: Evangelos Markakis and Georgios Papasotiropoulos
- Abstract要約: 条件最小 (Conditional Minisum, CMS) は、優先的な依存関係を持つ多問題選挙の投票規則である。
我々は,CMSを表現性と計算効率の良好なトレードオフを実現するソリューションとみなすことができることを示す。
- 参考スコア（独自算出の注目度）: 13.207754600697138
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We focus on a generalization of the classic Minisum approval voting rule,
introduced by Barrot and Lang (2016), and referred to as Conditional Minisum
(CMS), for multi-issue elections with preferential dependencies. Under this
rule, voters are allowed to declare dependencies between different issues, but
the price we have to pay for this higher level of expressiveness is that we end
up with a computationally hard rule. Motivated by this, we first focus on
finding special cases that admit efficient algorithms for CMS. Our main result
in this direction is that we identify the condition of bounded treewidth (of an
appropriate graph, emerging from the provided ballots) as the necessary and
sufficient condition for exact polynomial algorithms, under common complexity
assumptions. We then move to the design of approximation algorithms. For the
(still hard) case of binary issues, we identify natural restrictions on the
voters' ballots, under which we provide the first multiplicative approximation
algorithms for the problem. The restrictions involve upper bounds on the number
of dependencies an issue can have on the others and on the number of
alternatives per issue that a voter can approve. Finally, we also investigate
the complexity of problems related to the strategic control of conditional
approval elections by adding or deleting either voters or alternatives and we
show that in most variants of these problems, CMS is computationally resistant
against control. Overall, we conclude that CMS can be viewed as a solution that
achieves a satisfactory tradeoff between expressiveness and computational
efficiency, when we have a limited number of dependencies among issues, while
at the same time exhibiting sufficient resistance to control.
- Abstract（参考訳）: 我々は、barrot と lang (2016) によって導入された古典的なミニサム承認投票ルールの一般化に焦点をあて、優先的な依存関係を持つ多項目選挙のための条件付きミニサム (cms) と呼ぶ。
このルールの下では、有権者は異なる問題間の依存関係を宣言することができるが、この高い表現力のレベルのために支払わなければならない価格は、計算的に難しいルールに終わることである。
そこで我々はまず,CMSの効率的なアルゴリズムを認める特別な事例の発見に焦点をあてる。
この方向の主な結果は、(与えられた投票から生じる適切なグラフの)有界木幅の条件を、共通の複雑性仮定の下で、正確な多項式アルゴリズムに必要な十分条件として識別することである。
その後、近似アルゴリズムの設計に移行する。
二分問題(英語版)の場合には、投票者の投票に対する自然な制限を特定し、この問題に対する最初の乗法近似アルゴリズムを提供する。
この制限は、ある問題が他の問題に持てる依存関係の数と、投票者が承認できる問題ごとの代替案の数に上限がある。
最後に, 条件付き承認選挙の戦略的制御に関わる問題の複雑性について, 投票者や代替案の追加・削除によって検討し, それらの問題の多くにおいて, CMSは制御に対して計算的に抵抗的であることを示す。
全体として、CMSは、表現性と計算効率の良好なトレードオフを実現するソリューションであり、問題間の依存関係が限られていると同時に、制御に対する十分な抵抗を示すものであると結論付けている。
関連論文リスト
- Computing Voting Rules with Elicited Incomplete Votes [11.550634521005968]
我々は、有権者に$t m$の候補者を問うことで計算可能な投票ルールについて検討する。
限定的なクエリで計算可能なルールを評価するために、パラメータ化された上と下の境界をそのようなクエリの数に割り当てる。
論文 参考訳（メタデータ） (2024-02-16T22:17:01Z) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。
本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。
マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
論文 参考訳（メタデータ） (2023-05-01T06:46:22Z) - Robust Voting Rules from Algorithmic Robust Statistics [25.313563663123354]
サンプルの一定割合が任意に破損しても,精度よく中央ランクを推定できるアルゴリズムを提案する。
我々の研究は、アルゴリズムによる頑健な統計から、投票や情報集約における中心的な推論問題への視点の自然な注入と考えることができる。
論文 参考訳（メタデータ） (2021-12-13T02:30:26Z) - Recursive Causal Structure Learning in the Presence of Latent Variables
and Selection Bias [27.06618125828978]
本稿では,潜伏変数と選択バイアスの存在下での観測データからシステムの因果MAGを学習する問題を考察する。
本稿では,音と完全性を備えた計算効率のよい制約ベースの新しい手法を提案する。
提案手法と人工と実世界の両方の構造に関する技術の現状を比較した実験結果を提供する。
論文 参考訳（メタデータ） (2021-10-22T19:49:59Z) - Modularity in Reinforcement Learning via Algorithmic Independence in
Credit Assignment [79.5678820246642]
提案手法は, 事前決定の順序に対して, スパース変化のみを必要とする伝達問題に対して, 政策段階の手法よりも, より標本効率が高いことを示す。
我々は最近提案された社会的意思決定の枠組みをマルコフ決定プロセスよりもよりきめ細かい形式主義として一般化する。
論文 参考訳（メタデータ） (2021-06-28T21:29:13Z) - 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) - Adaptive Combinatorial Allocation [77.86290991564829]
割り当てが繰り返し選択され、戻り値は不明だが学習可能であり、決定には制約が伴う。
我々のモデルは、複雑な制約があっても、両側のマッチングと一方のマッチングをカバーしています。
論文 参考訳（メタデータ） (2020-11-04T15:02:59Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
i) 任意の状態空間, (ii) 任意の行動空間, (iii) 任意の送信者のユーティリティ関数を用いて, 一般の状況下での公衆の説得問題を考察する。
任意の公的な説得問題に対して準多項式時間ビクテリア近似アルゴリズムを提案し、特定の設定でQPTASを出力する。
論文 参考訳（メタデータ） (2020-02-12T18:59:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。