Characterizing the Vickrey combinatorial auction by induction

This note studies the allocation of heterogeneous commodities to agents whose private values for combinations of these commodities are monotonic by inclusion. This setting can accommodate the presence of complementarity and substitutability among the heterogeneous commodities. By using induction logic, we provide an alternative proof of Holmstrom’s (Econometrica 47:1137–1144, 1979) characterization of the Vickrey combinatorial auction as the unique efficient, strategy-proof, and individually rational allocation rule on a smoothly connected domain of value profiles. Our approach is elementary, not involving smoothness, and intuitive in the sense that familiar properties of the single-item second-price auction provide the first step in our induction on the number of auctioned items. Moreover, our method of proof can be applied to domains which may not be smoothly connected, including nonconvex ones. The authors acknowledge the helpful comments of anonymous referee. Serizawa greatly benefited from discussion with Rajat Deb.     

Children Crying at Birthday Parties. Why?

We consider the problem of dividing a non-homogeneous one-dimensional continuum whose endpoints are topologically identified. Examples are the division of a birthday cake, the partition of a circular market, the assignment of sentry duty or medical call. We study the existence of rules satisfying requirements of efficiency, fairness (no-envy), and immunity to misrepresentation of preferences (strategy-proofness). This work, supported by NSF under grant SES. 0214691, was presented at Laval University, at the May 2004 Israeli-Turkish Conference on Economic Design at Bilgi University, at the July 2004 Meeting of the Society for Economic Design at the University of Mallorca, and at the July 2004 Seventh International Meeting of the Society for Social Choice and Welfare at Osaka University. I thank Julius Barbanel, Steven Brams, Youngsub Chun, Bettina Klaus, Toyotaka Sakai, and Chun-Hsien Yeh for their comments.     

Population-monotonicity and separability for 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. We consider rules that satisfy Pareto efficiency, strategy-proofness, and in addition either the consistency property separability or the solidarity property population-monotonicity. We show that the class of rules that satisfy Pareto efficiency, strategy-proofness, and separability equals the class of rules that satisfy Pareto efficiency, strategy-proofness, and non-bossiness. We also provide characterizations of all rules satisfying Pareto efficiency, strategy-proofness, and either separability or population-monotonicity. Since any such rule consists for the largest part of serial-dictatorship components, we can interpret the characterizations as impossibility results. Received: September 29, 1999; revised version: March 22, 2000     

Fully sincere voting

In a general social choice framework where the requirement of strategy-proofness may not be sensible, we call a social choice rule fully sincere if it never gives any individual an incentive to vote for a less-preferred alternative over a more-preferred one and provides an incentive to vote for an alternative if and only if it is preferred to the default option that would result from abstaining. If the social choice rule can depend only on the number of votes that each alternative receives, those rules satisfying full sincerity are convex combinations of the rule that chooses each alternative with probability equal to the proportion of the vote it receives and an arbitrary rule that ignores voters' preferences. We note a sense in which the natural probabilistic analog of approval voting is the fully sincere rule that allows voters maximal flexibility in expressing their preferences and gives these preferences maximal weight.     

No-envy,solidarity, and strategy-proofness in the queueing problem

Given a group of agents, the queueing problem is concerned with finding the order to serve agents and the monetary transfers they should receive. In this paper, we characterize interesting subfamilies of the VCG mechanisms by investigating the implications of either no-envy or solidarity requirements. First, we present a characterization of the strategy-proofand envy-freemechanisms. Next, we present characterizations of VCG mechanisms satisfying one of two different formulations of cost monotonicity or population monotonicity. Finally, we show that among the envy-free and strategy-proof mechanisms, the only ones that satisfy one of two formulations of cost monotonicity or population monotonicity are extensions of the pivotal or the reward-based pivotal mechanisms.