03_Matching_Markets

• have two sets and want to create pairs based on certian preferences on both sides…

• along with other properties

• TUM

• kidney exchange

• med school residencies program

Participants:

• set of men M

• set of women W

• one to one matching -> each man can be matched to one woman and vice-versa

Preferences:

• each man has strict preferences over women and vice versa

• preference ranking of m1 -< w1 >m1 w2 >m1 w3 ….

• woman is acceptable to m if m prefers w to being unmatched

• matching: set of pairs (m,w) such that each individual has one partner

• matching is stable if:

  • every individual matched with acceptable partner

  • there is no man-woman pair that would rather match with each other than with their assigned partner (would not switch)

  • => if would exist -> so called blocking pair that would make match unstable…

• Men and Women rank all potential partners (all acceptable ones…)

• algorithm:

  • each man proposes to highest woman on his list

  • woman make tentative match based on preferred offer and rejects other offers

  • each rejected man removes rejecting woman from list and makes new offer (to next in line…)

  • continue until no more rejection offers happen at which point implement tentative matches

tentative:= not fixed / provisional…

• yes

• algo must end in finite number of rounds

• suppose m,w matched but m prefers w’

  • at some point m proposed to w’ but was rejected

  • at that point, w’ preffered her tentative match m’ to m

  • as algo goes forward, w’ can only do better (as reject current only if better match comes along…)

  • wo w’ prefers final match to m

• => no blocing pairs…

• group of students to be matched, two in each room

• A: B>C>D

• B: C>A>S

• C:>B>D

-> NO STABLE MATCH

• whoever pairs with D wants to change and can find willing partner (circular change…)

• stability in matching markets not a given even if each match involves just two people

• but if eixist, can be found in polytime… (NP complete if we were to match three people…)

• maybe w holds m’s offer for a longer time and then rejects it but only after market has cleared

• maybe m makes exploding offer to w and she has to decide before knowing her other optinos…

• => in general, no guarantee that market will be orderly…

• priority matching

• men and women submit preferences

  • each man-woman pair gets priority based on mutual rankings

  • algo matches all priority 1 couples and takes them out of marked

  • new priorities assigned and process iterates….

• in the man proposing version -> man has best posslble matching in stable matching (man optimal)

• and woman gets worst outcome in any stable matching

• no

• -> e..g everyone truthful but woman reports that m in unacceptable -> will get better matching…

• there is no matching mechanism that is strategy-proof and always generates a stable outcome given reported preferences

• => both, DA and priority lead to stable matches thus not strategy proof….

• yes -> can only improve by switch to truthful…

• no -> e.g. other side has no preference (e.g. student housing…)

• => requires other criteria

• N individuals and N houses

• each individual has strict preference over houses

• Goal: assign each individual to a house

• each student gets priority (perhaps randomly assigned)

• pick houses in order of their priority

• => can be very unfair ex-post

• strategy proof

  • -> individual with first pick gets preferred house so no incentive to lie

  • indivdual with second pick gets preferred house among remaining houses so again no reason to lie…

• efficient

  • individual with priority one does not want to trade

  • given that she is out, inividual with prio two also does not want to trade…

• implement some form of trading scheme

• -> e.g. top trading cycles by shapley and scarf

• each person points to most preferred house

• each hose points to its owner

• => creates directed graph with at least one cycle

• remove all cycles, assigning people to the house they are pointing at

• repeat using preference list where assigned houses have been deleted

• stable outcomes in situations where only one side of the markes has preferences

• core consists of all feasible unblocked assignments

• => blocked:= coalition of agents blocks if, from their initial endowments, there is an assignment among themselves that they all prefer to the candidate assignment.

• TTC mechanism leads to unique core assignment in the housing market

• blocking coalition cannot involve those matchied at round one (all agents get first choice)

• cannot involve only those matched in first two rounds (cant improve round 1 sutdents, and to improve round two, need to displace round one sutent, making him worse off)

• … (and so on by induction)

• assignments at round one necesarry or else these agents would block and inductively for rounds 2,3,…

• yes

• proof:

• for any agent j assigned at round n:

• no change in his report can give him a house that was assigned in earlier rounds

• no house assigned in a later round will make him better off…

• kidney exchange

• Donor Patient Pairs -> incompatible with each other…

• -> Donor of imcompatile pair donates to patient at top of waiting list

• patient of incompatilbe pair goes to top of wait list

(-> list exchange)

=> can make use of TTC…

• => e.g. hospital / courses want to match to more than a single partner…

• quota on the receiving side

• -> make tentative matchind and accept up to quota and then begin to reject or exchange if get better proposal…

• -> rejected propose to next preference

• -> when no rejections happen anymore -> implement tentative matches…

• quota on offering side

• each propose to all of its most preffered partners (up to quota)

• receiving side makes tentative match based on preferred offer and rejects other offers or all if not acceptable

• each proposant receiving rejections removes them from list and makes new offers from lower down…

• -> continue untli no more rejections or offres at which point implement tentative matches…

• at least one stable matching exists

• rural hospital theorem: all hospitals fill same number of positions across stable matchings and the same doctors are assigned a position

• but no stable matching is strategy proff for the hospitals, even in the hospital proposing DA algo….