論文の概要: Strengthening Full Justified Representation: Efficient Verification and Computation

• arxiv url: http://arxiv.org/abs/2608.11500v1
• Date: Tue, 11 Aug 2026 23:29:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-13 19:07:54.402157
• Title: Strengthening Full Justified Representation: Efficient Verification and Computation
• Title（参考訳）: 完全正当表現の強化:効率的な検証と計算
• Abstract要約: 本稿では, FJR と EJR+ の厳格な強化である FJR+ を紹介する。 我々はResidual-Budget Greedyアルゴリズムを解析し、FJR+を満足するような部分的な委員会を選択することを証明した。 RBGのプロジェクト固有のバージョンは、この特性を時間内に計算し、サブコアのコストベースのバージョンを満足する価格的な結果まで継続することができる。
• 参考スコア（独自算出の注目度）: 11.208733293527795
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Full justified representation (FJR) is among the strongest known satisfiable proportionality axioms for approval-based committee elections. Recent work has shown that an FJR committee can be found in polynomial time, but verifying whether a given committee satisfies FJR remains coNP-complete. We introduce FJR+, a strict strengthening of FJR and EJR+ that can be verified and satisfied in polynomial time. We then analyze the Residual-Budget Greedy (RBG) algorithm and prove that it selects a partial committee such that every size-$k$ completion satisfies FJR+. This freedom allows us to use sequential Phragmén to obtain a priceable completion. The resulting rule always satisfies FJR+ and the sub-core, and it is priceable whenever at least $k$ candidates receive an approval. We also obtain a Droop-quota version of FJR+. Finally, we extend FJR+ to approval-based participatory budgeting with arbitrary project costs. A project-specific version of RBG computes this property in polynomial time and can be continued to a priceable outcome satisfying a cost-based version of the sub-core.
• Abstract（参考訳）: 完全な正当性表現(FJR)は、承認ベースの委員会の選挙において、最も強力な比例公理である。 近年の研究では、FJR委員会が多項式時間内に見つかることが示されているが、与えられた委員会がFJRを満足するかどうかの検証はCoNP完全のままである。 本稿ではFJRとEJRを厳格に強化したFJR+を紹介する。 次に、Residual-Budget Greedy (RBG) アルゴリズムを分析し、FJR+を満足するような部分的な委員会を選択することを証明した。 この自由により、シーケンシャルなFragménを使って、高価な完成品を得ることができます。 結果のルールは常にFJR+とサブコアを満足しており、最低でも$k$の候補者が承認を受けると価格が上がる。 また、FJR+のDroop-quota版も取得する。 最後に、FJR+を任意のプロジェクトコストで承認ベースの参加予算に拡張する。 RBGのプロジェクト固有のバージョンは、この特性を多項式時間で計算し、サブコアのコストベースのバージョンを満足する価格的な結果まで継続することができる。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Rethinking Thinking Tokens: LLMs as Improvement Operators [80.12087211785949]
  推論トレーニングは、LLMに長い思考の連鎖(長いCoT)を生み出す動機を与え、自己チェックによるソリューション戦略を探索することを可能にする。 これにより、精度が高くなりますが、コンテキストの長さ、トークン/計算コスト、応答レイテンシが膨らみます。 現在のモデルはメタ認知を活用して、このParetoフロンティアで他の組み合わせを提供できるのでしょうか? i) 多様なドラフトを並列に生成し、(ii) それらを有界なテキストワークスペースに蒸留し、(iii) このワークスペース上に条件付き精製する。
  論文  参考訳（メタデータ） (2025-10-01T17:08:59Z)
• Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification [83.25968588249776]
  本稿では,LiRPAに基づく手法とサンプリングに基づく手法を組み合わせることで,厳密な中間到達性集合を計算できる新しいフレームワークを提案する。 無視可能な計算オーバーヘッドでは、$textttPT-LiRPA$は推定された到達可能な集合を利用し、ニューラルネットワークの出力の上下線形境界を著しく締め付ける。
  論文  参考訳（メタデータ） (2025-07-07T18:45:53Z)
• Strengthening Proportionality in Temporal Voting [19.55552582336426]
  承認投票による時間投票の枠組みにおける比例表現について検討する。 我々は,JR,PJR,EJRのより強力な変種について検討し,より要求の高い多元公理の時相適応を導入する。 我々は,EJR+とFJRの2つの公理が,いずれの選挙においても満足できるまま,EJRを強化していることを示す。
  論文  参考訳（メタデータ） (2025-05-28T16:02:52Z)
• Full Proportional Justified Representation [6.62942789921787]
  マルチウィンター投票では、有権者の承認投票を比例代表する委員会を形成することが不可欠である。 正当性表現(JR)の概念は、いかなる大きな「結束的な」有権者集団も比例的に「代表」すべきだと要求する。 FPJR(Full Proportional Justified Representation)と呼ばれる組み合わせ(C2)-(R1)について検討する。
  論文  参考訳（メタデータ） (2025-01-21T10:13:28Z)
• Combinatorial Logistic Bandits [30.829239785016934]
  我々はロジスティック・バンディット(CLogB)と呼ばれる新しいフレームワークを紹介する。 各ラウンドでは、ベースアームのサブセット(スーパーアームと呼ばれる)が選択され、各ベースアームの結果はバイナリとなる。 実世界のデータセットの実験では、ベンチマークアルゴリズムと比較してアルゴリズムの性能が優れていた。
  論文  参考訳（メタデータ） (2024-10-22T14:52:46Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• (1+1) Genetic Programming With Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error [16.075339182916128]
  GPシステムは、必要最小限のコンポーネントが備わっている場合、$n$変数の結合を進化させることができる。 GPシステムは、$O(ell n log2 n)$, $ell geq が受理木の大きさの極限であるような予想において、正確なターゲット関数を進化させることができることを示す。
  論文  参考訳（メタデータ） (2023-03-13T20:24:21Z)
• Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
  半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。 まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。 次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-31T13:09:39Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。 最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。 提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
  論文  参考訳（メタデータ） (2022-06-14T08:14:14Z)
• Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete [4.170994234169557]
  InpiricalRiskmization(英語版)として知られる、与えられたデータポイントのセットに可能な限り適合する2層完全連結ニューラルネットワークの重みとバイアスを求める問題を考察する。 任意のデータポイントが有理である場合でも、いくつかのインスタンスを最適に訓練できるウェイトとして、任意の大きな次数の代数数が必要であることを証明します。 この結果、Basu, Mianjy, Mukherjee [ICLR 2018]のような検索アルゴリズムは、$mathsfNP=existsでない限り、複数の出力次元を持つネットワークでは不可能である。
  論文  参考訳（メタデータ） (2022-04-04T10:28:11Z)
• Random Reshuffling with Variance Reduction: New Analysis and Better Rates [0.8594140167290099]
  一般問題に対するRRSVRG(Random Reshuffling)の最初の解析を提供します。 rrsvrgは、ほぼ広く使われている$mathcalo(kappa3/2)レートで$calo(kappa3/2)に改善できる。 これは以前の最高の$mathcalO(kappa3/2) RRSVRGメソッドを改善します。
  論文  参考訳（メタデータ） (2021-04-19T14:30:10Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

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

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