广告推广管理的近似算法

Mar, 2010

Approximation Algorithms for Campaign Management

Edith Elkind, Piotr Faliszewski

TL;DR研究选举活动中的投票管理场景，外部方可以购买选票，目的是使其首选候选人获胜，同时尽可能少地支付，提出了一种 2 - 逼近算法，适用于大多数评分规则并且适用于加权选民，可以应用于商业环境的竞选活动管理。同时，提出了对两种 Condorcet 一致规则（即 Copeland 准则和 maximin）的求近似算法。

Abstract

We study electoral campaign management scenarios in which an external party can buy votes, i.e., pay the voters to promote its preferred candidate in their preference rankings. The external party's goal is to make its preferred candidate a winner while paying as little as possible. We

electoral campaign voter bribery scoring rules weighted voters campaign management

发现论文，激发创造

贿赂作为候选人成功的衡量方式：基于批准的多胜者规则的复杂性结果

本文研究多个候选人选举中的贿赂问题，分析了各种基于赞成票的多赢家规则的时间复杂度、近似度和可解性，重点研究了参数化的时间复杂度

Apr, 2021

实现完全比例代表制：近似可行性结果

研究 Monroe 规则和 Chamberlin-Courant 规则下基于总 (不) 满意度的多赢家决策的复杂性，提供了计算总满意度和总不满意度的适应性和不适应性算法，并通过实验评估验证了这些算法的可用性和优越性。

Dec, 2013

加权选举控制

本文研究加权选举结果的控制问题，通过添加和删除选民探讨了研究有分值规则的加权选举结果控制的复杂度，得到了针对许多 NP 完全情况的多项式时间算法和近似算法。

May, 2013

选举胜者预测的样本复杂度

统计学选举学家研究了在通常非常困难获取全部选民偏好的情况下，最常用的赢家预测算法是将选举在少量随机选票中运行，并将获胜者作为预测结果的性能。研究了 $(\epsilon, \delta)$-winner determination 问题，并给出了多种常见投票规则下解决该问题所需样本数量的有趣下界和上界。

Feb, 2015

控制 k - 表决选举的复杂性

研究计算社会选择理论中，针对代理人之间的不良行为（如控制、操纵和贿赂）在竞选系统中的复杂性，并以无限多个候选人的无限得分协议为例，将计算复杂度的结果加以泛化，并展示了操纵竞选系统和图形理论问题之间的惊人联系。

May, 2010

选举中的克隆问题：寻找可能的赢家

本研究考虑通过克隆候选人来操纵选举结果，研究了克隆投票模型下不同投票规则、偏好以及成本对操纵结果的影响，研究了最小成本克隆操纵问题以及与控制通过增加候选人和可能的（共同）获胜者问题的关系。

Jan, 2014

在线批准委员会选举

该研究考虑在候选人随时出现的情况下，通过投票选择或拒绝候选人，使用最大期望分数方法来计算委员会并评估其在代表选民方面的比例。

Feb, 2022

多赢家规则的比例程度

本文研究了基于批准的多胜选举，旨在选择代表选民偏好的委员会，作者考察了不同的选举规则并探讨了它们的比例代表性，最终给出了一种关于选择代表性委员会与效用效率平衡的权衡方案。

Oct, 2018

贿选不确定性问题的选举：难度和近似算法

介绍一个考虑选民不确定性的新型投票贿赂问题 BVU，没有多项式 $O (1)$- 逼近算法，但有一种返回具有可接受误差的近似算法。

Nov, 2018

公民选举：代表性候选人更有效

本文考虑选举中的社会福利和代表性候选人对社会福利的影响，采用度量优先模型来探索社会最佳的程度和度量空间的复杂性对其影响，得到了多个近似比例的下限和上限。

May, 2017