論文の概要: Computational Aspects of Conditional Minisum Approval Voting in Elections with Interdependent Issues

• arxiv url: http://arxiv.org/abs/2202.01660v1
• Date: Thu, 3 Feb 2022 16:15:54 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-04 18:23:26.287633
• Title: Computational Aspects of Conditional Minisum Approval Voting in Elections with Interdependent Issues
• Title（参考訳）: 異なる問題のある選挙における条件付き最小投票の計算的側面
• Authors: Evangelos Markakis and Georgios Papasotiropoulos
• Abstract要約: 我々は、バロットとラングの研究によって導入されたミニサムの一般化(2016年)を条件最小(Conditional Minisum)と呼ぶ。 私たちの研究は、条件付き投票によってもたらされる複雑さの影響をよりよく理解します。
• 参考スコア（独自算出の注目度）: 16.219158909792256
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approval voting provides a simple, practical framework for multi-issue elections, and the most representative example among such election rules is the classic Minisum approval voting rule. We consider a generalization of Minisum, introduced by the work of Barrot and Lang [2016], referred to as Conditional Minisum, where voters are also allowed to express dependencies between issues. The price we have to pay when we move to this higher level of expressiveness is that we end up with a computationally hard rule. Motivated by this, we focus on the computational aspects of Conditional Minisum, where progress has been rather scarce so far. We identify restrictions that concern the voters' dependencies and the value of an optimal solution, under which we provide the first multiplicative approximation algorithms for the problem. At the same time, by additionally requiring certain structural properties for the union of dependencies cast by the whole electorate, we obtain optimal efficient algorithms for well-motivated special cases. Overall, our work provides a better understanding on the complexity implications introduced by conditional voting.
• Abstract（参考訳）: 承認投票は、多項目選挙のための単純かつ実用的な枠組みを提供し、そのような選挙規則の中で最も代表的な例は、古典的なミニサム承認投票規則である。 我々は,条件付きミニサム (conditional minisum) と呼ばれる barrot と lang [2016] によって導入されたminisum の一般化を検討する。 この高い表現力に移行するとき、私たちが支払うコストは、計算的に難しいルールに終止符を打つことです。 このことに動機づけられた我々は、これまで進歩が少なかった条件最小項の計算面に焦点を当てた。 我々は、有権者の依存関係と最適解の価値を懸念する制約を特定し、この問題に対する最初の乗算近似アルゴリズムを提供する。 同時に、選挙人全体によって鋳造される依存関係の和合に対する一定の構造的特性を付加することにより、モチベーションの良い特殊ケースに対して最適なアルゴリズムを得る。 全体として、我々の研究は条件付投票によってもたらされる複雑さの意味をよりよく理解する。

関連論文リスト

• 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)

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

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