Economic properties of social networks

ShamM.KakadeMichaelKearnsLuisE.Ortiz

RobinPemantleSiddharthSuri

UniversityofPennsylvania

Philadelphia,PA19104

Abstract

Weexaminethemarriageofrecentprobabilisticgenerativemodelsforsocialnetworkswithclassicalframeworksfrommathematicaleco-nomics.Weareparticularlyinterestedinhowthestatisticalstructureofsuchnetworksinfluencesglobaleconomicquantitiessuchaspricevari-ation.Ourfindingsareamixtureofformalanalysis,simulation,andexperimentsonaninternationaltradedatasetfromtheUnitedNations.

1Introduction

Thereisalonghistoryofresearchineconomicsonmathematicalmodelsforexchangemar-kets,andtheexistenceandpropertiesoftheirequilibria.TheworkofArrowandDebreu[1954],whoestablishedequilibriumexistenceinaverygeneralcommoditiesexchangemodel,wascertainlyoneofthehighpointsofthiscontinuinglineofinquiry.TheoriginsofthefieldgobackatleasttoFisher[1891].

Whiletherehasbeenrelativelyrecentinterestinnetworkmodelsforinteractionineco-nomics(seeJackson[2003]foragoodreview),itwasonlyquiterecentlythatanetworkorgraph-theoreticmodelthatgeneralizestheclassicalArrow-DebreuandFishermodelswasintroduced(Kakadeetal.[2004]).Inthismodel,theedgesinanetworkoverindividualconsumers(forexample)representthosepairsofconsumersthatcanengageindirecttrade.Assuch,themodelcapturesthemanyreal-worldsettingsthatcangiverisetolimitationsonthetradingpartnersofindividuals(regulatoryrestrictions,socialconnections,embargoes,andsoon).Inaddition,variationsinthepriceofagoodcanariseduetothetopologyofthenetwork:certainindividualsmayberelativelyfavoredorcursedbytheirpositioninthegraph.

Inaparalleldevelopmentoverthelastdecadeorso,therehasbeenanexplosionofinterestinwhatisbroadlycalledsocialnetworktheory—thestudyofapparently“universal”propertiesofnaturalnetworks(suchassmalldiameter,localclusteringofedges,andheavy-taileddistributionofdegree),andstatisticalgenerativemodelsthatexplainsuchproperties.Whenviewedaseconomicnetworks,theassumptionsofindividualrationalityintheseworksareusuallyeithernon-existent,orquiteweak,comparedtotheArrow-DebreuorFishermodels.

Inthispaperweexamineclassicaleconomicexchangemodelsinthemodernlightofsocialnetworktheory.Weareparticularlyinterestedintheinteractionbetweenthestatisticalstructureoftheunderlyingnetworkandthevariationinpricesatequilibrium.Wequantifytheintuitionthatincreasedlevelsofconnectivityinthenetworkresultintheequalizationof

prices,andestablishthatcertaingenerativemodels(suchasthethepreferentialattachmentmodelofnetworkformation(BarabasiandAlbert[1999])arecapableofexplainingtheheavy-taileddistributionofwealthfirstobservedbyPareto.CloselyrelatedworktooursisthatofKrantonandMinehart[2001],whichalsoconsidersnetworksofbuyersandsellers,thoughtheyfocusmoreontheeconomicsofnetworkformation.

Manyofourresultsarebasedonapowerfulnewlocalapproximationmethodforglobalequilibriumprices:weshowthatinthepreferentialattachmentmodel,pricescomputedfromonlylocalregionsofanetworkyieldstrikinglygoodestimatesoftheglobalprices.Weexploitthismethodtheoreticallyandcomputationally.OurstudyconcludeswithanapplicationofourmodeltoUnitedNationsinternationaltradedata.

2MarketEconomiesonNetworks

WefirstdescribethestandardFishermodel,whichconsistsofasetofconsumersandasetofgoods.Weassumethatthereareunitsofgoodinthemarket,andthateachgoodisbesoldatsomeprice.Eachconsumerhasacashendowment,tobeusedtopurchasegoodsinamannerthatmaximizestheconsumers’utility.Inthispaperwemakethewell-studiedassumptionthattheutilityfunctionofeachconsumerislinearintheamountofgoodsconsumed(seeGale[1960]),andleavethemoregeneralcasetofutureresearch.Let

denotetheutilityderivedbyonobtainingasingleunitofgood.Ifconsumesamountofgood,thentheutilityderivesis.Asetofpricesandconsumptionplansingtwoconditionshold:

constitutesanequilibriumifthefollow-.

1.Themarketclears,i.e.supplyequalsdemand.Moreformally,foreach,

2.Foreachconsumer,theirconsumptionplanisoptimal.Bythiswemeanthattheconsumptionplanmaximizesthelinearutilityfunctionof,subjecttotheconstraintthatthetotalcostofthegoodspurchasedbyisnotmorethantheendowment.Itturnsoutthatsuchanequilibriumalwaysexistsifeachgoodhasaconsumerwhichderivesnonzeroutilityforgood—thatis,forsome(seeGale[1960]).Further-more,theequilibriumpricesareunique.

WenowconsiderthegraphicalFishermodel,sonamedbecauseoftheintroductionofagraph-theoreticornetworkstructuretoexchange.InthebasicFishermodel,weimplicitlyassumethatallgoodsareavailableinacentralizedexchange,andallconsumershaveequalaccesstothesegoods.InthegraphicalFishermodel,wedesiretocapturethefactthateachgoodmayhavemultiplevendorsorsellers,andthatindividualbuyersmayhaveaccessonlytosome,butnotall,ofthesesellers.Thereareinnumerablesettingswheresuchasym-metriesarise.Examplesincludethefactthatconsumersgenerallypurchasetheirgroceriesfromlocalmarkets,thatsocialconnectionsplayamajorroleinbusinesstransactions,andthatsecuritiesregulationspreventcertainpairsofpartiesfromengaginginstocktrades.Withoutlossofgenerality,weassumethateachsellersellsonlyoneoftheavailablegoods.(Eachgoodmayhavemultiplecompetingsellers.)Letbeabipartitegraph,wherebuyersandsellersarerepresentedasvertices,andalledgesarebetweenabuyer-sellerpair.Thesemanticsofthegraphareasfollows:ifthereisanedgefrombuyertoseller,thenbuyerispermittedtopurchasefromseller.Notethatifbuyerisconnectedtotwosellersofthesamegood,hewillalwayschoosetopurchasefromthecheapersource,sincehisutilityisidenticalforbothsellers(theysellthesamegood).

ThegraphicalFishermodelisaspecialcaseofamoregeneralandrecentlyintroducedframework(Kakadeetal.[2004]).Oneofthemostinterestingfeaturesofthismodelisthefactthatatequilibrium,significantpricevariationscanappearsolelyduetostructuralprop-ertiesoftheunderlyingnetwork.Wenowdescribesomegenerativemodelsofeconomies.

3GenerativeModelsforSocialNetworks

Forsimplicity,inthesequelwewillconsidereconomiesinwhichthenumbersofbuyersandsellersareequal.Wewillalsorestrictattentiontothecaseinwhichallsellerssellthesamegood1.

Thesimplestgenerativemodelforthebipartitegraphmightbetherandomgraph,inwhicheachedgebetweenabuyerandasellerisincludedindependentlywithprobability.ThisissimplythebipartiteversionoftheclassicalErdos-Renyimodel(Bollobas[2001]).Manyresearchershavesoughtmorerealisticmodelsofsocialnetworkformation,inordertoexplainobservedphenomenasuchasheavy-taileddegreedistributions.Wenowdescribeaslightvariantofthepreferentialattachmentmodel(seeMitzenmacher[2003])forthecaseofabipartitegraph.Westartwithagraphinwhichonebuyerisconnectedtooneseller.Ateachtimestep,weaddonebuyerandonesellerasfollows.Withprobability,thebuyerisconnectedtoasellerintheexistinggraphuniformlyatrandom;andwithprobability

,thebuyerisconnectedtoasellerchoseninproportiontothedegreeoftheseller(preferentialattachment).Simultaneously,asellerisattachedinasymmetricmanner:withprobabilitythesellerisconnectedtoabuyerchosenuniformlyatrandom,andwithprobabilitythesellerisconnectedunderpreferentialattachment.Theparameterinthismodelthusallowsustomovebetweenapurepreferentialattachmentmodel(),andamodelclosertoclassicalrandomgraphtheory(),inwhichnewpartiesare

2

connectedtorandomextantparties.

Notethattheabovemodelalwaysproducestrees,sincethedegreeofanewpartyisalways1uponitsintroductiontothegraph.Wethuswillalsoconsideravariantofthismodelinwhichateachtimestep,anewsellerisstillattachedtoexactlyoneextantbuyer,whileeachnewbuyerisconnectedtoextantsellers.Theprocedureforedgeselectionisasoutlinedabove,withthemodificationthatthenewedgesofthebuyerareaddedwithoutreplacement—meaningthatweresamplesothateachbuyergetsattachedtoexactlydistinctsellers.IntheAppendix,weprovideresultsonthestatisticsofthesenetworks.Themainpurposeoftheintroductionofistohaveamodelcapableofgeneratinghighlycyclical(non-tree)networks,whilehavingjustasingleparameterthatcan“tune”theasym-metrybetweenthe(numberof)opportunitiesforbuyersandsellers.Therearealsoeco-nomicmotivations:itisnaturaltoimaginethatnewsellersofthegoodariseonlyuponobtainingtheirfirstcustomer,butthatnewbuyersarrivealreadyawareofseveralalterna-tivesellers.

Inthesequel,weshallrefertothegenerativemodeljustdescribedasthebipartite-model.Wewillusetodenotethenumberofbuyersandthenumberofsellers,sothenetworkhasvertices.Figure1anditscaptionprovideanexampleofanetworkgener-atedbythismodel,alongwithadiscussionofitsequilibriumproperties.

4EconomicsoftheNetwork:Theory

Wenowsummarizeourtheoreticalfindings.SketchesoftheproofsareprovidedintheAppendix.Wefirstpresentaratherintuitive“frontier”theorem,whichimpliesaschemeinwhichwecanfindupperandlowerboundsontheequilibriumpricesusingonlylocalcomputations.Tostatethetheoremwerequiresomedefinitions.First,notethatanysubsetofbuyersandsellersdefinesanaturalinducedeconomy,wheretheinducedgraphconsistsofalledgesbetweenbuyersandsellersinthatarealsoin.Wesaythat

Fromamathematicalandcomputationalstandpoint,thisrestrictionisratherweak:whencon-sideredinthegraphicalsetting,italreadycontainsthesettingofmultiplegoodswithbinaryutilityvalues,sinceadditionalgoodscanbeencodedinthenetworkstructure.2

WenotethatstilldoesnotexactlyproducetheErdos-Renyimodelduetotheincrementalnatureofthenetworkgeneration:earlybuyersandsellersarestillmorelikelytohavehigherdegree.

1

S5: 0.33S7: 0.33S11: 0.33S8: 1.00S9: 1.00B3B10B2B6S6: 1.00B9S0: 2.00B1B14S1: 2.00B8B13B5B12S13: 1.00B11B7B0S2: 2.00S14: 0.50S3: 1.00S12: 1.00B4S4: 0.50S10: 1.00Figure1:Samplenetworkgeneratedbythebipartite

-model.Buyersandsellers

arelabeledby‘B’or‘S’respectively,followedbyanindexindicatingthetimestepatwhichtheywereintroducedtothenetwork.Thesolidedgesinthefigureshowtheexchangesubgraph—thosepairsofbuyersandsellerswhoactuallyexchangecurrencyandgoodsatequilibrium.Thedottededgesareedgesofthenetworkthatareunusedatequilibriumbecausetheyrepresentinferiorpricesforthebuyers,whilethedashededgesareedgesofthenetworkthathavecompetitiveprices,butareunusedatequilibriumduetothespecificconsumptionplanrequiredformarketclearance.Eachsellerislabeledwiththepricetheychargeatequilibrium.Theexampleexhibitsnon-trivialpricevariation(from2.00downto0.33perunitgood).Notethatwhilethereappearstobeacorrelationbetweensellerdegreeandprice,itisfarfromadeterministicrelation,atopicweshallexaminelater.

hasabuyer(respectively,seller)frontierifonevery(simple)pathinfromanodeintoanodeoutsideof,thelastnodeinonthispathisabuyer(respectively,seller).Theorem1(FrontierBound)Ifhasasubgraphwithaseller(respectively,buyer)frontier,thentheequilibriumpriceofanygoodintheinducedeconomyonisalowerbound(respectively,upperbound)ontheequilibriumpriceofin.

Theorem1impliesasimplepriceupperbound:thepricecommandedbyanysellerisboundedbyitsdegree.Althoughthesameupperboundcanbeseenfromfirstprinciples,itisinstructivetoapplyTheorem1.Letbetheimmediateneighborhoodof(whichisanditsbuyers);thentheequilibriumpriceinisjust,sinceallbuyersareforcedtobuyfromseller.Thisprovidesanupperboundsincehasabuyerfrontier.Sinceitcanbeshownthatthedegreedistributionobeysapowerlawinthebipartite-model,wehaveanupperboundonthecumulativepricedistribution.Weuse.Theorem2Inthebipartite-model,theproportionofsellerswithpricegreaterthanis.Forexample,if(purepreferentialattachment)and,theproportionfallsoffas.Wedonotyethavesuchaclosed-formlowerboundonthecumulativepricedistribution.However,asweshallseeinSection5,thepricedistributionsseeninlargesimulationresultsdoindeedshowpower-lawbehavior.Interestingly,thisoccursdespitethefactthatdegreeisapoorpredictorofindividualsellerprice.

10Cumulative of Degree/Price010010Maximum to Minimum Wealth310Maximum to Minimum Wealth3k=110!1!=1102Average Error10!1k=210210!2!=21!=3!=410!310!2k=31010110!4k=4!110100Degree/Price10110210!350100150N200250101100N10210000.20.4alpha0.60.81Figure2:Seetextfordescriptions.

Anotherquantityofinterestiswhatwemightcallpricevariation—theratioofthepriceoftherichestsellertothepoorestseller.Thefollowingtheoremaddressesthis.Theorem3Inthebipartite

-model,if

,thentheratioofthemaximum

.

.Forthe

pricetotheminimumpricescaleswithnumberofbuyersassimplestcaseinwhichand,thislowerboundisjust

WeconcludeourtheoreticalresultswitharemarkonthepricevariationintheErdos-Renyi(randomgraph)model.First,letuspresentaconditionfortheretobenopricevariation.Theorem4Anecessaryandsufficientconditionfortheretobenopricevariation,ieforallpricestobeequalto,isthatforallsetsofvertices,,whereisthesetofverticesconnectedbyanedgetosomevertexin.

Thiscanbeviewedasanextremelyweakversionofstandardexpansionpropertieswell-studiedingraphtheoryandtheoreticalcomputerscience—ratherthandemandingthatneighborsetsbestrictlylarger,wesimplyaskthattheynotbesmaller.Onecanfurthershowthatforlarge,theprobabilitythatarandomgraph(foranyedgeprobability)obeysthisweakexpansionpropertyapproaches1.Inotherwords,intheErdos-Renyimodel,thereisnovariationinprice—astarkcontrasttothepreferentialattachmentresults.

5EconomicsoftheNetwork:Simulations

Wenowpresentanumberofstudiesonsimulatednetworks(generatedaccordingtothebipartite-model).EquilibriumcomputationsweredoneusingthealgorithmofDeva-nuretal.[2002](orviatheapplicationofthisalgorithmtolocalsubgraphs).Wenotethatitwasonlytherecentdevelopmentofthisalgorithmandrelatedonesthatmadepossiblethesimulationsdescribedhere(involvinghundredsofbuyersandsellersinhighlycyclicalgraphs).However,eventhespeedofthisalgorithmlimitsourexperimentstonetworkswith

ifwewishtorunrepeatedtrialstoreducevariance.Manyofourresultssuggest

thatthelocalapproximationschemesdiscussedbelowmaybefarmoreeffective.PriceandDegreeDistributions:Thefirst(leftmost)panelofFigure2showsempiricalcumulativepriceanddegreedistributionsonaloglogscale,averagedover25networksdrawnaccordingtothebipartite-modelwith.Thecumulativedegreedistributionisshownasadottedline,wherethey-axisrepresentsthefractionofthesellerswithdegreegreaterthanorequalto,andthedegreeisplottedonthex-axis.Similarly,thesolidcurveplotsthefractionofsellerswithpricegreaterthansomevalue,wherethepriceisshownonthex-axis.Thethinsoldlinehasourtheoreticallypredictedslopeof,whichshowsthatdegreedistributionisquiteconsistentwithourexpectations,atleastinthetails.Thoughanaturalconjecturefromtheplotsisthatthepriceofasellerisessentiallydeterminedbyitsdegree,belowwewillseethatthedegree

isaratherpoorpredictorofanindividualsellerprice,whilemorecomplex(butstilllocal)propertiesareextremelyaccuratepredictors.

Perhapsthemostinterestingfindingisthatthetailofthepricedistributionlookslinear,i.e.italsoexhibitspowerlawbehavior.Ourtheoryprovidedanupperbound,whichispreciselythecumulativedegreedistribution.Wedonotyethaveaformallowerbound.Thisplot(andotherexperimentswehavedone)furtherconfirmtherobustnessofthepowerlawbehaviorinthetail,forand.AsdiscussedintheIntroduction,Pareto’soriginalobservationwasthatthewealth(whichcorrespondstosellerpriceinourmodel)distributioninsocietiesobeyapowerlaw,whichhasbeenbornoutinmanystudiesonwesterneconomies.SincePareto’soriginalobserva-tion,therehavebeentoomanyexplanationsofthisphenomenatorecounthere.However,toourknowledge,alloftheseexplanationsaremoredynamicinnature(egadynamicalsystemofwealthexchange)anddon’tcapturemicroscopicpropertiesofindividualratio-nality.Herewehavepowerlawwealthdistributionarisingfromthecombinationofcertainnaturalstatisticalpropertiesofthenetwork,andclassicaltheoriesofeconomicequilibrium.BoundsviaLocalComputations:RecallthatTheorem1suggestsaschemebywhichwecandoonlylocalcomputationstoapproximatetheglobalequilibriumpriceforanyseller.Moreprecisely,forsomeseller,considerthesubgraphwhichcontainsallnodesthatarewithindistanceof.Inourbipartitesetting,forodd,thissubgraphhasabuyerfrontier,andforeven,thissubgraphhasasellerfrontier,sincewestartfromaseller.Hence,theequilibriumcomputationontheodd(respectively,even)subgraphwillprovideanupper(respectively,lower)bound.

Thisprovidesanheuristicinwhichonecanexaminetheequilibriumpropertiesofsmallregionsofthegraph,withouthavingtodoexpensiveglobalequilibriumcomputations.Theeffectivenessofthisheuristicwillofcoursedependonhowfasttheupperandlowerboundstighten.Ingeneral,itispossibletocreatespecificgraphsinwhichtheseboundsarearbitrarilypooruntilislargeenoughtoencompasstheentiregraph.Asweshallsee,theperformanceofthisheuristicisdramaticallybetterinthebipartite-model.ThesecondpanelinFigure2showshowrapidlythelocalequilibriumcomputationscon-vergetothetrueglobalequilibriumpricesasafunctionof,andalsohowthisconver-genceisinfluencedby.Intheseexperiments,graphsweregeneratedbythebipartite

model.Thevalueofisgivenonthex-axis;theaverageerrors(over

5trialsforeachvalueofand)inthelocalequilibriumcomputationsaregivenonthey-axis;andthereisaseparateplotforeachof4valuesfor.Itappearsthatforeachvalueof,thequalityofapproximationobtainedhaseithermildornodependenceon.Furthermore,theregularspacingofthefourplotsonthelogarithmicscalingofthey-axisestablishesthefactthattheerrorofthelocalapproximationsisdecayingexponentiallywithincreased—indeed,byexaminingonlyneighborhoodsof3stepsfromasellerinaneconomyofhundreds,wearealreadyabletocomputeapproximationstoglobalequilibriumpriceswitherrorsintheseconddecimalplace.Sincethediameterforwasoftenabout,thislocalgraphisconsiderablysmallerthantheglobal.However,forthecrudestapproximation,whichcorrespondsexactlytousingsellerdegreeasaproxyforprice,wecanseethatthisperformsratherpoorly.Computationally,wefoundthatthetimerequiredtodoall250localcomputationsforwasabout60%lessthantheglobalcomputation,andwouldresultinpresumablygreatersavingsatmuchlargervaluesof.ParameterDependencies:Wenowprovideabriefexaminationofhowpricevariationdependsontheparametersofthebipartite-model.WefirstexperimentallyevaluatethelowerboundsprovidedinTheorem3.ThethirdpanelofFigure2showsthemaximumtominimumpriceasfunctionof(averagedover25trials)onaloglogscale.Eachlineisforafixedvalueof,andthevaluesofrangeformto().

RecallfromTheorem3,ourlowerboundontheratiois(using).Weconjecturethatthisistight,and,ifso,theslopesoflines(intheloglogplot)shouldbe,whichwouldbe.Theestimatedslopesaresomewhatclose:

.Theoverallmessageisthatforsmallvaluesof,pricevariation

increasesrapidlywiththeeconomysizeinpreferentialattachment.

TherightmostpanelofFigure2isascatterplotofvs.themaximumtominimumpriceinagraph(where).Here,eachpointrepresentsthemaximumtominimumpriceratioinaspecificnetworkgeneratedbyourmodel.Thecirclesareforeconomiesgeneratedwithandthex’sareforeconomiesgeneratedwith.Hereweseethatingeneral,increasingdramaticallydecreasespricevariation(notethatthepriceratioisplottedonalogscale).Thisjustifiestheintuitionthatasisincreased,more“economicequality”isintroducedintheformoflesspreferentialbiasintheformationofnewedges.Furthermore,thedataforshowsmuchlargervariation,suggestingthatalargervalueofalsohastheeffectofequalizingbuyeropportunitiesandthereforeprices.

6AnExperimentalIllustrationonInternationalTradeData

Weconcludewithabriefexperimentexemplifyingsomeoftheideasdiscussedsofar.ThestatisticsdivisionoftheUnitedNationsmakesavailableexten-sivedatasetsdetailingtheamountsoftradebetweenmajorsovereignnations(seehttp://unstats.un.org/unsd/comtrade).Weusedadatasetindicating,foreachpairofna-tions,thetotalamountoftradeinU.S.dollarsbetweenthatpairintheyear2002.Forourpurposes,wewouldliketoextractadiscretenetworkstructurefromthisnumericaldata.Therearemanyreasonablewaysthiscouldbedone;herewedescribejustone.Foreachofthe70largestnations(intermsoftotaltrade),weincludeconnectionsfromthatnationtoeachofitstoptradingpartners,forsomeinteger.Wearethusincludingthemore“important”edgesforeachnation.Notethateachnationwillhavedegreeatleast,butasweshallsee,somenationswillhavemuchhigherdegree,sincetheyfrequentlyoccurasatoppartnerofothernations.Tofurthercastthisextractednetworkintothebipartitesettingwehavebeenconsidering,weranmanytrialsinwhicheachnationisrandomlyassignedaroleaseitherabuyerorseller(whicharesymmetricroles),andthencomputedtheequilibriumpricesoftheresultingnetworkeconomy.Wehavethusdeliberatelycreatedanexperimentinwhichtheonlyeconomicasymmetriesarethosedeterminedbytheundirectednetworkstructure.

TheleftmostpanelofFigure3showresultsfor1000trialsunderthechoice.Theupperplotshowstheaverageequilibriumpriceforeachnation,wherethenationshavebeensortedbythisaverageprice.Wecanimmediatelyseethatthereisdramaticpricevariationduetothenetworkstructure;whilemanynationssufferequilibriumpriceswellunder$1,themosttopologicallyfavorednationscommandpricesof$4.42(U.S.),$4.01(Germany),$3.67(Italy),$3.16(France),$2.27(Japan),and$2.09(Netherlands).Thelowerplotoftheleftmostpanelshowsascatterplotofanation’sdegree(x-axis)anditsaverageequilibriumprice(y-axis).Weseethatwhilethereisgenerallyamonotonicrelationship,atsmallerdegreevaluestherecanbesignificantpricevariation(ontheorderof$0.50).

ThecenterpanelofFigure3showsidenticalplotsforthechoice.Assuggestedbythetheoryandsimulations,increasingtheoverallconnectivityofeachpartyradicallyreducespricevariation,withthehighestpricebeingjust$1.10andthelowestjustunder$1.Interestingly,theidentitiesofthenationscommandingthehighestprices(inorder,U.S.,France,Switzerland,Germany,Italy,Spain,Netherlands)overlapssignificantlywiththe

case,suggestingacertainrobustnessintherelativeeconomicstatuspredictedby

themodel.Thelowerplotshowsthattherelationshipbetweendegreeandpricedividesthepopulationinto“have”(degreeabove10)and“havenot”(degreebelow10)components.ThepreponderanceofEuropeannationsamongthetoppricessuggestsourfinalexperi-

UN data network, top 3 lnks, fulset of nations5432101.41.21pricepriceUN data network, top 10 lnks, fulset of nations8UN data network, top 3 lnks, EU colapsed nation set6price0.80.60.40.242010203040price rank506070800010203040price rank50607080005101520price rank2530354054average priceaverage price1.151.11.0510.950.9average price863210420510average degree15202505101520average degree253035002468average degree101214Figure3:Seetextfordescriptions.

ment,inwhichwemodifiedthenetworkbymergingthe15currentmembersoftheEuropeanUnion(E.U.)intoasingleeconomicnation.Thismergedvertexhasmuchhigherdegreethananyofitsoriginalconstituentsandcanbeviewedasan(extremely)idealizedexperimentintheeconomicpowerthatmightbewieldedbyatrulyunifiedEurope.TherightmostpanelofFigure3providestheresults,whereweshowtherelativepricesandthedegree-pricescatterplotforthe35largestnations.ThetoppricesarenowcommandedbytheE.U.($7.18),U.S.($4.50),Japan($2.96),Turkey($1.32),andSingapore($1.22).Thescatterplotshowsaclearexampleinwhichthehighestdegree(heldbytheU.S.)doesnotcommandthehighestprice.

Acknowledgements.WearegratefultoTejasIyerandVijayVaziraniforprovidingtheirsoftwareimplementingtheDevanuretal.[2002]algorithm.SiddharthSuriacknowledgesthesupportofNIHgrant2-T32-HG-000046-06.RobinPemantleacknowledgesthesupportofNSFgrantDMS-0103635.

References

KennethJ.ArrowandGerardDebreu.Existenceofanequilibriumforacompetitiveeconomy.Econo-metrica,22(3):265–290,July1954.

A.BarabasiandR.Albert.Emergenceofscalinginrandomnetworks.Science,286:509–512,1999.B.Bollobas.RandomGraphs.CambridgeUniversityPress,2001.

NikhilR.Devanur,ChristosH.Papadimitriou,AminSaberi,andVijayV.Vazirani.Marketequilib-riumviaaprimal-dual-typealgorithm.InFOCS,2002.IrvingFisher.PhDthesis,YaleUniversity,1891.

D.Gale.TheoryofLinearEconomicModels.McGrawHill,N.Y.,1960.

MatthewJackson.Asurveyofmodelsofnetworkformation:Stabilityandefficiency.InGroupFormationinEconomics:Networks,ClubsandCoalitions.CambridgeUniversityPress,2003.S.Kakade,M.Kearns,andL.Ortiz.Graphicaleconomics.COLT,2004.

R.KrantonandD.Minehart.Atheoryofbuyer-sellernetworks.AmericanEconomicReview,2001.M.Mitzenmacher.Abriefhistoryofgenerativemodelsforpowerlawandlognormaldistributions.InternetMathematics,1,2003.

7Appendix

Wenowsketchtheproofsofalltheorems.Webeginwithresultsestablishingpurelysta-tistical(non-economic)propertiesofthebipartite-model,andthenapplythesetoestablisheconomicpropertiesofthemodel.Wenotethatwhilethestatisticalresultsarereminiscentoftherecentliterature(Mitzenmacher[2003]),weneedtoestablishtheirde-pendenceonand,aswellasdealwiththebipartitestructureofthegraph.7.1StatisticsoftheNetwork

Wefirstestablishthatthedegreedistributionofthesellersobeysapowerlaw.(Inthesequel,weonlyexaminepropertiesofthesellers;similarstatementsholdforbuyers.)Let

denotethedegreeoftheseller(inorderofarrival)attime(thatis,after

buyersandsellershavebeenaddedtothenetwork).Thefollowinglemmacharacterizesthebehavioroftherandomvariableasymptotically.Let

Lemma5Inthebipartitelarge.

-model,tendstoforsufficiently

Proof:(Sketch)Establishingthislemmarigorouslyisbeyondthescopeofthispaper,soweonlyprovideanon-rigorousargumentwithrespecttothemeans.Alongversionofthispaperwillhavethecompleteproof.

Thetotalnumberofedgesaftertimeis.Fromtimeto,eachoftheadditionaledgesisattachedtosellerwithprobability.Bylinearityofexpectation,wecansumovertheedgeswithoutworryingaboutthenegativedependencearisingfromsamplingwithoutreplacement,whichimplies

Intheforthcomingversion,wesolvethisformulaexactly,butherewetreatthesystemasthedifferentialequation(asinMitzenmacher[2003])

whereisusedforleadstotheresult.

.Solvingthiswiththeboundarycondition

Wemaynowtranslatethisresultintoapowerlawforthedistributionofsellerdegrees.Theorem6Inthebipartitetimewhosedegreeexceeds

-model,foris.

,theproportionofsellersat

Proof:(Sketch)Fix,andconsidertheproportionofsellerswhosedegreeexceedssome

value.Thatis,considerthethatsolves.Hence,.Dividingbyprovidestheproportionofsellers,whichisthedesiredresult.Inthelongversion,weshowthattheapproximationofonlyconsideringmeansissufficient.

Forthesimplestcaseofand,thetailofthiscumulativedegreedistribu-tionisjust.Moregenerally,asapproaches1(towardsunbiasedselection,andawayfrompreferentialattachment),theexponentblowsup,andthetailsofthedistributionbecomelighter.At,weactuallyhaveexponentialratherthanpowerlawdecay.

7.2EconomicsoftheNetwork

Westartbypresentingaratherintuitive“monotonicity”lemma,whichstatesthatifthesupplyofgoodsinaclassicalFishereconomyisdecreased,orthecashendowmentsareincreased,thentheequilibriumpricesdonotdecrease.Wethenusethislemma,alongwiththeresultsoftheprevioussection,toproveourtheorems.

Lemma7(Monotonicity)LetandbetwoFishereconomieswiththesamenumberofbuyersandsellersandidenticallinearutilityfunctions.Ifforallgoodsandbuyers,wehaveand(wheretheprimesdenotequantitiesforeconomy),thentheequilibriumpricessatisfyforall.Proof:Toprovethis,weusepropertiesofarecentalgorithmforcomputingequilibriainthelinearFishermodel(seeDevanuretal.[2002]),whichwenowdescribe.Definethe“bangperbuck”forbuyerconsuminggoodatpriceas.Clearly,itisonlyoptimalforbuyertopurchasesthosegoodswhichhavemaximalbangperbuck.Thealgorithmisaniterativeschemeinwhichpricesareincreasedateveryiteration,untilanequilibriumisreached.Importantly,thealgorithmcanbeinitializedtoanypriceswhichobeythefollowingproperty,whichisreferredtoasthe“Invariant”inDevanuretal.[2002]3.WesaythattheInvariantholdsatpricesifthebuyershaveenoughmoneytopurchaseallthegoodsinthemarket,whileonlypurchasinggoodswhichmaximizetheirbangperbuck(thoughthebuyersmayhaveleftovermoneyafterthispurchase).Essentially,theInvariantholdsatsomepricesifthebuyerscanclearthemarketwhilepurchasingoptimallyattheseprices.

Letusnowusethisalgorithmtocomputetheequilibriumpricesineconomy.Itsufficestoshowthatwecaninitializethisalgorithmtotheequilibriumpricesof,,sincethealgorithmonlyincreasestheprices.Toshowthatsuchaninitializationissound,weonlyneedtoshowthatthepricessatisfytheInvariantin.Toshowthis,firstnotethatsincethesepricesareanequilibriumin,thenthebuyerscanusetheirmoneyendowmentsoftoclearanamountofgoods,whileonlypurchas-inggoodswhichmaximizetheirbangperbuck.Hence,byassumption,thebuyersincanuselargermoneyendowmentsoftoclearasmalleramountofgoods,whileonlypurchasinggoodswhichmaximizetheirbangperbuck(sincetheutilityfunctionsinandareidentical).TheproofoftheFrontierTheorem1followsinastraightforwardmannerfromtheaboveMonotonicityLemma.

Proof:(ofTheorem1)Letusprovethelowerboundforthesellerfrontiercase.Considersettingthecashofallbuyersnotinto.Bythepreviouslemma,theequilibriumpricesinthismodifiedeconomyisalowerboundontheequilibriumpricesfortheeconomywithgraph.Notethatallsellersinhavenodemandfromanybuyersoutsideof,and,bydefinitionof,allbuyersinpurchasegoodsonlyfromsellersin.Sotheequilibriumpricesintheinducedeconomyonareidenticaltotheirrespectivepricesin.Asymmetricalargumentprovestheupperboundcase.

TheFrontierTheorem1impliesasimplewealthupperbound:thewealthofanysellerisboundedbyitsdegree.(Bythewealthofaseller,wemeanthepriceatwhichthatsellersellstheirgood.Althoughthesameupperboundcanbeseenfromfirstprinciples,itisinstructivetoapplyTheorem1toproveTheorem2.

Devanuretal.[2002]chooseaparticularinitialization,butitisclearthatthealgorithmissoundforanychoiceofinitialpriceswhichobeytheInvariant.

3

Proof:(ofTheorem2)Letbetheimmediateneighborhoodof(whichisanditsbuyers);thentheequilibriumpriceinisjust,sinceallbuyersareforcedtobuyfromseller.Thisprovidesanupperboundsincehasabuyerfrontier.Sincethedegreedistributioninthebipartite-modelobeysthepowerlawstatedinTheorem6,wehavetheclaimedupperboundonthecumulativewealthdistribution.

AgaincombiningtheFrontierTheorem1alongwiththeresultsonthestatisticalpropertiesofthenetwork,wecanproveTheorem3.Thisproofismoreinvolved.

Proof:(Sketch)(ofTheorem3)UsingLemma7,itstraightforwardtoshowthefollowingtwoboundsonthemaximumandminimumprice.Considerthefirstsellers(inorderoftime)andletbethenumberofbuyersthatareonlyconnectedtothesesellers.Hence,thetotalwealthofthesesellersmustbe,sooneofthefirstsellersmusthaveapricethatis,whichisalowerboundonthemaximumprice.Similarly,anupperboundontheminimumpriceisprovidedbythepricethefirstbuyerobtainsforhispurchases,.Equivalently,weusealowerbound,whichistheamountofgoodsthisbuyerpurchases.Thislowerboundisprovidedbythosesellerswhichareonlyconnectedtothefirstbuyer.

Letusnowboundthetotalwealthofthefirstsellers.Thedegreesofthesesellersattimeareall,sowhenabuyerarrivesatatimebetweenand,theprob-abilityofoneofthisbuyer’sconnectionslinkstoexactlythefirstsellersis.Hence,theprobabilitythatallofthisbuyer’sconnectionslinktoexactlythefirstsellersis.Summingoverthebuyersshowsthatthetotalnumberofsuchbuyersis,withhighprobability,.Deletingfromthislistthosebuyerswhoarelaterlinkedbysomesellerremovesaconstantfractionofthese(showninthelongversion).Hence,thefirstsellershaveatleasttotalwealth,whichimpliesthattherichestsellermusthaveatleastthiswealth(treatingisaconstant).

UsingsimilarargumentsasintheproofofLemma5,onecanshowthefirstbuyerhasdegree.Asimilarargumenttoaboveshowsthatthe,whichisthenumberofsellersonlyconnectedtothisbuyer,is.Combiningthepreviousboundsleadstotheresult.

Thisproofcanbegeneralizedtoobtainboundsonratioofthewealthcontainedamongthetoppercentofsellersversusthepoorestpercentofbuyers(whichismoreofarelevantquantityinlargeeconomies).

UsingtheFrontierTheorem1again,weproveTheorem4.

Proof:(ofTheorem4)Letusproceedwithaproofbycontradictionbyassumingthatallpricesarenotequalto.Thisimpliesthattheremustexistsomesellerswithequilibriumpricelessthan(ifallequilibriumpricesweregreaterthanthanthemarketwouldnotclear).Letbethesetofallsellerswithpricelessthan.Allbuyersinwillbuyonlyfromsellersinsincethepricesoutsideofarestrictlygreater(theyareorlarger).Hence,theclearanceconditionimpliesthatallthebuyerswillspendalltheirmoneywithin.Thisisleadstoacontradiction,sincebyassumption,whichimpliesitisnotpossibleforsupplytoequaldemandamongthesellersinandthebuyersin,ifallpriceswerelessthan1in.