文献

J-GLOBAL ID：202202278339324186   整理番号：22A1045778

逐次選挙におけるオンライン bの複雑性【JST・京大機械翻訳】

The complexity of online bribery in sequential elections

著者 (3件)： Hemaspaandra Edith (Department of Computer Science, Rochester Institute of Technology, Rochester, NY, 14623, USA) ,  Hemaspaandra Lane A. (Department of Computer Science, University of Rochester, Rochester, NY, 14627, USA) ,  Rothe Jorg (Institut fuer Informatik, Heinrich-Heine-Universitaet Duesseldorf, Duesseldorf, 40225, Germany)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 127  ページ： 66-90  発行年： 2022年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： brの複雑度に関する以前の研究は, brが同時に起こると仮定し,そして, brはすべての投票の十分な知識を持つ。しかし,多くの実世界の設定投票は,逐次的に来る,そして, brは,与えられた投票を変えるかどうかを決定するのに,また,その決定が,どの投票者が何の投票者を投げるかを知らないかどうかを決定するために,使用-または-ose-それモーメントを持つかもしれない。ここでは,そのようなオンライン,逐次設定において,モデルを導入し,その研究を開始した。勝者決定問題が多項式時間計算可能である選択システムであっても,オンライン,逐次設定は,多項階層またはPSPACEの高レベルに対する完全性まで問題をジャンプする。しかし,いくつかの自然で重要な選択システムに対して,そのような劇的な複雑性増加が起こらないこと,また,著者らは,それらの brな問題の複雑性を指摘していることも示した。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 決定問題 ,  選択 ,  知識 ,  計算量 ,  モデル ,  投票 ,  *モーメント ,  *性質 ,  完全性 ,  量化記号
準シソーラス用語： 複雑性 ,  多項式時間 ,  複雑度 ,  *オンライン , 【Automatic Indexing@JST】

著者キーワード (6件)： Br ,  計算の複雑さ ,  計算社会的選択 ,  論理 ,  限定子割当 ,  逐次選択

分類 (2件)： 人工知能  (JE08000Z) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 選挙 ,  オンライン ,  複雑性