The rationing of healthcare resources has emerged as an important issue, which has been discussed by medical experts, policy-makers, and the general public. We consider a rationing problem where medical units are to be allocated to patients. Each unit is reserved for one of several categories, and each category has a priority ranking over the patients. We present a class of allocation rules that respect the priorities, comply with the eligibility requirements, allocate the largest feasible number of units, and do not penalize agents for rising in the priority ranking of a category. The rules characterize all possible allocations that satisfy the first three properties and are polynomial-time computable.

During the COVID-19 pandemic, fair and efficient rationing of healthcare resources has emerged as an important issue that has been discussed by medical experts, policy-makers, and the general public. We consider a healthcare rationing problem where medical units are to be allocated to patients. Each unit is reserved for one of several categories and the patients have different priorities for the categories. We present an allocation rule that respects the priorities, complies with the eligibility requirements, allocates the largest feasible number of units, and does not incentivize agents to hide that they qualify through a category. Moreover, the rule is polynomial-time computable. To the best of our knowledge, it is the first known rule with the aforementioned properties.

We consider a setting in which agents contribute amounts of a divisible resource (such as money or time) to a common pool, which is used to finance projects of public interest. How the collected resources are to be distributed among the projects is decided by a distribution rule that takes as input a set of approved projects for each agent. An important application of this setting is donor coordination, which allows philanthropists to find an efficient and mutually agreeable distribution of their donations. We analyze various distribution rules (including the Nash product rule and the conditional utilitarian rule) in terms of classic as well as new axioms, and propose the first fair distribution rule that satisfies efficiency and monotonicity. Our main result settles a long-standing open question of Bogomolnaia, Moulin, and Stong (2005) by showing that no strategyproof and efficient rule can guarantee that at least one approved project of each agent receives a positive amount of the resource. The proof reasons about 386 preference profiles and was obtained using a computer-aided method involving SAT solvers.

Voting rules allow multiple agents to aggregate their preferences in order to reach joint decisions. A common flaw of some voting rules, known as the no-show paradox, is that agents may obtain a more preferred outcome by abstaining from an election. We study strategic abstention for set-valued voting rules based on Kelly's and Fishburn's preference extensions. Our contribution is twofold. First, we show that, whenever there are at least five alternatives and seven agents, every Pareto-optimal majoritarian voting rule suffers from the no-show paradox with respect to Fishburn's extension. This is achieved by reducing the statement to a finite - yet very large - problem, which is encoded as a formula in propositional logic and then shown to be unsatisfiable by a SAT solver. We also provide a human-readable proof which we extracted from a minimal unsatisfiable core of the formula. Secondly, we prove that every voting rule that satisfies two natural conditions cannot be manipulated by strategic abstention with respect to Kelly's extension and give examples of well-known Pareto-optimal majoritarian voting rules that meet these requirements.

Randomized voting rules are gaining increasing attention in computational and non-computational social choice. A particularly interesting class of such rules are maximal lottery (ML) schemes, which were proposed by Peter Fishburn in 1984 and have been repeatedly recommended for practical use. However, the subtle differences between different ML schemes are often ignored. Two canonical subsets of ML schemes are C1-ML schemes (which only depend on unweighted majority comparisons) and C2-ML schemes (which only depend on weighted majority comparisons). We prove that C2-ML schemes are the only Pareto efficient---but also among the most manipulable---ML schemes. Furthermore, we evaluate the frequency of manipulable preference profiles and the degree of randomization of ML schemes via extensive computer simulations. In general, ML schemes are rarely manipulable and often do not randomize at all, especially when there are only few alternatives. For up to 21 alternatives, the average support size of ML schemes lies below 4 under reasonable assumptions. The average degree of randomization (in terms of Shannon entropy) of C2-ML schemes is significantly lower than that of C1-ML schemes.

Two important requirements when aggregating the preferences of multiple agents are that the outcome should be economically efficient and the aggregation mechanism should not be manipulable. In this article, we provide a computer-aided proof of a sweeping impossibility using these two conditions for randomized aggregation mechanisms. More precisely, we show that every efficient aggregation mechanism can be manipulated for all expected utility representations of the agents’ preferences. This settles an open problem and strengthens several existing theorems, including statements that were shown within the special domain of assignment. Our proof is obtained by formulating the claim as a satisfiability problem over predicates from real-valued arithmetic, which is then checked using a satisfiability modulo theories (SMT) solver. To verify the correctness of the result, a minimal unsatisfiable set of constraints returned by the SMT solver was translated back into a proof in higher-order logic, which was automatically verified by an interactive theorem prover. To the best of our knowledge, this is the first application of SMT solvers in computational social choice.

Our input is a bipartite graph G=(A\cup B,E) where each vertex in A\cup B has a preference list strictly ranking its neighbors. The vertices in A and in B are called students and courses, respectively. Each student a seeks to be matched to cap(a)\geq 1 many courses while each course b seeks cap(b)\geq 1 many students to be matched to it. The Gale-Shapley algorithm computes a pairwise-stable matching (one with no blocking edge) in G in linear time. We consider the problem of computing a popular matching in G - a matching M is popular if M cannot lose an election to any matching where vertices cast votes for one matching versus another. Our main contribution is to show that a max-size popular matching in G can be computed by the 2-level Gale-Shapley algorithm in linear time. This is an extension of the classical Gale-Shapley algorithm and we prove its correctness via linear programming.

Efficiency--no agent can be made better off without making another one worse off--and strategyproofness--no agent can obtain a more preferred outcome by misrepresenting his preferences--are two cornerstones of economics and ubiquitous in important areas such as voting, auctions, or matching markets. Within the context of random assignment, Bogomolnaia and Moulin have shown that two particular notions of efficiency and strategyproofness based on stochastic dominance are incompatible. However, there are various other possibilities of lifting preferences over alternatives to preferences over lotteries apart from stochastic dominance. In this paper, we give an overview of common preference extensions, propose two new ones, and show that the above-mentioned incompatibility can be extended to various other notions of strategyproofness and efficiency in randomized social choice.

No abstract available.