Implementation of stable solutions in a restricted matching market

I analyze the admission mechanism used in Spanish universities. The system is open to strategic manipulation. This is because students are not allowed to express the whole list of available options. However, the mechanism implements the set of stable matchings in Nash equilibrium and the student's optimum in strong equilibrium. The mechanism also implements the students' optimum, in Nash equilibrium, under the class of “non-reverse” preferences. All these properties come from the fact that colleges do not have the opportunity to misrepresent their preferences. Received: 30 June 1995 / Accepted: 31 January 1997     

Achieving the first best in sequencing problems

Abstract. In a sequencing problem with linear time cost, Suijs (1996) proved that it is possible to achieve first best. By first best we mean that one can find mechanisms that satisfy efficiency of decision, dominant strategy incentive compatibility and budget balancedness. In this paper we show that among a more general and natural class of sequencing problems, sequencing problems with linear cost is the only class for which first best can be achieved. Received: 2 December 1999/Accepted: 9 May 2001     

Restricted houseswapping games

Restricted houseswapping games (RHGs) are a generalization of ‘one-sided matching games’, in which we specify a class II* of ‘allowable’ simple trading cycles. The cores of such games may be empty. Given II*, all possible closed RHGs have non-empty cores of II* is ‘strongly balanced’. Examples include the one-sided matching markets (^{Shapley and Scarf. Journal of Mathematical Economics 1974. 1. 23–37}. ^{Tijs et al., OR Spektrum 1984, 6, 119–123}; ^{Quinzii, International Journal of Game Theory 1984, 13, 41–60}) and the two-sided matching markets (^{Gale and Shapley. American Mathematical Monthly 1962. 69, 9–16}; ^{Shapley and Shubik, International Journal of Game Theory 1972, 1, 111–130}: and ^{Demange and Gale Econometrica 1985, 53, 873–888}).We then consider the subclass of RHGs in which there is no transferable resource. In this case, a weaker condition on II*, called ‘weak balancedness’, is sufficient to guarantee core non-emptiness. In addition, if II* is not weakly balanced, then there exists a preference profile such that the strict core of the resultant game is empty.Several other examples are given of II* that are (a) strongly balanced: (b) weakly balanced but not strongly balanced: and (c) not even weakly balanced.Finally, we discuss the issues of equilibrium definition, existence, and core-equilibrium allocation equivalence in RHGs.     

Strategy-proofness in many-to-one matching problems

We search forstrategy-proof solutions in the context of (many-to-one) matching problems (Gale and Shapley, 1962). In this model, whenever the firms can hire as many workers as they want (the capacities are unlimited) the stable set is a singleton. There exists aPareto efficient, individually rational, andstrategy-proof matching rule if and only if the capacities are unlimited. Furthermore, whenever the capacities unlimited, the matching rule which selects the unique stable matching is the only matching rule that isPareto efficient, individually rational, andstrategy-proof.     

Stable matchings and the small core in Nash equilibrium in the college admissions problem

Both rematching proof and strong equilibrium outcomes are stable with respect to the true preferences in the marriage problem. We show that not all rematching proof or strong equilibrium outcomes are stable in the college admissions problem. But we show that both rematching proof and strong equilibrium outcomes in truncations at the match point are all stable in the college admissions problem. Further, all true stable matchings can be achieved in both rematching proof and strong equilibrium in truncations at the match point. We show that any Nash equilibrium in truncations admits one and only one matching, stable or not. Therefore, the core at a Nash equilibrium in truncations must be small. But examples exist such that the set of stable matchings with respect to a Nash equilibrium may contain more than one matching. Nevertheless, each Nash equilibrium can only admit at most one true stable matching. If, indeed, there is a true stable matching at a Nash equilibrium, then the only possible equilibrium outcome will be the true stable matching, no matter how different are players' equilibrium strategies from the true preferences and how many other unstable matchings are there at that Nash equilibrium. Thus, we show that a necessary and sufficient condition for the stable matching rule to be implemented in a subset of Nash equilibria by the direct revelation game induced by a stable mechanism is that every Nash equilibrium profile in that subset admits one and only one true stable matching. Received: 30 December 1998 / Accepted: 12 October 2001 This paper is a revision of the paper “Manipulation and Stability in a College Admissions Problem” circulated since 1994. I thank Rich McLean, Abraham Neyman, Mark Satterthwaite, Sang-Chul Suh, and Tetsuji Yamada for helpful discussions. I thank the associate editor and the two anonymous referees for their helpful comments that have greatly improved the paper. I am grateful to the Kellogg G.S.M. at the Northwestern University for the hospitality for my visit. Any errors are mine.     

Buyers' and sellers' cartels on markets with indivisible goods

This paper analyzes the formation of cartels of buyers and sellers in a simple model of trade inspired by Rubinstein and Wolinsky's (1990) bargaining model. When cartels are formed only on one side of the market, there is at most one stable cartel size. When cartels are formed sequentially on the two sides of the market, there is also at most one stable cartel configuration. Under bilateral collusion, buyers and sellers form cartels of equal sizes, and the cartels formed are smaller than under unilateral collusion. Both the buyers' and sellers' cartels choose to exclude only one trader from the market. This result suggests that there are limits to bilateral collusion, and that the threat of collusion on one side of the market does not lead to increased collusion on the other side.     

A bootstrap algorithm for testing cointegration rank in VAR models in the presence of stationary variables

In this paper, a bootstrap algorithm for a reduced rank vector autoregressive (VAR) model which also includes stationary regressors, is analyzed. It is shown that the bootstrap distribution for estimating the rank converges to the distribution derived from the usual asymptotic framework. Because the asymptotic distribution will typically depend on unknown parameters, bootstrap distributions are of considerable interest in this context. The result of an application and some Monte Carlo experiments are also presented.     

On preferences over subsets and the lattice structure of stable matchings

This paper studies the structure of stable multipartner matchings in two-sided markets where choice functions are quotafilling in the sense that they satisfy the substitutability axiom and, in addition, fill a quota whenever possible. It is shown that (i) the set of stable matchings is a lattice under the common revealed preference orderings of all agents on the same side, (ii) the supremum (infimum) operation of the lattice for each side consists componentwise of the join (meet) operation in the revealed preference ordering of the agents on that side, and (iii) the lattice has the polarity, distributivity, complementariness and full-quota properties. Received: 5 March 1999 / Accepted: 12 May 2000     

Metonymy and cross-section demand

Cross-section consumer expenditure data are frequently used to draw conclusions about consumer demand behavior. Such conclusions, however, are justified only under certain assumptions, which are often left unstated in the empirical demand literature. An assumption of this type, the metonymy hypothesis, was stated rigorously and exploited by Härdle et al. when analyzing the monotonicity of aggregate demand functions. The purpose of the present paper is to examine the metonymy hypothesis in more detail. We prove that the distribution of demand vectors derived from a not necessarily metonymic population is identical with the distribution derived from some metonymic population. This implies, in particular, that the metonymy hypothesis cannot be rejected or confirmed on the basis of data from a single cross-section.     

Strategyproof multiple assignment using quotas

The allocation of heterogeneous and indivisible objects is considered where there is no medium of exchange. We characterize the set of strategyproof, nonbossy, Pareto-optimal, and neutral social choice functions when preferences are monotonic and quantity-monotonic. The characterized sets of social choice functions are sequential; agents are assigned their favorite objects among the objects not given to others before them, subject to a quota. Received: 5 January 1999 / Accepted: 14 June 1999     

Stable and efficient bargaining networks

Abstract. We examine a bargaining game among players connected by a network, where successively potential partners negotiate over terms of a project. For any network structure and ordering of selection of bargaining partners, there is a unique subgame perfect equilibrium outcome which coincides with the standard Rubinstein split. Based on this, we derive expected payoffs for players as a function of the network. We the characterize the pairwise stable and efficient bargaining networks. These two sets do not always coincide and in many situations pairwise stable networks are over-connected. Received: 10 April 2001 / Accepted: 17 January 2002 I am indebted to Matthew Jackson for suggesting this paper. I also thank Bernard Caillaud, Sanjeev Goyal, and the seminar participants at Universidad de Alicante, Universidad Carlos III de Madrid, CEMFI (Madrid), Universitat Autònoma de Barcelona, Erasmus University of Rotterdam, Universitat Pompeu Fabra (Barcelona) and CERAS (Paris) for helpful comments. This paper was written while at Universitat Pompeu Fabra and CERAS. Financial support from the Spanish Ministry of Education through research grant DGESIC PB96-0302, and from the Ecole Nationale des Ponts et Chaussées, Paris is gratefully acknowledged. All errors are of course mine.     

Lattice structure of knowledge and agreeing to disagree

This paper is a contribution to the study of the underlying mathematical structure of common-knowledge, which gives the well-known result of Aumann about the impossibility of ‘agreeing to disagree’. We present the Bayesian subjective probability model with player's belief: i.e. a triple (? %plane1D;4AF;, μ), in which i is a player. ? is a lattice in the field of sets of a state space Ω, %plane1D;4AF;, is a correspondence assigning to each state ω a filter %plane1D;4AF;(ω) in ?, and μ is a common-prior. For this model, we impose none of the important restrictions on the information structure in the Aumann-Bacharach model: axiom of knowledge K₁. axiom of transparency K₂ and axiom of wisdom K₃. We can extend both the disagreement theorem of Aumann and the agreement theorem of Geanacoplos and Polemarchakis under the assumption that each ? is an Artinian lattice.     

Sequential regularity in smooth production economies

In general equilibrium models where agents trade sequentially in multiple periods, the equilibria that endogenously occur in later periods can be robustly indeterminate if production sets are not everywhere differentiable (as. for example, with linear activities). The present paper proves that if technology is smooth, then equilibria are sequentially regular. That is. the equilibria of the endogenously generated economies occurring in later periods that confirm the unanimous expectations formed by agents in earlier periods are regular (and thus, for example, isolated from other equilibria). The paper also proves and utilizes the standard result that the overall intertemporal equilibria are regular.