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.     

A modified deferred acceptance algorithm for conditionally lexicographic-substitutable preferences

We study a class of preferences that generalize substitutable ones and allows complementarities in a college admissions model. We show that a stable matching exists under this class of preferences by using an algorithm which we call the Conditional Deferred Acceptance Algorithm. Furthermore, we show that the algorithm is strategy-proof for the student side if we assume in addition a law of aggregate demand adapted to our setting.     

The substitutes condition and the lattice structure of the set of stable allocations

In the many-to-one matching model with contracts, I show that there is no restriction on preferences weaker than substitutable preferences which guarantees that the set of stable allocations is a lattice. Thus, when contracts are not substitutes, removing agents from the economy may decrease the payoffs to existing agents on both sides of the market.     

A note on strategy-proofness from the doctor side in matching with contracts

In a general one-to-many matching model with contracts, Hatfield and Milgrom (Ame Econ Rev 95:913–935, 2005) show that the doctor optimal stable rule is strategy-proof from the doctor side. We strengthen their result by showing that this rule is in fact the unique stable rule that is strategy-proof from the doctor side.     

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.     

A one-sided many-to-many matching problem

This study discusses a one-sided many-to-many matching model wherein agents may not be divided into two disjoint sets. Moreover, each agent is allowed to have multiple partnerships in our model. We restrict our attention to the case where the preference of each agent is single-peaked over: (i) the total number of partnerships with all other agents, and (ii) the number of partnerships that the agent has with each of the other agents. We represent a matching as a multigraph, and characterize a matching that is stable and constrained efficient. Finally, we show that any direct mechanism for selecting a stable and constrained efficient matching is not strategy-proof.     

Stable many-to-many matchings with contracts

We consider several notions of setwise stability for many-to-many matching markets with contracts and provide an analysis of the relations between the resulting sets of stable allocations for general, substitutable, and strongly substitutable preferences. Apart from obtaining “set inclusion results” on all three domains, we introduce weak setwise stability as a new stability concept and prove that for substitutable preferences the set of pairwise stable matchings is nonempty and coincides with the set of weakly setwise stable matchings. For strongly substitutable preferences the set of pairwise stable matchings coincides with the set of setwise stable matchings.     

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.     

Many-to-one matching markets with externalities among firms

We study a labor market described by a many-to-one matching market with externalities among firms in which each firm’s preferences depend not only on workers whom it hires, but also on workers whom its rival firms hire. We define a new stability concept called weak stability and investigate its existence problem. We show that when the preferences of firms satisfy an extension of substitutability and two new conditions called increasing choice and no external effect by an unchosen worker, then a weakly stable matching exists. We also show that a weakly stable matching may fail to exist without these restrictions.     

Agreement toward stability in matching markets

For firms with responsive preferences, we prove that the set of stable matchings unanimously preferred by workers to any firm quasi-stable matching has a lattice structure. This follows from a generalization of the Decomposition Lemma. The result does not hold when firms have q-substitutable preferences. Nevertheless, we show that the set of stable matchings unanimously preferred by workers to a firm quasi-stable matching contains an element which is unanimously least preferred by workers, and most preferred by firms. When a firm quasi-stable matching is fed into our extension of the Deferred Acceptance algorithm (where firms propose), the existence of this matching guarantees the success of the algorithm.     

A modified deferred acceptance algorithm for many-to-one matching markets with externalities among firms

We consider a many-to-one matching market with externalities among firms where each firm’s preferences satisfy substitutability, increasing choice and no external effect by unchosen workers, which are defined by  Bando (2012). We first illustrate that a sequential version of the deferred acceptance (DA) algorithm with worker-proposing may not find a worker-optimal quasi stable matching. Then, we provide a modified DA algorithm in which (i) each worker simultaneously proposes to his most preferred firm that has not rejected him and (ii) each firm chooses its acceptable workers from the cumulative set of workers who have ever proposed to it, assuming that the other workers proposing to its rival firms are hired. We show that this algorithm finds a worker-optimal quasi stable matching. We also show that this algorithm can be generalized into a fixed point algorithm.     

Probabilistic strategy-proof rules over single-peaked domains

It is proved that every strategy-proof, peaks-only or unanimous, probabilistic rule defined over a minimally rich domain of single-peaked preferences is a probability mixture of strategy-proof, peaks-only or unanimous, deterministic rules over the same domain. The proof employs Farkas’ Lemma and the max-flow min-cut theorem for capacitated networks.     

The efficiency of training and hiring with intrafirm bargaining

This paper demonstrates that firms hire and train workers efficiently in a matching and intrafirm bargaining economy when the Hosios condition holds and returns to scale are constant. This conclusion stands in contrast to the prevailing view that training costs are a source of inefficiency in imperfect labor markets. The efficiency of the competitive economy relies on the ability of large firms to take into account the negative impact of the training rate on the wages negotiated inside the firm through intrafirm bargaining: untrained workers accept a wage reduction in compensation for potential training that is accessible only following employment. This intrafirm bargaining process solves efficiency problems associated with training costs that would otherwise lead to inefficient hiring and training decisions. This conclusion holds true for both specific and general human capital.     

Labour market recruiting with intermediaries

We consider a Rothschild–Stiglitz–Spence labour market model and employ a centralised mechanism to coordinate the efficient matching of workers to firms. This mechanism can be thought of as operated by a recruitment agency, an employment office or head hunter. In a centralised descending-bid, multi-item procurement auction, workers submit wage-bids for each job and are assigned stable jobs as equilibrium outcome. We compare this outcome to independent, sequential hiring by firms and conclude that, in general, a stable assignment can only be implemented if firms coordinate to some extent.      

Are shirking and leisure substitutable? An empirical test of efficiency wages based on urban economic theory

Recent theoretical work has examined the spatial distribution of unemployment using the efficiency wage model as the mechanism by which unemployment arises in the urban economy. This paper extends the standard efficiency wage model in order to allow for behavioral substitution between leisure time at home and effort at work. In equilibrium, residing at a location with a long commute affects the time available for leisure at home and therefore affects the trade off between effort at work and risk of unemployment. This model implies an empirical relationship between expected commutes and labor market outcomes, which is tested using the Public Use Microdata sample of the 2000 U.S. Decennial Census. The empirical results suggest that efficiency wages operate primarily for blue collar workers, i.e. workers who tend to be in occupations that face higher levels of supervision. For this subset of workers, longer commutes imply higher levels of unemployment and higher wages, which are both consistent with shirking and leisure being substitutable.     

Strategy-proof fuzzy aggregation rules

We investigate the structure of fuzzy aggregation rules which, for every permissible profile of fuzzy individual preferences, specify a fuzzy social preference. We show that all fuzzy aggregation rules which are strategy-proof and satisfy a minimal range condition are dictatorial. In other words, there is an individual whose fuzzy preferences determine the entire fuzzy social ranking at every profile in the domain of the aggregation rule. To prove this theorem, we show that all fuzzy aggregation rules which are strategy-proof and satisfy the minimal range condition must also satisfy counterparts of independence of irrelevant alternatives and the Pareto criterion. There has been hardly any treatment of the manipulability problem in the literature on social choice with fuzzy preferences.     

Centralized allocation in multiple markets

We provide a characterization result for the problem of centralized allocation of indivisible objects in multiple markets. Each market may be interpreted either as a different type of object or as a different period. We show that every allocation rule that is strategy-proof, Pareto-efficient and nonbossy is a sequential dictatorship. The result holds for an arbitrary number of agents and for any preference domain that contains the class of lexicographical preferences.     

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.     

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.     

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