論文の概要: Shift Bribery over Social Networks

• arxiv url: http://arxiv.org/abs/2510.21200v1
• Date: Fri, 24 Oct 2025 07:05:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 09:00:15.405632
• Title: Shift Bribery over Social Networks
• Title（参考訳）: ソーシャルネットワークへ移行する贈賄
• Authors: Ashlesha Hota, Susobhan Bandopadhyay, Palash Dey, Shruti Thiagu,
• Abstract要約: シフト贈収賄では、議員は有権者にそのランクを上げるよう支払うことで、自分の好む候補者を奨励しようと試みている。 我々は、ネットワーク上のシフト収賄について研究し、有権者は有向重み付きグラフのノードとしてモデル化され、弧はそれらの間の社会的影響を表す。
• 参考スコア（独自算出の注目度）: 1.2070251470948772
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In shift bribery, a briber seeks to promote his preferred candidate by paying voters to raise their ranking. Classical models of shift bribery assume voters act independently, overlooking the role of social influence. However, in reality, individuals are social beings and are often represented as part of a social network, where bribed voters may influence their neighbors, thereby amplifying the effect of persuasion. We study Shift bribery over Networks, where voters are modeled as nodes in a directed weighted graph, and arcs represent social influence between them. In this setting, bribery is not confined to directly targeted voters its effects can propagate through the network, influencing neighbors and amplifying persuasion. Given a budget and individual cost functions for shifting each voter's preference toward a designated candidate, the goal is to determine whether a shift strategy exists within budget that ensures the preferred candidate wins after both direct and network-propagated influence takes effect. We show that the problem is NP-Complete even with two candidates and unit costs, and W[2]-hard when parameterized by budget or maximum degree. On the positive side, we design polynomial-time algorithms for complete graphs under plurality and majority rules and path graphs for uniform edge weights, linear-time algorithms for transitive tournaments for two candidates, linear cost functions and uniform arc weights, and pseudo-polynomial algorithms for cluster graphs. We further prove the existence of fixed-parameter tractable algorithms with treewidth as parameter for two candidates, linear cost functions and uniform arc weights and pseudo-FPT with cluster vertex deletion number for two candidates and uniform arc weights. Together, these results give a detailed complexity landscape for shift bribery in social networks.
• Abstract（参考訳）: シフト贈収賄では、議員は有権者にそのランクを上げるよう支払うことで、自分の好む候補者を奨励しようと試みている。 シフト収賄の古典的なモデルは、有権者が社会的影響力の役割を見越して独立して行動することを前提としている。 しかし実際には、個人は社会的存在であり、しばしばソーシャルネットワークの一部として表現される。 我々はネットワーク上のシフト収賄について研究し、有権者は有向重み付きグラフのノードとしてモデル化され、弧はそれらの間の社会的影響を表す。 この設定では、収賄は直接対象の有権者に限らず、その効果はネットワークを通じて伝播し、隣人に影響を与え、説得力を高めることができる。 各投票者の選好を指定された候補に移すための予算と個別のコスト関数が与えられた場合、その目標は、直接的かつネットワークにプロパゲートされた影響が作用した後、好まれる候補が勝つことを保証する予算内にシフト戦略が存在するかどうかを判断することである。 2つの候補と単位コストがあってもNP-Completeが問題であり、予算や最大度によってパラメータ化される場合、W[2]-hardが問題であることが示される。 正の面では,複数個のルールと一様エッジウェイトに対するパスグラフ,2つの候補に対するトランジショナルトーナメントのための線形時間アルゴリズム,線形コスト関数と一様アークウェイトに対する線形時間アルゴリズム,クラスタグラフのための擬似ポリノミカルアルゴリズムを用いて,完全グラフの多項式時間アルゴリズムを設計する。 さらに、線形コスト関数と一様アーク重みと、クラスタ頂点削除数と一様アーク重みの擬似FPTの2つの候補に対するパラメータとして、木幅を持つ固定パラメータトラクタブルアルゴリズムの存在を証明した。 これらの結果から、ソーシャルネットワークにおけるシフト贈収賄の複雑な状況が明らかになった。

関連論文リスト

• Latent Topic Synthesis: Leveraging LLMs for Electoral Ad Analysis [51.95395936342771]
  ラベルなしコーパスから解釈可能なトピック分類を自動生成するエンドツーエンドフレームワークを提案する。 われわれはこの枠組みを、2024年アメリカ合衆国大統領選挙の1ヶ月前のMeta政治広告の大規模なコーパスに適用する。 提案手法は,潜在談話構造を明らかにし,意味的に豊かなトピックラベルを合成し,モラル・フレーミングの次元でトピックを注釈する。
  論文  参考訳（メタデータ） (2025-10-16T20:30:20Z)
• Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
  STV (Single Transferable vote) は、複数議席の選挙において、優先的な比例投票方式である。 勝利のマージン(英: margin of victory)は、勝利者の集合を変えるために操作される必要のある最小数の投票である。 マージンの低い境界は、正確なマージンを計算するのが難しい場合、この目的のためにも使われる。
  論文  参考訳（メタデータ） (2025-01-24T13:39:23Z)
• Blink: Link Local Differential Privacy in Graph Neural Networks via Bayesian Estimation [79.64626707978418]
  分散ノード上でのリンクローカル差分プライバシーを用いてグラフニューラルネットワークをトレーニングする。 当社のアプローチでは、グラフトポロジをより悪用するために、グラフのリンクと学位を別々に、プライバシ予算に費やしています。 当社のアプローチは、様々なプライバシー予算の下での精度において、既存の手法よりも優れています。
  論文  参考訳（メタデータ） (2023-09-06T17:53:31Z)
• Graphical House Allocation [18.119269486735245]
  このような問題の鍵となる基準は、うらやましい自由さのような公正な制約を満たすことである。 我々のゴールは、自然公正の目的として、エージェント間の集合的うらやみを最小限にすることである。 同一のバリュエーションが不均一な場合、私たちはこの古典的な問題から脱却する深遠で驚くべき方法をいくつか示します。
  論文  参考訳（メタデータ） (2023-01-03T19:26:15Z)
• Bring Your Own View: Graph Neural Networks for Link Prediction with Personalized Subgraph Selection [57.34881616131377]
  異なるエッジに対して最適なサブグラフを自動,個人的,帰納的に識別するプラグイン・アンド・プレイ・フレームワークとしてパーソナライズされたサブグラフセレクタ(PS2)を導入する。 PS2は二段階最適化問題としてインスタンス化され、効率よく解ける。 GNNLPトレーニングに対する新たなアプローチとして,まずエッジの最適な部分グラフを識別し,次にサンプル部分グラフを用いて推論モデルをトレーニングすることを提案する。
  論文  参考訳（メタデータ） (2022-12-23T17:30:19Z)
• Learning to Elect [7.893831644671976]
  投票システムには、推薦システム、ウェブ検索、製品デザイン、選挙など幅広いアプリケーションがある。 本研究では,セットトランスフォーマーや完全連結グラフネットワーク,DeepSetsといったセットインプットニューラルネットワークアーキテクチャが,理論的にも経験的にも投票ルールの学習に適していることを示す。
  論文  参考訳（メタデータ） (2021-08-05T17:55:46Z)
• GAEA: Graph Augmentation for Equitable Access via Reinforcement Learning [50.90625274621288]
  異なるサブ人口によるリソースへの別のアクセスは、社会および社会技術ネットワークにおける一般的な問題です。 予算制約下でグラフエッジを編集することにより,ネットワークシステムにおける公平性を高めるため,新たな問題クラスであるグラフ拡張・等価アクセス(GAEA)を導入する。
  論文  参考訳（メタデータ） (2020-12-07T18:29:32Z)
• Forecasting Election Polls with Spin Systems [0.0]
  政治予測の問題は、古典的スピンシステムの基底状態構成を見つけるためにマッピングできることが示される。 また,本手法は傾向検出アルゴリズムとして理解することができ,特に感情分析や偽ニュースの同定に有用である。
  論文  参考訳（メタデータ） (2020-07-09T21:10:54Z)
• Differential Privacy of Hierarchical Census Data: An Optimization Approach [53.29035917495491]
  国勢調査局(Census Bureaus)は、個人に関する機密情報を明らかにすることなく、大人口に関する社会経済的データをまとめて公開することに興味を持っている。 最近の出来事では、これらの組織が直面しているプライバシー上の課題がいくつか特定されている。 本稿では,階層的な個人数を解放する新たな差分プライバシ機構を提案する。
  論文  参考訳（メタデータ） (2020-06-28T18:19:55Z)

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

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