参与式预算（PB）最近由于其在社会选择环境中的广泛适用性而引起了很多关注。在本文中，我们认为不可分割的PB涉及将可用的，有限的预算分配给一组不可分割的项目，每个项目都根据代理商而不是项目的偏好而有一定的成本。我们在本文中解决的具体，重要的研究差距是提出针对排名较弱（即弱的顺序偏好）的不可分割的PB规则类别，并研究其关键算法和公理问题。我们提出了两类规则具有不同意义和动力的规则。第一个是分层的批准规则，可以通过将其仔细地转化为批准票来研究弱排名。第二个是基于需求的规则，可以捕获公平性问题。根据分层的批准规则，我们研究了两个自然的规则家庭：贪婪的结局规则和价值价值的规则。该纸有两个部分。在第一部分中，我们研究了拟议规则的算法和复杂性问题。在第二部分中，我们对这些规则进行了详细的公理分析，为此，我们在文献中检查和概括了公理，并引入了新的公理，促销性。该论文有助于强调这些规则的实际吸引力，计算复杂性和公理合规性之间的权衡。

我们在单峰偏好下研究社会选择环境中的公平性。在先前的作品中，已经对单峰领域中社会选择规则的构建和表征进行了广泛的研究。实际上，在单峰域中，众所周知，一致和防止策略的确定性规则必须是Min-Max规则，并且那些满足匿名的规则必须是中位数规则。此外，满足这些属性的随机社会选择规则已被证明是各自确定性规则的凸组合。我们通过在社会选择中包括公平考虑因素来非凡地增加了这一结果。我们的研究直接解决了代理人群体的公平性。为了研究群体对象，我们根据性别，种族和位置等自然属性考虑了代理商的现有分区分为逻辑群体。为了捕捉每个小组的公平性，我们介绍了小组匿名的概念。为了捕捉整个群体的公平性，我们提出了一个薄弱的观念以及公平的强烈概念。拟议的公平概念事实证明是对现有的个人财产概念的自然概括，此外，与现有的团体财产概念不同，对严格的顺序偏好提供了非平凡的结果。我们提供了满足群体对象的随机社会选择规则的两个单独的特征：（i）直接表征（ii）极端表征（作为公平确定性社会选择规则的凸组合）。我们还探索了没有群体并提供实现个人财产的规则的特殊情况。

许多重要的集体决策问题可以被视为离散优化问题的多档版本。例如，参与式预算是背包问题的集体版本;其他示例包括集体调度和集体跨越树。对于每个问题，而不是开发特定模型，而不是开发特定模型，以及特定的算法技术，我们建议在统治与加权问题的统治聚合框架中表示和解决它们。我们基于将设定评分功能与运营商耦合，提供了集体离散优化（CDO）规则的模块化定义，我们展示了它们如何概括为特定CDO问题开发的几个现有程序。我们还基于整数线性编程（ILP）的实现，并在集体跨越树的问题上测试。

Gibbard-Satterthwaite定理表明，没有一致和非独裁的投票规则是战略的。我们重新审视投票规​​则，并考虑较弱的战略防护概念，不明显的可操纵性是由特罗桑和莫里尔提出的（2020年）提出的。我们确定了满足此概念的几种投票规则。我们还表明，包括K批准的若干投票规则未能满足此属性。我们在其特征在于，表征明显可操纵的条件。我们的见解之一是，当与选民数量相比，某些规则显然是可操纵的。与Gibbard-Satterthwaite定理相比，我们检查的许多规则并不明显可操纵。这反映了对概念的相对容易的可靠性以及与不明显的可操纵性的零信息假设相反，而不是完美的策略预防。我们还提出了计算明显的操纵和实验报告的算法结果。

我们研究了多翼投票的{pac}可学习性，重点是基于批准的委员会评分（ABC）规则。这些是对批准选票的个人资料的投票规则，每个选民都批准了一些候选人。根据ABCS规则，$ K $候选人的每个委员会都从每个选民那里收集一个分数，这取决于选民投票的规模以及与委员会的交汇处的规模。然后，最高得分的委员会是获胜的委员会。我们的目标是使用有关少数采样配置文件的获胜委员会的信息来学习目标规则（即，学习相应的评分功能）。尽管与单打选举相比，尽管存在指数级的结果，但我们表明样本复杂性仍然很低：多项式数量的样本具有足够的信息来以高度的置信度和准确性来学习目标规则。不幸的是，即使需要解决这些样品学习的简单任务也很难。我们证明，确定是否存在某些ABC规则，使给定的委员会在给定的个人资料中获胜是一个计算问题上的问题。我们的结果扩展到了顺序Thiele规则的类别，由于其简单性，该规则最近受到了关注。

我们介绍了一个多功能代理商的投票模型。这种型号概述了液体民主的两个方面：首先，代理商的代表团可以使用多个其他代理商的投票来确定自己的投票 - 例如，代理商的投票可能对应于可值得信赖的代理人票数的大多数结果;其次，代理商可以在多个代表团上提交排名，以便在他们的首选代表团参与周期时可以使用备份代表团。本文的主要焦点是解开程序的研究，使从代理商处收到的代表团投票转变为直接投票的概况，从中可以通过使用标准投票规则来确定获胜的替代方案。我们提出并研究了六个这样的解开程序，两个基于优化和四种使用贪婪的方法。我们研究了算法和公理性质，以及我们解开程序的相关计算复杂性问题，以针对药剂可以提交的选票类型的不同限制。

我们专注于简单，一维的集体决策问题（通常被称为设施位置问题），并探索战略防护和比例公平的问题。我们为满足战略防护和不同程度的比例公平程度的机制提出了几种特征结果。我们还将其中一个机制描述为满足自然公平性和单调性性质的任何机制的独特均衡结果。最后，我们确定了战略和按比例公平机制，提供了满足相应公平公理的所有机制中的最佳福利最佳逼近。

我们考虑将每个代理分配一个项目时改革无嫉妒的匹配的问题。给定无嫉妒的匹配，我们考虑一个操作，将代理商与代理人首选的未分配项目交换，从而导致另一种无嫉妒的匹配。我们尽可能地重复此操作。我们证明，由此产生的无嫉妒匹配是唯一确定的，可以在选择初始嫉妒的匹配下进行选择，并且可以在多项式时间中找到。我们称之为由此产生的匹配，是一个不正确的嫉妒的匹配，然后我们研究了最短的序列，以从最初的无嫉妒匹配中获得无嫉妒的嫉妒匹配。我们证明，即使每个代理最多接受四个项目，最短的序列在计算上也很难获得，并且每个项目最多都被三个代理所接受。另一方面，当每个代理最多接受三个项目或最多两个代理接受每个项目时，我们给出多项式时间算法。还讨论了不可Ximibibibibibibility和固定参数（IN）的障碍性。

For centuries, it has been widely believed that the influence of a small coalition of voters is negligible in a large election. Consequently, there is a large body of literature on characterizing the asymptotic likelihood for an election to be influenced, especially by the manipulation of a single voter, establishing an $O(\frac{1}{\sqrt n})$ upper bound and an $\Omega(\frac{1}{n^{67}})$ lower bound for many commonly studied voting rules under the i.i.d.~uniform distribution, known as Impartial Culture (IC) in social choice, where $n$ is the number is voters. In this paper, we extend previous studies in three aspects: (1) we consider a more general and realistic semi-random model, where a distribution adversary chooses a worst-case distribution and then a data adversary modifies up to $\psi$ portion of the data, (2) we consider many coalitional influence problems, including coalitional manipulation, margin of victory, and various vote controls and bribery, and (3) we consider arbitrary and variable coalition size $B$. Our main theorem provides asymptotically tight bounds on the semi-random likelihood of the existence of a size-$B$ coalition that can successfully influence the election under a wide range of voting rules. Applications of the main theorem and its proof techniques resolve long-standing open questions about the likelihood of coalitional manipulability under IC, by showing that the likelihood is $\Theta\left(\min\left\{\frac{B}{\sqrt n}, 1\right\}\right)$ for many commonly studied voting rules. The main technical contribution is a characterization of the semi-random likelihood for a Poisson multinomial variable (PMV) to be unstable, which we believe to be a general and useful technique with independent interest.

Applications such as employees sharing office spaces over a workweek can be modeled as problems where agents are matched to resources over multiple rounds. Agents' requirements limit the set of compatible resources and the rounds in which they want to be matched. Viewing such an application as a multi-round matching problem on a bipartite compatibility graph between agents and resources, we show that a solution (i.e., a set of matchings, with one matching per round) can be found efficiently if one exists. To cope with situations where a solution does not exist, we consider two extensions. In the first extension, a benefit function is defined for each agent and the objective is to find a multi-round matching to maximize the total benefit. For a general class of benefit functions satisfying certain properties (including diminishing returns), we show that this multi-round matching problem is efficiently solvable. This class includes utilitarian and Rawlsian welfare functions. For another benefit function, we show that the maximization problem is NP-hard. In the second extension, the objective is to generate advice to each agent (i.e., a subset of requirements to be relaxed) subject to a budget constraint so that the agent can be matched. We show that this budget-constrained advice generation problem is NP-hard. For this problem, we develop an integer linear programming formulation as well as a heuristic based on local search. We experimentally evaluate our algorithms on synthetic networks and apply them to two real-world situations: shared office spaces and matching courses to classrooms.

为了关注稳定的室友（SR）实例，我们为进行稳定匹配问题的实验的工具箱做出了贡献。我们引入了一个多项式时间可计算的伪计，以测量SR实例的相似性，分析其属性并使用它来创建SR实例的地图。该地图可视化460个合成SR实例（每个统计培养物之一中的一个采样），如下所示：每个实例都是平面中的一个点，如果相应的SR实例彼此相似，则在地图上有两个点接近。随后，我们进行了几个模范实验，并在地图上描述了它们的结果，说明了地图作为非聚集可视化工具的有用性，生成的数据集的多样性以及使用从不同统计文化中采样的实例。最后，为了证明我们的框架也可以用于偏爱的其他匹配问题，我们创建和分析了稳定的婚姻实例地图。

许多情况下，具有限制代理商竞争资源的代理商可以作为两分图上的最大匹配问题施放。我们的重点是资源分配问题，在这些问题上，代理可能会限制与某些资源不兼容的限制。我们假设一个原理可以随机选择最大匹配，以便每个代理都具有一定概率的资源。代理商希望通过在一定范围内修改限制来提高他们的匹配机会。原则的目标是建议一个不满意的代理商放松其限制，以便放松的总成本在预算范围内（代理商选择），并最大程度地提高了分配资源的可能性。我们为这种预算受限的最大化问题的某些变体建立硬度结果，并为其他变体提供算法结果。我们通过实验评估合成数据集以及两个新颖的现实数据集：度假活动数据集和一个教室数据集的方法。

该度量扭曲框架认为，n个选民和M候选人共同嵌入到公制空间中，因此选民对候选人的距离更高。投票规则的目的是仅鉴于排名，而不是实际距离，挑选了与选民总距离最小距离的候选人。结果，在最坏的情况下，每个确定性规则都选择了一个候选人，其总距离至少比最佳候选者大三倍，即至少有失真。最近的突破结果表明，达到3个边界可能但是，证明是非构造性的，投票规则本身是一个复杂的详尽搜索。我们的主要结果是一个非常简单的投票规则，称为多数否决权，它实现了相同的最佳失真为3。每个候选人的分数均以等于他的第一名选票数量的分数开始。然后，这些分数通过N回能的否决过程逐渐降低，在该过程中，当候选人得分达到零时，候选人会退出。一个接一个地，选民在常设候选人中降低了他们最不可能的选择，最后一位常设候选人赢得了胜利。我们给出一个单段证明，该投票规则实现了失真3.该规则也非常实用，它仅对每个选民进行两个疑问，因此它的沟通开销较低。我们还通过以下方式将多元化否决权否决为一类随机投票规则：复数否决仅针对k <n回合；然后，选择候选人的概率与他的剩余分数成正比。该一般规则在随机独裁统治（对于K = 0）和多数否决（对于K = N-1）之间，而K控制输出的方差。我们表明，对于所有k，该规则最多都会失真3。

$ k $ -means和$ k $ -median集群是强大的无监督机器学习技术。但是，由于对所有功能的复杂依赖性，解释生成的群集分配是挑战性的。 Moshkovitz，Dasgupta，Rashtchian和Frost [ICML 2020]提出了一个优雅的可解释$ K $ -means和$ K $ -Median聚类型号。在此模型中，具有$ k $叶子的决策树提供了集群中的数据的直接表征。我们研究了关于可解释的聚类的两个自然算法问题。 （1）对于给定的群集，如何通过使用$ k $叶的决策树找到“最佳解释”？ （2）对于一套给定的点，如何找到一个以美元的决策树，最小化$ k $ -means / median目标的可解释的聚类？要解决第一个问题，我们介绍了一个新的可解释群集模型。我们的型号受到强大统计数据的异常值概念的启发，是以下情况。我们正在寻求少数积分（异常值），其删除使现有的聚类良好可解释。为了解决第二个问题，我们开始研究Moshkovitz等人的模型。从多元复杂性的角度来看。我们严格的算法分析揭示了参数的影响，如数据的输入大小，尺寸，异常值的数量，簇数，近似比，呈现可解释的聚类的计算复杂度。

参与式预算（PB）是选民决定如何分配共同预算的过程;最常见的是普通人所做的 - 特别是一些市政府的居民 - 决定市政预算的一小部分。从社交选择的角度来看，PB的现有研究几乎专注于设计了满足研究界认为“可望”的某些公理性质的计算上有效的聚集方法。我们的工作通过用户学习（n = 215）补充了这一研究，涉及若干实验，旨在识别在简单的PB设置中认为是公平或可取的潜在选民（即非专家）。我们的研究结果表明，一些现代PB聚合技术与用户的期望大大不同，而其他更多的标准方法，则提供更多的对齐结果。我们还确定了非专家考虑的一些可能的差异\说{可取的}以及如何在PB背景下认为“公平”的概念。我们共同采取，我们的结果可用于帮助研究界确定适当的PB聚集方法以便在实践中使用。

当代理具有矩阵排名估值时，我们研究不可分割的商品的公平分配。我们的主要贡献是一种基于口语洋基交换程序的简单算法，该程序计算出可证明公平有效的洛伦兹（Lorenz）主导分配。尽管存在多项式时间算法来计算此类分配，但我们提出的方法以两种方式对它们进行了改进。（a）我们的方法易于理解，并且不使用复杂的Matroid优化算法作为子例程。（b）我们的方法是可扩展的；事实证明，计算洛伦兹主导分配的所有已知算法要快。这两个属性是在任何真正的公平分配设置中采用算法的关键。我们的贡献使我们更接近这个目标。

公平性是在算法决策中的重要考虑因素。当具有较高优异的代理人获得比具有较低优点的试剂更差的代理人时，发生不公平。我们的中心点是，不公平的主要原因是不确定性。制定决策的主体或算法永远无法访问代理的真实优点，而是使用仅限于不完全预测优点的代理功能（例如，GPA，星形评级，推荐信）。这些都没有完全捕捉代理人的优点;然而，现有的方法主要基于观察到的特征和结果直接定义公平概念。我们的主要观点是明确地承认和模拟不确定性更为原则。观察到的特征的作用是产生代理商的优点的后部分布。我们使用这个观点来定义排名中近似公平的概念。我们称之为algorithm $ \ phi $ -fair（对于$ \ phi \ in [0,1] $）如果它具有以下所有代理商$ x $和所有$ k $：如果代理商$ x $最高$ k $代理以概率至少为$ \ rho $（根据后部优点分配），那么该算法将代理商在其排名中以概率排名，至少$ \ phi \ rho $。我们展示了如何计算最佳地互惠对校长进行近似公平性的排名。除了理论表征外，我们还提出了对模拟研究中的方法的潜在影响的实证分析。对于真实世界的验证，我们在纸质建议系统的背景下应用了这种方法，我们在KDD 2020会议上建立和界定。

匹配市场通常以多级和分散的方式组织。此外，现实世界匹配市场的参与者通常具有不确定的偏好。本文基于非参数统计方法和变分分析，开发了在这种环境中学习最佳策略的框架。我们提出了一种高效的算法，建立在“较低不确定性绑定”和“校准分散匹配”的概念上，以最大限度地提高参与者的预期收益。我们表明存在福利与公平性权衡，其特征在于接受的不确定性水平。参与者将战略性地提起低度不确定性水平，以减少竞争并增加预期的收益。与单阶段匹配相比，我们证明参与者可以更好地使用多级匹配。我们通过模拟和使用大学录取的真实数据的实验展示了理论预测的方面。

大多数算法研究到目前为止，多智能经纪信息设计的研究专注于没有代理商外部性的限制情况;一些例外调查了真正的战略游戏，如零和游戏和二价格拍卖，但只关注最佳的公共信令。本文启动了\ emph {public}和\ emph {privy}信号传导的算法信息设计，其中of基本的外部性，即单例拥塞游戏，在今天的数字经济中的应用范围广，机器调度，路由，对于公共和私人信令等，我们表明，当资源数量是常数时，可以有效地计算最佳信息设计。为了我们的知识，这是一系列高效的\ EMPH {精确}算法，用于在简明地代表的许多玩家游戏中的信息设计。我们的结果符合新颖的技术，如开发某些“减少形式”，以便在公共信令中紧凑地表征均衡或代表私人信令中的球员边际信仰。当有许多资源时，我们会显示计算难扰性结果。为了克服多个均衡问题，这里我们介绍了均衡 - \ EMPH {忽视}硬度的新概念，这条规定了计算良好信令方案的任何可能性，而不管均衡选择规则如何。

In the Priority $k$-Center problem, the input consists of a metric space $(X,d)$, an integer $k$, and for each point $v \in X$ a priority radius $r(v)$. The goal is to choose $k$-centers $S \subseteq X$ to minimize $\max_{v \in X} \frac{1}{r(v)} d(v,S)$. If all $r(v)$'s are uniform, one obtains the $k$-Center problem. Plesn\'ik [Plesn\'ik, Disc. Appl. Math. 1987] introduced the Priority $k$-Center problem and gave a $2$-approximation algorithm matching the best possible algorithm for $k$-Center. We show how the problem is related to two different notions of fair clustering [Harris et al., NeurIPS 2018; Jung et al., FORC 2020]. Motivated by these developments we revisit the problem and, in our main technical contribution, develop a framework that yields constant factor approximation algorithms for Priority $k$-Center with outliers. Our framework extends to generalizations of Priority $k$-Center to matroid and knapsack constraints, and as a corollary, also yields algorithms with fairness guarantees in the lottery model of Harris et al [Harris et al, JMLR 2019].