Matching Theory & Contract Theory Overview

A Tutorial on Matching Theory & Contract Theory 1 Yanru Zhang

OUTLINE 2 INTRODUCTION MATCHING THEORY Stable Matching with Complete Preference Lists Stable Matching with Relaxed Preference Lists CONTRACT THEORY Optimal Employment Contracts without Uncertainty, Hidden Information, or Hidden Actions Optimal Contracts under Uncertainty Information and Incentives Optimal Contracting with Multilateral Asymmetric Information

INTRODUCTION 3 Economics a field that aims to understand the process by which scarce resources are allocated to their most efficient uses markets playing a central role in this allocation process

INTRODUCTION 4 Examples Matching doctors and hospitals Matching students and high-schools Matching kidneys and patients Investment under risk Insurance Hiring employees Existing Theories of Matching Theory Contract Theory

MATCHING THEORY 5 The Nobel Prize in Economic Sciences 2012 to Lloyd Shapley and Alvin Roth Lloyd Shapley Developed the theory in the 1960s Alvin Roth Generated further analytical developments practical design of market institutions

MATCHING THEORY 6 Definition on Wikipedia a mathematical framework attempting to describe the formation of mutually beneficial relationships over time. Where is it used The U.S. National Resident Matching Program (NRMP) for medical school graduates Public schools in Boston and NYC Many medical and other labor markets across

PART I: Matching Problem with Complete Preference List 7 Three types of matching problems One-to-one (stable marriage) One-to-many (college admissions) Many-to-many (complex scenarios, P2P)

Solution of a Matching Problem 8 We seek to find a stable matching such that There does not exist any pair of players, i and j matches, respectively to players, a and b but.. j prefers a to b and a prefers j to i How can we find a stable matching? many approaches(minimizing sum/ max of ranks, minimizing diff of total ranks, Gale and Shapley algorithm) Most popular: Deferred acceptance or GS algorithm Illustrated via an example

Example 1: Matching partners 9 women and men be matched respecting their individual preferences Adam Fran Geeta Bob Carl Heiki David Irina

Example 1: Matching partners 10 The Gale-Shapley algorithm can be set up in two alternative ways: men propose to women women propose to men Each man proposing to the woman he likes the best Each woman looks at the different proposals she has received (if any) retains what she regards as the most attractive proposal (but defers from accepting it) and rejects the others The men who were rejected in the first round Propose to their second-best choices The women again keep their best offer and reject the rest Continues until no men want to make any further proposals Each of the women then accepts the proposal she holds The process comes to an end sparetier

Here Comes the Story 11 Adam, Bob, Carl, David Geeta, Heiki, Irina, Fran Adam Fran Carl, David, Bob, Adam Irina, Fran, Heiki, Geeta Geeta Bob Geeta, Fran, Heiki, Irina Carl, Bob, David, Adam Heiki Carl Irina, Heiki, Geeta, Fran Adam, Carl, David, Bob Irina David

Search for a Matching 12 X Geeta Adam David Heiki Geeta prefers Carl to Adam! Blocking Pair X Fran Carl Irina Carl likes Geeta better than Fran! Bob

Stable Matching 13 Irina Unfortunately, Irina loves David better! Adam Heiki David Bob and Irina are not a blocking pair Stable Matching: a matching without blocking pairs Bob Fran Geeta Carl Bob likes Irina better than Fran!

Gale-Shapley Algorithm 14 Geeta, Heiki, Irina, Fran Fran Adam Irina, Fran, Heiki, Geeta This is a stable matching Carl > Adam Geeta Bob Geeta, Fran, Heiki, Irina Carl Heiki Irina, Heiki, Geeta, Fran David > Bob Irina David

GS Algorithm 15 1: a c b d e a: 2 1 3 4 5 1, 2, 3, 4 represent men a, b, c, d represent women 2: c a e b d b: 2 1 4 5 3 3: b a e d c c: 1 2 3 5 4 4: c b d e a d: 3 1 4 2 5 5: c d b e a e: 4 3 1 2 5 no blocking pairs

Example 1: Matching partners 16 The setup of the algorithm have important distributional consequences it matters a great deal whether the right to propose is given to the women or to the men If the women propose the outcome is better for them than if the men propose Conversely, the men propose leads to the worst outcome from the women s perspective optimality is defined on each side, difficult to guarantee on both sides The matching may not be unique

Different Stable Matchings 17 1: a c b d a: 2 4 1 3 2: b d c a b: 3 1 2 4 3: c a d b c: 4 2 3 1 4: d b a c d: 1 3 4 2 Maching 1: a c b d a: 2 4 1 3 2: b d c a b: 3 1 2 4 3: c a d b c: 4 2 3 1 4: d b a c d: 1 3 4 2 1 Maching Women get best satisfactory 1, 2, 3, 4 represent men a, b, c, d represent women 3 1: a c b d a: 2 4 1 3 2: b d c a b: 3 1 2 4 3: c a d b c: 4 2 3 1 4: d b a c d: 1 3 4 2 1: a c b d a: 2 4 1 3 2: b d c a b: 3 1 2 4 3: c a d b c: 4 2 3 1 4: d b a c d: 1 3 4 2 2 Maching Men get better satisfactory 4 Maching

Extensions to new markets 18 Prices are not part of the process for the previous implementation Does the absence of a price mechanism in the basic Gale-Shapley algorithm limit its applicability? Not necessarily Algorithms including prices work in much the same way produce stable matches with similar features Matching with prices is closely related to auctions objects are matched with buyers and where prices are decisive Matching vs. Auction Synergistic but more about matching, less about pricing

Example 2: Mini Cost Matching 19 a b c d e 1 1 3 1 2 5 4 4 2 1 3 3 2 4 3 2 5 5 3 5 4 2 1 5 4 A B C D E 2=1+1 A a 8 b B 6 c C 3 A B C D E d D 1 3 3 1 2 4 2 4 5 3 2 1 5 4 1 3 5 2 3 5 5 4 1 2 4 6 a b c d e E e

Cost Minimum but Not Stable 20 1: a c b a: 1 3 2 cost=10 2: b a c b: 2 1 3 3: a b c c: 1 2 3 1: a c b a: 1 3 2 cost=8 2: b a c b: 2 1 3 3: a b c c: 1 2 3

Stability of Matching 21 Blocking pair 1: a c b d e a: 2 1 3 4 5 2: c a e b d b: 2 1 4 5 3 3: b a e d c c: 1 2 3 5 4 4: c b d e a d: 3 1 4 2 5 5: c d b e a e: 4 3 1 2 5

To Remove Blocking Pairs 22 1: a c b d e a: 2 1 3 4 5 2: c a e b d b: 2 1 4 5 3 3: b a e d c c: 1 2 3 5 4 4: c b d e a d: 3 1 4 2 5 5: c d b e a e: 4 3 1 2 5 No blocking pairs any more

PART II: Relaxed Preference Lists 23 National Resident Matching Program Assigning many medical students to many hospitals Complete total order is unrealistic 2: c a e b d Indifferences (ties) in the list 2: (c a) (e b d) Incomplete lists 2: c a e

Stable Matching with Ties (SMT) 24 Theorem: Any SMT instance admits at least one (weakly) stable matching 1: a (c b d) a: 2 4 1 3 2: b d c a b: (3 2 1) 4 3: (c a) d b c: 4 2 (3 1) 4: d b a c d: 1 3 (4 2) 1: a b c d a: 2 4 1 3 2: b d c a b: 1 2 3 4 3: a c d b c: 4 2 3 1 4: d b a c d: 1 3 2 4

25 Stable Matching with Incomplete List (SMI) 1: a c b a: 2 1 3 4 5 2: c a b: 2 1 3: b a c: 1 2 4: c b d e d: 3 1 4 5: c d b e: 4 3 Matching may be partial Theorem [Gale, Sotomayor 1985] There may be more than one stable matchings, but their size is all the same and one of them can be obtained in poly time.

26 Matching Games In communication networks Assign base stations to users Resources to device VMs to jobs in a cloud system

Many-to-Many Game: Femto-cells 27 Femto-cell access points (FAPs) are low-power wireless access points that operate in macro-cells access points (MAPs) licensed spectrum using residential DSL or cable broadband connections Challenges: Random spatial placement of FAPs and huge interference MAPs to FAPs, FAPs to MAPs and FAPs to FAPs interference No distributed mechanism to handle the final users (FUs)-FAPs and FAPs-WOs allocation

Contract Theory 28 Definition on Wikipedia studies how economic actors can and do construct contractual arrangements, generally in the presence of asymmetric information A standard practice in the contract theory to solve the problem under certain numerical utility structures represent the behavior of a decision maker apply an optimization algorithm to identify optimal decisions

Major Topics in Contract Theory 29 Bilateral contracting Under no uncertainty Under hidden information or hidden action multilateral contracting under hidden information or hidden actions auction theory long-term contracts incomplete contracts

Contracting Situation 30 Employer and employee a manager hiring a worker a farmer hiring a sharecropper a company owner hiring a manager contracting parties are rational individuals aiming to achieve the highest possible payoff a court between two parties who operate in a market economy with a well-functioning legal system A system any contract the parties decide to write will be enforced perfectly The penalties for breaking the contract will be sufficiently severe no contracting party will ever consider not honoring the contract

Problems in Contract Theory 31 transaction is a exchange of goods or services for money What is the price per unit the parties shall agree on? Are there penalty or reward? transaction is an insurance contract determining how the terms vary with the underlying risk with the private information the insuree or the insurer have about the nature of the risk

Example 1: Optimal Employment Contracts without Uncertainty, Hidden Information, or Hidden Actions 32 a situation involving only two parties facing no uncertainty and no private information or hidden actions U(l,t), employer's utility l, the quantity of employee time the employer has acquired t, the quantity of "money" that he has at his disposal (the "output" that this money can buy) initial endowment, ( 1, 1)=(0,1) u(l,t), employee utility l, the quantity of time the employee has kept for herself t, the quantity of money that she has at her disposal initial endowment, ( 2, 2)=(1,0)

PART I: Optimal Employment Contracts without Uncertainty, Hidden Information, or Hidden Actions 33 Without any trade The employer gets no employee time but has all the money The employee has all of her time for herself but has no money each achieve an initial utility of =U(0,1) and =u(1,0) Utility functions U(l,t) and u(l,t) strictly increasing and concave both individuals can increase their joint payoff exchanging labor services l for money/output

Example 1: Optimal Employment Contracts without Uncertainty, Hidden Information, or Hidden Actions 34 Question raised How many hours of work will the employee be willing to offer? What (hourly) wage will she be paid? the joint surplus maximization problem: Max U(l1,t1)+ u(l2,t2) , reflect both the individuals' respective reservation utility levels and , and their relative bargaining strengths Subject to l1+l2= 1+ 2=1and t1+t2= 1+ 2=1

Example 1: Optimal Employment Contracts without Uncertainty, Hidden Information, or Hidden Actions 35 Take the first-order conditions Ul+ ul=0=Ut+ ut Ul/Ut=ul/ut joint surplus maximization is achieved when the marginal rates of substitution between money and leisure for both individuals are equalized

Example 1: Optimal Employment Contracts without Uncertainty, Hidden Information, or Hidden Actions 36 The highest possible utility that the employee can get: max u(l2, t2) Subject to U(1-l2, 1-t2) The highest payoff the employer can get: max U(l1,t1) Subject to u(1-l1, 1-t1)

PART II: Optimal Contracts under Uncertainty 37 There is more uncertainty in reality than Example 1 Insurance employees are insured against economic downturns A question concerning these insurance schemes is how much risk should be absorbed by employers how much by employees Enrich Example 1 by introducing uncertainty analyze the question of optimal risk allocation

Example 2: Pure Insurance 38 In two possible future states of nature, L and H L, an adverse output shock, or a "recession" H, a good output realization, or a "boom" a pure insurance problem without production disregard time endowments in the time/output bundles (l,t) Adopt the consumption bundles (tL,tH) the state of nature influences only the value of output E(tL,tH) for the employer e(tL,tH) for the employee

Example 2: Pure Insurance 39 the initial endowments for each individual in each state: ( 1L, 1H)=(1,2), for individual 1 (employer) ( 2L, 2H)=(1,2), for individual 2 (employee) The initial utility (before the state of nature is realized) =E(1,2) for employer =e(1,2) for employee the ex ante utility function E(tL,tH), for employer e(tL,tH), for employee

Example 2: Pure Insurance 40 the cosinsurance optimization problem: Max E(tL,tH)+ e(tL,tH) Take the first-order conditions EL+ eL=0=EH+ eH EL/EH=eL/eH joint surplus maximization is achieved when the marginal rates of substitution between nature L and H for both individuals are equalized pure exchange under certainty can be transposed entirely to the case with uncertainty

Von NeumannMorgenstern Utility Functions 41 two important elements are hidden in the optimal insurance contract The ex post utility once the state of nature has been realized The probability of each state occurring ex post utility functions U(t) for the employer u(t) for the employee Pj (0,1), the probability of occurrence of any particular state of nature j the ex ante utility function is the expectation over ex post utility outcomes: E(t1L,t1H)= pLU(t1L)+ pHU(t1H) e(t2L,t2H)= pLu(t2L)+ pHu(t2H)

Example 3: Optimal Employment Contracts under Uncertainty 42 extended to the Optimal Employment Contracts under Uncertainty problem the framework of von Neumann and Morgenstern of Example 2 the contracting problem of Example 1 with two goods, leisure l and a consumption good t (l1L,t1L) and (l1H,t1H) two different state-contingent time/output bundles of the employer (l2L,t2L) and (l2H,t2H) Two different state-continent time/output bundles of the employee ( ij, ij) denote initial endowments i=1, 2; j=L, H

Example 3: Optimal Employment Contracts under Uncertainty 43 the optimal contracting problem for the employer max[pLU(l1L,t1L)+pHU(l1H,t1H)] Subject to pLu(l2L,t2L)+pHu(l2H,t2H) l1j+l2j 1j+ 2j t1j+t2j 1j+ 2j Where =pLu( 2L, 2L)+pHu( 2H, 2H)

PART III: Information and Incentives 44 Two general types of asymmetric imformation problems hidden-information problem---- adverse selection relevant characteristics of the employee are hidden from her employer distaste for certain tasks, her level of competence hidden-action problem---- moral hazard employee's actions that are hidden from the employer whether she works or not, how hard she works, how careful she is

Adverse Selection 45 Screening problems the party making the contract offers is the uninformed party the uninformed party attempts to screen the different pieces of information the informed party has signaling problems the informed party makes the contract offers the party making the offer attempts to signal to the other party what it knows

Screening Problems 46 In practice, employers try to overcome the informational asymmetry (to improve their pool of applicants) by hiring only employees with some training only high school and college graduates more-able employees have a lower disutility of education more willing to educate themselves than less-able employees pay greater than market-clearing wages attract better applicants How efficient can contracting under asymmetric information be?

Screening Problems 47 consider an employer who contracts with two possible types of employees a "skilled" employee and an "unskilled" one does not know which is which employee productivity is private information All employee types would respond by "pretending to be skilled" to get the higher wage revelation principle employer offers two employment contracts one destined to the skilled employee the other to the unskilled one make sure that each contract is incentive compatible each type of employee wants to pick only the contract that is destined to her the problem reduces to a standard contracting problem Second Price Auction

Example 4: Screening Problems 48 Extend the previous examples with uncertainty with private information added Suppose that employee time and output enter additively: U[ (1-l)-t] for the employer u( l+t) for the employee (1-l), the employee time sold to the employer l, the time the employee keeps for herself t, the monetary/output transfer from the employer to the employee , a positive constant , measures the "unit value of time," or the skill level of the employee U(l1,t1), u(l2,t2)

Example 4: Adverse selection 49 The utility function: U[ (1-l)-t] for the employer u( l+t) for the employee , the state of nature The employee knows whether she is skilled with a value of time H or unskilled, with a value of time L< H The employer knows only that the probability of facing a skilled employee is pH

Example 4: Adverse selection 50 in state j the employee's endowment j = j relevant reservation utility is H =u( H), employer faces a skilled employee L=u( L), employer faces an unskilled employee incentive compatibility constraints the employee's time is more efficient when sold to the employer >1 u(ti) u( j)