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

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

在我们生活在深厚的互连世界中，我们周围的各个信息链接域。由于图形数据库包含了数据之间有效的关系，并允许处理和查询这些连接，因此它们正迅速成为支持广泛域和应用程序的流行平台。与关系情况一样，可以预期数据保留了一组完整性约束，这些限制定义了它代表的世界的语义结构。当数据库不满足其完整性约束时，一种可能的方法是搜索确实满足约束（也称为维修）的“类似”数据库。在这项工作中，我们使用基于一组Reg-GXPath表达式作为完整性约束的一致性概念来研究图形数据库的计算子集和超集修复的问题。我们表明，对于Reg-GxPath的积极片段，这些问题承认了多项式时间算法，而语言的全部表达力使它们棘手。

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

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

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

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

大多数-AT是确定联合正常形式（CNF）中输入$ N $的最低价公式的问题至少为2 ^ {n-1} $令人满意的作业。在对概率规划和推论复杂性的各种AI社区中，广泛研究了多数饱和问题。虽然大多数饱满为期40多年来，但自然变体的复杂性保持开放：大多数 - $ k $ SAT，其中输入CNF公式仅限于最多$ k $的子句宽度。我们证明，每辆$ k $，大多数 - $ k $ sat是在p的。事实上，对于任何正整数$ k $和ratic $ \ rho \ in（0,1）$ in（0,1）$与有界分比者，我们给出了算法这可以确定给定的$ k $ -cnf是否至少有$ \ rho \ cdot 2 ^ n $令人满意的分配，在确定性线性时间（而先前的最着名的算法在指数时间中运行）。我们的算法对计算复杂性和推理的复杂性具有有趣的积极影响，显着降低了相关问题的已知复杂性，例如E-Maj-$ K $ Sat和Maj-Maj- $ K $ Sat。在我们的方法中，通过提取在$ k $ -cnf的相应设置系统中发现的向日葵，可以通过提取向日葵来解决阈值计数问题的有效方法。我们还表明，大多数 - $ k $ sat的易腐烂性有些脆弱。对于密切相关的gtmajority-sat问题（我们询问给定公式是否超过2 ^ {n-1} $满足分配），这已知是pp-cleanting的，我们表明gtmajority-$ k $ sat在p for $ k \ le 3 $，但为$ k \ geq 4 $完成np-cleante。这些结果是违反直觉的，因为这些问题的“自然”分类将是PP完整性，因为GTMAJority的复杂性存在显着差异 - $ k $ SAT和MOSTION- $ K $ SAT为所有$ k \ ge 4 $。

最近关于Littmann的报告[Comment。 ACM'21]概述了学术同行评论中勾结环的存在和致命影响。我们介绍和分析了问题周期的审查，该审查旨在找到审查任务，没有以下勾结戒指：一系列审稿人员每次审查下一个审阅者在序列中撰写的文件（与最后审查员审查一篇论文第一个），从而创建一个审查周期，每个审界者都提供了有利的评论。因此，该循环中的所有文件都有很大的接受机会与各自的科学优点无关。我们观察到，使用标准线性编程方法计算的审核分配通常允许许多短审查周期。在消极方面，我们表明，在各种限制性案件中，无期临时审查是NP - 困难（即，当每个作者有资格审查所有论文时，人们想要防止作者互相审查或他们自己的论文或每篇作者何时审查只有一篇论文，只有有资格审查几篇论文）。在积极的方面，除了其他方面，我们表明，在一些现实的设置中，没有任何审查周期的分配总是存在。这一结果也引发了用于计算（加权）自由审查任务的有效启发式，我们在实践中表现出优良的品质。

最近已经提出了几个查询和分数来解释对ML模型的个人预测。鉴于ML型号的灵活，可靠和易于应用的可解释性方法，我们预见了需要开发声明语言以自然地指定不同的解释性查询。我们以原则的方式通过源于逻辑，称为箔，允许表达许多简单但重要的解释性查询，并且可以作为更具表现力解释性语言的核心来实现这一语言。我们研究箔片查询的两类ML模型的计算复杂性经常被视为容易解释：决策树和OBDD。由于ML模型的可能输入的数量是尺寸的指数，因此箔评估问题的易易性是精细的，但是可以通过限制模型的结构或正在评估的箔片段来实现。我们还以高级声明语言包装的箔片的原型实施，并执行实验，表明可以在实践中使用这种语言。

我们回答以下问题，哪些结合性查询以多种方式上的许多正和负面示例以及如何有效地构建此类示例的特征。结果，我们为一类连接的查询获得了一种新的有效的精确学习算法。我们的贡献的核心是两种新的多项式时间算法，用于在有限结构的同态晶格中构建前沿。我们还讨论了模式映射和描述逻辑概念的独特特征性和可学习性的影响。

Posibilistic Logic是处理不确定和部分不一致信息的最扩展方法。关于正常形式，可能性推理的进步大多专注于字幕形式。然而，现实世界问题的编码通常导致非人（NC）公式和NC-To-Clausal翻译，产生严重的缺点，严重限制了字符串推理的实际表现。因此，通过计算其原始NC形式的公式，我们提出了几种贡献，表明可能在可能的非字词推理中也是可能的显着进展。 {\ em首先，我们定义了{\ em possibilistic over非词素知识库，}或$ \ mathcal {\ overline {h}} _ \ sigma $的类别，其中包括类：可能主义的喇叭和命题角 - NC。 $ \ mathcal {\ overline {h}} _ \ sigma $被显示为标准喇叭类的一种NC类似的。 {\ em hightly}，我们定义{\ em possibilistic非字词单元分辨率，}或$ \ mathcal {u} _ \ sigma $，并证明$ \ mathcal {u} _ \ sigma $正确计算不一致程度$ \ mathcal {\ overline {h}} _ \ sigma $成员。 $ \ Mathcal {Ur} _ \ \ Sigma $之前未提出，并以人为人的方式制定，这会让其理解，正式证明和未来延伸到非人类决议。 {\ em第三}，我们证明计算$ \ mathcal {\ overline {h}} _ \ sigma $成员的不一致程度是多项式时间。虽然可能存在于可能存在的逻辑中的贸易课程，但所有这些都是字符串，因此，$ \ mathcal {\ overline {h}} _ \ sigma $ of to是可能的主要推理中的第一个特征的多项式非锁友类。

合理验证是指检查系统中的代理在系统中选择形成游戏理论平衡的策略的假设，该问题是检查哪种时间逻辑属性。可以将合理验证理解为模型检查多种系统系统的对应物，但是对于某些时间逻辑规范语言（例如CTL）和具有LTL规格的多项式空间，可以在多项式时间内完成经典模型检查，但合理验证却更加困难：虽然很难：合理验证的关键决策问题是2与LTL规格的Exptime-Complete，即使使用显式状态系统表示。在这种背景下，我们在本文中的贡献是三倍。首先，我们表明，可以通过将规格限制为GR（1），这可以大大降低合理验证的复杂性，GR（1）是LTL的片段，可以代表反应性系统的宽泛且实际上有用的响应属性类别。特别是，我们表明，对于许多相关设置，可以在多项式空间甚至多项式时间内完成合理验证。其次，在考虑均值付费公用事业功能给出的玩家的目标时，我们为合理验证提供了改进的复杂性结果；可以说是并发系统中最广泛使用的定量目标方法。最后，我们考虑了满足社会福利约束的计算结果的问题。为此，我们考虑了实用和平等主义的社会福利，并表明计算此类结果是Pspace-Complete或NP完整的。

Models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations, the sudden and widespread adoption of various strategies in game-theoretic settings, and the effects of "word of mouth" in the promotion of new products. Motivated by the design of viral marketing strategies, Domingos and Richardson posed a fundamental algorithmic problem for such social network processes: if we can try to convince a subset of individuals to adopt a new product or innovation, and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target?We consider this problem in several of the most widely studied models in social network analysis. The optimization problem of selecting the most influential nodes is NP-hard here. The two conference papers upon which this article is based (KDD 2003 and ICALP 2005) provide the first provable approximation guarantees for efficient algorithms. Using an The present article is an expanded version of two conference papers [51,52], which appeared in KDD 2003 and ICALP 2005, respectively.

本文研究了人工神经网络（NNS）与整流线性单元的表现力。为了将它们作为实际计算的模型，我们介绍了最大仿射算术计划的概念，并显示了它们与NNS之间的等效性有关自然复杂度措施。然后我们使用此结果表明，使用多项式NNS可以解决两个基本组合优化问题，这相当于非常特殊的强多项式时间算法。首先，我们显示，对于带有N $节点的任何无向图形，有一个NN大小$ \ Mathcal {O}（n ^ 3）$，它将边缘权重用为输入，计算最小生成树的值图表。其次，我们显示，对于任何带有$ N $节点和$ M $弧的任何定向图，都有一个尺寸$ \ mathcal {o}（m ^ 2n ^ 2）$，它将电弧容量作为输入和计算最大流量。这些结果尤其尤其暗示，相应的参数优化问题的解决方案可以在多项式空间中编码所有边缘权重或电弧容量的方法，并在多项式时间中进行评估，并且由NN提供这种编码。

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.

我们根据描述逻辑ALC和ALCI介绍并研究了本体论介导的查询的几个近似概念。我们的近似值有两种：我们可以（1）用一种以易访问的本体语言为例，例如ELI或某些TGD，以及（2）用可拖动类的一个替换数据库，例如其treewidth的数据库，由常数界定。我们确定所得近似值的计算复杂性和相对完整性。（几乎）所有这些都将数据复杂性从Conp-Complete降低到Ptime，在某些情况下甚至是固定参数可拖动和线性时间。虽然种类（1）的近似也降低了综合复杂性，但这种近似（2）往往并非如此。在某些情况下，联合复杂性甚至会增加。

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

推荐系统是帮助用户以个性化方式找到信息过载的兴趣项目，使用关于各用户的需求和偏好的知识。在会话推荐方法中，这些需求和偏好由系统中的交互式多匝对话框中的。文献中的一种常见方法来驱动这些对话框是逐步向用户逐步询问他们关于期望和不期望的项目特征或关于单个项目的偏好。在这种情况下，在该上下文中的核心研究目标是效率，在找到令人满意的项目之前对所需交互的数量进行评估。这通常是通过对向用户询问的最佳下一个问题的推断来实现。如今，对对话效率的研究几乎完全是经验的，旨在说明，例如，选择问题的一个策略优于给定的应用程序中的另一个策略。通过这项工作，我们将实证研究补充了理论，域名的对话建议的独立模型。该模型旨在涵盖一系列应用方案，使我们能够以正式的方式调查会话方法的效率，特别是关于设计最佳相互作用策略的计算复杂性。通过如此理论分析，我们表明，找到高效的会话策略是NP - 硬，并且在PSPace中，但对于特定类型的目录，上限降低到Polylogspace。从实际的角度来看，该结果意味着目录特征可以强烈影响个人对话策略的效率，因此在设计新策略时应考虑。从真实世界派生的数据集的初步实证分析与我们的研究结果对齐。

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