An Evolutionary Model for the Stable Marriage Problem

PAGE 1

ANEVOLUTIONARYMODELFORTHESTABLEMARRIAGEPROBLEM BY SARAHROSEKARR AThesisSubmittedtotheDivisionofMathematics/Economics NewCollegeofFlorida inpartialfulllmentoftherequirementsforthedegree BachelorofArts UnderthesponsorshipofDavidT.Mullins Sarasota,FL June,2008

PAGE 3

iii Acknowledgments Thanksrstandforemostto:Dr.DavidMullins.Withouthimandhisremarkablepatience,generosity,andinsight,thispaperwouldnotexist.Icannotthankhimenough. WhenIrstcametoNewCollege,mathematicswasnotmyintendedmajor.Ichangedmymind aftertakingclasseswithProfessorMullinsandProfessorMcDonald.Bothprofessorsspentcountless hourshelpingmeunderstandconceptsandsolveproblems.Inshowingmethebeautyofmathematics,theyhavegivenmeagreatgift. Thanks,therefore,to:Dr.PatrickMcDonald,abrilliantteacherandmathematician,andamember ofmythesiscommittee. Thanksto:Dr.TarronKhemrajforagreeingtoserveonmythesiscommittee,despitenotknowing me.IamgladIhadthechancetoworkwithhim. Thanksto:Dr.CatherineElliott,myacademicsponsormyrstyearhereandthemostdedicatedprofessorI'veevermet.Herworkandintelligenceareinspiring.Hadcircumstancesallowed, shewouldhavebeenonmycommittee. Thanksto:RobertMichelson,myhighschooleconomicsteacher,whogotmeinterestedinthe subject,andwithoutwhomIwouldn'thavestudiedeconomicsincollege. Thanksto:mydad,whoewoutheretohelpmewhenIhadtomoveandprepareformybaccalaureateexamsimultaneously.Thankstobothmyparents,whohavealwaysbeenwonderfuland supportive,andwhohaven'tcomplainedtoomuchaboutmytakingtoolongtograduate.Iloveyou both!

PAGE 5

v Abstract ANEVOLUTIONARYMODELFORTHESTABLEMARRIAGEPROBLEM SarahRoseKarr NewCollegeofFlorida,2008(Classof2009) ManyvariantsoftheStableMarriageProblem(aone-to-onematchingproblemwithnobearingon actualmarriage)havebeenexploredinthe46yearssincetheproblemwasrstintroduced.Webelieveourmodelisthersttobebasedontheassumptionthatindividualsgainutilitybothfromtheir ownandfromtheirpartners'happiness.Participants'initialpreferencesareformulatedthesame wayasintheoriginalmodel.Inourmodel,however,participantsthenreordertheirpreferences, preferringthosepairingswhichprovidethegreatesttotalutility.Allpreferencesarere-ordereduntil theyceasetochange(becomestable).TheparticipantsarethenmatchedviatheGale-Shapley algorithm(inaccordancewiththesenewpreferences). Ourmostimportantdiscoveryisthatall(initial)setsofpreferenceseventuallystabilize.Weexplore, experimentally,therelationshipbetweengroupsize(cardinalityofeachset)andhowmanytimes preferencesmustbereorderedbeforestabilizing.Weexplainwhyandwhereourmodelmaybe applicableanduseourmodeltohelpexplainthedisparityinageofrstmarriageinmetropolitan versusnon-metropolitanareas.Finally,wediscussconjecturesandvariationsforpossiblefuture study. ThesisAdvisor:DavidT.Mullins Division:Mathematics/Economics

PAGE 7

TableofContents Acknowledgements ........................................ i Abstract ............................................... v Chapter1:Introduction ..................................... 1 Chapter2:TheStableMarriageProblem&Algorithm ................. 5 Chapter3:OurEvolutionaryModel ............................. 9 Chapter4:AnExample ..................................... 13 Chapter5:PropertiesoftheGale-ShapleyAlgorithm .................. 19 5.1UtilityintheGale-ShapleyStableMarriageAlgorithm.................19 5.2NumberofRoundstoCompletionintheGale-ShapleyStableMarriageAlgorithm.20 Chapter6:PropertiesofOurEvolutionaryModel .................... 21 6.1UtilityinOurEvolutionaryModel............................21 6.2RoundstoCompletioninourEvolutionaryModel...................24 Chapter7:ProofthatRankingsStabilize .......................... 29 7.1OverviewoftheProof...................................30 7.2DenitionsandNotation..................................30 7.3LemmasandTheorems...................................31 Theorem1..........................................37 Theorem2..........................................38 Theorem3..........................................40 Theorem4..........................................41 7.4Proof.............................................43 Chapter8:EconomicHistory ................................. 45 Chapter9:EconomicAspectsandImplications ...................... 49 Chapter10:PopulationDensityandMarriage ...................... 53 Chapter11:ConjecturesandVariations ........................... 59 11.1Variations..........................................59 11.2Conjectures.........................................61 AppendixA:Programs ..................................... 63 AppendixB:RepeatingAnExperiment ........................... 73 References .............................................. 75

PAGE 9

Chapter1 Introduction TheStableMarriage'problemisaone-to-onematchingproblem;ithaslittletodowithmarriage. TheproblemwasrstintroducedbyDavidGaleandLloydShapleyintheJanuary1962issueof AmericanMathematicalMonthly(GaleandShapley[1962]).TheStableMarriageProblemisbased onthefollowingpremise:Thereexisttwodisjointsetsofequalcardinality(intheGale-Shapley version,agroupofmenandagroupofwomen).Eachelementoftherstset(callthesethemen) haslistedallmembersoftheoppositeset(callthesethewomen)inorderofpreference,frommost toleastpreferred 1 .Anyelementofasetmustbepairedwithanelementoftheotherset(ina one-to-onematching).TheStableMarriageProblemisthatofpairingtheelementssuchthatfor anyindividual ,if prefers to 'scurrentpartner 2 ,then prefers 'scurrentpartnerto (this statementmustbetrueofbothgroups).FormoreabouttheStableMarriageProblem,pleasesee chapter2. SincetheStableMarriageProblemwasrstintroduced,muchresearchhasgoneintodeveloping e cientmatchingalgorithms,ndingallpossiblestablematchings,creatingdivorcedigraphs,and maximizingparticipants'utility.Afewstudieshavebeendoneonone-to-onematchingwithinterdependentutility,buttheyusedinterdependencemostlyasamechanismforcorrectingincomplete ornoisyinformation. Inthispaper,weintroduceamodelofmarriageinwhichcouplesshareutility.Weassumea linearrelationshipbetweenutilityandplacementonGale-Shapelypreferencelists.Participantscare 1 Thesepreferencesarestrictlyordered. 2 isamemberofthegroupofwhich isnotamember.

PAGE 10

2 CHAPTER1.INTRODUCTION asmuchabouttheirpartners'preferencesastheydotheirown,exceptinthecaseofties,which participantsbreakbygivingtheirownpreferencesgreaterweight.Participantsstartwithtemporary preferencelists,whichevolvebasedonthisassumptionofsharedutility.Preferenceseventuallystabilize(weprovethisinchapter7),afterwhichparticipantsarepairedviatheGale-ShapleyMatching Algorithm. InChapter2,weintroducetheStableMarriageproblem.Wediscussthealgorithm,whichGale andShapleypresentedin1962,forndingmale-optimalandfemale-optimalstablematchings.We denenotationbothforpreferencelistsandforrankinglists. Inchapter3,weintroduceourevolutionarymatchingmodelanddeneutilitywithinourmodel. WeuseanexampletoillustratebothourevolutionarymodelandtheGale-ShapleyAlgorithmin chapter4. Inchapter5,wediscussbrieysomepropertiesoftheGale-ShapleyAlgorithm.Section5.1describes utilitydistributioninstablematchingsfoundviaGale-ShapleyAlgorithm.Section5.2discusseshow longthealgorithmtakestoterminate. Chapter6coverssomepropertiesofourevolutionarypreferencemodel.Wediscussutilityinour evolutionarymodelinsection6.1.Insection6.2weexploretherelationship,inourevolutionary model,betweengroupsizeandhowlongpreferencestaketostabilize:Werunrandomsetsofpreferencesofvaryingsizesthroughourmodelviaacomputerprogram,andwerecordhowlongthese preferencesetstaketostabilize.Weobtainsomeinterestingresultsregardingthemeanandmedian numberofroundsofreorderingnecessarytoreachstability.Ourexperimentaldataisnotusefulin estimatingthemaximumnumberofroundsofreordering. InChapter7weprovethatinourmodelpreferencesalwaysstabilize(assuminganitenumber ofparticipants).Section7.1givesusanoutlineoftheproof.Wedenethetermsandnotationfor theproofinsection7.2andprovethenecessarylemmasandtheoremsinsection7.3.Theproof itselfisinsection7.4. Wethendiscusshowourmodeltsintoeconomictheory.Inchapter8,wediscusstheeconomic theoriesleadinguptoourmodel.Inchapter9,wesuggestsomeinterpretationsofourmodeland

PAGE 11

3 trytouncoverwhichaspectsofourmodelmayhaveusefulapplications.Inchapter10,wedescribe howourmodelmightexplainsomeofthevarianceinageofrstmarriageintheUnitedStates. Chapter11providessomesuggestionsforfuturestudy.Section11.1describespossiblevariations ofourmodel.Section11.2discussessomeunansweredquestionsaboutourmodelandconjectures possibleanswerstothesequestions.

PAGE 13

Chapter2 TheStableMarriageProblem& Algorithm ThetraditionalStableMarriageProblemrstappearedintheJanuary,1962AmericanMathematical Monthlyarticle,CollegeAdmissionsandtheStabilityofMarriage',byDavidGaleandLloyd Shapley.Inthispaper,GaleandShapleyintroducedandprovidedasolutiontotheStableMarriage Problem'.Theproblemisasfollows: Acertaincommunityconsistsofnmenandnwomen.Eachpersonranksthoseofthe oppositesexinaccordancewithhisorherpreferencesforamarriagepartner.Weseek asatisfactorywayofmarryingo"allmembersofthecommunity...wecallasetof marriagesunstable...ifunderitthereareamanandawomanwhoarenotmarriedto eachotherbutprefereachothertotheiractualmates.(GaleandShapley[1962]pg11) Moreformally:Therearetwodisjointsetsofcardinality n { N } .Inthistraditionalpresentation, welabelonegroupwomen'andtheothermen'. 1 Eachperson'(eachelementofaset)isassigned anumber { m | m N 1 m n } ,uniquewithinthatperson'sset.Inthetraditionalversionof thisproblem,eachelementofeachset(eachwomanorman)constructsapreferencelist'bystrictly orderingeachoftheelementsoftheotherset(eachmanorwoman)inorderfrommosttoleast preferred.Forexample:for n =4ifawoman'srstchoiceisman1,secondchoiceisman4,third choiceisman2,andfourthchoiceisman3,herpreferencelistwillbeasfollows:[1 4 2 3]Awoman 1 Obviously,thetwogroupsneednotbemen'andwomen'(theGale-Shapleyalgorithmactuallyusedbythe NationalResidentsMatchingProgramtomatchhospitalswithmedicalstudentsapplyingforresidencies.Wewill explainandexpandonthisapplicationelsewhere).Theproblemistraditionallyreferencedasthestablemarriage' problem,however,thuswecontinueinthistradition.

PAGE 14

6 CHAPTER2.THESTABLEMARRIAGEPROBLEM&ALGORITHM (man)issaidtoprefer'man(woman) toman(woman) ifandonlyifman(woman) precedes man(woman) onthewoman's(man's)preferencelist.Wewillencloseallpreference'listsin squarebrackets.Whenworkingwithournew,evolutionary'model,wewillhavetheparticipants createrankinglists'insteadofpreferencelists.Rankinglistspresentthesameexactinformationas preferencelists,butdosoinadi" erentformat. Tocreaterankinglists:Eachmemberofthewomen's(men's)grouprankseachofthemembers ofthemen's(women's)group,labelingher(his)rstchoice1',her(his)secondchoice2',andso on.Usingourearlierexample:For n =4ifawoman'srstchoiceisman1,secondchoiceisman4, thirdchoiceisman2,andfourthchoiceisman3,herrankinglistwillbeasfollows: (1 3 4 2)(correspondingtomen1,2,3,and4respectively) 2 Wewilldi" erentiatebetweenpreferencelistsandrankinglistbyenclosingtheformerinsquare bracketsandenclosingthelaterinparenthesis.Whileournewrankings'listformatmaybemore confusingthanthepreference'listformat,useoftherankings'formatwilleasetheexecutionof someofouralgorithms. 3 Inaonetoonematching,M,betweenthesetofwomenandthesetof men,thefollowingnotationisusedtosignifythatwoman y andman x arepartners(Guseld& Irving[1995]pg6): p M (woman y )=man x woman y 'spartnerundermatchingMisman x p M (man x )=woman y man x 'spartnerundermatchingMiswoman y Notethatthesetwostatementsareequivalent,asthisisaonetoonematching.Amatching,M,is saidtobeunstableifandonlyifthereexistmanxandwomanysuchthat p M (woman y ) # =man x and manxprecedes p M (woman y )onwoman y 'spreferencelist 4 2 Reminder:thisrankinglistisequivalenttothepreferencelist[1,4,2,3] 3 Sincetherankings'andpreference'listformatspresentthesameinformation,wenotethatwecanalwaysconvert betweenthetwo. 4 ThisisequivalenttosayingWoman y givesalower(better)rankingtoman x thanshedoesto p M (womany). Wearepresentingtheoriginalproblem,however,soweareusingtheoriginalnotation.

PAGE 15

7 and woman y precedes p M (man x )onman x 'spreferencelist. 5 Inthiscase,man x andwoman y arecalledablockingpair,'as x and y wouldbehappiertogether thanwiththeircurrentpartners. Ifamatchingisnotunstable,itissaidtobestable. Thestablemarriageproblemisthatofdesigninganalgorithmthatwillalwaysndastablematching. Intheirpaper,GaleandShapleyprovidedthefollowingalgorithmforndingastablematching: [L]eteachboyproposetohisfavoritegirl.Eachgirlwhoreceivesmorethanoneproposal rejectsallbutherfavoritefromamongthosewhohaveproposedtoher.However,she doesnotaccepthimyet,butkeepshimonastringtoallowforthepossibilitythat someonebettermaycomealonglater.Wearenowreadyforthesecondstage.Those boyswhowererejectednowproposetotheirsecondchoices.Eachgirlreceivingproposals choosesherfavoritefromthegroupconsistingofthenewproposersandtheboyonher string,ifany.Sherejectsalltherestandagainkeepsthefavoriteinsuspense.We proceedinthesamemanner.Thosewhoarerejectedatthesecondstageproposeto theirnextchoices,andthegirlsagainrejectallbutthebestproposaltheyhavehadso far.(GaleandShapley[1962]pg12) Thisalgorithm,calledtheGale-Shapleyalgorithmyieldsthemale-optimal'stablematching.The matchingiscalledmale-optimalbecauseinallotherstablematchings,themenndthemselves eitherwiththesamepartnersasinthemale-optimalmatching,orwithpartnerslowerontheir preferenceliststhanthepartnersinthemale-optimalmatching.Switchingthemenandwomenin thealgorithm,wecanndafemaleoptimal'stablematching.(GaleandShapley[1962]pp13-14) 5 ThisisequivalenttosayingMan x givesalower(better)rankingtowoman y thanhedoesto p M (manx).

PAGE 17

Chapter3 OurEvolutionaryModel Ourmodelassumesthateachparticipant'srankings(and,byourutilityfunction,eachparticipant's utility)evolvedependingonalltheotherparticipants'rankings(withparticipantspreferringhappy partners,ceterisparibus).Intraditionaleconomics,weassumeallindividualsaremotivatedexclusivelybyself-interest.Whydoweseenocontradictionbetweenself-interestandinterestinahappy partner? Anindividual'sdesirabilityasapartnerdependsonhisorherbehavior.Anindividual'sbehaviormayvarydependingonhowhappytheindividualiswithhisorherpartnership.Therefore,a person'sdesirabilityasapartnermaydependonhisorherlevelofsatisfactionwiththepartnership. Peopleinourmodelpreferfortheirpartnerstobehappy,notoutofselessness,butbecausehappy partnersbehavebetter. 1 Inourmodel,wedenealinearrelationshipbetweenutilityandtherankings,asfollows: 2 Equation1 Individual y 'scontributionto x and y 'sJoint-Utility= n (rankingofperson x on y 'slist) 1 Forfurtherdetails,pleaseseechapter9. 2 Itisworthyofnotethatourchoiceofalinearrelationship,betweenutilityandthepartners'positionsoneach othersrankinglists,isarbitrary.Forexample,wecouldjustaseasilyhavedenedutilityas:Utility=(placeonlist) n where n< 1 or ( n ) ( placeonlist)where0
PAGE 18

10 CHAPTER3.OUREVOLUTIONARYMODEL Weassumethatutilityisshared,i.e.thetotalutilityofaparingisequaltothesumoftheutility providedbyeachperson: Equation2 Equation2.a Joint-Utility(matchingwoman A andman B ) =Woman A 'scontributiontojoint-utility+ Man B 'scontributiontojoint-utility But,byequation1,thisisequivalenttosaying: Equation2.b =[ n (rankingofman B onwoman A 'slist)] +[ n (rankingofwoman A onman B 'slist)] Additioniscommutative,so: Equation2.c =2 n [(rankingofman B onwoman A 'slist) +(rankingofwoman A onman B 'slist)] E.g.,for n =4,ifwoman1listsman1asherthirdchoice,andman1listswoman1ashissecond choice,thejoint-utilityfrompairingman1andwoman1isequalto: (4 $ 3)+(4 $ 2)=1Util+2Utils=3Utils Inboththetraditionalmodelandinournewevolutionarymodel,eachpersondevelopshis(her) owninitialrankinglistwhilehe(she)isblindtoeveryoneelse'srankinglists.Inthetraditional model,everyoneisimmediatelymatchedinaccordancewiththoseinitiallists.Intheevolutionary' ordating'model,theparticipantsmeeteachotherandre-ordertheirrankingsbasedonthejointutilityofeachpotentialmatch.Incaseswhereaman(woman)hastwopossiblematcheswiththe sameutility,he(she)willprefertheone,whichhe(she)wouldhavepreferredonthepriorround. Thewomenandmencontinuetoreordertheirrankingsinaccordancewiththismethoduntilthe

PAGE 19

11 rankingsarestable'(i.e.untilreorderinginthismannernolongerchangestherankinglists).The menandwomenarethenmatchedviatheGaleShapleyAlgorithm.

PAGE 21

Chapter4 AnExampleIllustratingOur EvolutionaryModel Westartwithtworankingsmatrices':oneforthemenandoneforthewomen.Toaidinevaluating sharedutility,wesetupthematricessothateachrowrepresentsaman'srankinglistandeach columnrepresentsawoman'srankinglist.Forexampleiftherankingsmatricesare: MenWomen ! ! 312 132 132 ! ! ! ! ! 333 122 211 ! ! Man1'srankinglistis(3,1,2),i.e.hisrstchoiceiswoman2,hissecondchoiceiswoman3and histhirdchoiceiswoman1.Man2andMan3'srankinglistsareboth(1,3,2).Becausethewomen arerepresentedbythecolumns,wereadthewomen'srankinglistso"vertically.Woman1'sranking listis(3,1,2)andWoman2andWoman3'srankinglistsareboth(3,2,1). Wecanconvertrankingliststolistsofindividualcontributionstojoint-utility.Forexample,by equation1,Man1'scontributiontothejoint-utilityofapairingwithwoman1is:

PAGE 22

14 CHAPTER4.ANEXAMPLE 3 $ 3=0 Hiscontributiontothejoint-utilityofapairingwithwoman2is: 3 $ 1=2 Hiscontributiontothejoint-utilityofapairingwithwoman3is: 3 $ 2=1 Equivalently,wecansubtracttherankinglistfromalistoflengthn,whoseentriesarealln. (3 3 3) $ (3 1 2)=(0 2 1) Foramatrixofcontributionstojoint-utility,wesubtracttherankingsmatrixfromannbynmatrix whoseentriesarealln. Tondthesharedutilityofthepairings,weconvertrankingmatricestomatricesofindividual contributionstojointutility...: fortheMen: ! ! 333 333 333 ! ! $ ! ! 312 132 132 ! ! = ! ! 021 201 201 ! ! fortheWomen: ! ! 333 333 333 ! ! $ ! ! 333 122 211 ! ! = ! ! 000 211 122 ! ! ...andthenndthejoint-utilitymatrix(bysummingthetwomatricesoftheindividualcontributionstojoint-utility,inaccordancewithequations2.aand2.b):

PAGE 23

15 ! ! 021 201 201 ! ! + ! ! 000 211 122 ! ! = ! ! 021 412 323 ! ! Thepeoplethenreordertheirrankingsinaccordancewiththisnewmatrix:Forthemen:man1 nowgetsthehighestutilityfrompairingwithwoman2,thesecondhighestutilityfrompairingwith woman3andthelowestutilityfrompairingwithwoman1.Therefore,hisrankinglistis(3,1,2). Man2'srankinglistis(1,3,2).Man3seesequalutilityfrombeingpairedwithwomen1or3,so welookathispriorrankings.Beforewereorderedtherankings,Man3'srstchoicewaswoman1 andhissecondchoicewaswoman3.Therefore,Man3willpreferbeingwithwoman1inthisround; hisrankinglistisnow:(1,3,2). Forthewomen:Woman1'srankinglistis(3,1,2).Woman2preferredMan3toMan1in thepriorround,soherrankinglistwillbe(2,3,1).Woman3'srankinglistis(3,2,1). Thenewrankingmatricesare: MenWomen ! ! 312 132 132 ! ! ! ! ! 323 132 211 ! ! Tosaveourselvesastep,insteadofusing(amatrixversionof)equation1,wecanuse(amatrix versionof)equation2.c.Weaddtogethertherankingmatrices: MenWomen ! ! 312 132 132 ! ! + ! ! 323 132 211 ! ! = ! ! 635 264 343 ! ! ...andconverttheresultantmatrixtoajointutilitymatrix.LetMbethemen'sutilitymatrixand letWbethewomen'sutilitymatrix.Previouslywesaid[ n $ M ]+[ n $ W ]=joint-utilitymatrix (matrixequivalentofequation2.b).Wecanseethat[ n $ M ]+[ n $ W ]=2 % n $ [ M + W ]=joint-

PAGE 24

16 CHAPTER4.ANEXAMPLE utilitymatrix(matrixequivalentofequation2.c).Therefore,wecanndthejointutilitymatrix bytakingannxnmatrixwithallentriesequalto2 % n andsubtractingthesumofthetworanking matrices. ! ! 666 666 666 ! ! $ ! ! 635 264 343 ! ! = ! ! 031 402 323 ! ! Thenewrankingmatricesare: MenWomen ! ! 312 132 213 ! ! ! ! ! 313 132 221 ! ! Ifwesumthesematrices,converttoajoint-utilitymatrixandcreatenewrankingmatricesbased onthejoint-utilitymatrix,wendthatthenewsetofrankingmatricesisthesameastheprevious setofrankingmatrices.Wethereforedeclaretheserankingmatricesstable.Wesaythatittook tworounds'ofreorderingfortherankingstobecomestable.Withthesestablerankingmatrices, weimplementthemaleoptimalGale-ShapleyAlgorithmtondstablenalpairings: Thenalrankinglistsareasfollows: Man1:(3 1 2)Woman1:(3 1 2) Man2:(1 3 2)Woman2:(1 3 2) Man3:(2 1 3)Woman3:(3 2 1) Wecanconverttheserankinglistsintothepreferencelists,ifwewish: Man1:[2 3 1]Woman1:[2 3 1] Man2:[1 3 2]Woman2:[1 3 2] Man3:[2 1 3]Woman3:[3 2 1] Eachmanproposestohisrstchoice: Man1andman3proposetowoman2.Man2proposestowoman1. Wedenotethisinaproposallist':

PAGE 25

17 M1:2 M2:1 M3:2 Woman1hasgottenaproposalfromonlyoneman(man2),soshetentativelyacceptshisproposal, reservingtherighttorejecthimifshegetsabettero" er.Woman2hasgottenproposalsfromtwo men.Woman2prefersman1toman3,sosherejects 1 man3andtentativelyacceptsman1's proposal.Wecandenoteman3'srejectionbywoman2,bycrossinghero"hisproposallist.Man 3nowproposestohisnext(second)choice:woman1: M1:2 M2:1 M3: 2 $& 1 Woman1getstochoosebetweenman2andman3.Woman1prefersman2toman3,sosherejects man3.Man3crosseswoman1o"hisproposallist,andasksouthisnext(thirdandnal)choice: woman3.Woman3hasreceivednootherproposals,sosheacceptsman3'sproposal: M1:2 M2:1 M3: 2 $& 1 $& 3 Allpersonsarenowmatchedasfollows: Man1&Woman2 Man2&Woman1 Man3&Woman3 Or,inmoreformalnotation: p M (Man1)=Woman2 p M (Man2)=Woman1 p M (Man3)=Woman3 Ouruseofthemale-optimalversionoftheGale-Shapleyalgorithmisarbitrary.Wecouldjustas easilyusethefemale-optimalversion.(Inthiscase,however,thefemale-optimalandmaleoptimal versionsyieldthesameresult.) 1 Notethatwhileacceptancesaretentativeuntileachpersonismatched,allrejectionsarenal.

PAGE 27

Chapter5 PropertiesoftheGale-Shapley StableMarriageAlgorithm Beforeexploringthepropertiesofourevolutionarypreferencemodel,wewilldiscusssomeproperties oftheoriginalGale-Shapleyalgorithmforndingstablepairings. 5.1UtilityintheGale-ShapleyStableMarriageAlgorithm Thefemaleoptimal'(maleoptimal')Gale-ShapleyAlgorithmresultsinastablematchingsuch thateachwoman(man)hasthebestpartnershe(he)canhaveinanystablematchingandeach man(woman)hastheworstpossiblepartnerhe(she)canhaveinanystablematching.(Guseld& Irving[1995]pp11-12) Ifthemale-optimal'andfemale-optimal'versionsoftheGale-ShapleyAlgorithmyieldthesame matching,therearenootherpossiblestablematchings. Thereisatrade-o"'inutilityintheStableMatchingProblem:IfAandBarestablematchings,andifthereexistsanindividual suchthat prefersherpartnerinAtoherpartnerinB, thenthereexistsanindividual ,suchthat prefershispartnerinBtohispartnerinA 1 1 Proof:IfAisastablematching,thenforanymatchingB,ifnoparticipantsprefermatchingBtomatchingA, butsomeprefermatchingAtomatchingB,thentheparticipantswhoprefermatchingAconstituteblockingpair, andmatchingBisunstable.

PAGE 28

20 CHAPTER5.PROPERTIESOFTHEGALE-SHAPLEYALGORITHM 5.2NumberofRoundstoCompletionintheGale-Shapley StableMarriageAlgorithm Fromourdescription,itisclearthatthealgorithmterminates.Inthemale-optimalversionofthe GaleShapleyAlgorithm,eachmanaskseachwomanoutnomorethanonce.Itwouldtake n 2 stages'(astagebeinganincidenceofanymanaskinganywomanout)for n mentoask n women out.Itmustthereforetakenomorethan n 2 stagesfortheGaleShapleyAlgorithmtoterminate. Furtherresearchshowsthatthealgorithmwillterminateafteramaximumof n 2 $ n +1stages. (Guseld&Irving[1995]pg13) AccordingtoGuseldandIrving'sbook,TheStableMarriageProblem:StructuresandAlgorithms "theaveragenumberofproposalsmade...is nH n + O ((log n ) 4 ),where H n =1+1 / 2+1 / 3+ +1 /n isthenthharmonicnumber...theaverage-casecomplexityofthealgorithmis# ( n log n )".(Guseld &Irving[1995]pg14)

PAGE 29

Chapter6 PropertiesofOurEvolutionary Model 6.1UtilityinOurEvolutionaryModel Ifwehavethefollowingoriginal'rankingsmatrices.... MenWomen ! ! ! 1342 4132 4312 4123 ! ! ! ! ! ! 1341 4132 3413 2224 ! ! ! ...andwereordertherankingsinthesematrices,inaccordancewithourevolutionarymodel,we endupwiththefollowingrevised'rankingsmatrices.

PAGE 30

22 CHAPTER6.PROPERTIESOFOUREVOLUTIONARYMODEL MenWomen ! ! ! 1342 4132 4312 3124 ! ! ! ! ! ! 1341 4132 3413 2224 ! ! ! Theserankingsmatricesarestable(ifwereordertheminaccordancewithourevolutionarymodel, theydonotchange). IfweusetheGale-ShapleyMatchingAlgorithmtocreatingstablematchings,wendonlyone stablematching(themale-optimalandfemale-optimalversionsofthealgorithmbothyieldthesame results,which,aswesaidin5.1,meansthereisonlyonestablematching),fortheoriginal'rankings: Man1&Woman1Man3&Woman3 Man2&Woman2Man4&Woman4 Andonlyonestablematchingfortherevised'rankings: Man1&Woman1Man3&Woman3 Man2&Woman2Man4&Woman4 Thesematchingsareidentical.Therankingsbehindthem,however,aredi" erent. Fortheoriginalrankings:Men1,2,and3,andwomen1,2,and3areeachwiththeirtopchoice. Byequation2.c,eachofthesepairingsresultsinajointutilityof: 2 % 4 $ [1+1]=8 $ 2 =6 Woman4isman4'sthirdchoice,andman4iswoman4'sfourthchoice,forajoint-utilityof: 2 % 4 $ [3+4]=8 $ 7 =1

PAGE 31

6.1.UTILITYINOUREVOLUTIONARYMODEL 23 Fortherevisedrankings: Men1,2,and3,andwomen1,2,and3arestilleachwiththeirtopchoice.Byequation2.c,each ofthesepairingsresultsinajoint-utilityof: 2 % 4 $ [1+1]=8 $ 2 =6 Woman4isnowman4'sthirdchoice,andman4iswoman4'sfourthchoice,forajoint-utilityof: 1 2 % 4 $ [4+4]=8 $ 8 =0 Sixoftheparticipants(threeofthecouples)obtainequalutilitywhetherornottheyrevisetheir rankings.Twooftheparticipants(onecouple),however,areworseo"havingrevisedtheirpreferences. IntheoriginalStableMatchingProblem,wehaveatradeo"inutility;ifonepersongainsutilityinswitchingbetweenstablematchingAtostablematchingB,thenanotherpersonlosesutility (see5.1).Inourevolutionarymodel,weseenosuchtradeo" Howdidthishappen? Fromaquantitativeperspective,man4rankedwoman4ashisthirdchoice,butwomen1,2, and3eachrankedman4astheirsecondchoice,whilewoman4rankedman4asherfourthchoice. Thisresultedinman4gettingpotentialjoint-utilityof: 2 % 4 $ [4+2]=2frompairingwithwoman1 2 % 4 $ [1+2]=5frompairingwithwoman2 2 % 4 $ [2+2]=4frompairingwithwoman3 2 % 4 $ [3+4]=1frompairingwithwoman4 Man4thenreorderedhisrankings,andgotarevisedrankinglistof:(3 1 2 4). 1 Allowingparticipantstohave0utilityimpliesthattheymaybeindi! erentbetweenbeingmarriedandstaying single.Wecouldxthisbyrevisingourutilityfunction(adding1toindividualcontributionstojointutility,making theminimumjoint-utility2),butthisdoesn'ta! ectthestabilityoftheothermatchings.Wecould(alternatively) choosetoclaimthatremainingsinglehasnegativeutility.

PAGE 32

24 CHAPTER6.PROPERTIESOFOUREVOLUTIONARYMODEL Howmightweinterpretsuchresultsfromabehavioraleconomicsperspective? Beforereorderinghispreferences,man4didn'trealize'howmuchwomen1,2,and3likedhim.In ignorance,man4couldhavederivedautilityof1frommatchingwithwoman4.Havingseenhow happyheandhisotherpotentialpartnerswouldbetogether(andhavingrealizedthatwoman4 wouldnotcontributeanyutilitytoaunionwithhim),man4re-evaluatedhispreferencesandcould nolongerenjoybeingpartneredwithwoman4. 6.2RoundstoCompletioninourEvolutionaryModel Data:RoundstoTermination Inchapter7,weprovethatallpossiblesetsofrankingseventuallystabilize.Thattherankings stabilizeimpliesthatnosetofrankingscanappearmorethanonce,unlessthatsetofrankings isstable(otherwise,wegetaninniteloop) 2 .Therefore,foranygivengroupsize,therankings mustbestableafterbeingreorderedq-1times,whereq=numberofpossiblesetsofrankingsofthat particulargroupsize.Sinceqgrowsquiterapidlywithgroupsize,q-1formsaridiculouslylargeand unhelpfulupperboundtothenumberofre-orderingsneededtostabilizetherankingsforanygiven groupsize. Whilewehaven'tfoundausefulupperbound,weshouldbeabletoestimatethemediannumber ofreorderingsnecessaryforanygivengroupsizebyrunningouralgorithmonabunchofrandomly generatedpreferencesetsoftheappropriatesize. Usingtheprogram r_rand_mult_size_MW_simult.m anditssubsidiaries(alllistedintheappendix), wehavecreatedandreordereduntilstable1000randomsetsofrankingmatricesofeachsizefrom 1to100.Wehaverecordedtheresultsandplottedthedataforeachgroupsize(below): 2 Thisisbecausethe REORDER functiondependsonlyontherankings;if REORDER ( A )= B and REORDER n ( B )= A ,where A = B then REORDER n +1 ( A )= REORDER k ( n +1) ( A )= A and REORDER ( A )= REORDER k ( n +1)+1 ( A )= B # k $ N ,therefore, A and B repeataninnitenumberoftimes,thereforetherankings neverstabilize.

PAGE 33

6.2.ROUNDSTOCOMPLETIONINOUREVOLUTIONARYMODEL 25 Boththemedianandthemeanseemtohavealogarithmicrelationshiptogroupsize.Wewilltry totalogarithmiccurvetoeach:

PAGE 34

26 CHAPTER6.PROPERTIESOFOUREVOLUTIONARYMODEL Themedianvalueshaveacorrelationofapproximately0.97withalogarithmicfunction.Themean valueshaveacorrelationofapproximately0.98withalogarithmicfunction.Wenotethatthemean numberofroundstostabilityseemtoexhibitsomestrangebehaviorbetweengroupsize10and groupsize20(morespecically,thereanunexpectedlylargeincreaseinthenumberofroundsof reorderingneededbetweengroupsizes13and14) 3 .Thecauseforthisapparentjumpisunknown 3 Toseeifthejumpwasreallythere,orjustaquirkofoursample,werananewsetofrandomlygeneratedranking matricesthroughourprogram.Betweengroupsizes13and14,weendedupwithalargerjumpinthenumberof

PAGE 35

6.2.ROUNDSTOCOMPLETIONINOUREVOLUTIONARYMODEL 27 tous,andcouldbeasubjectforfutureinquiry. Wealsoobservedthemaximumnumberofroundsneededforeachgroupsize'srankingstobecomestable.Thelarge(andrapidlyincreasing)varianceinourresultssuggeststhatasgroupsize grows,thepercentofsetsofrankings,whichrequirethemaximumnumberofroundstostabilize, increasesrapidly,makingourdatauselessinestimatingthemaximumroundstostability. roundsorreorderingneededthanwedidinthepriorattempt.Thejumpwasapparentinboththemeanandthe median.Foradisplayofthevalueswegotinthesecondattempt,pleaseseeAppendix2.

PAGE 36

28 CHAPTER6.PROPERTIESOFOUREVOLUTIONARYMODEL

PAGE 37

Chapter7 ProofthatRankingsStabilize Instudyingtheevolutionarymodelofrankings,wewanttoknowwhetherallpossiblerankingsets willeventuallybecomestableafterapplyingthealgorithmasu! cientnumberoftimes.Running randompreferencesetsthroughouralgorithminsection6.2,wefoundnosetsofpreferences,which didnoteventuallystabilize 1 .Inthischapter,wewillprovethatthereexistnosetsofpreferences whichwillnoteventuallystabilize. Denition. Foranyrankingset, X ,let REORDER bethefunctionthatreordersrankingset X inaccordancewiththealgorithm.Ifreorderingrankingset X yieldsrankingset Y ,wewillsay REORDER ( X )= Y REORDER t ( X ) isthefunctionthatreorderstherankingset, X t times. Observation. Wenotethatforanygivengroupsize,thenumberofpossiblerankingsetsisnite. Therefore,iftherankingsneverstabilize,therankingsmustcycle,i.e. A ,arankingset,suchthat REORDER ( A )= B ( B # = A ) ,which,ifoperateduponbythealgorithmagainanitenumberof times,willyieldrankingset A again,i.e. REORDER n ( A )= A forsomeinteger n # =1 Wewillprovethatforanygivenrankingset, A REORDER n ( A )= A ( n =1thatis,wewill provethatrankingsnevercycle,therebyprovingthatthereorderingalgorithmterminates. 1 Thisisobviousbasedonourniteresultsforthemean.

PAGE 38

30 CHAPTER7.PROOFTHATRANKINGSSTABILIZE 7.1OverviewoftheProof Foranyrankingset A ,letusconsidersomewoman, .Wewillshowthatifwoman 'srstranked (mostpreferred)manunderrankingset A giveswoman arankingof q ,thenwoman 'srst rankedmanunderrankingset REORDER ( A )mustgiveherarankinglower(better)thanorequal to q (Theorems1,2,3,&4).Furthermore,ifequalityholds,thenherrstchoiceforamanhas notchangedfromthepriorround(fromTheorems3&4).Thisstatementisgenderneutraland thereforeappliesequallytothemen. Giventheabove,therankinggiventoapersonbytheirrstchoice,foranygivenround,can onlydecrease(improve)underthe REORDER function.Becausethereareanitenumberofpossiblerankingsets,itwilltakeanitenumberofreorderingsforthisrankingtoreachaminimum. Wewillshowthatoncetherankingsgiventoallpersonsbytheirrstchoicesarestableunder the REORDER function,therankinggiventoanypersonbyhersecondchoicewillreachaminimum(becomestable)inthemannerdescribedearlierfortherstchoice.Oncetherankingsgiven toallpersonsbytheirsecondchoicesarestableunderthe REORDER function,therankinggiven toanypersonbyherthirdchoicewillreachaminimum(becomestable)andsoonuntilallrankings arestableunderthe REORDER function(Theorems1,2,3,&4). 7.2DenitionsandNotation Notation. Thefollowingnotationiscumbersome,however,itwillallowforgreaterclarityinour proof.Forwoman ,underagivenrankingset, A : t m,i = means is 's i thrankedmanunderrankingset REORDER t ( A ) t w,i = means is 's i thrankedwomanunderrankingset REORDER t ( A ) t r,i = k means is t m,i 's k thrankedchoice. Note: If t m,i = and t r,i = k ,then t r,k = i Denition. RANKSUM :Forastartingrankingsetof A RANKSUM ( !," ) n isthesumof 's rankfor underrankingset REORDER n ( A ) plus 'srankfor underrankingset REORDER n ( A ) Denition. MINUNSTABLE n ( A ) isthefunctionsuchthatafter n roundsofre-ordering,if

PAGE 39

7.3.LEMMASANDTHEOREMS 31 MINUNSTABLE n ( A )= $ ,thenfor q< $ ,foranyfemaleparticipant, : n + i m,q = n m,q and n + i r,q = n r,q ,forall i ) 0 andforanymaleparticipant, : n + i w,q = n w,q and n + i r,q = n r,q ,forall i ) 0 If MINUNSTABLE n ( A )=$ ,thenforanyparticipant ,ifinround n 'srankingfor or 's rankingfor islessthan$ ,then and 'smutualrankingswillnotchangeafterround n Note:The MINUNSTABLE functionwillbethecenterpieceofourproof.Wewillultimately showthatifwedene P as: P ( k,A )= t MINUNSTABLE t ( A )= k Suchthatforany j k t + i m,j = t m,j t + i r,j = t r,j and t + i w,j = t w,j t + i r,j $ t r,j forall i> 0 Thenwecanshowthat P (1 ,A )existsforall A Furthermore,wewillshowthat,for k< groupsizein A ,if P ( k,A )exists,then P ( k +1 ,A )exists. Thiswillcompleteourinductiveproof. 7.3LemmasandTheorems Lemma1 Ifbetweenrounds n and n +1, and # switchrelativepositionson 'spreferenceslist,with 's rankingimproving,thenthe RANKSUM for and # inround n isgreaterthanthe RANKSUM for and inround n If n m,a = n +1 m,b = and n m,c = n +1 m,d = # andif

PAGE 40

32 CHAPTER7.PROOFTHATRANKINGSSTABILIZE a>c but bRANKSUM n ( n n m,a ) Proof: If n m,a = n +1 m,q = and n m,v = n +1 m,s = # andif qv : RANKSUM n ( !,! m,v ) # = RANKSUM n ( !,! m,a ) Letusassumethat a>v and RANKSUM n ( !,! m,v )= RANKSUM n ( !,! m,a ) Byouralgorithm,incaseswhereapersonhastwopossiblepairingswiththesameutility,he(she) willprefertheone,whichhe(she)wouldhavepreferredonthepriorround.Therefore: q>s CONTRADICTION(Wealreadyassumedthat qv but qRANKSUM n ( !,! m,a )

PAGE 41

7.3.LEMMASANDTHEOREMS 33 Lemmas2.aand2.b Thesearelemmasforwhen 'srankingfor worsensfrom a to b atstep n +1 Lemmas2.aand2.bbothassumepertaintocaseswhere: = n w,a = n +1 w,b suchthat aa andwhoserankingby atstep n +1is d suchthat d a If = n w,a = n +1 w,b Andif aa ) d Proof: Let = n w,a = n +1 w,b where aa ) d If = n w,a = n +1 w,b where aa ) d

PAGE 42

34 CHAPTER7.PROOFTHATRANKINGSSTABILIZE Lemma2.b If 'srankingfor worsensfrom a to b atstep n +1,thenthereissomeman # ,whoserankingby atstep n is c ) b andwhoserankingby atstep n +1is d suchthat dd Proof: Let = n w,a = n +1 w,b where ad If = n w,a = n +1 w,b where ad

PAGE 43

7.3.LEMMASANDTHEOREMS 35 Lemma3 [ 'srankingfor atstep n ]plus[ 'srankingfor atstep n ]willalwaysbegreaterthan[ 'sranking for atstep n +1] If RANKSUM n ( !," )= c and n +1 m,a = Then ab Weassumed(andaretryingtodisprove): a ) c

PAGE 44

36 CHAPTER7.PROOFTHATRANKINGSSTABILIZE Therefore, a>b (Thismeans 'srankfor hasincreasedinround n +1) Bylemma2.b,thereexistsman % suchthat: % = n m,v = n +1 m,s where v ) a>s butbyLemma1: RANKSUM n ( !,% ) b v ) a ) c Therefore: v +1 >v ) a ) c Transitively: v +1 >c CONTRADICTION(wealreadyshowed v +1
PAGE 45

7.3.LEMMASANDTHEOREMS 37 Theorem1 If,atstep n gives arankingof1,then 'srankingfor cannotbelarger(worse)atstep n +1 thanatstep n ( 'srankingfor canonlyimproveatstep n +1). If n m, 1 = "and" n w,a = n +1 w,b = Then b a Proof: RANKSUM n ( !," )= a +1 ByLemma3, b
PAGE 46

38 CHAPTER7.PROOFTHATRANKINGSSTABILIZE Theorem2 If,atstep n gives arankingof$ ,where$= MINUNSTABLE n ( A ),then 'srankingfor cannotbelarger(worse)atstep n +1thanatstep n ( 'srankingfor canonlyimproveatstep n +1). If n m, = and n w,a = n +1 w,b = Where $ = MINUNSTABLE n ( A ) Then a ) b Proof: Thiswillbeaproofbycontradiction. Given n m, = and n w,a = n +1 w,b = Assume: ad ,byLemma1 RANKSUM n ( ",% ) a )

PAGE 47

7.3.LEMMASANDTHEOREMS 39 thereforeourassumptionmustbewrong. If n m, = and n w,a = n +1 w,b = ,then a ) b

PAGE 48

40 CHAPTER7.PROOFTHATRANKINGSSTABILIZE Theorem3 If 'srankingfor improvesfrom k> 1atstep n ,to1atstep n +1,thentheranking getsfrom herrstchoiceatstep n isgreater(worse)thantheranking getsfrom (hernewrstchoice)at step n +1. If n m,k = n +1 m, 1 = where k # =1 Then n r, 1 > n +1 r, 1 Proof: Given: n m,k = n +1 m, 1 = where k # =1 Let # = n m, 1 Then RANKSUM n ( !,# )=1+ n r, 1 Since 'spositionon 'slistimprovesrelativeto # 'satthe n +1thround,byLemma1, RANKSUM n ( !," ) n +1 r, 1

PAGE 49

7.3.LEMMASANDTHEOREMS 41 Theorem4 If 'srankingfor improvesfrom k> $attime n ,to$attime n +1,thentheranking getsfrom her$ thchoiceatstep n isgreater(worse)thantheranking getsfrom (hernew$ thchoice)at step n +1. If n m,k = n +1 m, = Suchthat: k> $ and $ = MINUNSTABLE n ( A ) Then n r, > n +1 r, Proof : Supposethat: n m,k = n +1 m, = Suchthat: k> $ and $ = MINUNSTABLE n ( A ) Andlet a and b besuchthat = n w,a = n +1 w,b Weneedtoshowthat n +1 r, = b< n r, Let # = n w, Since # and changepositions,weknow: RANKSUM n ( !," ) $ ,so a< n r, ,soassumethat:

PAGE 50

42 CHAPTER7.PROOFTHATRANKINGSSTABILIZE ad Further,since 'srankingof % changes,weknowthatif z issuchthat % n m,z = Then z ) $ Further,since,attime n +1, 'srankingfor % improvesrelativeto 'srankingfor # : RANKSUM n ( % ," ) $and$= MINUNSTABLE n ( A )then n +1 r, < n r,

PAGE 51

7.4.PROOF 43 7.4Proof Wewillnowprovethatinourmodelofevolvingpreferences,allinitialsetsofrankingseventually stabilize.Wewillusethefollowing,whichwehavejustproventobetrue: Observation1. Foranygivengroupsize,thenumberofpossiblerankingsetsisnite.If therankingsneverstabilize,therankingsmustcycle. Theorem1. If,atstepn, gives arankingof1,then 'srankingfor cannotbelarger (worse)atstepn+1thanatstepn( 'srankingfor canonlyimproveatstepn+1). Theorem2. If,atstepn, gives arankingof $ ,where $ = MINUNSTABLE n ( A ) then 'srankingfor cannotbelarger(worse)atstepn+1thanatstepn( 'srankingfor can onlyimproveatstepn+1). Theorem3. If 'srankingfor improvesfromk1atstepn,to1atstepn+1,thenthe ranking gotfromherrstchoiceatstepnwaslarger(worse)thantheranking getsfrom (her newrstchoice)atstepn+1. Theorem4. If 'srankingfor improvesfromk $ attimen,to $ attime n +1 ,thenthe ranking gotfromher $ thchoiceatstep n waslarger(worse)thantheranking getsfrom (her new $ thchoice)atstep n +1 Letusassumethattherankingsdonotstabilize.ByObservation1,thisimpliesthattherankingscycle.Intheinitialrankings,sayperson 'srstrankedpersonis .Either 'srstranked personafterreorderingonce(atstep2)is ,or 'srstrankedpersonafterreorderingonceis someoneelse.If 'srstrankedpersonisstill ,thenbyTheorem1,therank receivesfrom atstep2mustbeless(better)thanorequaltotherank receivedfrom atstep1.Say 'srst rankedpersonatstep2is # ,where # and arenotthesameperson.ByTheorem3,therank receivesfrom # atstep2islower(better)thantherank receivedfrom atstep1.Eitherway, therank receivesfrom 'srstrankedchoiceatstep2islower(better)thanorequaltotherank receivedfrom 'srstrankedchoiceatstep1.Thisargumentappliesforallparticipantsand allsteps.Therankingeachparticipantgetsfromhisorherrstrankedchoiceismonotonically

PAGE 52

44 CHAPTER7.PROOFTHATRANKINGSSTABILIZE decreasing(improving).ByObservation1,thepreferencescycle.Thismeansthattherankingeach participantgetsfromhisorherrstrankedchoicereachesitsminimuminnitetimeand(sinceit ismonotonicallydecreasing)maintainsthatminimum. Letussaythattherankingeachparticipantreceivedfromhisorherrstchoicehasstabilized (reacheditsminimum)bystepn.ByTheorem3,sincetherankingeachpersongetsfromhisor herrstrankedchoiceisnolongerdecreasing,(bymodustollens)theperson,whomheorsheranked number1,cannotchange.Byourdenitionofthe MINUNSTABLE function, MINUNSTABLE n (Initial Rankings) ) 2. Let$= MINUNSTABLE n (InitialRankings).Say 's$ thchoiceis % .Atstep n +1,either % isstill 's$ thrankedchoice,orsomeoneelseis.Say % isstill 's$ thrankedchoiceatstep n +1. ByTheorem2,therank gotfrom % musthaveimproved(decreased)orstayedthesame.Say 's $ thrankedchoiceatstep n +1isnot % ,but $ .ByTheorem4,theranking $ givesto atstepn+1 mustbelower(better)thantheranking % gaveto atstepn.Asbefore,thismeansthattheranking getsfromher$ thrankedchoiceatstepn+1islower(better)thanorequaltotheranking got fromher$ thrankedchoiceatstepn.Thisargumentappliestoallparticipantsandallstepsgreater thanorequalton.ByObservation1,therankingeachparticipantgetsfromhisorher$ thranked choiceatanystepafterstep n ismonotonicallydecreasing,andreachesitsminimumandstabilizes inaniteamountoftime.Saytherankingeachparticipantgetsfromhisorher$ thrankedchoice hasstabilizedbystep r .Thismeansthat$+1 ) MINUNSTABLE r (InitialRankings). Wecontinuereasoninginductivelyuntilwereachsteps,where MINUNSTABLE s (InitialRankings)=numberofmen=numberofwomen.Alltherankingswillhavethenstabilizedinanite amountoftime. Therankingseventuallystabilize.Thismeansthatgivenrankingset,Asuchthat REORDER n ( A )= A ,itmustbethecasethatn=1

PAGE 53

Chapter8 TheHistoryofInterdependent Utility,DemandSchedulesand PreferencesinEconomicTheory Pleasenote:Thefollowingisaverygeneralsurveyofprioreconomicworkandshouldbynomeans beconsideredcomplete. Economicsisoftendescribedasthestudyofthedistributionofscarcegoods,orasthestudyof theinteractionsofrational,self-interestedindividuals. Ourmodelisconsistentonallbutoneofthesepoints.Individualmatesandpartnersarescarce; thereisonlyoneofeachpotentialmate.Ourparticipantsactinaccordancewiththeirdesires, andthereforearerational.Clearly,ourparticipantsinteract.Theparticipantsarenotexclusively self-interested,however,theycareabouteachother'sutilityandpreferences.Somepeoplemight claimthattheparticipants'lackofself-interestmakesourmodelpsychological,ratherthaneconomic. Thecombinationofpsychologyandeconomicsisnotnew,however,noristheincorporationof interdependentutility,interdependentdemand,orinterdependentpreferences.

PAGE 54

46 CHAPTER8.ECONOMICHISTORY From1776,untilthelatenineteenthcentury,ClassicalEconomicswastheprevailingeconomicphilosophy.ClassicalEconomicsallowedforthecombinationofeconomicsandpsychology 1 .Inthelate nineteenthcentury,however,theNeoclassicalRevolution'dispensedwithpsychologyandstressed theimportanceofmarginalutility.(Mason[1995]) In1892,anEconomistnamedHenryCunynghamecriticizedAlfredMarshall(arguablythepreeminenteconomistoftheday)forignoringtheimportanceofinterdependentdemandschedulesin determiningprice.(Cunynghame[1892]) ThorsteinVeblenusedideasfromLocke 2 ,Cunynghameandothersinwritinghisbook, Theory of the Leisure Class.Veblenassertedthattheutilityofcertaingoodsandserviceslay,notintheir inherentutility,'butintheiruseasasignierofwealth.Veblencoinedthetermpecuniaryemulation,'theideathatindividualskeepup'theappearanceofrelativewealthbyattemptingto conspicuously'consumethesamegoodsasthosewithhigheconomicstatus.Amodernwardrobe, Veblenexplained,actsasasignierofwealth.Thewealthypopulation,saidVeblen,setsthepacein mattersoffashion(Veblen[1899]pg116).Whenthewealthypopulationupdatesitswardrobe,the lesswealthyfollowsuit,attemptingtocopythewardrobeasbestastheycan,giventheirmorelimited means.Astheeconomicelitechangetheirpreferencesforfashion,sodoestherestofthepopulation. Intheearly1900s,alotofsocialscienceandbusinessliteraturediscussedtheimportanceofinterdependentpreferences,whileeconomicliterature,forthemostpart,ignoredit.(Mason[1995]) In1920,ArthurPigoudevelopedtheconceptofexternalities,inwhichindividualconsumption a ectssocietalutility. In1948,OskarMorgensternwroteanarticleinfavorofamodelofconsumerbehaviorinvolving 1 AsshowninSmith'sTheoryofMoralSentiments [1776],andinBentham'sThePsychologyofEconomicMan [1817] 2 In1691,JohnLockewrote,inalettersenttoamemberofparlament: ...thingsofFashionwillbehadaslongasMenhaveMoneyorCredit,whateverRatestheycost, andtheratherbecausetheyaredear.ForitbeingVanitynotUsethatmakestheExpensiveFashion ofyourPeople,theEmulationis,whoshallhavethenest,thatis,thedearestthings,notthemost convenientoruseful.Howmanythingsdowevalueorbuy,becausetheycomeatdearratesfromJapan andChina,whichiftheywereourownManufactureorProduct,commontobehad,andforalittle Money,wouldbecontemnedandneglected?

PAGE 55

47 interdependentdemandcurves: Currenttheorypossessesnomethodsthatallowtheconstructionofaggregatedemand curveswhenthevariousconstituentindividualdemandcurvesarenotindependentof eachotherifthereisinterdependenceamongindividualdemandfunctionsitisdoubtful thataggregateorcollectivedemandfunctionsoftheconventionaltypeexistanddonot havetobereplacedbymorecomplicatedconceptsItisaseriousshort-comingofthe currenttreatmentofaggregatedemandcurvesthattheirstudyhasnotbeenextended tothemostimportantcasewhereadditivityisabsent.(Morgenstern[1948]) In1966,usingcrimeandeconomicstatisticsfrom1960,BeltonFleisherfoundacorrelationbetween income,unemploymentconditionsandjuveniledelinquency.(Fleisher[1966])Fleisherarguedthat, consideringtheriskofgettingcaught,arationalpersonmightchoosetoengageincriminalbehavior ifandonlyifheorshewerehavingnancialdi! culties(bothbecauseheorshemightneedtosteal inordertosurviveandalsobecausetheopportunitycostofgoingtojailislowerforpeoplewithan alreadybleakfuture).Implicitly,lowpovertyandunemploymentratesbenetallmembersofsociety. In1974,GeryBeckerwroteanarticletitledATheoryofMarriage:PartII.Inthispaper,Becker discusses,inbrief,thee" ectonaperson'sindi"erencecurveofhavingtheperson'sutilitydepend notonlyonhisconsumption,butalsoontheconsumptionofhispartner'. Recently,theuseofpsychologyineconomicmodelsexperiencedarevivalintheeldofbehavioral'economics. In2001,YannBramoullewroteapapertitledInterdependentUtilities,PreferenceIndeterminacy, andSocialNetworks'.Bramoulleintroducedamodelofinterdependentutility,inwhicheachparticipantAcouldlikeanyotherparticipant,B,(andthereforederiveutilityfromparticipantB's utility),hateparticipantB(andthereforehaveutilityinverselydependentonB'sutility),ornot careaboutparticipantB.Bramoulledidnotapplyhismodelofutilitytomatching.Muchofthe articleisdevotedtonetworkmodelsofinterdependentsocialutility. Overthepastdecade,severalarticleshavebeenwrittenontwo-sidedmatchingandinterdependent utility.Subjectsexploredincludenoise(Chade[2006])theacceptancecurse'(anapplicationofthe winner'scurse'fromauctiontheory)(Chade[2006]),searchfrictions(Shimer&Smith[2000];Chade

PAGE 56

48 CHAPTER8.ECONOMICHISTORY [2006];Smith[1997]),incompleteinformation(inwhichplayersmakeguessesbasedontheirowninformationandonotherplayers'actions)(Chade,Lewis,andSmith[2006];Ostrovsky,Chakraborty, andCitanna[2008]),andreputation(Anderson&Smith[2006]).

PAGE 57

Chapter9 EconomicAspectsand ImplicationsoftheEvolutionary RankingsModel Theevolutionary'modelhasthusfarbeendescribedasmodelingthebehaviorofdatingcouples and,inonecase,asmodelingthepairingofmedicalstudentswithhospitals.Themodelhasmore importanteconomicapplications,whichwewillnowdiscuss. AccordingtotheEconomist.com,[m]orethantwo-thirdsofoutput[frommembercountriesofthe OrganisationforEconomicCo-operationandDevelopment],anduptofour-fthsofemployment,is nowintheservicessector.(Economist.com)Services,unlikemass-producedgoods,tendtoderive valuefrominteractionbetweenthebuyer(patron)andseller(provider).Someservices,suchas paperdelivery,don'trequirealotofcollaboration.Others,suchaspersonal(athletic)training, therapy,waitservices(atrestaurantsandbars),andpaidcompanionship,havemorevaluewhen bothpartiesgetalong. Aswementionedbrieyinourintroductiontotheevolutionarymodel,thisisn'tnecessarilya matterofindividualsactingtomaximizeothers'utility.Whilepatronspayforaservice,theservice itselfvariesbasedontheprovider'sattitudetowardthepatron.Adisgruntleddoctormayhavean inferiorbedsidemanner.Thetherapist,ofapatientwithself-esteemissues,maybemorehelpfulif

PAGE 58

50 CHAPTER9.ECONOMICASPECTSANDIMPLICATIONS shedoesn'thatethepatient.Apaidcompanionisgenerallypaidtohaveorfeigna" ectionforthe personbeingaccompanied.Whilepaidcompanionsdon'tnecessarilyneedtoadoretheirpatrons (actingabilityisassumedavaluableskillintheprofession)acompanionmaynditdi! cultor impossibletopretendtolikesomeoneheloathes.Thosedininginrestaurantsmayrespondtoa waitertheylikebygivinghimagoodtip,resultinginhisbeingkinderthenexttimetheyvisit, resultinginayetlargertip.Similarly,patronsmayrespondtoawaitertheydon'tlikebytipping himpoorly,whichmayresultinthewaiterbeingrudetothemthenexttimetheyvisit,whichmay resultinthepatronswalkingout,leavingnotip. Theevolutionarymodelappliesnotonlytointeractionsbetweenpatronsandserviceproviders, butalsotosymbioticrelationshipsbetweenserviceproviders.Forexample,electricians,plumbers andotherconstructioncontractorsrecommendeachother,worktogether,andhavetogetalong. Fewpeoplelikeworkingsidebysidewiththosewhoopenlydespisethem.Psychologistsandpsychiatristshavetoworktogethertomonitordosageforthosemedicatedformentalillness.Psychiatrists oftenrelyonpsychologistsforinformationonwhetheramedicationisworking.Psychologistsneed totrustpsychiatristsinordertogivepatientsreferrals.Thesamegoesforallspecialistsinthe medicalprofession.Comicbooksandgraphicnovelscaninvolvetheworkofoneorallofthefollowing:writers,pencilers,inkers,colorists(exceptingblackandwhiteworks),letterers,and,inmany cases,coverartists(Caplan[2008]).Allofthesepeoplehavetoworktogether.(Aswe'vepresented itthusfar,ourmodeldealswithpairs,butwecouldconceiveofaversioninvolvingcoordinating thepreferencesofthreeormoreparties.Unfortunately,stablethree-dimensionalmatchingsdon't alwaysexist.SeeAlkan[1988])Theirrelationshipscanevolve.Individualwriterscanchoosetowork withthesameordi" erentillustratorsdependingonhowwelltheygetalong. Sofar,we'vepresentedhappypartnersasbeingmoredesirableduetotheirenthusiasm.Wehave assumedthathappypeopleareinherentlymorepleasant,orthatthemoreapersonvaluesapartnership,themoreshewillbewillingtosacriceinordertopreserveit.Thereisanotherpossible factor,whichwehaveignored:thatofRabinfairness. Thegrowingpopularityofbehavioraleconomicsasoflatehasencouragedtheintegrationofindividualdesireforfairnessandjusticeintomodelsofeconomicbehavior.Suchintegrationissupported bydataonthebehaviorofexperimentalsubjectsparticipatingintheUltimatumGame.TheUlti-

PAGE 59

51 matumGame,rstpresentedin1982byGuth,Werner,Schmittberger,andSchwarze 1 ,involvestwo players.Playeroneisaskedtodivideaspeciedamountofmoneybetweenhimselfandplayertwo. Playertwothengetsthechoiceofeitheracceptingthedealo" eredtohimbyplayerone,orrejecting thedeal,inwhichcaseneitherplayergetsanymoney.Thegameisnotrepeatedandtheplayersare anonymous.Iftheplayershavetraditional(non-interdependent)vonNeumann-Morgensternutility functions,weexpectplayer2toacceptanydealinwhichheisgivenapositiveamountofmoney. Experimentally,thisisnotwhatusuallyhappens.Mostplayersrejecto" ersoflessthan10%,in ordertopunishthepersonmakingtheo" erforbeingunfair'(Oosterbeeketal.[2004]pg177). Becauseoftheseresults,aneconomistnamedMatthewRabinproposedamodelofbehaviorin whichindividualsgainutilityfromenforcingwhattheyconsiderjust(theygetutilityfromhelping thosetheyseeasrighteousandfromhurtingthosetheyperceiveaswicked;seeRabin[1993].) TakingintoaccountRabinFairness',wecanseeanotherpossiblecauseforthebehaviorinour model:muchlikeintheUltimatumGame,individualsplacedwithpeopletheydon'tlike,butwho likethem,mayseethearrangementasunfair,andmaythereforetrytosabotagesucharelationship. Rabinfairnessalsosupportstheuseofourrankingmodelofutility:apersonmayjudgeamatch byhowthepersonheismatchedwithcomparestohisotherpotentialpartners.Ifallhispotential partnersareunattractive,andheismatchedwiththeleastunattractiveone,hemaybehappier thanhewouldbewereallhispotentialpartnersattractive,andhisnalmatchingwiththeleast attractiveofthem(amatchinghemightconsiderunfair'tohim). Thepracticalapplicationofourmodelmaynotbeinndingstablematchings,butinanalyzingorpredictinghowlongittakesforrankings/preferencestobecomestable(basedonthenumber ofpotentialpartners).Therearecostsassociatedwithbeinginandgettingoutofsuboptimalpartnerships.Peoplewithstill-evolvingopinionsoftheirpotentialpartnersmaydelaymakinglarge investmentsinpartnerships,untiltheyperceivethattheirpreferenceshavestabilized 2 Ifthisstabilizationofpreferencesovertimeisreectedinactualbehavior,wemaywishtoinclude,insomemodelsofsocialoreconomicbehavior,ananalysisoftimeneededforpreferencesto 1 ThisistheearliestsuchexampleaccordingtoMcCabe[2003] 2 Or,ifweincorporateopportunitycostorsearchfrictions',untiltheriskofasub-optimalpartnershipnolonger counteractstheanticipatedcostofwaitingforpreferencestostabilize.

PAGE 60

52 CHAPTER9.ECONOMICASPECTSANDIMPLICATIONS becomestable. PleaseseetheData'sectionforinformationonthenumberofroundsofre-orderingbeforepreferencesbecomestable.PleaseseethePopulationDensityandAgeofFirstMarriagesectionforan analysisofthepossibleapplicabilityofthisconjecturetomarriagedata.

PAGE 61

Chapter10 AnApplication:Population DensityandAgeofFirstMarriage Theevolutionary'modeltellsusthat,asthesizeofthegroupbeingmatchedgrows,theaverage amountoftimenecessaryforpreferencestostabilizegrowsaswell.Ifourevolving'preferences modelisaccurate,rationalindividualsconsideringpermanentpartnershipswillwanttowaituntil theirpreferencesarestable,beforepairingup.(Iftheydon'twait,theycouldendupinasub-optimal match.)Wewishtoknowwhetherdemographicdatasupportsthistheory. Informationonhowlongpeoplewaitbeforeenteringintolongtermorpermanentbusinesspartnershipsisn'treadilyavailable.Informationonhowlongpeoplewaittogetmarried,however,iseasy toobtain.Marriageisagreatexamplebecauseitrepresentsalongtermcommitment,evenwhen takingintoaccounttheriskofdivorce 1 Peoplelivinginareasofhighpopulationdensityhavealargernumberofindividualstointeract withthandopeopleinareasoflowpopulationdensity,therefore,peoplelivingindenseareasshould havealargerpotentialdatingpool.Ifpeoplehaveevolvingpreferencesconsistentwithourmodel, thoselivinginhighdensityareasshouldwaitlongertogetmarriedthanpeoplelivinginlowdensity areas 2 1 Novak(2008)claimsthatofthoseAmericanswhogetmarried,66%stayintheirrstmarriageuntildeath(the deathofeitherspouse). 2 Thisis,ofcourseageneralization.Wearespeakingoftheexpectedmedianvalue.

PAGE 62

54 CHAPTER10.POPULATIONDENSITYANDMARRIAGE Data WehavegathereddatafromtheU.S.Censuswebsite.Theinformationonpopulationdensity bystateisfromthe2000U.S.Census(themostrecentinformationwecouldnd)(Bureau[2000]). Medianageatrstmarriagedataforeachstatewasavailableseparatelyformenandwomenviathe 2005AmericanCommunitySurvey(Bureau[2005a]andBureau[2005b]).Wehavecalculatedthe approximatemedianageofrstmarriageforeachstatebyaveragingthemaleandfemalevalues. (Thegenderratiomaynotbeexactlyone,butitshouldbecloseenough'forourpurposes). WemeasuredthecorrelationbetweenageofrstmarriageandpopulationdensityintheUnited States(NotincludingDC.DCisnotastateandisanoutlierintermsofpopulationdensity,with nearlytentimesthepopulationdensityofthedenseststate): Wealsolookedatthee" ectofexcludingAlaskafromouranalysis.(Alaskahasthelargestmaleto femaleratioofanystateandhasapproximately1/5thepopulationdensityofthesecondleastdense state.Itmayactasanoutlierandskewourdata.)

PAGE 63

55 Theredoesn'tseemtobeahugee" ectontheR-squaredvalueeitherway,butwewillcontinueexcludingAlaskafromouranalysis.Wenoticethatthereisareasonablystrongcorrelation(withor withoutAlaska)betweenmedianagerstmarriageandnumberofpersonspersquaremile.The relationshipdoesn'tseemquitelinear,buttheR-squaredvalueislowerforalogarithmiccorrelation thanforthelinearcorrelation,sowewillkeepusingtheassumptionofalinearrelationship:

PAGE 64

56 CHAPTER10.POPULATIONDENSITYANDMARRIAGE Wewishtotestthehypothesisthatpopulationdensityisaexplanatoryvariableonwhichageof rstmarriageisdependent.Whilewedoseeacorrelationbetweenthetwovariables,wedonot knowifthiscorrelationisdirectorindirect.Populationdensitymaysimplyactasanunintentional proxyforanomittedthirdvariable. Thisomittedthirdvariablecouldhavetodowithlevelofeducation.Thosewhostayinschool longermaywaitlongertogetmarried.Peopleinmetropolitan(moredenselypopulated)areasmay bemorelikelytopursueasecondaryeducation.Unemploymentandpovertymayformastrongincentivetogetmarriedinordertotakeadvantageofhouseholdeconomiesofscale(cohabitationmay reducelivingexpenses 3 ).Alternatively,thoselivingunderthepovertylineorwithoutemployment maywishtodelaystartingafamily'untiltheyfeelmorenanciallysecure.Unemploymentand povertyratesmayalsocorrelatewithpopulationdensity,givingusthefalseimpressionofadirect relationshipbetweenpopulationdensityandageofrstmarriage. Wecouldre-runouranalysisincludingvariablesfortheseandothersocioeconomicfactors.Our smallnumberofdatapoints(only49,nowthatwehaveexcludedAlaska),however,makesitimpossibleforustousealotofexplanatoryvariablesatonce(thestandarderrorsgrowtoolarge).Ideally, wewouldliketousedataorganizedbyindividual,ratherthanbystate.Wecouldgetdataonthe populationdensityofthetownorcityeachindividuallivesin(weassumepeoplearemorelikelyto datethoseinthesametownthanthosewholiveacrossthestate),aswellasassortedsocioeconomic data. Fortunately,thisworkhasalreadybeendoneforus.ThearticleSomeWomenMarryYoung: TransitionstoFirstMarriageinMetropolitanandNonmetropolitanAreas,'waspublishedinthe JournalofMarriageandtheFamilyin1993.Theauthors,McLaughlin,LichterandJohnston,look forfactorsthatexplainthestrongcorrelationbetweentheageatwhichwomenenterintotheirrst marriageandthewomen'sresidenceinmetropolitanversusnon-metropolitanareas 4 .Theauthors... ...examinetheextenttowhichthetimingofrstmarriagedi" ersformetropolitanand non-metropolitanyoungwomen.Individual-leveldatafromtheNationalLongitudinal SurveyofYoutharematchedtolocalmarriagemarketconditionstoestimatediscrete 3 Cohabitationdoesnotimplymarriage,butwemayseeacorrelation. 4 Residenceinametropolitanversusnonmetropolitanareaisrepresentedintheregressionanalysisviaabinary dummyvariable.

PAGE 65

57 timehazardmodelsoftransitionstorstmarriage.(McLaughlinetal.[1993]pg827) Explanatoryvariablesusedincludethewoman'srace,levelofeducation,parents'maritalstatus, mother'slevelofeducation,earnings,employmentstatusovertheprioryear,receiptofpublicassistance,enrollmentinschool,cohabitation,thesexratiowhereshelives,theunemploymentrate fornearbymen,thepovertyratefornearbymen,whethershehasanychildren,andwhethershe livesintheSouth.Theauthorsalsoexamineeachwoman'sattitudetowardwomen'srolesandemployment,'viaasurvey,andlookintowhetherthesetheresultsareusefulasanexplanatoryvariable. Theauthorsconclude,Youngnonmetropolitanwomenmarryatayoungeragethanmetropolitanwomen,adi" erenceonlypartiallyexplainedbyvariationsintheattributesoftheyoungwomen, theirfamilies,andthelocalmarriagemarket.(McLaughlinetal.[1993]pg827).Inotherwords,the dummyvariableformetropolitanversusnon-metropolitanresidencewasstillconsideredsignicant aftertheincorporationofthesefactors. Lackingotherfactorsthatmightexplainthecorrelation,wesuggestthatwomeninareasofhigh populationdensitywaitlongertogetmarriedbecausetheyhavealargerdatingpool,whichresults intheirpreferencestakinglongertostabilize.

PAGE 67

Chapter11 ConjecturesandVariationsonOur Model,forPossibleFutureStudy 11.1Variations Wehavepresentedabasicmodelforevolvingpreferences.Ourdenitionofutilityisarbitrary.As statedearlier,wecouldjustaseasilydeneanonlinearrelationshipbetweenrankingandutility, suchas: Utility=(placeonlist) n where n< $ 1 or n ( placeonlist ) where0
PAGE 68

60 CHAPTER11.CONJECTURESANDVARIATIONS ...wherekisaconstantdetermininghowmuch caresabout 'shappiness.Inourmodel,everyone discoverseveryoneelse'srankingssimultaneously,andtheneveryonereordershisorherrankingssimultaneously.Wecouldhaveaversion,inwhichgroupstaketurnsreorderingtheirrankings.For example,inthemarriagemodel,thewomencouldreordertheirrankingsrst.Themencouldthen reordertheirrankings,basingtheirestimatesforJoint-Utilityontheir(original)rankingsandthe women's(nowrevised)rankings.Thenthewomencouldreordertheirrankingsbasedontheirand themen'sonce-revisedrankings.Thenthemenwouldreordertheirrankingsbasedonthewomen's twice-revisedandtheironcerevisedrankings,andsoon,untilrankingsstabilize. Insteadofadatingfollowedbymarriagemodel,wecouldhaveamodelinwhicheveryoneisalwayspairedup,butblindtotheopinionsofanyonebuthisorherpartnerforanygivenround. Forexample,saywomenA,B,andCarebeingmatchedwithmenD,E,andF.Westarto"with everyonepairedup.Let'ssaywomanAstartso"pairedwithmanD.WomanAandmanDknow whattheythinkofeachother,soAandDestimatetheirjoint-utilityviaourJoin-Utilityfunction. WomanAdoesnotknowwhatmenEandFthinkofher;sheassumestheyhavegivenherthe samerankingshehasgiventoeachofthem.Athenreordersherrankings,estimatingherjointutilityfromamatchwithEorFtobeequalto2 % n $ 2 % (rankingofman E onwoman A 'slist) or2 % n $ 2 % (rankingofman F onwoman A 'slist),respectively.Otherparticipantsestimatetheir joint-utilitysimilarly.TheparticipantsarethenpairedviatheStableMatchingAlgorithm(inaccordancewiththeirnewpreferences).Everyonethenreordershisorherrankings(again). AswementionedinChapter8,somemodelsofone-to-onematchingincludereputation'asafactor. Mostofthesemodelsusereputationasaproxyformissinginformation.Ourparticipantsaren't tryingtodeciphereachother'snoisysignals.However,theymaycareabouttheirpartners'potential useasapositionalgood. Positionalgoodsaregoodsconsumedprimarilytoimpressothers.Oneexampleofapositional goodiswardrobeforjobinterviews.Inanexperiment,whengiventhechoicebetweenthefollowing twohypotheticalscenarios: A:Youhavea$200outttoweartojobinterviews;otherpeoplehave$100outts. B:Youhavea$400outttoweartojobinterviews;otherpeoplehave$600outts. (Solnick&Hemenway[2005]pg18)

PAGE 69

11.2.CONJECTURES 61 Sixty-twopercentofsurveyrespondentschoseoptionA(Solnick&Hemenway2005,pg14).Aless positionalgood,accordingtothissamesurvey,islifeexpectancy.Whengivenachoicebetweenthe followingtwoscenarios: A:Lifeexpectancyinyourcountryis72years;inothercountriesitis80years. B:Lifeexpectancyinyourcountryis68years;inothercountriesitis60years. (Solnick&Hemenway[2005]pg17) ElevenpercentofrespondentschoseoptionA.(Solnick&Hemenway[2005]pg14) Choosingalifepartnermay,tosome,beanon-positionalgood.However,thefactthateleven percentofparticipantsinthisexperimentsawlifeexpectancyasapositionalgood,suggeststhat thereareprobablysomepeopleforwhomanattractivespouseisapositionalgood.Wecaneasily conceiveofaversionofourevolutionarypreferencemodel,inwhichpeoplereordertheirpreferences notonlybasedontheirownpreferencesandthepreferencesoftheirpotentialspouses,butalsobased onthepopularityofthepotentialspouses. 11.2Conjectures InChapter6.2,weconductedanexperimenttodiscoverhowgroupsizea" ectsthenumberofrounds ofreorderingnecessaryforrankingstostabilize.Itappearsthatthemeanandmediannumberof roundsneededgrowslogarithmicallywithgroupsize.Wesawsomeoddbehaviorbetweengroup sizes13and14.Wewerenotabletogetanyusefulexperimentaldataonthemaximumnumberof trials. Wetheorizethatthemeanandmediannumberoftrialsneededgrowslogarithmicallyorsemilogarithmically.Wetheorizefurtherthat,neargroupsizes13and14,thereisasuddengainin meanandmediannumberofroundsneeded.Futurestudymightyieldamodelorexplanationof thisbehavior. Furtherstudymayalsoshowhowthemaximumpossiblenumberofroundsofreorderingneeded toreachstabilityvarieswithgroupsize.Basedonourtrialdata,wesuggestthatthemaximum possiblenumberofroundstostabilitygrowsquicklywithgroupsize,butthatthepercentofsetsof preferencesrequiringthemaximumnumberofroundsdecreaseswithgroupsize.

PAGE 70

62 CHAPTER11.CONJECTURESANDVARIATIONS Wehaveproposed(whatwebelievetobe)anewvariantoftheStableMarriageProblem.We havedemonstratedhowpreferencesinourmodelevolveandstabilize.Wehaveexploredsomeeconomicandmathematicalaspectsofourmodel.Weleavewithabetterunderstandingofourmodel, someunexpectedobservations,andseveralunansweredquestionsforfuturestudy.

PAGE 71

AppendixA Programs r randranks.m Theprogram r_randranks.m createsasetofrankingmatricesofsizen(tobespeciedbyuser) andoutputsthemasMandW.TherowsofMandthecolumnsofWcorrespondtorankinglists. TousethisprogramweaddittooneofMATLAB'sdirectoriesorincludeitinthepathand typeinthecommandwindow: [M,W]=r_randranks(n) Wherenisthenumberofmembersofeachgroup(inmarriagecontext:n=numberofwomen=number ofmen)andMandWarewhatevernamestheuserwantstostoreeachmatrixas.Forexample,if wetype: [X,Y]=r_randranks(3) Theprogramwillcreatetwo3x3matricescalledXandY.X'srowsandY'scolumnswillrepresent thepreferencelistsofthemembersofgroupsXandY,respectively. %r_randranks.m function[M,W]=r_randranks(n); M=zeros(n); W=zeros(n); fork=1:n M(k,:)=randperm(n); W(:,k)=randperm(n)';

PAGE 72

64 APPENDIXA.PROGRAMS end Theoutputwilllooksomethinglikethis: EDU>>[X,Y]=r_randranks(3) X= 312 132 132 Y= 333 122 211 EDU>>

PAGE 73

65 r MakePgsRanks.m Theprogram r_MakePgsRanks.m usesthe r_randranks.m programtocreatespairsof n by n ranking matrices.Werefertothe q thpreferencematrixfromgroup M as: PgsM(:,:,q) andthe q th preferencematrixfromgroup W as: PgsW(:,:,q) %r_MakePgsRanks.m function[PgsM,PgsW]=r_MakePgsRanks(n,s) pgs_done=0; PgsM=[]; PgsW=[]; whilepgs_done
PAGE 74

66 APPENDIXA.PROGRAMS r Match Alg.m r_Match_Alg.m usestheM-optimalversionoftheGale-ShapleyAlgorithmtomatcheveryoneup. BecausetherowsofMandcolumnsofWarerankinglists,ifwewanttondtheW-optimalmatching, wetypein: [w_partner,m_partner]=r_Match_Alg(W',M') wheninitializingthealgorithm.The 'functioninMATLABgivesusthetransposeofthematrix.Now,thecolumnsofMandrowsofW arerankinglists. %r_Match_Alg.m function[m_partner,w_partner]=r_Match_Alg(M,W)%note:wedidn'treallyhave %tocreateseperatepartnerlistsforthemenandwomen,however,this %makestheprogrammingeasier,albeitlesselegant n=length(M); w_partner=zeros(1,n);%noonepartneredupyet m_partner=zeros(1,n); m_opt=zeros(1,n);%m_opt(man)istherankingonman'slistofthelastwomanheasked whilesum(~(m_partner)) forman=1:n%foreachman if~(m_partner(man))%ifthemanisnotyetpartneredup m_opt(man)=m_opt(man)+1;%themanthinksofhisnextbestchoice w_ask=find(M(man,:)==m_opt(man));%hisnextbestchoiceisthewomanhewillask if~(w_partner(w_ask))%ifthewomanbeingaskedisnotyetpartnered w_partner(w_ask)=man;%sheautomaticallysaysyesandispartnered m_partner(man)=w_ask;%andthemanispartnered elseifW(man,w_ask)
PAGE 75

67 end

PAGE 76

68 APPENDIXA.PROGRAMS r reorder ranks.m The r_reorder_ranks.m programreorderstherankingmatricesMandWonce(therankingsmay ormaynotbestableafteronlyoneround)andstoresthereorderedmatricesas r_NewM and r_NewW %r_reorder_ranks.m function[r_NewM,r_NewW]=r_reorder_ranks(M,W) t=length(W); [r_comboM,r_comboW]=r_combo(M,W); [extraneous_crap,r]=sort(r_comboM'); r=r'; v=zeros(t); fork=1:t forw=1:t v(k,r(k,w))=w; end end r_NewM=v; [extraneous_crap,r]=sort(r_comboW); v=zeros(t); fork=1:t forw=1:t v(r(w,k),k)=w; end end r_NewW=v;

PAGE 77

69 r combo M.m r_combo_M.m isaprogramusedby r_reorder_ranks.m .Wewillneveruseitdirectly. %r_combo.m function[r_comboM,r_comboW]=r_combo(M,W); %notethisistherevisedsystem,whereinanibyjmatrixialways %representsmenandjalwaysrepresentswomeninboththemen'sprefmatrix %andinthewomen'srankingmatrix. t=length(M); s=(10^(-(t+1))); r_comboM=(M+W+M*s); r_comboW=(W+M-M*s); end

PAGE 78

70 APPENDIXA.PROGRAMS r until stable.m r_until_stable.m tellsushowmanyroundsofreorderingtherankingmatricesMandWhaveto undergobeforetherankingsstabilize. \verb#number_trials#=thenumberofroundsofreordering \verb#r_NewM#isthefinal(stable)rankingsmatrixforgroupM \verb#r_NewW#isthefinal(stable)rankingsmatrixforgroupW %r_until_stable.m function[number_trials,r_NewM,r_NewW]=r_until_stable(M,W); number_trials=-1; t=length(M); r_OldM=zeros(t); r_OldW=zeros(t); r_NewM=M; r_NewW=W; whilesum(sum((abs(r_OldM-r_NewM)+abs(r_OldW-r_NewW))))>eps%whilethenewsetofranksisdifferentfromthepervioussetofranks r_OldM=r_NewM;%thenewranksarenowthepreviodranks r_OldW=r_NewW;%ditto [r_NewM,r_NewW]=r_reorder_ranks(r_OldM,r_OldW);%wereorderthenowoldrankstogetthenewranksforthisround number_trials=number_trials+1; end

PAGE 79

71 r many trial one size.m %r_many_trial_one_size.m function[trials_needed]=r_many_trial_one_size(n,trials); trials_needed=[]; fork=1:trials [M,W]=r_randranks(n); [number_trials]=r_until_stable(M,W); if(number_trials>5) M; W; number_trials; end trials_needed=[trials_needed,number_trials]; k; end

PAGE 80

72 APPENDIXA.PROGRAMS r rand mult size MW simult.m %r_rand_mult_size_MW_simult.m initial_men=input('Pleaseenterinitialnumberofmen:>') increment_men=input('Pleaseentertheincrement(mustbeawholenumber):>') final_men=input('Pleaseenterthefinalnumberofmen:>') s=input('Pleaseenternumberoftrials:>') group_sizes=[initial_men:increment_men:final_men]; r_Rounds_Needed_for_Each=[]; fork=1:length(group_sizes) n=group_sizes(k) s=s [PgsM,PgsW]=r_MakePgsRanks(n,s); r_Final_Rounds_Needed=[]; fork=1:s M=PgsM(:,:,k); W=PgsW(:,:,k); [Rounds_Needed]=r_until_stable(M,W); r_Final_Rounds_Needed=[r_Final_Rounds_Needed,Rounds_Needed]; end r_Rounds_Needed_for_Each=cat(3,r_Rounds_Needed_for_Each,r_Final_Rounds_Needed); end r_Rounds_Needed_for_Each;

PAGE 81

AppendixB RepeatingAnExperiment Aswasstatedinfootnote11,weranourexperimentasecondtimetoseeiftherewasajumpin meannumberoftrialsbetweengroupsizes13and14: Wesawamorepronouncedjumpthanwedidinthepreviousattempt.Thejumpislocatedin thesameplace:betweengroupsizes13and14.Furthermore,inthissecondattempt,wealsonoticedajumpinthemediannumberofroundsuntilstability:

PAGE 82

74 APPENDIXB.REPEATINGANEXPERIMENT Thissuggeststhatthejumpwasnotaquirkofourrandomdatafromthersttimewedidthis experiment.

PAGE 83

REFERENCES 75 References AhmetAlkan.Nonexistenceofstablethreesomematchings. "Mathematical Social Sciences,16(2): 207209,1988. AxelAndersonandLonesSmith.Assortativematchingandreputation. SSRN eLibrary,2006. U.S.CensusBureau.Census2000summaryle1(sf1)100-percentdata:Datasetgct-ph1-r. population,housingunits,area,anddensity(geographiesrankedbytotalpopulation)',2000. URL http://factfinder.census.gov/servlet/GCTTable?_bm=n&_lang=en&mt_name=DEC_ 2000_SF1_U_GCTPH1R_US9S&format=US-9S&_box_head_nbr=GCT-PH1-R&ds_name=DEC_2000_ SF1_U&geo_id=01000US U.S.CensusBureau.2005americancommunitysurvey;datasetr1204.medianageatrstmarriage formen:2005',2005a.URL http://factfinder.census.gov/servlet/GRTTable?_bm=y&-geo_ id=01000US&-_box_head_nbr=R1204&-ds_name=ACS_2005_EST_G00_&-_lang=en&-redoLog= false&-mt_name=ACS_2005_EST_G00_R1204_US30&-format=US-30 U.S.CensusBureau.2005americancommunitysurvey;datasetr1205.medianageatrstmarriage forwomen:2005',2005b.URL http://factfinder.census.gov/servlet/GRTTable?_bm= y&-ds_name=ACS_2005_EST_G00_&-_col=disp_order&-CONTEXT=grt&-mt_name=ACS_2005_ EST_G00_R1205_US30&-_source=mdr&-redoLog=false&-geo_id=01000US&-format=US-30&-_ lang=en BryanCaplan.Divisionoflaboringraphicnovels. EconLog,2008.URL http://econlog.econlib. org/archives/2007/04/division_of_lab.html HectorChade.Matchingwithnoiseandtheacceptancecurse. Journal of Economic Theory,129(1): 81113,2006.

PAGE 84

76 REFERENCES HectorChade,GregLewis,andLonesSmith.Thecollegeadmissionsproblemunderuncertainty. Society for Economic Dynamics,2006.URL http://ideas.repec.org/p/red/sed006/125.htm HenryCunynghame.Someimprovementsinsimplegeometricalmethodsoftreatingexchangevalue, monopoly,andrent. The Economic Journal,2(5):3552,1892. TheEconomist.services,unknown.URL http://www.economist.com/research/economics/ searchActionTerms.cfm?query=services BeltonMFleisher. The Economics of Delinquency.QuadrangleBooks,Chicago,1966. D.GaleandL.S.Shapley.Collegeadmissionsandthestabilityofmarriage. The American Mathematical Monthly,69(1):915,1962. DanGuseldandRobertW.Irving. The Stable Marriage Problem : Structure and Algorithms. MITPress,Cambridge,Mass,1995. WernerGuth,RolfSchmittberger,andBerndSchwarze.Anexperimentalanalysisofultimatum bargaining. Journal of Economic Behavior & Organization,3(4):367388,1982. JohnLocke. Some Considerations of the Consequences of the Lowering of Interest, and Raising the Value of Money.HistoryofEconomicThoughtBooks.McMasterUniversityArchivefor theHistoryofEconomicThough,1691.URL http://socserv.mcmaster.ca/econ/ugcm/3ll3/ locke/consid.txt RogerMason.Interpersonale" ectsonconsumerdemandineconomictheoryandmarketingthought, 1890-1950. Journal of Economic Issues,29,1995. KevinMcCabe.Whatistheultimatumgame?,2003.URL http://neuroeconomics.typepad. com/neuroeconomics/2003/09/what_is_the_ult.html DianeK.McLaughlin,DanielT.Lichter,andGailM.Johnston.Somewomenmarryyoung:Transitionstorstmarriageinmetropolitanandnonmetropolitanareas. Journal of Marriage and the Family,55(4):827838,1993. OskarMorgenstern.Demandtheoryreconsidered. The Quarterly Journal of Economics,62(2): 165201,1948. MichaelNovak.Understandingamerica:Theanatomyofanexceptionalnation.In Understanding America: The Anatomy of an Exceptional Nation.AmericanEnterpriseInstituteforPublic

PAGE 85

REFERENCES 77 PolicyResearch,April2008.URL http://www.aei.org/events/filter.all,eventID.1691/ transcript.asp HesselOosterbeek,RandolphSloof,andGijsvandeKuilen.Culturaldi" erencesinultimatumgame experiments:Evidencefromameta-analysis. Experimental Economics,7(2):171188,062004. URL http://ideas.repec.org/a/kap/expeco/v7y2004i2p171-188.html MichaelOstrovsky,ArchishmanChakraborty,andAlessandroCitanna.Two-sidedmatchingwith interdependentvalues.In 2008 AEA Conference.AEA,January2008.URL http://www.aeaweb. org/annual_mtg_papers/2008/2008_334.pdf MatthewRabin.Incorporatingfairnessintogametheoryandeconomics. The American Economic Review,83(5):12811302,1993. RobertShimerandLonesSmith.Assortativematchingandsearch. Econometrica,68(2):343369, 2000. LonesSmith.TheMarriageModelWithSearchFrictions. Journal of Political Economy, Vol. 114, pp. 1124-1144, December 2006,1997. SaraJ.SolnickandDavidHemenway.Arepositionalconcernsstrongerinsomedomainsthanin others? American Economic Review,95(2):147151,May2005.URL http://ideas.repec.org/ a/aea/aecrev/v95y2005i2p147-151.html ThorsteinVeblen. The Theory of the Leisure Class.OxfordUniversityPressInc.,Oxford,1899. republished2007.