یک الگوریتم پذیرش معوق اصلاح شده برای تطبیق بسیار زیاد بازار با اثرات جانبی میان شرکت ها

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.

Since the seminal paper of Gale and Shapley (1962), two-sided matching problems have been extensively analyzed by many researchers.1 Pairwise stability is the main solution concept used in two-sided matching problems. In a stable matching, each agent cannot be better off by rejecting his current partner and no pair of agents prefers each other over their current partner. Gale and Shapley (1962) showed the existence of a stable matching by the well-known deferred acceptance (DA) algorithm in a marriage market. They also showed that interests of agents on the same side coincide in the set of stable matchings in that there exists a stable matching that all men (or women) weakly prefer over any other stable matching. In practice, this property is important when a social planner chooses a single outcome from multiple stable matchings. The coincidence of interests in the set of stable matchings is extended to more general models (cf. Kelso and Crawford (1982) and Roth (1984)). These studies typically assume that each agent’s preferences depend only on his current partners. In labor markets, however, it is natural to consider that each firm’s preferences depend not only on workers whom it hires, but also on workers whom its rival firms hire, since they compete among themselves in a market. There has been a growing literature on the market with externalities (cf. Sasaki and Toda (1996), Hafalir (2008), Mumcu and Saglam (2010) and Bando (2012)).2 In particular, Bando (2012) introduced the notion of quasi stability in a many-to-one matching market with externalities among firms. It was shown that if each firm’s preferences satisfy substitutability, increasing choice and no-external effect by unchosen workers, then there exists a quasi stable matching. The main purpose of this paper is to consider the existence of a worker-optimal quasi stable matching and a worker-worst quasi stable matching under the same preference domain of Bando (2012). We first examine the construction in the existence proof by Bando (2012). The analysis reveals that we can find the worker-worst quasi stable matching by iteratively satisfying a quasi blocking pair from an initial matching in which no agents are matched. However, we cannot directly apply this algorithm to find a worker-optimal stable matching. Similarly, a sequential version of the DA algorithm in which (i) an unmatched worker proposes to his most preferred firm that has not rejected him and (ii) the proposed firm chooses the acceptable workers based on the current matching may not find a worker-optimal quasi stable matching or a quasi stable matching. The failure is caused by the fact that firms may have incentives to rehire a worker that it has rejected earlier. This paper provides a modified DA algorithm that finds a worker-optimal quasi stable matching. The algorithm is a DA algorithm where (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. The property (ii) rules out the incentive that firms rehire workers in the algorithm and guarantees that the termination of the algorithm produces a worker-optimal quasi stable matching. We also show that the modified DA algorithm can be generalized into a fixed point algorithm similar to those defined by Adachi (2000) and Echenique and Oviedo (2004).3 The advantage of the fixed point approach is that the same procedure can be used to find both extremes by changing the starting point. In the fixed point method, the set of quasi stable matchings is characterized as the set of fixed points of an increasing function from a finite lattice to itself, and Tarski’s fixed point theorem is used to show a lattice structure of the set of quasi stable matchings. The partial order used in this model is the same as in Ostrovsky (2008). Another natural question is whether it is a dominant strategy for each worker to report true preferences under the mechanism that assigns a worker-optimal quasi stable matching. In one-to-one matching market without externalities, Dubins and Freedman (1981) and Roth (1982) showed that the truth-telling is a dominant strategy for each worker under the worker-optimal stable matching mechanism.4 Unfortunately, this property does not hold when externalities exist. The rest of this paper is organized as follows. Section 2 introduces the model and the stability concepts. Section 3 analyzes the algorithm considered in Bando (2012) and the sequential DA algorithm with worker-proposing. In Section 4, we define the modified DA algorithm and show that it finds a worker-optimal quasi stable matching. In Section 5, the fixed point algorithm is defined. Section 6 discusses some additional results.