Researching with whom? Stability and manipulation

This paper explores the existence of stable research teams, when the preferences of each agent depend on the set of researchers who are collaborating. We introduce a property over researchers’ preferences, called top responsiveness, guaranteeing the existence of stable research teams configurations. We also provide a stable mechanism, induced by the so-called top covering algorithm, which is strategy-proof when researchers preferences satisfy top responsiveness. Furthermore, we find that, in this framework, the top covering mechanism is the only strategy-proof mechanism that always selects stable allocations.     

A solution to the random assignment problem on the full preference domain

We consider the problem of allocating a set of indivisible objects to agents in a fair and efficient manner. In a recent paper, Bogomolnaia and Moulin consider the case in which all agents have strict preferences, and propose the probabilistic serial (PS) mechanism; they define a new notion of efficiency, called ordinal efficiency, and prove that the probabilistic serial mechanism finds an envy-free ordinally efficient assignment. However, the restrictive assumption of strict preferences is critical to their algorithm. Our main contribution is an analogous algorithm for the full preference domain in which agents are allowed to be indifferent between objects. Our algorithm is based on a reinterpretation of the PS mechanism as an iterative algorithm to compute a “flow” in an associated network. In addition we show that on the full preference domain it is impossible for even a weak strategyproof mechanism to find a random assignment that is both ordinally efficient and envy-free.     

Augmented serial rules for an excludable public good

Summary. We present a new class of rules named augmented serial rules for the provision of an excludable public good. First, we characterize this class by the four axioms of strategy-proofness, envy-freeness, access independence, and nonbossiness. Second, we identify two important subclasses by imposing an additional axiom: (i) anonymous augmented serial rules by anonymity, and (ii) Moulins serial rule by individual rationality.Received: 31 December 2002, Revised: 9 June 2004, JEL Classification Numbers: D71, D82, H41.This paper is a substantial revision of Serial cost sharing with simple games. I would like to thank Hervé Moulin, Yoshikatsu Tatamitani, an associate editor, and three anonymous referees for helpful suggestions and detailed comments. This research was partially supported by the Ministry of Education, Culture, Sports, Science, and Technology in Japan (Grant-in-Aid for 21st Century COE Program Microstructure and Mechanism Design in Financial Markets).     

Impossibilities for strategy-proof committee selection mechanisms with vetoers

When a group of voters selects a committee out of a set of candidates, it is common and often desirable to endow these voters with some veto power. I present impossibility results showing that even limited veto power makes many mechanisms of interest manipulable. This applies in particular (i) to mechanisms the range of which contains a degenerate lottery in which a committee is chosen for sure and (ii) to mechanisms that are constructed from extensive game forms with a finite number of strategies. These impossibilities hold on a large set of domains including the domain of additive preferences, and even when probabilistic mechanisms are allowed and voters can report cardinal preferences.     

Strategy-proof preference aggregation: Possibilities and characterizations

An aggregation rule maps each profile of individual strict preference orderings over a set of alternatives into a social ordering over that set. We call such a rule strategy-proof if misreporting one's preference never produces a different social ordering that is between the original ordering and one's own preference. After describing two examples of manipulable rules, we study in some detail three classes of strategy-proof rules: (i) rules based on a monotonic alteration of the majority relation generated by the preference profile; (ii) rules improving upon a fixed status-quo; and (iii) rules generalizing the Condorcet–Kemeny aggregation method.     

Efficient resource allocation under multi-unit demand

We study resource allocation with multi-unit demand, such as the allocation of courses to students. In contrast to the case of single-unit demand, no stable mechanism, not even the (student-proposing) deferred acceptance algorithm, achieves desirable properties: it is not strategy-proof and the resulting allocation is not even weakly efficient under submitted preferences. We characterize the priority structure of courses over students under which stability is consistent with strategy-proofness or efficiency. We show that stability is compatible with strategy-proofness or efficiency if and only if the priority structure is essentially homogeneous. This result suggests that efficient allocation under multi-unit demand is difficult and that the use of stable mechanisms may not deliver desirable outcomes.     

Non-manipulable domains for the Borda count

Summary. We characterize the preference domains on which the Borda count satisfies Arrows independence of irrelevant alternatives condition. Under a weak richness condition, these domains are obtained by fixing one preference ordering and including all its cyclic permutations (Condorcet cycles). We then ask on which domains the Borda count is non-manipulable. It turns out that it is non-manipulable on a broader class of domains when combined with appropriately chosen tie-breaking rules. On the other hand, we also prove that the rich domains on which the Borda count is non-manipulable for all possible tie-breaking rules are again the cyclic permutation domains.Received: 24 November 2003, Revised: 12 December 2004, JEL Classification Numbers: D71. Correspondence to: Clemens PuppeThe third author gratefully acknowledges the financial support from the Deutsche Forschungsgemeinschaft (DFG), Graduiertenkolleg 629 at the University of Bonn and from the Hungarian Scientific Research Fund (OTKA F 043496).     

Manipulation of voting schemes with restricted beliefs

In this paper we define manipulation with restricted beliefs as the possibility for some voter to have an insincere preference ordering that dominates the sincere one within the given individual beliefs over other agents’ preferences. We then show that all non-dictatorial voting schemes are manipulable in this sense, up to a given threshold.     

Second price auctions on general preference domains: two characterizations

Auction theory usually assumes the quasi-linearity of individual preferences. We drop this assumption and define an extension of second price mechanisms that applies to general preferences. It turns out that the extended second price mechanisms are the only rules satisfying efficiency, strategy-proofness, and a mild non-imposition property. Their definition is simple just as much as the definition of usual second price mechanisms: everyone reports his maximum willingness to pay and the bidder whose reported value is highest buys the auctioned object for the price equal to the second highest reported value. The characterization is valid if efficiency is replaced by envy-freeness. I gratefully acknowledge an associate editor and two anonymous referees for their very helpful comments. Hiroki Saitoh and Shigehiro Serizawa independently obtain a result that is closely related to my main result (see, Remark in Sect. 1). I thank them for sending me the paper and communication, and Yuji Fujinaka for informing me about their work. I also thank the financial support by KAKENHI (19310031).     

The structure of strategy-proof random social choice functions over product domains and lexicographically separable preferences

We characterize the class of dominant-strategy incentive-compatible (or strategy-proof) random social choice functions in the standard multi-dimensional voting model where voter preferences over the various dimensions (or components) are lexicographically separable. We show that these social choice functions (which we call generalized random dictatorships) are induced by probability distributions on voter sequences of length equal to the number of components. They induce a fixed probability distribution on the product set of voter peaks. The marginal probability distribution over every component is a random dictatorship. Our results generalize the classic random dictatorship result in Gibbard (1977) and the decomposability results for strategy-proof deterministic social choice functions for multi-dimensional models with separable preferences obtained in LeBreton and Sen (1999).