Voting, Assignment and Matching Under Dichotomous Preferences

二分偏好下的投票、分配和匹配

• 批准号: 0112032
• 负责人: Herve Moulin
• 金额: --
• 依托单位: William Marsh Rice University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-01 至 2004-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0112032&HistoricalAwards=false
• 关键词: Voting; Assignment; Matching; Under; Dichotomous

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.

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