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.     

The Blocking Lemma for a many-to-one matching model

The Blocking Lemma identifies a particular blocking pair for each non-stable and individually rational matching that is preferred by some agents of one side of the market to their optimal stable matching. Its interest lies in the fact that it has been an instrumental result to prove key results on matching. For instance, the fact that in the college admissions problem the workers-optimal stable mechanism is group strategy-proof for the workers and the strong stability theorem in the marriage model follow directly from the Blocking Lemma. However, it is known that the Blocking Lemma and its consequences do not hold in the general many-to-one matching model in which firms have substitutable preference relations. We show that the Blocking Lemma holds for the many-to-one matching model in which firms’ preference relations are, in addition to substitutable, quota q-separable. We also show that the Blocking Lemma holds on a subset of substitutable preference profiles if and only if the workers-optimal stable mechanism is group strategy-proof for the workers on this subset of profiles.     

Exchange-proofness or divorce-proofness? Stability in one-sided matching markets

Two stability concepts for one-sided matching markets are analyzed: Gale-Shapley stability and ξ-stability. The first one applies best to markets where no status quo allocation is considered, whereas the second one is a solution to be used when property rights are allowed. A common problem of existence is shared by both solution concepts. Hence, we study economic environments where this problem does not exist, and present a family of agents’ preferences for which existence is guaranteed for both Gale-Shapley stable and ξ-stable outcomes. This work was finished while the author was visiting Duke University, whose hospitality is gratefully acknowledged. Swveral discussions with Salvador Barberà, Hervé Moulin and Marilda Sotomayor and some advice by an anonymous referee were specially useful. This work is partially supported by Grants PB 92-0590 and PB 93-0938 from the DGICYT, the Spanish Ministery of Educación Ciencia, and the Institut Valencià d’Investigacions Econòmiques.     

Implementation in generalized matching problems

We search for (Nash) implementable solutions on a class of one-to-one matching problems which includes both the housing market (Shapley and Scarf, Journal of Mathematical Economics, 1974, 1, 23–28) and marriage problems (Gale and Shapley, American Mathematical Monthly, 1962, 69, 9–15). We show that the core correspondence is implementable. We show, furthermore, that any solution that is Pareto efficient, individually rational, and implementable is a supersolution of the core correspondence. That is, the core correspondence is the minimal solution that is Pareto efficient, individually rational, and implementable. A corollary of independent interest in the context of the housing market is that the core correspondence is the only single-valued solution that is Pareto efficient, individually rational, and implementable.     

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     

A note on the multiple partners assignment game

In the assignment game of Shapley and Shubik [Shapley, L.S., Shubik, M., 1972. The assignment game. I. The core, International Journal of Game Theory 1, 11–130] agents are allowed to form one partnership at most. That paper proves that, in the context of firms and workers, given two stable payoffs for the firms there is a stable payoff which gives each firm the larger of the two amounts and also one which gives each of them the smaller amount. Analogous result applies to the workers. Sotomayor [Sotomayor, M., 1992. The multiple partners game. In: Majumdar, M. (Ed.), Dynamics and Equilibrium: Essays in Honor to D. Gale. Mcmillian, pp. 322–336] extends this analysis to the case where both types of agents may form more than one partnership and an agent's payoff is multi-dimensional. Instead, this note concentrates in the total payoff of the agents. It is then proved the rather unexpected result that again the maximum of any pair of stable payoffs for the firms is stable but the minimum need not be, even if we restrict the multiplicity of partnerships to one of the sides.     

Fairness and implementability in allocation of indivisible objects with monetary compensations

This paper introduces a general framework for the fair allocation of indivisible objects when each agent can consume at most one (e.g., houses, jobs, queuing positions) and monetary compensations are possible. This framework enables us to deal with identical objects and monotonicity of preferences in ranking objects. We show that the no-envy solution is the only solution satisfying equal treatment of equals, Maskin monotonicity, and a mild continuity property. The same axiomatization holds if the continuity property is replaced by a neutrality property.     

Sequential bargaining with common values

We study the alternating-offers bargaining problem of assigning an indivisible and commonly valued object to one of two players who jointly own this object. The players are asymmetrically informed about the object’s value and have veto power over any settlement. There is no depreciation during the bargaining process which involves signalling of private information. We characterise the perfect Bayesian equilibrium outcome of this game which is unique if offers are required to be strictly increasing. Equilibrium agreement is reached gradually and non-deterministically. The better informed player obtains a rent.     

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.     

Dynamics,stability, and foresight in the Shapley–Scarf housing market

While most of the literature starting with Shapley and Scarf (1974) have considered a static exchange economy with indivisibilities, this paper studies the dynamics of such an economy. We find that both the dynamics generated by competitive equilibrium and the one generated by the weak dominance relation, converge to a set of allocations we define as strictly stable, which we can show to exist. Moreover, we show that even when only pairwise exchanges between two traders are allowed, the strictly stable allocations are attained eventually if traders are sufficiently farsighted.     

Learning in a multilateral bargaining experiment

This paper analyzes data from an investigation of a majoritarian bargaining experiment. A learning model is proposed to account for the evolution of play in this experiment. It is also suggested that an adjustment must be made to account for the panel structure of the data. Such adjustments have been used in other fields and are known to be important as unadjusted standard errors may be severely biased downward. These results indicate that this adjustment also has an important effect in this application. Furthermore, an efficient estimator that takes into account heterogeneity across players is proposed. A unique learning model to account for the paths of play under two different amendment rules cannot be rejected with the standard estimator with adjusted standard errors, however it can be rejected using the efficient estimator. The data and the estimated learning model suggest that after proposing “fair” divisions, subjects adapt and their proposals change rapidly in the treatment where uneven proposals are almost always accepted. Their beliefs in the estimated learning model are influenced by more than just the most recent outcomes.     

A mechanism implementing the proportional solution

We consider the problem of a commonly owned technology which transforms a single input into a single output. We are interested in implementing a social choice rule called theproportional solution. We introduce a mechanism which implements the proportional solution in Nash, strong (Nash) and undominated Nash equilibria. In the mechanism each agent announces only two numbers which can be interpreted as the total output and her share of the total input-output combination. This paper was originally titled "Doubly implementing the proportional solution." I would like to thank my advisor William Thomson for his detailed comments and suggestions. I would also like to thank Jeffrey Banks and Sung-Whee Shin for their comments. Two anonymous referees and an editor’s comments improved this paper substantially.     

On the robustness of location estimators in models of firm growth under heavy-tailedness

Focusing on the model of demand-driven innovation and spatial competition over time in Jovanovic and Rob (1987), we study the effects of the robustness of estimators employed by firms to make inferences about their markets on the firms’ growth patterns. We show that if consumers’ signals in the model are moderately heavy-tailed and the firms use the sample mean of the signals to estimate the ideal product, then the firms’ output levels exhibit positive persistence. In such a setting, large firms have an advantage over their smaller counterparts. These properties are reversed for signals with extremely heavy-tailed distributions. In such a case, the model implies anti-persistence in output levels, together with a surprising pattern of oscillations in firm sizes, with smaller firms being likely to become larger ones next period, and vice versa. We further show that the implications of the model under moderate heavy-tailedness continue to hold under the only assumption of symmetry of consumers’ signals if the firms use a more robust estimator of the ideal product, the sample median.     

Instability in the cobweb model under the BNN dynamic

The cobweb model where firms choose between rational and naive forecasting strategies has a 2-cycle when the slope of supply is greater than the slope of demand for a number of different dynamics describing the evolution of strategy choices. This paper proves that the 2-cycle is exponentially unstable under the learning dynamic of Brown et al. (1950). Issues arising in the analysis of piecewise smooth discrete time maps are discussed.     

Multiplicity of mixed equilibria in mechanisms: A unified approach to exact and approximate implementation

We characterize full implementation of social choice sets in mixed-strategy Bayesian equilibrium. Our results concern both exact and virtual mixed implementation. For exact implementation, we identify a strengthening of Bayesian monotonicity, which we refer to as mixed Bayesian monotonicity. It is shown that, in economic environments with at least three agents, mixed Bayesian implementation is equivalent to mixed Bayesian monotonicity, incentive compatibility and closure. For implementing a social choice function, the case of two-agents is also covered by these conditions and mixed Bayesian monotonicity reduces to Bayesian monotonicity. Following parallel steps, mixed virtual implementation is shown to be equivalent to mixed virtual monotonicity, incentive compatibility and closure. The key condition, mixed virtual monotonicity, is argued to be very weak. In particular, it is weaker than Abreu–Matsushima’s measurability, thereby implying that: (1) virtual implementation in mixed Bayesian equilibrium is more permissive than virtual implementation in iteratively undominated strategies, and (2) non-regular mechanisms are essential for the implementation of rules in that gap.     

Defining efficient policies in a general equilibrium model: a multi-objective approach

Macroeconomic policy makers are typically concerned with several indicators of economic performance. We thus propose to tackle the design of macroeconomic policy using Multicriteria Decision Making (MCDM) techniques. More specifically, we employ Multi-objective Programming (MP) to seek so-called efficient policies. The MP approach is combined with a computable general equilibrium (CGE) model. We chose use of a CGE model since it has the dual advantage of being consistent with standard economic theory while allowing one to measure the effect(s) of a specific policy with real data. Applying the proposed methodology to Spain (via the 1995 Social Accounting Matrix) we first quantified the trade-offs between two specific policy objectives: growth and inflation, when designing fiscal policy. We then constructed a frontier of efficient policies involving real growth and inflation. In doing so, we found that policy in 1995 Spain displayed some degree of inefficiency with respect to these two policy objectives. We then offer two sets of policy recommendations that, ostensibly, could have helped Spain at the time. The first deals with efficiency independent of the importance given to both growth and inflation by policy makers (we label this set: general policy recommendations). A second set depends on which policy objective is seen as more important by policy makers: increasing growth or controlling inflation (we label this one: objective-specific recommendations).     

Nonparametric least squares estimation in derivative families

Cost function estimation often involves data on a function and a family of its derivatives. Such data can substantially improve convergence rates of nonparametric estimators. We propose series-type estimators which incorporate the various derivative data into a single nonparametric least-squares procedure. Convergence rates are obtained and it is shown that for low-dimensional cases, much of the beneficial impact is realized even if only data on ordinary first-order partials are available. In instances where root-n$n$ consistency is attained, smoothing parameters can often be chosen very easily, without resort to cross-validation. Simulations and an illustration of cost function estimation are included.     

What restrictions do Bayesian games impose on the value of information?

In a Bayesian game players play an unknown game. Before the game starts some players may receive a signal regarding the specific game actually played. Typically, information structures that determine different signals, induce different equilibrium payoffs. In two-person zero-sum games the equilibrium payoff measures the value of the particular information structure which induces it. We pose a question as to what restrictions Bayesian games impose on the value of information. We provide answers for two kinds of information structures: symmetric, where both players are equally informed, and one-sided, where only one player is informed.     

On top responsiveness and strict core stability

Alcalde and Revilla [Journal of Mathematical Economics 40 (2004) 869–887] introduce a top responsiveness condition on players’ preferences in hedonic games and show that it guarantees the existence of a core stable partition. In the present note we strengthen this observation by proving that under top responsiveness even the strict core is non-empty.