Preliminary and Incomplete Matching with Heterogeneity John Hillas Benoit Julien Ian King University of Auckland University of Miami University of Auckland June 2000 Prepared for presentation at the NBER Summer Institute 2000 1. INTRODUCTION Individuals are constrained by the number of hours in a day that they have to work with. Also, employers are often constrained by the number of jobs that they have to fill. These facts make the analysis of equilibria with capacity constraints, developed by Peters (1984), particularly relevant to the labor market. Recent work by Montgomery (1991), Burdett, Shi, and Wright (2000), Julien, Kennes, and King (2000a,b), Shi (1999), and Shimer (2000) has explored the implications of this insight. One major implication is that, when buyers randomize in their decision about which seller to approach, the equilibrium matching function generated by this process in large economies shares many properties with the matching function commonly used in macroeconomics (for example, Pissarides (1990)). Thus, these "directed search" models can be used to analyse factors that influence this matching process. The existence of heterogeneity in a matching problem can either worsen or improve the problem of coordination, depending on the nature of the heterogeneity. In this paper, we explore this relationship in a simple competing-auction model with two-sided heterogeneity, two buyers, and two sellers. We demonstrate that, in the presence of either strict supermodularity or strict submodularity, the unique equilibrium has buyers playing pure strategies and the equilibrium allocation is efficient. With strict supermodularity, the equilibrium exhibits positive assortative matching, and with strict submodularity it exhibits negative assortative matching. However, when matches are both supermodular and submodular then multiple equilibria exist. In particular, in this case, a coordination problem and equilibria with mixing exist. Several interesting special cases have this property: homogeneous agents, one-sided heterogeneity, and additive two-sided heterogeneity. In this setting, the mixing equilibrium is inefficient but, given the coordination friction, is constrained-efficient in the sense that a constrained planner would assign the same probabilities for buyer locations if the planner were unable to coordinate. Thus, if heterogeneity is either strictly supermodular or submodular, then it can act as a "coordination device" (as argued by Coles and Eeckhout (1999), assuming supermodularity) in the sense that it rules out the mixing equilibrium present in the homogenous agent case. However, if matching is both submodular and supermodular, then the coordination problem is strictly increasing in the magnitude of heterogeneity. 1 2. THE MODEL The market consists of 2 buyers and 2 sellers, all of whom are risk neutral, and seek to maximize their expected payoffs. Each seller has one unit of a good to sell. If she sells at price p then her payoff is p. If she is unable to sell, then her payoff is zero. Each buyer wants to purchase one unit of the good, and is willing to pay up to his valuation of the good. The valuation that buyer j places on the good offered by seller i is denoted S ij for i, j ∈ {1,2} . We place the following restrictions on S: S11 ≥ S 12 , S 21 ≥ S 22 (2.1) If buyer j purchases from seller i at price p ij , his payoff is S ij − p ij . If he is unable to buy then his payoff is zero. Each buyer has only one opportunity to buy, and must choose only one seller to visit. The order of play is as follows. First, sellers announce reserve prices σ ij (in general, these are different for the different buyers -- we allow for price discrimination). Second, after observing σ , buyers choose which seller to approach. Finally, once buyers have been allocated to sellers, goods are sold according to a bidding game. Equilibria are solved through backwards induction. 2.1 The Bidding Game Let wi denote the payoff for seller i. In the bidding game, this is a function of the allocation of buyers:  0 if no buyers visit σ  if only buyer 1 visits wi =  i1 (2.2) σ i 2 if only buyer 2 visits S i2  if both buyers visit 2 Clearly, if no buyers visit seller i, then her payoff will be zero. If only one approaches, then the seller sells at the reserve price σ ij . If both buyers visit, then the bidding game determines that the good is sold to the buyer with the highest valuation (buyer 1) at the price of the second-highest valuation S i 2 . 2.2 Buyers' Location Choices Given the reserve price matrix σ , buyer j's payoff from approaching seller i is given by:  S ij − σ ij if alone Rij =  (2.3)  S ij − S i 2 if not alone Buyer payoffs in this location subgame can be represented in the normal form: Buyer 2 Seller 1 Seller 2 Buyer 1 Seller 1 S11 − S12 , 0 S11 − σ11 , S 22 −σ22 Seller 2 S 21 − σ21 , S12 − σ12 S 21 − S 22 , 0 Table 1 Let Pij denote the probability that buyer j assigns to visiting seller i. Buyer j's expected payoff from visiting seller i is given by: Π ij = (1 − Pi , − j )( S ij − σ ij ) + Pi , − j ( S ij − S i 2 ) (2.4) 3 The following 9 distinct possible cases exist for buyer 1: 1. S11 − S12 > S 21 − σ21 and S11 −σ11 > S 21 − S 22 2. S11 − S12 > S 21 − σ21 and S11 −σ11 = S 21 − S 22 3. S11 − S12 > S 21 − σ21 and S11 −σ11 < S 21 − S 22 4. S11 − S 12 = S 21 − σ21 and S11 −σ11 > S 21 − S 22 5. S11 − S 12 = S 21 − σ21 and S11 −σ11 = S 21 − S 22 6. S11 − S 12 = S 21 − σ21 and S11 −σ11 < S 21 − S 22 7. S11 − S12 < S 21 − σ21 and S11 −σ11 > S 21 − S 22 8. S11 − S12 < S 21 − σ21 and S11 −σ11 = S21 − S 22 9. S11 − S12 < S 21 − σ21 and S11 −σ11 < S 21 − S 22 Restricting reserve prices to be no greater than valuations (σ ij ≤ S ij ) , there are 4 distinct cases for buyer 2: A. S22 > σ22 and S12 > σ12 B. S22 > σ22 and S12 = σ12 C. S22 = σ22 and S12 > σ12 D. S22 = σ22 and S12 = σ12 4 Lemma 1: The buyers' subgame has the following equilibria in pure strategies: Case Up, Left Up, Right Down, Left Down, Right 1A yes 1B yes 1C yes yes 1D yes yes 2A yes 2B yes yes 2C yes yes 2D yes yes yes 3A 3B yes 3C yes 3D yes yes 4A yes yes 4B yes yes 4C yes yes yes 4D yes yes yes 5A yes yes 5B yes yes yes 5C yes yes yes 5D yes yes yes yes 6A yes 6B yes yes 6C yes yes 6D yes yes yes 7A yes yes 7B yes yes 7C yes yes 7D yes yes 8A yes yes 8B yes yes yes 8C yes yes 8D yes yes yes 9A yes 9B yes yes 9C yes 9D yes yes Proof: Follows from exhaustive examination of Table 1. QED Notice that, in every case except 3A, some equilibrium exists in this subgame. 5 Lemma 2: Wherever mixing equilibria exist, visit probabilities are given by: S 12 − σ 12 P11 = S 22 + S 12 − σ 22 − σ 12 S 22 − σ 22 P12 = S 22 + S 12 − σ 22 − σ 12 S 11 + S 22 − S 21 − σ 11 P21 = S 22 + S 12 − σ 22 − σ 12 S 21 + S 12 − S 11 − σ 21 P22 = S 22 + S 12 − σ 22 − σ 12 Proof: Buyers choose their probabilities to be indifferent between which seller is visited. Setting Π 1 j = Π 2 j , j = 1, 2, in (2.4), one obtains the above values for P. QED 2.3 Sellers' Reserve Price Decisions We now turn to consider sellers' optimal choices of σ . We start by considering equilibria in pure strategies. Proposition 1: When considering equilibria in pure strategies: a) No equilibria exist where both buyers visit the same seller. b) Equilibria with positive assortative matching exist if and only if match valuations are supermodular: S11 + S22 ≥ S12 + S21 (2.5) 6 c) Equilibria with negative assortative matching exist if and only if match valuations are submodular: S11 + S 22 ≤ S12 + S 21 (2.6) d) Positive assortative and negative assortative matching equilibria co-exist if and only if match valuations are both supermodular and submodular: S 11 + S 22 = S 12 + S 21 (2.7) Proof: (Sketch) a) Examination of the table in Lemma 1 reveals that the following restrictions must be imposed for (Up, Left) to be an equilibrium of the buyers' subgame: σ21 ≥ S 21 − ( S11 − S12 ) , σ22 = S 22 For all possible ranges of σ 1 = (σ 11 , σ 12 ) , one can find a vector * * * σ2 = (σ21 , σ22 ) which violates the above restrictions and which yields a strictly larger payoff for seller 2 in all equilibria of the (σ 1 , σ 2 ) subgame. All * possible (Down, Right) equilibria are ruled out similarly. b) Consider the following candidate equilibrium: P * = 1 , P22 = 1 11 * σ 11 = S 11 − ( S 21 − S 22 ) , σ 12 = S 12 , σ * = S 21 − ( S 11 − S 12 ) , σ * = S 22 * * 21 22 This is an equilibrium of the buyers' subgame (case 5D). Also, for every σ 1 , one can demonstrate that there exists some equilibrium of the (σ 1 , σ 2 ) * subgame where seller 1 is no better off, iff S is supermodular. Similarly, for every σ 2 , one can demonstrate that there exists some equilibrium of the 7 (σ 1 , σ 2 ) subgame where seller 2 is no better off. Thus, (σ 1 , σ 2 ) is a * * * subgame perfect equilibrium. Similarly, one can find subgame perfect equilibria for all P * = 1 , P22 = 1 11 * σ 11 = S 11 − ( S 21 − S 22 ) , σ 12 ∈ [0, S 12 ] , σ * ∈ [0 , S 21 ] , σ * = S 22 * * 21 22 iff S is supermodular. c) Consider the following candidate equilibrium: P11 = 0 , P22 = 0 * * σ 11 = S 11 , σ 12 = S 12 , σ * = S 21 − ( S 11 − S 12 ) , σ * = S 22 * * 21 22 This is an equilibrium of the buyers' subgame (case 6D). Also, for every σ1 , one can demonstrate that there exists some equilibrium of the (σ 1 , σ 2 ) * subgame where seller 1 is no better off. Similarly, for every σ2 , one can demonstrate that there exists some equilibrium of the (σ 1 , σ 2 ) subgame * where seller 2 is no better off iff S is submodular. Thus, (σ 1* , σ 2 ) is a * subgame perfect equilibrium. Similarly, one can find subgame perfect equilibria for all P11 = 0 , P22 = 0 * * σ 11 ∈ [0, S 11 ] , σ 12 = S 12 , σ * = S 21 − (S 11 − S 12 ) , σ * ∈ [0, S 22 ] * * 21 22 iff S is submodular. d) Follows immediately from (b) and (c). Discussion Notice that positive (negative) assortative matching maximizes aggregate surplus when match valuations are supermodular (submodular). Thus, the pure strategy equilibria maximize aggregate surplus. When matches are both supermodular and submodular, the allocation of buyers to sellers does not affect aggregate surplus, 8 as long as both buyers do not visit the same seller (which cannot occur in the pure strategy equilibria). However, in this case, pure strategy equilibria with both positive and negative assortative matching exist. This implies the existence of equilibria with mixing. At this point, it is useful to consider conditions under which this can occur. Lemma 3: Match valuations are both supermodular and submodular in the following special cases: a) Either buyers or sellers are homogeneous. b) Heterogeneity is additive. Proof: Straightforward. In either of these two cases, equilibria exist where buyers mix in their location choice. These equilibria are clearly less efficient than the pure strategy equilibria, because they have an associated non-zero probability that both buyers will visit the same seller. However it can be shown that buyers choose the same probabilities that a planner would, if the planner were unable to avoid the coordination problem. Proposition 2: Where equilibria exist with buyers mixing in their location choice these equilibria are constrained-efficient and the expected matching rate is strictly decreasing in the magnitude of the heterogeneity. Proof: In the works. 9 CONCLUDING DISCUSSION Heterogeneity can either worsen or improve coordination problems, depending on the form that it takes. If the cardinality of the types of agents and the number of agents is the same, and match valuations are either strictly supermodular or strictly submodular, then the existence of heterogeneity can eliminate inefficient equilibria with mixing. Otherwise, when mixing equilibria exist, then heterogeneity can worsen the coordination problem. 10 REFERENCES Burdett, K., S. Shi, and R. Wright, (2000) "Pricing and Matching with Frictions", University of Pennsylvania manuscript. Cao, M., and S. Shi, (1999) "Coordination, Matching, and Wages", Queen's University manuscript. Coles, M., and J. Eeckhout, (1999) "Heterogeneity as a Coordination Device", University of Pennsylvania manuscript. Hosios, A., (1990) "On the Efficiency of Matching and Related Models of Search and Unemployment", Review of Economic Studies, 57, 279-298. Julien, B., J. Kennes, and I. King (2000a) "Bidding for Labor" Review of Economic Dynamics, forthcoming. Julien, B., J. Kennes, and I. King (2000b) "Matching, Foundations", University of Auckland manuscript. Montgomery, J., (1991) "Equilibrium Wage Dispersion and Interindustry Wage Differentials", Quarterly Journal of Economics, 106, 163-179. Peters, M., (1984) "Equilibrium with Capacity Constraints and Restricted Mobility", Econometrica, 52, 1117-1129. Pissarides, C., (1990) Equilibrium Unemployment Theory, Basil Blackwell, Oxford. Shi, S., (1998) "Frictional Assignment", Queen's University manuscript Shi, S., (1999) "Product Market and the Size Wage Differential" Queen's University manuscript. Shimer, R., (2000) "Job Auctions", Princeton University manuscript. 11