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

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

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

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

随着优化软件的显着改进，几十年前似乎棘手的大规模问题的解决方案现在已成为日常任务。这将更多的现实应用程序纳入了优化器的范围。同时，解决优化问题通常是将解决方案付诸实践时较小的困难之一。一个主要的障碍是，可以将优化软件视为黑匣子，它可能会产生高质量的解决方案，但是当情况发生变化时，可以创建完全不同的解决方案，从而导致对优化解决方案的接受率低。这种可解释性和解释性的问题在其他领域（例如机器学习）引起了极大的关注，但在优化方面却不那么关注。在本文中，我们提出了一个优化框架，以得出本质上具有易于理解的解释性规则的解决方案，在哪些情况下应选择解决方案。我们专注于代表解释性规则的决策树，我们提出了整数编程公式以及一种启发式方法，以确保我们的方法即使在大规模问题上也适用。使用随机和现实世界数据的计算实验表明，固有的可解释性成本可能很小。

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

We deal with a challenging scheduling problem on parallel machines with sequence-dependent setup times and release dates from a real-world application of semiconductor work-shop production. There, jobs can only be processed by dedicated machines, thus few machines can determine the makespan almost regardless of how jobs are scheduled on the remaining ones. This causes problems when machines fail and jobs need to be rescheduled. Instead of optimising only the makespan, we put the individual machine spans in non-ascending order and lexicographically minimise the resulting tuples. This achieves that all machines complete as early as possible and increases the robustness of the schedule. We study the application of Answer-Set Programming (ASP) to solve this problem. While ASP eases modelling, the combination of timing constraints and the considered objective function challenges current solving technology. The former issue is addressed by using an extension of ASP by difference logic. For the latter, we devise different algorithms that use multi-shot solving. To tackle industrial-sized instances, we study different approximations and heuristics. Our experimental results show that ASP is indeed a promising KRR paradigm for this problem and is competitive with state-of-the-art CP and MIP solvers. Under consideration in Theory and Practice of Logic Programming (TPLP).

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

组合优化是运营研究和计算机科学领域的一个公认领域。直到最近，它的方法一直集中在孤立地解决问题实例，而忽略了它们通常源于实践中的相关数据分布。但是，近年来，人们对使用机器学习，尤其是图形神经网络（GNN）的兴趣激增，作为组合任务的关键构件，直接作为求解器或通过增强确切的求解器。GNN的电感偏差有效地编码了组合和关系输入，因为它们对排列和对输入稀疏性的意识的不变性。本文介绍了对这个新兴领域的最新主要进步的概念回顾，旨在优化和机器学习研究人员。

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

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.

我们研究了通过中等数量的成对比较查询引发决策者偏好的问题，以使它们成为特定问题的高质量推荐。我们受到高赌场域中的应用程序的推动，例如选择分配稀缺资源的政策以满足基本需求（例如，用于移植或住房的肾脏，因为那些经历无家可归者），其中需要由（部分）提出引出的偏好。我们在基于偏好的偏好中模拟不确定性，并调查两个设置：a）脱机偏出设置，其中所有查询都是一次，b）在线诱因设置，其中按时间顺序选择查询。我们提出了这些问题的强大优化制剂，这些问题集成了偏好诱导和推荐阶段，其目的是最大化最坏情况的效用或最小化最坏情况的后悔，并研究其复杂性。对于离线案例，在活动偏好诱导与决策信息发现的两个半阶段的稳健优化问题的形式中，我们提供了我们通过列解决的混合二进制线性程序的形式提供了等效的重构。 -Constraint生成。对于在线设置，主动偏好学习采用多级强大优化问题的形式与决策依赖的信息发现，我们提出了一种保守的解决方案方法。合成数据的数值研究表明，我们的方法在最坏情况级别，后悔和效用方面从文献中倾斜最先进的方法。我们展示了我们的方法论如何用于协助无家可归的服务机构选择分配不同类型的稀缺住房资源的政策，以遇到无家可归者。

蒙特卡洛树搜索（MCT）是设计游戏机器人或解决顺序决策问题的强大方法。该方法依赖于平衡探索和开发的智能树搜索。MCT以模拟的形式进行随机抽样，并存储动作的统计数据，以在每个随后的迭代中做出更有教育的选择。然而，该方法已成为组合游戏的最新技术，但是，在更复杂的游戏（例如那些具有较高的分支因素或实时系列的游戏）以及各种实用领域（例如，运输，日程安排或安全性）有效的MCT应用程序通常需要其与问题有关的修改或与其他技术集成。这种特定领域的修改和混合方法是本调查的主要重点。最后一项主要的MCT调查已于2012年发布。自发布以来出现的贡献特别感兴趣。

Monte Carlo Tree Search (MCTS) is a recently proposed search method that combines the precision of tree search with the generality of random sampling. It has received considerable interest due to its spectacular success in the difficult problem of computer Go, but has also proved beneficial in a range of other domains. This paper is a survey of the literature to date, intended to provide a snapshot of the state of the art after the first five years of MCTS research. We outline the core algorithm's derivation, impart some structure on the many variations and enhancements that have been proposed, and summarise the results from the key game and non-game domains to which MCTS methods have been applied. A number of open research questions indicate that the field is ripe for future work.

由于机器学习，统计和科学的应用，多边缘最佳运输（MOT）引起了极大的兴趣。但是，在大多数应用中，MOT的成功受到缺乏有效算法的严重限制。实际上，MOT一般需要在边际K及其支撑大小n的数量中指数时间n。本文开发了一个关于“结构”在poly（n，k）时间中可溶解的一般理论。我们开发了一个统一的算法框架，用于通过表征不同算法所需的“结构”来解决poly（n，k）时间中的MOT，这是根据双重可行性甲骨文的简单变体所需的。该框架有几个好处。首先，它使我们能够证明当前是最流行的MOT算法的Sinkhorn算法比其他算法要在poly（n，k）时间中求解MOT所需的结构更严格。其次，我们的框架使得为给定的MOT问题开发poly（n，k）时间算法变得更加简单。特别是（大约）解决双重可行性Oracle是必要和足够的 - 这更适合标准算法技术。我们通过为三个通用类成本结构类别的poly（n，k）时间算法开发poly（n，k）时间算法来说明这种易用性：（1）图形结构； （2）设定优化结构； （3）低阶和稀疏结构。对于结构（1），我们恢复了Sindhorn具有poly（n，k）运行时的已知结果；此外，我们为计算精确且稀疏的解决方案提供了第一个poly（n，k）时间算法。对于结构（2） - （3），我们给出了第一个poly（n，k）时间算法，甚至用于近似计算。这三个结构一起涵盖了许多MOT的当前应用。

在本文中，我们研究了通过优化的流量路由的路径增加对运输网络的影响。特别是，我们研究了总旅行时间的行为，并考虑了自我利益的路由范式，例如用户平衡（UE）路由以及合作范式，例如经典多商品（MC）网络流量和系统最佳（因此）路由。我们提供了一个正式的框架，用于通过迭代路径添加设计运输网络，引入跨越树和跳跃路径图的概念。使用此形式化，我们证明了运输网络设计的目标函数的多个属性。由于基础路由问题是NP-HARD，因此我们研究了提供近似算法设计保证的属性。首先，尽管Braess的悖论表明，对于在自私路由（UE）下的路径添加（UE）方面，总旅行时间并不是单调的非侵扰，但我们证明，相反，单调性具有合作路由（MC等）。该结果具有重要的含义，即合作社可以充分利用冗余基础设施。其次，我们通过反例证证明，直观的语句``在传输网络中添加路径始终赋予用户更大或平等的好处，而不是将其添加到该网络的超集中'是错误的。换句话说，我们证明，对于所有研究的路由公式，相对于路径添加而言，总旅行时间不是超模型。尽管这种违反直觉结果为算法设计带来了硬度属性，但我们提供了特定的实例，而相反，超模型的属性则具有。我们关于相对于路径增加的总旅行时间的单调性和超模样的研究提供了正式的证明和场景，构成了运输网络设计师的重要见解。

近年来，在平衡（超级）图分配算法的设计和评估中取得了重大进展。我们调查了过去十年的实用算法的趋势，用于平衡（超级）图形分区以及未来的研究方向。我们的工作是对先前有关该主题的调查的更新。特别是，该调查还通过涵盖了超图形分区和流算法来扩展先前的调查，并额外关注并行算法。

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

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.

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