Voting, Assignment and Matching Under Dichotomous Preferences

当偏好允许不可分割的决策、对象或伴侣之间的无差异时，选择公共决策（投票）、为对象分配代理人或配对一组男性和女性的机制就不能满足理想社会选择的所有基本要求。作为全面处理概率投票、分配和匹配中的完整和传递偏好的第一步，本项目探索了二分类偏好的简单而基本的领域，即可行分配最多属于两个无关的类别，好和坏，可接受或不可接受，效用为零或效用为一。二分类领域的一个非常吸引人的特点是，与严格的偏好领域不同，效率、激励兼容和公平这三个要求是兼容的。批准投票（AV）是二分类领域中最自然的投票机制。有一组有限的结果——公共决策——必须从中选择一个。在AV模式下，每个主体报告一个他或她认可的结果子集，得到最多选民认可的结果当选；平局是通过抽签来解决的，所有中奖者都有相同的概率。本项目使用批准投票的公理化特征来确定存在公平，有效和群体策略证明（即不受任何联盟在所有配置文件中的错误报告的影响）投票方法的条件。公共设施的分时分配是一个丰富的例子来源，其中二分偏好是合理的。该项目考察了平衡功利主义的数学模型，即选择最大数量用户所需的东西，和平等主义的模型，即保证每个用户的最低满意度。在公平份额要求下，确定了有效且防策略规则的存在性。该项目还解决了更具挑战性的问题，即群体策略证明是否在有效和最低限度公平规则的范围内（例如AV不符合这一属性）。项目的第二个和第三个模型分别是分配问题和双边匹配问题。这两个模型在形式上是相似的，大多数公理，一致性，策略证明，公平份额保证，很容易从概率投票模型中改编。一个重要的新事实可以从匹配的数学文献中借用：所有有效的（确定性的）分配（或匹配）都有相同数量的代理接收一个好对象（相同数量的相互接受的对）。因此，所有有效分配（匹配）的统一平均值在所有概率机制中都是有效的。一个合理的推测是，这个解决方案的特点是，像AV一样，一致性，效率和对称处理的代理。其他有趣的高效解决方案也出现了：人们可以随机排序代理，并找到按字典顺序最大化效用的分配；我们可以尽可能地使事前效用相等，也就是最大化他们的纳什产品，或者应用收入相等时的竞争均衡。根据这些规则的公平性和防策略性，系统地分析了这些规则和其他规则。

Mechanisms to select a public decision (voting), or to assign agents to objects, or to match a set of men and women in pairs, can not satisfy all of the basic requirements of desirable social choice when preferences allow indifferences between the indivisible decisions, or objects, or mates. As a first step toward a full treatment of complete and transitive preferences in probabilistic voting, assignment and matching, this project explores the simple yet basic domain of dichotomous preferences, namely those where feasible allocations fall in at most two indifferent classes, good and bad, acceptable or not, utility of zero or utility of one. A very appealing feature of the dichotomous domain is that, unlike the strict preference domain, the three requirements of efficiency, incentive-compatibility and fairness are compatible. Approval Voting (AV) is the most natural voting mechanism in the dichotomous domain. There is a finite set of outcomes - public decisions - among which one must be chosen. Under AV, each agent reports a certain subset of outcomes that he or she approves of and the outcome that is approved by the largest number of voters is elected; ties are resolved by a lottery in which all winners have equal probability. This project uses an axiomatic characterization of approval voting to determine the conditions under which a fair, efficient and group strategyproof (i.e., immune to misreports by any coalition at all profiles) voting method exists. Time-sharing of a public facility is a rich source of examples where dichotomous preferences are plausible. This project examines mathematical models that balance the utilitarian, i.e., choose what is desired by the largest number of users, and the egalitarian, i.e., guarantee a minimal level of satisfaction for every user. Under the fair share requirement, the existence of an efficient and strategyproof rule is determined. The project also addresses the more challenging question of whether or not group strategyproofness is within the reach of efficient and minimally fair rules (for instance AV does not meet this property).The second and third models of the project are respectively the assignment and the bilateral matching problem. Both models are formally similar and most axioms, Consistency, Strategy-proofness, Fair Share Guarantee, are easily adapted from the probabilistic voting model. One important new fact can be borrowed from the mathematical literature on matching: all efficient (deterministic) assignments (or matching) have the same number of agents receiving a good object (the same number of mutually acceptable pairs). Accordingly the uniform average of all efficient assignments (matching) is efficient among all probabilistic mechanisms. A reasonable conjecture is that this solution is characterized, like AV, by Consistency, efficiency and symmetric treatment of agents. Other interesting efficient solutions emerge as well: one can order the agents randomly and find the allocation maximizing lexicographically the utilities in that order; we could equalize as much as possible the (ex ante) utilities, which turns out to be the same thing as maximizing their Nash product, or as applying the old idea of competitive equilibrium with equal incomes. These and other rules are systematically analyzed in the light of their fairness and strategy-proofness properties.