• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >The complexity of probabilistic lobbying
【24h】

The complexity of probabilistic lobbying

机译：概率游说的复杂性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We propose models for lobbying in a probabilistic environment, in which an actor (called "The Lobby") seeks to influence voters' preferences of voting for or against multiple issues when the voters' preferences are represented in terms of probabilities. In particular, we provide two evaluation criteria and two bribery methods to formally describe these models, and we consider the resulting forms of lobbying with and without issue weighting. We provide a formal analysis for these problems of lobbying, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria and on various natural parameterizations. Specifically, we show that some of these problems can be solved in polynomial time, some are NP-complete but fixed-parameter tractable, and some are W[2]-complete. Finally, we provide approximability and inapproximability results for these problems and several variants.
机译：我们提出了一种在概率环境中进行游说的模型，在这种模型中，当以概率表示投票者的偏好时，演员（称为“游说者”）试图影响投票者的投票偏好，以支持或反对多个问题。特别是，我们提供了两种评估标准和两种贿赂方法来正式描述这些模型，并且我们考虑了在有问题权重和没有问题权重的情况下产生的游说形式。我们对这些游说问题进行了形式分析，并根据给定的贿赂/评估标准和各种自然参数设置确定了它们的经典和参数化复杂性。具体来说，我们证明了其中的一些问题可以在多项式时间内解决，一些问题是NP完全的，但固定参数易于处理，有些问题是W [2]的。最后，我们提供了这些问题和几种变体的近似和不近似结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号