Second-best efficiency of allocation rules: strategy-proofness and single-peaked preferences with multiple commodities

We study strategy-proof allocation rules in economies with perfectly divisible multiple commodities and single-peaked preferences. In this setup, it is known that the incompatibility among strategy-proofness, Pareto efficiency and non-dictatorship arises in contrast with the Sprumont (Econometrica 59:509–519, 1991) one commodity model. We first investigate the existence problem of strategy-proof and second-best efficient rules, where a strategy-proof rule is second-best efficient if it is not Pareto-dominated by any other strategy-proof rules. We show that there exists an egalitarian rational (consequently, non-dictatorial) strategy-proof rule satisfying second-best efficiency. Second, we give a new characterization of the generalized uniform rule with the second-best efficiency in two-agent case.     

When too little is as good as nothing at all: Rationing a disposable good among satiable people with acceptance thresholds

We study the problem of rationing a divisible good among a group of people. Each person?s preferences are characterized by an ideal amount that he would prefer to receive and a minimum quantity that he will accept: any amount less than this threshold is just as good as receiving nothing at all. Any amount beyond his ideal quantity has no effect on his welfare.We search for Pareto-efficient, strategy-proof, and envy-free rules. The definitions of these axioms carry through from the more commonly studied problem without disposability or acceptance thresholds. However, these are not compatible in the model that we study. We adapt the equal-division lower bound axiom and propose another fairness axiom called awardee-envy-freeness. Unfortunately, these are also incompatible with strategy-proofness. We characterize all of the Pareto-efficient rules that satisfy these two properties. We also characterize all Pareto-efficient, strategy-proof, and non-bossy rules.     

On the Interplay of Hidden Action and Hidden Information in Simple Bilateral Trading Problems

A buyer and a seller can exchange one unit of an indivisible good. While producing the good, the seller can exert unobservable effort (hidden action). Then the buyer realizes whether his or her valuation is high or low, which stochastically depends upon the seller's effort level (hidden information). The parties are risk neutral—they can rule out renegotiation and write complete contracts. It is shown that the first best cannot be achieved whenever the ex post efficient trade decision is trivial. The second-best contract is characterized and an application of the model to the choice of risky projects is briefly discussed. Journal of Economic Literature Classification Numbers: C72, C78, D23, D82.     

Strategy-proof Location on a Network

We consider rules that choose a location on a graph (e.g. a road network) based on agents' single-peaked preferences. First, we characterize the class of strategy-proof, onto rules when the graph is a tree. Such a rule is based on a collection of generalized median voter rules (Moulin, 1980) satisfying a consistency condition. Second, we characterize such rules for graphs containing cycles. We show that while such a rule is not necessarily dictatorial, the existence of a cycle grants some agent an amount of decisive power, unlike the case of trees. Rules for this case can be described in terms of a subclass of such rules for trees. Journal of Economic Literature Classification Numbers: C72, D78.     

Priorities in the location of multiple public facilities

A collective decision problem is described by a set of agents, a profile of single-peaked preferences over the real line and a number of public facilities to be located. We consider public facilities that do not suffer from congestion and are non-excludable. We characterize the class of rules satisfying Pareto-efficiency, object-population monotonicity and sovereignty. Each rule in the class is a priority rule that selects locations according to a predetermined priority ordering among “interest groups”. We characterize the subclasses of priority rules that respectively satisfy anonymity, avoid the no-show paradox, strategy-proofness and population-monotonicity. In particular, we prove that a priority rule is strategy-proof if and only if it partitions the set of agents into a fixed hierarchy. Any such rule can also be viewed as a collection of generalized peak-selection median rules, that are linked across populations, in a way that we describe.     

Joint misrepresentation with bribes

We study the problem of assigning objects to buyers. Monetary transfers are allowed. Each buyer’s preference space contains, but is not limited to, the linear additively separable preferences. A rule maps each preference profile to an allocation. We are concerned about the possibility that a group of buyers may engage in the following kind of manipulation: They make side payments internally and then carry out a joint misrepresentation. A rule is strongly group strategy-proof if no group can gain by engaging in such operations. We also consider several other appealing requirements. We find that the posted-price rules are the only one that satisfies non-triviality, non-imposition, envy-freeness, and strong group strategy-proofness.     

Coalitional Strategy-Proofness in Economies with Single-Dipped Preferences and the Assignment of an Indivisible Object

We study two allocation models. In the first model, we consider the problem of allocating an infinitely divisible commodity among agents with single-dipped preferences. In the second model, a degenerate case of the first one, we study the allocation of an indivisible object to a group of agents. Our main result is the characterization of the class of Pareto optimal and coalitionally strategy-proof allocation rules. Alternatively, this class of rules, which largely consists of serially dictatorial components, can be characterized by Pareto optimality, strategy-proofness, and weak non-bossiness (in terms of welfare). Furthermore, we study properties of fairness such as anonymity and no-envy. Journal of Economic Literature Classification Numbers: D63, D71.     

Strategy-Proof Probabilistic Decision Schemes for One-Dimensional Single-Peaked Preferences

Collective decision problems are considered with a finite number of agents who have single-peaked preferences on the real line. A probabilistic decision scheme assigns a probability distribution over the real line to every profile of reported preferences. The main result of the paper is a characterization of the class of unanimous and strategy-proof probabilistic schemes with the aid of fixed probability distributions that play a role similar to that of the phantom voters in H. Moulin (Public Choice35 (1980), 437-455). Thereby, the work of Moulin (1980) is extended to the probabilistic framework. Journal of Economic Literature Classification Numbers: D71, D81.     

Group strategyproof cost sharing: The role of indifferences

Every agent reports his willingness to pay for one unit of a good. A mechanism allocates goods and cost shares to some agents. We characterize the group strategyproof (GSP) mechanisms under two alternative continuity conditions interpreted as tie-breaking rules. With the maximalist rule (MAX) an indifferent agent is always served. With the minimalist rule (MIN) an indifferent agent does not get a unit of the good.GSP and MAX characterize the cross-monotonic mechanisms. These mechanisms are appropriate whenever symmetry is required. On the other hand, GSP and MIN characterize the sequential mechanisms. These mechanisms are appropriate whenever there is scarcity of the good.Our results are independent of an underlying cost function; they unify and strengthen earlier results for particular classes of cost functions.     

On the uniqueness of Groves mechanisms and the payoff equivalence principle

Consider a standard mechanism design setting with quasi-linear preferences and private valuations. From Holmström (1979), we know that if the valuations are smooth with respect to types then any efficient, dominant strategy mechanism is in the class of Groves mechanisms. Here I show that, given regular assumptions on the primitives of the design problem, a weaker condition that includes the case of non-smooth valuations is sufficient and necessary for the uniqueness of Groves mechanisms among all efficient, dominant strategy mechanisms. This condition, which imposes a restriction on the behavior of the one-sided directional derivatives of the valuation functions with respect to individual types, is also shown to be sufficient and necessary to obtain the Payoff Equivalence principle for dominant strategy mechanisms whose choice rules are affine maximizers.     

Eliciting Preferences to Assign Positions and Compensation

We describe strategy-proof rules for economies where an agent is assigned a position (e.g., a job) plus some of a divisible good. For the 2-agent–2-position case we derive a robust characterization. For the multi-agent–position case, many “arbitrary” such rules exist, so we consider additional requirements. By also requiring coalitional strategy-proofness or nonbossiness, the range of a solution is restricted to the point that such rules are not more complex than those for the Shapley–Scarf housing model (no divisible good). Third, we show that essentially only constant solutions are immune to manipulations involving “bribes.” Finally, we demonstrate a conflict between efficiency and strategy-proofness. The results extend to models (without externalities) in which agents share positions. Journal of Economic Literature Classification Numbers: C72, D70.     

Public goods with congestion

I consider the problem of the efficient provision of a congested (limited capacity) public good in a setting with asymmetric information. I show, in particular, that when the capacity of the good is limited, in a wide class of economies it is possible to construct an incentive compatible mechanism that always produces the good at the efficient level, balances the budget and satisfies voluntary participation constraints. This result is in contrast with the corresponding impossibility result for pure public goods due to Mailath and Postlewaite (Rev. Econ. Stud. 57 (1990) 351-359) and Rob (J. Econ. Theory 47 (1989) 307-333).     

Ordinal efficiency and dominated sets of assignments

Using lotteries is a common tool for allocating indivisible goods. Since obtaining preferences over lotteries is often difficult, real-life mechanisms usually rely on ordinal preferences over deterministic outcomes. Bogomolnaia and Moulin (J. Econom. Theory 19 (2002) 623) show that the outcome of an ex post efficient mechanism may be stochastically dominated. They define a random assignment to be ordinally efficient if and only if it is not stochastically dominated. In this paper we investigate the relation between ex post efficiency and ordinal efficiency. We introduce a new notion of domination defined over sets of assignments and show that a lottery induces an ordinally efficient random assignment if and only if each subset of the full support of the lottery is undominated.     

The Scholarship Assignment Problem

There are n graduate students and n faculty members. Each student will be assigned a scholarship by the joint faculty. The socially optimal outcome is that the best student should get the most prestigious scholarship, the second-best student should get the second most prestigious scholarship, and so on. The socially optimal outcome is common knowledge among all faculty members. Each professor wants one particular student to get the most prestigious scholarship and wants the remaining scholarships to be assigned according to the socially optimal outcome. We consider the problem of finding a mechanism such that in equilibrium, all scholarships are assigned according to the socially optimal outcome. Journal of Economic Literature Classification Numbers: D70, D78.     

Collective choice under dichotomous preferences

Agents partition deterministic outcomes into good or bad. A mechanism selects a lottery over outcomes (time-shares). The probability of a good outcome is the canonical utility. The utilitarian mechanism averages over outcomes with largest “approval”. It is efficient, strategyproof, anonymous and neutral.We reach an impossibility if, in addition, each agent's utility is at least , where n is the number of agents; or is at least the fraction of good to feasible outcomes. We conjecture that no ex ante efficient and strategyproof mechanism guarantees a strictly positive utility to all agents, and prove a weaker statement.     

Optimal collusion-resistant mechanisms with verification

We present the first general positive result on the construction of collusion-resistant mechanisms, that is, mechanisms that guarantee dominant strategies even when agents can form arbitrary coalitions and exchange compensations (sometimes referred to as transferable utilities or side payments). This is a much stronger solution concept as compared to truthful or even group strategyproof mechanisms, and only impossibility results were known for this type of mechanisms in the “classical” model.We describe collusion-resistant mechanisms with verification that return optimal solutions for a wide class of mechanism design problems (which includes utilitarian ones as a special case). Note that every collusion-resistant mechanism without verification must have an unbounded approximation factor and, in general, optimal solutions cannot be obtained even if we content ourselves with truthful (“non-collusion-resistant”) mechanisms. All these results apply to problems that have been extensively studied in the algorithmic mechanism design literature like, for instance, task scheduling and inter-domain routing.     

Implementation in undominated strategies by bounded mechanisms: Some results on compromise alternatives

We consider an impossibility result in Börgers (1991), which says in a restricted environment with two players or three alternatives it is impossible to implement a social choice correspondence that is efficient, enforces compromises at a profile and is implementable in undominated strategies by a bounded mechanism. We extend and refine this result in many ways- we generalize the impossibility result for any number of players and alternatives when the compromises are enforced at a near-unanimous preference profile. We further show that the impossibility result in Börgers (1991) holds good if we replace efficiency of SCCs by neutrality. Also the impossibility result holds good for two agents and any number of alternatives when the SCC is unanimous and minimal. Interestingly, we get a possibility result when we relax the assumption of minimality.     

Optimal search,learning and implementation

We characterize the incentive compatible, constrained efficient policy (“second-best”) in a dynamic matching environment, where impatient, privately informed agents arrive over time, and where the designer gradually learns about the distribution of agents? values. We also derive conditions on the learning process ensuring that the complete-information, dynamically efficient allocation of resources (“first-best”) is incentive compatible. Our analysis reveals and exploits close, formal relations between the problem of ensuring implementable allocation rules in our dynamic allocation problems with incomplete information and learning, and between the classical problem, posed by Rothschild (1974) [20], of finding optimal stopping policies for search that are characterized by a reservation price property.     

Matching mechanisms and matching quality: Evidence from a top university in China

We compare competing college admission matching mechanisms that differ in preference submission timing (pre-exam, post-exam but pre-score, or post-score) and in matching procedure (Boston (BOS) and serial dictatorship (SD) matching). Pre-exam submission asks students to submit college preferences before entrance exam scores are known, whereas post-score (post-exam) submission removes (reduces) score uncertainties. Theoretical analyses show that although mechanisms with post-score submission or SD matching are ex-post fair and efficient, they are not so ex-ante. Instead, the mechanism with pre-exam submission and BOS matching can be more fair and efficient ex-ante. These hypotheses are supported by empirical test on data from a top school at a top-ranked Chinese university with identification based on temporal and provincial changes. We find that although students admitted under the pre-exam BOS mechanism have lower college entrance exam scores than students admitted through other mechanisms on average, they exhibit similar or even better college academic performance.     

Reducing Inefficiency in Public Good Provision Through Linking

We characterize the optimal mechanism for the provision of n public goods in an economy with m agents, binary valuations. The mechanism “links” the n problems together because decisions and transfers are based on the whole vector of valuations of the agents. In particular, the decision on whether or not to provide a public good depends not only on the valuations of the agents for that good but, in some cases, also on the valuations for the other goods reported by the low‐valuation agents. For the two‐agent case, we show that the mechanism is asymptotically efficient and we provide an example that compares its relative efficiency with optimal separate provision and with another asymptotically efficient mechanism in the literature.