Respecting Priorities when Assigning Students to Schools

We consider the problem of assigning students to schools on the basis of priorities. Students are allowed to have equal priority at a school. We characterize the efficient rules which weakly/strongly respect students’ priorities. When priority orderings are not strict, it is not possible to simply break ties in a fixed manner. All possibilities of resolving the indifferences need to be considered. Neither the deferred acceptance algorithm nor the top trading cycle algorithm successfully solve the problem of efficiently assigning the students to schools whereas a modified version of the deferred acceptance algorithm might. In this version tie breaking depends on students’ preferences.

Matching Markets under (In)complete Information

We are the first to introduce incomplete information to centralized many-to-one matching markets such as those to entry-level labor markets or college admissions. This is important because in real life markets (i) any agent is uncertain about the other agents' true preferences and (ii) most entry-level matching is many-to-one (and not one-to-one). We show that for stable (matching) mechanisms there is a strong and surprising link between Nash equilibria under complete information and Bayesian Nash equilibria under incomplete information. That is,given a common belief, a strategy profile is a Bayesian Nash equilibrium under incomplete information in a stable mechanism if and only if, for any true profile in the support of the common belief, the submitted profile is a Nash equilibrium under complete information at the true profile in the direct preference revelation game induced by the stable mechanism. This result may help to explain the success of stable mechanisms in these markets.

Oligarchies in Spatial Environments

In spatial environments we consider social welfare functions satisfying Arrow’s requirements, i.e. weak Pareto and independence of irrelevant alternatives. Individual preferences measure distances between alternatives according to the Lp-norm (for a fixed p => 1). When the policy space is multi-dimensional and the set of alternatives has a non-empty interior and it is compact and convex, any quasi-transitive welfare function must be oligarchic. As a corollary we obtain that for transitive welfare functions weak Pareto, independence of irrelevant alternatives, and non-dictatorship are inconsistent if the set of alternatives has a non-empty interior and it is compact and convex.

Sharing a River among Satiable Countries

With diminishing global water reserves the problem of water allocation becomes increasingly important. We consider the problem of efficiently sharing a river among a group of satiable countries. Inducing countries to efficiently cooperate requires monetary compensations via international agreements. We show that cooperation of the other countries exerts a positive externality on the benefit of a coalition. Our problem is to distribute the benefit of efficiently sharing the river under these constraints. If the countries outside of a coalition do not cooperate at all, then the downstream incremental distribution is the unique compromise between the absolute territorial sovereignty (ATS) doctrine and the unlimited territorial integrity (UTI) doctrine. If all countries outside of a coalition cooperate, then there may not exist any distribution satisfying the UTI doctrine.

Externalities, Potential, Value and Consistency

We provide new characterization results for the value of games in partition function form. In particular, we use the potential of a game to define the value. We also provide a characterization of the class of values which satisfies one form of reduced game consistency.

Manipulation via Capacities Revisited

This paper revisits manipulation via capacities in centralized two-sided matching markets. Sönmez (1997) showed that no stable mechanism is nonmanipulable via capacities. We show that non-manipulability via capacities can be equivalently described by two types of non-manipulation via capacities: non-Type-I-manipulability meaning that no college with vacant positions can manipulate by dropping some of its empty positions; and non-Type-II-manipulability meaning that no college with no vacant positions can manipulate by dropping some of its filled positions. Our main result shows that the student-optimal stable mechanism is the unique stable mechanism which is non-Type-I-manipulable via capacities and independent of truncations. Our characterization supports the use of the student-optimal stable mechanism in these matching markets because of its limited manipulability via capacities by colleges.

Allocation via Deferred-Acceptance under Responsive Priorities

In many economic environments - such as college admissions, student placements at public schools, and university housing allocation - indivisible objects with capacity constraints are assigned to a set of agents when each agent receives at most one object and monetary compensations are not allowed. In these important applications the agent-proposing deferred-acceptance algorithm with responsive priorities (called responsive DA-rule) performs well and economists have successfully implemented responsive DA-rules or slight variants thereof. First, for house allocation problems we characterize the class of responsive DA-rules by a set of basic and intuitive properties, namely, unavailable type invariance, individual rationality, weak non-wastefulness, resource-monotonicity, truncation invariance, and strategy-proofness. We extend this characterization to the full class of allocation problems with capacity constraints by replacing resource- monotonicity with two-agent consistent con ict resolution. An alternative characterization of responsive DA-rules is obtained using unassigned objects invariance, individual rationality, weak non-wastefulness, weak consistency, and strategy-proofness. Various characterizations of the class of "acyclic" responsive DA-rules are obtained by using the properties efficiency, group strategy-proofness, and consistency.

School Choice with Control

Controlled choice over public schools is a common policy of school boards in the United States. It attempts giving choice to parents while maintaining racial and ethnic balance at schools. This paper provides a foundation for controlled school choice programs. We develop a natural notion of fairness and show that assignments, which are fair for same type students and constrained non-wasteful, always exist in controlled choice problems; a "controlled" version of the student proposing deferred acceptance algorithm (CDAA) always finds such an assignment which is also weakly Pareto-optimal. CDAA provides a practical solution for controlled school choice programs.

Regulation via the Polluter-Pays Principle

We consider the problem of regulating an economy with environmental pollution. We examine the distributional impact of the polluter-pays principle which requires that any agent compensates all other agents for the damages caused by his or her (pollution) emissions. With constant marginal damages we show that regulation via the polluter-pays principle leads to the unique welfare distribution that assigns non-negative individual welfare and renders each agent responsible for his or her pollution impact. We extend both the polluter-pays principle and this result to increasing marginal damages due to pollution. We also discuss the acceptability of the polluter-pays principle and compare it with the Vickrey-Clark-Groves mechanism.

Budget-Balance, Fairness and Minimal Manipulability

A common real-life problem is to fairly allocate a number of indivisible objects and a fixed amount of money among a group of agents. Fairness requires that each agent weakly prefers his consumption bundle to any other agent’s bundle. Under fairness, efficiency is equivalent to budget-balance (all the available money is allocated among the agents). Budget-balance and fairness in general are incompatible with non-manipulability (Green and Laffont, 1979). We propose a new notion of the degree of manipulability which can be used to compare the ease of manipulation in allocation mechanisms. Our measure counts for each problem the number of agents who can manipulate the rule. Given this notion, the main result demonstrates that maximally linked fair allocation rules are the minimally manipulable rules among all budget-balanced and fair allocation mechanisms. Such rules link any agent to the bundle of a pre-selected agent through indifferences (which can be viewed as indirect egalitarian equivalence).

Strategy-proof tie-breaking

We study a general class of priority-based allocation problems with weak priority orders and identify conditions under which there exists a strategy-proof mechanism which always chooses an agent-optimal stable, or constrained efficient, matching. A priority structure for which these two requirements are compatible is called solvable. For the general class of priority-based allocation problems with weak priority orders,we introduce three simple necessary conditions on the priority structure. We show that these conditions completely characterize solvable environments within the class of indifferences at the bottom (IB) environments, where ties occur only at the bottom of the priority structure. This generalizes and unifies previously known results on solvable and unsolvable environments established in school choice, housing markets and house allocation with existing tenants. We show how the previously known solvable cases can be viewed as extreme cases of solvable environments. For sufficiency of our conditions we introduce a version of the agent-proposing deferred acceptance algorithm with exogenous and preference-based tie-breaking.

«School choice with controlled choice constraints: hard bounds versus soft bounds»

Controlled choice over public schools attempts giving options to parents while maintaining diversity, often enforced by setting feasibility constraints with hard upper and lower bounds for each student type. We demonstrate that there might not exist assignments that satisfy standard fairness and non-wastefulness properties; whereas constrained non-wasteful assignments which are fair for same type students always exist. We introduce a "controlled" version of the deferred acceptance algorithm with an improvement stage (CDAAI) that finds a Pareto optimal assignment among such assignments. To achieve fair (across all types) and non-wasteful assignments, we propose the control constraints to be interpreted as soft bounds-flexible limits that regulate school priorities. In this setting, a modified version of the deferred acceptance algorithm (DAASB) finds an assignment that is Pareto optimal among fair assignments while eliciting true preferences. CDAAI and DAASB provide two alternative practical solutions depending on the interpretation of the control constraints. JEL C78, D61, D78, I20.