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.
