Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On efficient recommendations for online exchange markets Abbassi, Zeinab 2008

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
ubc_2008_fall_abbassi_zeinab.pdf [ 1.53MB ]
[if-you-see-this-DO-NOT-CLICK]
Metadata
JSON: 1.0051430.json
JSON-LD: 1.0051430+ld.json
RDF/XML (Pretty): 1.0051430.xml
RDF/JSON: 1.0051430+rdf.json
Turtle: 1.0051430+rdf-turtle.txt
N-Triples: 1.0051430+rdf-ntriples.txt
Original Record: 1.0051430 +original-record.json
Full Text
1.0051430.txt
Citation
1.0051430.ris

Full Text

OnEfficientRecommendationsforOnlineExchangeMarketsbyZeinabAbbassiBSc.,SharifUniversityofTechnology,2006ATHESISSUBMITTEDINPARTIALFULFILLMENTOFTHEREQUIREMENTSFORTHEDEGREEOFMasterofScienceinTHEFACULTYOFGRADUATESTUDIES(ComputerScience)TheUniversityOfBritishColumbia(Vancouver)August2008?ZeinabAbbassiAbstractbythepopularityofmarketplaceapplicationsoversocialnetworks,westudyoptimalrecommendationalgorithmsforonlineexchangemarkets.Examplesofsuchmarketsincludepeerflix.cornandreaditswapit.co.uk.Wemodelthesemarketsasasocialnetworkinwhicheachuserhastwoassociatedlists:Theitemlist,i.e,thesetofitemstheuseriswillingtogiveaway,andthewi.shlist,i.e.,thesetofitemstheuserisinterestedinreceiving.Atransactioninvolvesausergivinganitemtoanotheruser.Usersaremotivatedtoengageintransactionsinexpectationofrealizingtheirwishes.Wishesmayberealizedbyapairofusersswappingitemscorrespondingtoeachother?swishes,butmoregenerallybymeansofusersexchangingitemsthroughacycle,whereeachusergivesanitemtothenextuserinacycle,inaccordancewiththereceivinguser?swishes.Inthisthesis,wefirstconsidertheproblemofhowtoefficientlygeneraterecommendationsforitemexchangecyclesinanonlinemarketsocialnetwork.Weconsiderdeterministicandprobabilisticmodelsandshowthatunderbothmodels,theproblemofdetermininganoptimalsetofrecommendationsthatmaximizestheexpectedvalueofitemsexchangedisNP-hardanddevelopefficientapproximationalgorithmsforbothmodels.Next,westudyexchangemarketsovertimeandtrytooptimizeusers?waitingtimes,11Abstractandfairnesswherebyfairnesswemean:givehigherprioritytouserswhocontributemoretothesysteminadditiontomaximizingexpectedvalue.Weshowthatbyintroducingtheconceptofpoints,averagewaitingtimecanbeimprovedbyalargefactor.Bydesigningacreditsystem,wetrytomaximizefairnessinthesystem.WeshownotonlyisthefairnessoptimizationproblemNP-hard,butalsoinapproximablewithinanymultiplicativefactor.Weproposetwoheuristicalgorithms,oneofwhichisbasedonroundingthesolutiontoalinearprogrammingrelaxationandtheotherisagreedyalgorithm.Forboththeone-shotmarketandtheovertimemarketstudiedinthisthesis,weconductacomprehensivesetofexperiments,andexploretheperformanceandalsoscalabilityoftheproposedalgorithms.Ourexperimentssuggestthattheperformanceofouralgorithmsinpracticecouldbemuchbetterthantheworst-caseperformanceguaranteefactors.111TableofContentsAbstract...iiTableofContentsivListofTablesviiListofFiguresviiiAcknowledgementsxi1Introduction11.1StructureoftheThesis72One-shotExchangeMarkets82.1RelatedWork92.2Model122.3HardnessResults192.4TheAlgorithms262.4.1AlgorithmMaximal272.4.2GreedyAlgorithm292.4.3LocalSearchAlgorithm30ivTableofContents2.4.4Greedy/LocalSearch2.5AnalysisPerformance.2.5.2RunningTime2.6ExperimentalResults2.6.1DataSet2.6.2Experiments.2.7Conclusion3OnlineExchangeMarketsOverTime3.1Introduction3.2RelatedWork3.2.1SchedulingProblems3.2.2FairnessMaximization3.3Model3.4MinimizingAverageWaitingTime3.5ACreditSystem3.6MaximizingFairness3.7ALinearProgrammingFormulation3.8AStrongInapproximabilityResult3.9HeuristicAlgorithms3.9.1GreedyAlgorithm3.9.2AnLP-roundingAlgorithm3.10ExperimentalEvaluation3.10.1Dataset30inP2PSystemsvTableofContents3.10.2Experiments713.11Conclusion744ConclusionsandFutureWork79Bibliography82viListofTables2.1Alice?sItemandWishlist132.2Bob?sItemandWishlist142.3Joe?sItemandWishlist142.4Amy?sItemandWishlist152.5Mary?sItemandWishlist152.6%Increaseincoveragewhenconsideringcyclesoflength3,4and537ListofFigures2.1Bothexchangescannotbepresentinthesystematthesametime162.2Exchangecycleoflengththree:[(Alice,B(Bob,B(Amy,B172.3HardnessProof242.4GraphRepresentationofRunningExample282.5DescriptionoftheMaximalAlgorithm412.6DescriptionoftheGreedyAlgorithm422.7DescriptionoftheLocalSearchAlgorithm432.8ResultsoftheMaximalalgorithmondatasetsofsize10000,25000and50000442.9ResultsoftheGreedyalgorithmondatasetsofsize10000,25000and50000452.10ResultsoftheLocalSearchalgorithmondatasetsofsize10000,25000and50000462.11PercentageofcoveragefordifferentM?sintheMaximalalgorithm462.12AverageRunningTimeofVariousAlgorithms47viiiListofFigures2.13RunningTimeofAlgorithmMaximalondatasetofsize10,0000overvariousalphas472.14RunningTimeofAlgorithmMaximalondatasetofsize25,0000overvariousaiphas482.15RunningTimeofAlgorithmMaximalondatasetofsize50,0000overvariousalphas482.16RunningTimeofAlgorithmGreedyondatasetofsize10,0000overvariousalphas492.17RunningTimeofAlgorithmGreedyondatasetofsize25,0000overvariousalphas492.18RunningTimeofAlgorithmGreedyondatasetofsize50,0000overvariousalphas502.19RunningTimeofAlgorithmLocalSearchondatasetofsize10,0000overvariousalphas502.20RunningTimeofAlgorithmMaximalondatasetofsize25,0000overvariousaiphas512.21RunningTimeofAlgorithmMaximalondatasetofsize50,0000overvariousalphas513.1PerformanceoftheheuristicscomparedtotheoptimalsolutiongivenbyILPondatasetof10users723.2PerformanceoftheheuristicscomparedtotheoptimalsolutiongivenbyILPondatasetof20users733.3Performanceofdifferentalgorithmsondatasetofsize100.743.4Performanceofdifferentalgorithmsondatasetofsize500.75ixListofFigures3.5Performanceofdifferentalgorithmsondatasetofsize1000763.6Runningtimesfordatasetofsize100763.7Runningtimesfordatasetofsize500773.8Runningtimesfordatasetofsize1000773.9Numberoftransactingusersin6consecutivetimewindows78xAcknowledgementswouldliketotakethisopportunitytothankmysupervisor,ProfessorLaksLakshmanan,forhisgreathelpandguidancethroughthisthesis.Iamindebtedtohimforhisinsightfulcommentsonmyresearchandhissupportduringthepastyear.IamalsogratefultoProfessorRaymondNgforreviewingmythesisandforhisvaluablecomments.IowethankstoallmembersoftheDatabaseManagementandMininglab,andalsoHollyKwanformakingmyyearsatUBCmemorable.Last,butnotleast,Iwouldliketoexpressmygratitudetomydearfamily,myparents,LayaandAbbas;mybrotherandhiswife,HosseinandSara;andmyhusbandVahab,whoseendlessloveandsupporthasalwaysbeenablissforme.Thanksforeverything.xiChapter1Introductionhavestudiedsocialnetworksextensivelyinthepastyears.ThesixdegreesofseparationexperimentperformedbyStanleyMilgraminthelate1960sisawell-knownandalsoremarkableinstanceofsuchstudies.Thenetworksstudiedinsocialsciencesaretypicallysmallduetothefactthatcollectinginformationisdifficultandtypicallydonebythecirculationofquestionnairesordoinginterviews,askingrespondentstodetailtheirinteractionswithothers[291.Thesedays,theavailabilityoftheInternethascauseddramaticchanges.Onlinesocialnetworkshaveemergedandbecomepopular,dataisavailableinamuchlargerscalethanbefore,andtheincreasedcomputationalpowerletsusstudythestatisticalpropertiesofthegraphinadditiontotheindividualstudiesdonebefore.ThefieldofsocialnetworksincomputerscienceisrapidlygrowingduetotherelativelyrecentpopularityofonlinesocialnetworkssuchasMySpaceandFaceBook.Usersarespendingincreasingamountsoftimeonsocialnetworkwebsites.Forinstance,arecentsurvey[1]thatrankswebsitesbasedonaveragetimespentbyauser,identifiesMySpaceandFacebookamongthetop10websites,andMySpacestandsatthetopby11.9%.Ontheotherhand,theincreasingamountofchoicesavailableonthe1Chapter1.IntroductionWebhasmadeitincreasinglydifficulttofindwhatoneislookingfor.Threemethodsarecommonlyappliedtohelpwebusersinlocatingtheirdesireditems:searchengines,taxonomiesand,morerecently,recommendersystems[24].Thisiswhererecommendersystemscomeintotheplay.Recommendersystemshavebeenextensivelystudied.However,inmostofthemthepropertiesofsocialnetworksareignored.OneimportantexampleofsocialinteractionamongusersontheInternetisonlineexchangemarketswhicharecurrentlypresentontheweb.Someexamplesareasfollows:?peerflix.com[3]forexchangingmovies:ItletstheusersexchangetheirDVDswitheachotherinsteadofrentingthem.?readitswapit.co.uk[4]allowsbookloverstoexchangetheirafreadyreadbooksandreceivenewbooksinreturn.Almostallofthe?matching?(i.e.,findingbooksandownerstoexchangewith)isdonemanuallybytheuserherself,meaningthatshehastogoandfindherdesiredbookinalibraryandthenmarkit.Theownerofthedesiredbookwillbeinformedbyanemailandwillchecktheseeker?slistofbooksandifwillingtodotheexchange,theywillpostthebooksforeachother.?oddshoe.org:[2]isanationalorganizationwhichisaresourcefornew,qualitysingleshoesandpairsofsignificantlydifferentsizes.Manyhavethisneedduetoinjury,diseaseandgeneticdisorders.Thisorganizationhasbeenaroundsince1943andtheexchangesarenotdoneonline.2Chapter1.Introduction?IntervacInternationalisaworld-widenon-profitorganizationwhichhasfacilitatedhomeexchangesbetweenitsmemberssince1953.Theyoperateamulti-languagereal-timedatabaseofhomeexchangelistingsontheirwebsitewithanoptiontoreceiveprintedcataloguesoflistings.?Joebarter.comisanonlinebartersite,plusanarrayofnetworkingservicesandresourcestopaythetypicalchargesandfeesassociatedwithonlinebarterexchanges.Otherthantheaboveexamplesforexchangemarkets,variousmarketplacesforexchangingitemscanbedesignedasnewapplicationsoveronlinesocialnetworksontheweb.ThiscanbealreadyseentobehappeningoverFacebook.Motivatedbytheabove,westudyoptimal?matching?algorithmsforonlineexchangemarkets.Here,by?matching?,wemeanfindingasetofusersanditemssuchthattheycanexchangeitemsinacycleoflengthtwoormore.1Amainmotivationbehindourworkisthelackofcomprehensiveandefficientrecommendationalgorithmsforitemexchangeinthecurrentsystems.Thesealgorithmscanimprovethequalityofuserexperienceinexchangemarkets,andinturn,theycanmakevariouswaysofmonetizingsuchsystems,suchasonlineadvertising,moreeffective.InChapter2wefocusontheproblemofgeneratingrecommendationsundertwomodels:deterministicmodelandprobabilisticmodel.Inbothmodelseachuserreceivesaniteminreturnfortheitemwhichshegivesaway.Weformulatetheproblemoffindingrecommendationsasthatof?Noconfusionshouldarisewiththestandardgraph-theoreticnotionofmatching.Thecontextwillmakethemeaningclear.3Chapter1.Introductionfindingasetofconflict-freecyclesinthegraph.Conflict-freemeanscyclesinthesetarepairwiseedge-disjoint,aconditionnecessarytoensurethatwhenausercommitstoarecommendedexchange,sheisnotsurprisedthattherecommendeditemisalreadytaken.Thus,arecommendationconsistsofasetofconflict-freecycles.Thevalueofarecommendationisthenumberofitems(potentially)exchangedthroughthecyclesrecommended.Whenthecyclelengthisrestrictedtotwo,wecallthecorrespondingproblemsimpleexchangemarkets.Inasimpleexchangemarket,theonlyacceptablerecommendationisasetof(conflict-free)swaps,calledaswaprecommendation.WeprovethesurprisingresultthatevenfindinganoptimalswaprecommendationisNP-complete.Next,weconsideramoregeneralsituationwhereexchangethroughshortcycles,i.e.,cyclesoflengthuptok,wherekisasmallpredeterminedconstant.Wetypicallyconsiderk=2,...,5.Wecallthisexchangemarketswithshortcycles.Thereasonwhywefocusonshortcyclesisthat,evenifoneuserinthecyclewithdrawsthetransaction,thewholeexchangecyclecollapses.Ifwehavelongcycles,thenmoreuserswouldbeaffected.Now,arecommendationisasetofconflict-freecycleswithlengthboundedbyk.Ofcourse,thehardnessextendstofindingoptimalrecommendationsforthiscase.Finally,weconsidertheprobabilisticexchangemarket.Inthiscase,thereisaprobabilityassociatedwitheachuserengaginginatransactionwithanyotheruser.Aswell,thereisaprobabilityofauserbeingwillingtotradeoneitemforanother.Weassumeallprobabilitiesareindependent.Arecommendationisdefinedinexactlythesamewayasforexchangemar4Chapter1.Introductionketsthroughshortcycles.Thevalueofarecommendationistheexpectednumberofitemsexchanged.Thecontributionofacycletothevalueofarecommendationisthenumberofitemsexchangedinthecyclemultipliedbytheproductofallprobabilitiesassociatedwiththecycle.WeshowthatfindinganoptimalrecommendationremainsNP-complete.Wedevelopheuristicandapproximationalgorithmsforfindingoptimalrecommendationforallthreekindsofmarkets.Wediscussthreeapproximationalgorithms?Greedy,Localsearch,andcombinationofgreedyandlocalsearch?andoneheuristicalgorithm?Maximal.Weprovethattheapproximationalgorithmsfindrecommendationsthatarewithinafactorof2k,2k?1,and(2k+1)/3oftheoptimal,respectively.Wealsoanalyzethecomplexityoftheproposedalgorithms.WhileMaximalhasnoprovableapproximationguarantees,itisbyfarthemostefficient.Weconductadetailedempiricalstudyofallalgorithmsproposedusingsyntheticdatathatwegenerated.Thedatawasgeneratedtoconformtopowerlawdistributionscommonlyfoundinsocialnetworks.OurexperimentsshowthateventhoughMaximalhasnotheoreticalapproximationguarantees,recommendationsfoundbyMaximalareverycompetitivewiththosefoundbytheapproximationalgorithms.Ontheotherhand,Maximalsignificantlyoutperformstheotheralgorithmswhenitcomestoscalabilityw.r.t.networksizeandthesizesofitemandwishlists.Inchapter23weconsiderexchangemarketsovertime.Wesetnewobjectivesinthisnewsettingandtrytoachievethembyintroducingefficientfeaturesandalgorithms.Ourobjectivesare:5Chapter1.Introduction?Maximizingthenumber(orthetotalvalue)ofitemsexchangedinthemarket.?Minimizingtheaveragewaitingtimeofusersinthesystem.?Maximizingfairnessinthesystem.Inordertoachievetheaboveobjectivesweintroducevirtualpointsandalsoacreditsystem.Weprovethatvirtualpointscandecreasetheaveragewaitingtimeinthesystemandalsoassumingthatusersputtheiritemsarandompermutation,thereareinstanceinwhichinexpectationthewaitingtimedecreasesbyafactorof2k+2B.Moreover,inordertoachievethefairnessmaximizationgoal,wedefineacreditsystemandweprovethatnotonlyisthisproblemNP-complete,butalsonotapproximablewithinanymultiplicativefactor.Therefore,weproposetwoheuristicsforthisproblem.Thefirstoneisanlinearprogramming-roundingapproachinwhichweusetheresultsoftheIprelaxationoftheintegerlinearprogrammingmodeloftheproblem.Theotherheuristicisasimplegreedyalgorithm.ForthischapterweperformexperimentsonthedatasetthatwehadgeneratedforChapter2?sexperiments.Asmentionedabovethedatasetisgeneratedaccordingtopowerlawdistributionscommoninsocialnetworks.Theexperimentsshowthat6Chapter1.Introduction1.1StructureoftheThesisInthisthesisourfocusisonexchangemarketswhichareanimportantexampleofonlinesocialnetworks.Chapters2,and3studygenerationofrecommendationsforonlineexchangemarkets,inwhichtheusershavetwosetsofitems.Onesetincludesitemswhichtheuserwishesforthem(a.k.awish-list)andtheotheristhelistofitemstheuserdoesnotwantanymore(a.k.aitem-list).Chapter2,modelsthenetworkasaone-shotmodelandchapter3addressesthemarketsovertime.7Chapter2One-shotExchangeMarketsInthischapterwediscussOne-shotexchangemarketsandfocusontheproblemofgeneratingrecommendationsundertwomodels:deterministicmodelandprobabilisticmodel.Inbothmodelseachuserreceivesaniteminreturnfortheitemwhichshegivesaway.Weformulatetheproblemoffindingrecommendationsasthatoffindingasetofconflict-freecyclesinthegraph.Conflict-freemeanscyclesinthesetarepairwiseedge-disjoint,aconditionnecessarytoensurethatwhenausercommitstoarecommendedexchange,sheisnotsurprisedthattherecommendeditemisalreadytaken.Thus,arecommendationconsistsofasetofconflict-freecycles.Thevalueofarecommendationisthenumberofitems(potentially)exchangedthroughthecyclesrecommended.Thischapterisorganizedasfollows.RelatedworkaredescribedinSection2.1.TheproposedexchangemarketmodelsaredescribedinSection3.3,whichalsoformalizesandillustratestheproblemsstudied.ThecomplexityoftheproblemsisanalyzedinSection2.3.TheheuristicandapproximationalgorithmsaredevelopedinSection2.4whiletheiranalysisisdiscussedinSection2.5.Section2.6discussestheexperiments.8Chapter2.One-shotExchangeMarkets2.1RelatedWorkTherelatedworkcanbeclassifiedinthethreefollowingcategories:CycleCoverProblemThecyclecoverproblemhasbeenstudiedthoroughly.Givenagraphandasubsetofmarkedelements:nodes,edgesorsomecombinationofthem,acyclecoverproblemseekstofindaminimumlengthsetofcycleswhoseunioncontainsallmarkedelements[22].In[22]theauthorsstudycyclecoverproblemforcycleswithboundedsizewhichcoverasubsetoftheedgesofagraph.Morespecifically,theyimprovethetrivialapproximationfactorof2to1+ln(2)inweightedgraphsandO(lnk)foruniformgraphs.TheChinesepostmanproblemwasintroducedbyGuan[17]andEdmondsandJohnson[121proposedapolynomial-timealgorithmtosolvetheprobleminundirectedgraphs.Papadimitriou[30]provedthattheproblemisNP-hardformixedgraphs.Later,RaghavachariandVeerasamy[33]gaveafapproximationforthisinstanceoftheproblem.AnNP-hard[39]variantoftheChinesepostmanproblem,theminimumweightcyclecoverproblem,addstheconstraintthatcoveringcyclesmustbesimple.Theboundedcyclecoverproblem,whichconstrainscyclestobeofboundedsizeaswellassimple,wasintroducedbyHochbaumandOlinick[18].Theypresentedaheuristicfortheproblemalongwithempiricalanalysis.ThelanecoveringproblemwasintroducedbyErgunetal.[13],whogaveaheuristicfortheproblemalongwithanempiricalanalysis.Avariantonthecyclecoveringproblemwhichimposesalowerboundonthe9Chapter2.One-shotExchangeMarketssizeofeachcyclehasbeenstudiedaswell[9].Othercoveringproblemsincludecoveringagraphbycliques[16].ThebookbyZhang[41]reviewstheliterature.RecommenderSystemsExtensiveworkhasbeendoneintheareaofrecommendersystemsindifferentresearchareassuchascognitivescience[36],approximationtheory[31],informationretrieval[37]andalsomanagementscience[28].Thefieldgainedmoreimportanceinthemid1990swiththeemergenceofcollaborativefilteringpapers.[34,35,38].Moreover,recommendersystemsareusuallyclassifiedintothefollowingcategories,basedonhowrecommendationsaremade[7]:?Content-basedrecommendations:Theuserwillberecommendeditemssimilartotheonestheuserpreferredinthepast;?Collaborativerecommendations:Theuserwillberecommendeditemsthatpeoplewithsimilartastesandpreferenceslikedinthepast;?Hybridapproaches:Thesemethodscombinecollaborativeandcontent-basedmethods.Combiningtrust-basedandCFapproachesisadirectionofcurrentresearch[7].Inadditiontorecommendersystemsthatpredicttheabsolutevaluesofratingsthatindividualuserswouldgivetotheyetunseenitems(asdiscussedabove),therehasbeenworkdoneonpreference-basedfiltering,i.e.,predictingtherelativepreferencesofusers[11,14,25,26].Preference-based10Chapter2.One-shotExchangeMarketsfilteringtechniqueswouldfocusonpredictingthecorrectrelativeorderoftheitems,ratherthantheirindividualratings.TheKidneyExchangeProblem.Arelatedprobleminexchangemarketsisthenationalkidneyexchangeproblem[5].Formanypatientswithkidneydisease,thebestoptionistofindalivingdonor,thatis,ahealthypersonwillingtodonateoneofhis/hertwokidneys.Theproblemisthatfrequently,apotentialdonorandhisintendedrecipientareblood-typeortissue-typeincompatible.Inthepast,theincompatibledonorwassenthome,leavingthepatienttowaitforadeceased-donorkidney.However,therearenowafewregionalkidneyexchangesintheUnitedStates,inwhichpatientscanswaptheirwillingbutincompatibledonorswitheachother,inorderforeachtoobtainacompatibledonor[5].Thekidneyexchangeproblemisverysimilartoourproblem,specificallythesimpleexchangemarketandtheexchangemarketthroughshortcycles.Inkidneyexchange,eachpatientneedsoneandonlyonekidneyandeachdonoriswillingtodonateonlyonekidney(!).Becauseofmedicalconstraints,onewantsshortexchangecycles.Itisshownin[5]that(optimal)kidneyexchangeisNP-completewhenexchangecyclesoflengthkareconsidered,wherek>2.Ifexchangesarerestrictedtoswaps,thekidneyexchangeproblemcanbesolvedusingthemaximumweightedperfectmatchingprobleminwhichgivenanedge-weightedbipartitegraph,wearelookingforamaximumweightedperfectmatching.Asaresult,theproblemwillbesolvedpolynomially.GivenanetworkG=(V,E),abipartitegraphcanbeconstructedasfollows:putonevertexforeachagentandonevertexforeachcorrespond11Chapter2.One-shotExchangeMarketsingitem(i.e.kidney).Connecteachagenttoitscorrespondingitemwithanedgeewithweightzero.ForeachedgeeEE,e=(vi,v)intheoriginalgraph,connectagentvtoitemvwithanedgewithweightwe.Perfectmatchingsinthismodelareequivalenttocyclecovers,becausereceivinganitemisequaltogivinganitemaway,andfindingamaximumweightedmatchingsolvestheproblemoffindinganoptimalsetofkidneyswaps.However,inallourexchangemarkets,usersmayhavemultipleitemsintheiritemandwishlistsandmaybewillingtotrademorethanoneitematatime.Thissubtledifferencealonemakesourproblemmuchharder.Asweshowlater,evenfindingoptimalswaprecommendationsforsimplemarketexchangeisNP-complete.2.2ModelInourproposedsystem,weassumethealgorithmforgeneratingrecommendationsforexchangecyclesisrunperiodicallyandthesetofpotentialfeasibleexchangesarediscovered.Usersinvolvedinthesepotentialcyclesareinformedthroughemailand/ortheiraccountwillbeupdated.Iftheyareinterestedinperformingthetransaction,theywillgetintouchwiththeotherusers.Otherwisetheywillwithdrawthetransactionandallotherinvolveduserswillbeinformed.Inanycasewhenthetransactionisdonetheexchangeditemsareremovedfromtheitemlistsandwishlists,andthesystemwillbeupdated.Wealsoassumethatauserdoesnotownmultiplecopiesofanitemandalsodoesnotwishformultiplecopiesofanitem.Obviouslythesystemisdynamicmeaningthatitchangeswithtime.12Chapter2.One-shotExchangeMarketsThepossiblechangesare:(i)auserjoinsorleavesthenetwork;(ii)anitemisaddedtoorremovedfromauser?swishlistoritemlist:thesechangesmaybeduetoatransactiondoneorduetochangeinuser?sinterests.Thesechangesimplythatthesetoffeasibleexchangeswillalsochangebytime.Thus,thesystemrunsthealgorithmtofindthesetofnewexchangesthathavebecomeavailableperiodically(e.g.,onceadayorweek).Inthissection,weformallydefineourproblems.Inthedeterministiccasestheobjectiveistomaximizethenumberofitemsexchangedandintheprobabilisticcasetomaximizetheexpectednumberofitemsexchanged.Thefollowingexampleillustratesmanyofthenotionsandwillserveasarunningexample.Example2.2.1[ExchangeMarket]Consideracollectionoffiveusers?Alice,Bob,Joe,Amy,andMary.Eachofthemhasanitemlistandawishlist.Thelistsareshownintables2.1,2.1,2.2,2.3,2.4,and2.5.Itemlistsofauserconsistsitemstheuseriswillingtogiveawayinexchangeforsomeitemintheirwishlistthattheywouldliketoreceive.IThetablesindicatingtheusers?wishlistsanditemlists.Alice?sItemlistAlice?sWishlistB1:HarryPotterIB2:HarryPotterIICookBookB3:ThesecretB9:PCsfordummiesBTable2.1:Alice?sItemandWishlist13Chapter2.One-shotExchangeMarketsBob?sItemlistBob?sWishlistB4CLRSB5Intro,toDBMSB7CookBookTable2.2:Bob?sItemandWishlistJoe?sItemlistJoe?sWishlistB2HarryPotterIIB6HarryPotterIIIB3ThesecretTable2.3:Joe?sItemandWishlistInallourproblemsbelow,weassumeasetofusersUandasetofitemsI.UseruEUownsasetofitems(akaitemlist)S,andrequiresasetofitems(akawishlist)W,,.SimpleExchangeMarket:Inasimpleexchangemarket,weonlymatchupusersonebyone,i.e.,ineachexchange,twousersuandvcanexchangeapairofitemsiandj.GivenasetofusersUwiththeitemlistsSandwishlistsWforeachuseruEU,thesimplemarketproblem,denotedbySimpleMarket,istofindasetofpairs[(u,i),(v,j)]whereiESflW,,,jeSflW,.Wecalleachpairaswap.TheproblemcanbemodeledasadirectedgraphC=(V,E)withusersasnodesVandadirectededge(u,v)EElabelediwheneverieS,flW,,i.e.,uownsitemiandvisinterestedinreceivingit.Thus,swapscorrespondtocyclesoflengthtwo.SinceeachusertypicallyhasoneinstanceofaniteminS,andalsoneedsoneinstancefromeachiteminW,[(u,i),(*,*)1shouldappearinthesetatmostonce,wherethefirst*isanyotheruservuandthesecond*isanyitem.Intermsofgraphs,theconfigurationshowninFigure2.1isforbidden,i.e.,thesetofrecommendedswapsshouldnotcontainthisasasubgraph.Wecallarecommendation,i.e.,setofswaps,without14Chapter2.One-shotExchangeMarketsAmy?sItemlistAmy?sWishlistB3:TheSecretB2:HarryPotterII[B8:TAOCPIB4:CLRSTable2.4:Amy?sItemandWishlistMary?sItemlistMary?sWishlistB9:PCsforDummiesB2:TAOCPIB10:TAOCPIITable2.5:Mary?sItemandWishlistsuchaforbiddenconfigurationconflict-free.Toseewhyconflict-freedomisnecessary,considerrecommendingbothpairs[(u,i),(v,j)]and[(u,i),(w,j)jtotheusers.Ifuseruexchangesiforjwithuserv,thentherecommendedexchangeisnolongerfeasibleforuserw.Thus,setofrecommendedexchangescontainsaconflict.Theconditionaboveensuresitisconflict-free.Conflict-freerecommendationsensurethatusersdonotgetturnedofforlosetheirtrustintheirsystembyfindingoutthatarecommendationtheyreceivedfromthesystemisnolongerfeasible.Inourrunningexample(Example2.2.1),JoecangiveawayB2tobothAmyandAlice,butbothedgescannotbeinthegraphatthesametime.ExchangeMarketsthroughShortCycles.Inanonlineexchangemarket,wecanfindcyclesofsizelargerthan2,forexample,ascanbeseeninFigure2.2,wemayfindusersAlice,BobandAmywithitemsB7,B4,andB8.IfAlice,BobandAmyhaveitemsB8,B7,andB4respectivelyintheirwishlists,wecansetupa3-wayexchangeamongthemandhaveallofthemsatisfytheirwishlists.Notethat,inthisexample,ifwerestrictourselvestoswaps,noneoftheusersmaybesatisfied.Anexchangecycleisasequence15Chapter2.One-shotExchangeMarketsFigure2.1:Bothexchangescannotbepresentinthesystematthesametime.(U2,i.(uk,ik)1,withi,jEflwhereje1=j+1,1<j<k,andke1=1.Asetofexchangecyclesissaidtobeconflict-freeprovidedthepattern[(u,i),(*,*)Jappearsatmostonceintheset,i.e.,thecorrespondinggraphdoesnotcontaintheforbiddensubgraphinFigure2.1.Ourgoalistofindanoptimalsetofconflict-freecycles:Theobjectiveistomaximizethenumberofitemsinvolvedinexchanges,thusmaximizingthenumberoftransactions.Furthermore,inpractice,wemaywishtolimitthelengthoftheexchangecyclestoamaximumofk,wherekissomepredeterminedconstant.Weusuallyconsiderk=2,...,5.Thereasonwhywefocusonshortcyclesisthat,evenifoneuserinthecyclewithdrawsthetransaction,thewholeexchangecyclecollapses.Ifwehavelongcycles,thenmoreuserswouldbeaffected.16Chapter2.One-shotExchangeMarketsFigure2.2:Exchangecycleoflengththree:[(Alice,B7),(Bob,B4),(Amy,B8)]Inourrunningexample,wecanseethatAlicehasB7inheritemlistandBobhasitinhiswishlist.BobhasB4inhisitemlistandAmyhaswishedforthatbook.AtthesametimeB8inAmy?sitemlistwhileAliceisinterestedinB8.Asweseethecycle[(Alice,B7),(Bob,B4),(Amy,B8)]isafeasiblecycle.Probabilisticexchangemarkets.Formalizingtheaboveprobleminaprobabilisticsetting,wecanassumethatusingareputationsystem,wecanestimatetheprobabilityofrealizingeachexchangeintheexchangemarketgraph.ReputationsystemshavebecomeoneoftheessentialcomponentsofB817Chapter2.One-shotExchangeMarketsweb-basedmulti-agentsystems.Thesesystemsgateagentsreviewsofoneanother,aswellasaboutexternalevents,intovaluableinformation[32].Asaresult,wehaveagraphwithsomeprobabilityoneachedge.Assumingthattheprobabilityofrealizingeachedgeisindependentofotheredges,ourgoalistofindasetofcycleswiththemaximumexpectednumberofedgescovered,sinceeachedgecorrespondstoanitembeingexchanged.Notethattheprobabilityofacycleistheproductoftheprobabilityofitsedges.Itwouldbeinterestingtounderstandthecomplexityofthisproblem.TheprobabilityP(v)denotestheprobabilitythatuiswillingtodoanexchangewithuserv,andpU(j,j)istheprobabilitythatuseruwillexchangeitemiwithitemj,i.e.,shegivesiandtakesj.Inthiscase,theprobabilityofacyclebeingrealizedwillbePxpul(jl,jk)XPXFU2(j2...xPuk(ul)xpuk(jk,jk_1).Ourgoalistofindcyclesthatmaximizethetotalexpectednumberofitemsexchanged.2.2.2[ProbabilisticExchangeMarket]ConsiderFigure2.2asanexample.Lettheprobabilitiesassociatedwiththeedges(Alice,Bob),(Bob,Amy)and(Amy,Alice)be0.7,0.55and0.9.Forsimplicity,supposetheprobabilityofthiscyclebeingrealizedwillbe0.7x0.55x0.9=0.3465.LetRbearecommendationincludingthisexchangecycleamongothers.Thentheprobabilityofthiscyclebeingrealizedwillbe0.7x0.55x0.9=0.3465.LetRbearecommendationincludingthisexchangecycleamongothers.ThenthecontributionofthiscycletothevalueofR,Chapter2.One-shotExchangeMarketsi.e.,totheexpectednumberofexchangeditemsis3x0.3465=1.0395.IInalmostallofthecases,theprobabilityofeachedgebeingrealizedislessthanone,sowhenthecyclegetslarger,theprobabilitywouldbeverylow.Therefore(similartowhatwearguedbeforeforthedeterministiccase)intheprobabilisticcaseshortcyclesarepracticallymoreappealing.2.3HardnessResultsInthissection,weshowthattheSimpleMarketproblemisNP-complete.WealsoshowthattheProbMarketproblemisNP-complete,regardlessofwhetherweconsiderswapsorshortcycleswithlengthboundedbyaconstantk>2.Eventhe?kidneyexchangeversion?ofProbMarketwhereeveryuserownsonlyoneitemandwishesforonlyoneitemremainsNP-completewhencyclesoflength>2areallowed.Wefirstdefinethedecisionversionsoftheseproblemsformally.SimpleMarketDecisionProblemInstance:AsetofusersUwiththeitemlistsS,andwishlistsWforeachuseruEU.Question:Doesaconflict-freeswapcoverCwithnumberofitemsexchangedK?Thesimplemarketdecisionversion,Probusrassociateswitheveryuseraprobabilitythatshewilltransactwithanyuser.Probjtmassociateswitheachuserandapairofitemsi,j,aprobabilitythattheuserwillgiveiandtakejinexchange.19Chapter2.One-shotExchangeMarketsProbMarketProblemInstance:AsetofusersUwiththeitemlistsSandwishlistsWforeachuserueUandtwoprobabilityassignmentfunctionsProbusr:UxU?*[0,ljandProbjtm:UxIxI?[O,1].DoesacyclecoverCwhoseexpectednumberofitemsis>K?WenextdefineTriEdgePart,awell-knownNP-completeproblem.Wewillreducethisproblemtoourproblem.TriEdgePartProblemInstance:AtripartitegraphGwiththreevertexpartitions(X,Y,Z)andanedgesetEcXxYUXxZUYxZDoesanedgepartitioningofGintodisjointsetsofcyclesofsizethree?Finally,wedefine4CycEdgePart,aprobleminvolving4-partitegraphs.Wewillfinditconvenienttousethisproblemasanintermediaryinourreductions.20Chapter2.One-shotExchangeMarkets4CycEdgePartProblemInstance:A4-partitegraphGwithfourvertexpartitions(X,Y,I,J)andacollectionofedgesEconsistingofasubsetofedgesfromXxYUXxIUYxJ,togetherwithamultisetofedgesfromIxJ.Question:DoesanedgepartitioningofGintodisjointsetsofcyclesofsizefour?Wefirstshowthatthe4CycEdgePartproblemisNP-completeandthengiveareductionfrom4CycEdgeParttoSimpleMarketshowingNP-completenessofSimpleMarket.Theorem1The4CycEdgePartproblemisNP-complete.Proof:ThemembershipinNPisstraightforward:givenanedgepartitioningPofC,wecancheckinpolynomialtimewhetherPconsistsof4-cyclesthatarepairwiseedge-disjoint,coveringalledgesofC.Toprovethehardness,wegiveareductionfromTriEdgePart.Thetriangleedge-partitioningoftripartitegraphsisknowntobeNP-complete(andinfactAPX-hard)byaresultofAbrahamet.al[6],followinganNP-completenessbyHolyer[20].GivenaninstanceG(XUYUZ,E)ofTriEdgePart,weconstructaninstanceG?(X?UY?UI?UJ?,E?)of4CycEdgePartasfollows:foranyvertexwEZ,weaddtwocorrespondingverticesweI?andw2eJ?;foreachuX,weaddavertexu?EX?;andforanyvEY,weaddavertexv?eY?.21Chapter2.One-shotExchangeMarketsInotherwords,welet=ixi,I1?I=11,1=I.?!=i.e.,wechooseX?,Y?tobeanysetswithsizelxi,iYlandI?andJ?tobeanysetswithsizeIZI,withX?,Y?,I?,J?beingpairwisedisjoint.Then,weconstructedgesE?(G?)ofthenewinstanceasfollows:foranyedge(u,v)eE(G)whereueXandveY,weaddanedge(u?,v?)toE?(G?);foranyedge(u,w)EE(G)whereuEXandwEZ,weaddanedge(u?,w1toE?(G?);andforanyedge(v,w)E(G)whereveYandweZ,weaddanedge(v?,w2)toE?(G?).Finally,weaddde(w)edgesbetweeneverypairw1EI?andw2EJ?(correspondingtoavertexw?Z).Notethatdeg(w)iseveninourcase,otherwiseitisclearthatthereisnotrianglepartitioning.Thereasonthatweputdes(w)edgesisthattheremaybemorethanonetrianglepassingthroughwEZ,andeachtrianglecorrespondstotwoedgesforpassingthroughanynode,thereforetomaintainthesamenumberofcyclesinthe4-partitegraph,weneedtoconnectwandw2withdew)edges.Clearly,G(X?UY?UI?UJ?,E?)isaninstanceofthe4CycEdgePartproblem.ItshouldalsobenotedthatwhileinstancesoftheTriEdgePartarealwayssimplegraphs,instancesofthe4CycEdgePartcanbemulti-graphssinceweneedmultipleedgesbetweenw1andw2forvariouswEZ.However,theyarenotarbitrarymulti-graphs:e.g.,betweenxEXandyeYatmostoneedgeisrequired(seetheformaldefinitionofthe4CycEdgePartdecisionproblemabove).22Chapter2.One-shotExchangeMarketsNow,weformallyshowthatthereexistsanedge-partitioningofedgesofGintoedge-disjointtrianglesifandonlyifthereexistsanedge-partitioningofG?intoedge-disjoint4-cycles.Consideranedge-partitioningTofedgesofCtoedge-disjointtrianglesT={((xiylzl),...,(x,yz))}forp=E(G)IForeachtriangleXjjZjinthisedge-partitioningTwherexE,y2EY,andz.eZ,weassociateacorresponding4-cyclex?y?z1inC?wherex?eX?,y?EY?,andziEI?,andz2EJ?.Sincetheedgesofptriangle(xjyjzj)for1ipcoveralledgesofG,eachvertexzeZappearsexactlyintriangles.LetT?bethesetofcorresponding4-cyclestotrianglesinT.Thus,thereareexactly4-cyclesinT?correspondingtotrianglesinT,andasaresult,T?isalsoanedge-partitioningofG?intoedge-disjoint4-cycles.Now,consideranedge-partitioningT?ofG?intoedge-disjointtriangles.Similartotheaboveconstruction,wecanconstructasetToftrianglespartitioningtheedgesofGtopedge-disjointtriangles.Theabovetwofactsshowthatthereexistsanedge-partitioningofedgesofCtoedge-disjointtrianglesifandonlyifthereexistsanedge-partitioningofC?toedge-disjoint4-cycles.Thiscompletestheproofofhardness.IWenextshow:Theorem2TheSimpleMarketproblemisNP-complete.Proof:Onceagain,membershipinNPisstraightforward:givenasetswaps,itiseasytocheckwhetheritisconflict-freeandthenumberofitemscoveredisK.Toprovethehardness,wegiveareductionfrom4CycEdgeParttotheSimpleMarketproblem.23Chapter2.One-shotExchangeMarketsFigure2.3:HardnessProof24Chapter2.One-shotExchangeMarketsGivenaninstanceG(XUYUIUJ,E)ofthe4CycEdgePartproblem,weconstructaninstanceEofthesimplemarketingproblemasfollows:weletthesetofusersbeXUJ,andthesetofitemsbeIUY.ForeachuserXEX,wesettheitemlistofxtoS={iEli(x,i)EE(G)}andthewishlistofxtoW={yEJ(x,y)EE(G)}.Similarly,foreachuserjEJ,wesettheitemlistofjtoS,={yEY(y,j)EE(G)}andthewishlistofjtoWj={iEI(i,j)EE(G)}.Now,weshowthatthereexistsanedge-partitioningofGintop=edge-disjoint4-cyclesifandonlyifthereexistsaconflict-freesetofpswapsbetweenpairsofusersintheinstanceofthesimplemarketexchangeproblem.Consideranedge-partitioningTofGintopedge-disjoint4-cyclesT={(x,y,j,i)i1vp}.Inany4-cycle(Xv,yv,iv,jv)clearlyxEX,YvEY,ivEI,andJvEJ.ConsiderthecorrespondingpossibleswapwherexgivesitemivtouservandreceivesitemYvinreturnfromv.Bytheconstructionofitemandwishlists,thisswapisfeasible.LetSbethesetofswapsderivedfromT.ClearlySi=p.WeshowSisconflict-free.Supposenot.Thenthereisapairofswapsin$oftheform:useraswapsitemaforitem/3withuserbandaalsotradesaforitemywithuserc(whichmayormaynotbeb).ThisimpliesTcontainstwo4-cycleswhichsharetheedge(a,a),acontradictiontotheedge-disjointnessofT.Now,supposeSisanyconflict-freesetofpswapsfortheinstanceD.Weconstructanedge-disjoint4-cyclecoverTasfollows.Foreveryswapwhereuseratradesafor/3withuserb,choosethecorresponding4-cycle(a,a,b,/3,a).ItiseasytoshowTcoversalledgesofGanditispairwiseedge-disjoint.Thiscompletesthereductionandtheproof.?25Chapter2.One-shotExchangeMarketsWenextturnourattentiontotheProbMarketproblem.Thefollowingrestrictedversionsareparticularlyinteresting.First,whatcanwesayaboutProbMarketwhenwerestrictattentiontoswaps,i.e.,whenweareinterestedinfindinganoptimalconflict-freesetofswaps?Thehardnessforthecorrespondingdeterministiccaseimpliestheprobabilisticversionishardaswell.Inparticular,thedeterministicversionisaspecialcasewhenallprobabilitiesaresetto1.Second,supposeeveryuserownsjustoneitemandwishesforjustoneitem.Thisissimilartothekidneyexchangeproblemandwecallitthe?kidneyexchangeversion?ofProbMarket.Ifexchangecycleswithlengthmorethantwoareallowed,bytheresultof[5],itfollowsthatthisproblemisNP-complete.Whenonlyswapsareallowed,thesametechniqueoffindingmaximumweightedperfectmatchingcanbeusedtosolvethisproblemexactlyinpolynomialtime.Wethushave:Corollary1FindinganoptimalsetofswapsforProbMarketisingeneralNP-complete.However,forthekidneyexchangeversion,theproblemcanbesolvedinpolynomialtime.Findinganoptimalconflict-freesetofexchangecycleswherecyclelengthisboundedbyk>2forthekidneyexchangeversionofProbMarketisNP-complete.2.4TheAlgorithmsInthissection,wedevelopfouralgorithmsforvariantsoftheexchangemarketproblem.Threeofthemhaveprovableapproximationboundsw.r.t.optimalalgorithm.Theremainingoneisaheuristicalgorithmwithnosuchguarantees.However,aswewillseeshortly,itismuchmoreefficientthanthe26Chapter2.One-shotExchangeMarketsapproximationalgorithms.Whiletheoreticallytheheuristicalgorithmmaynotsoundinterestingcomparedtotheapproximationones,westudytheirrelativeperformanceonsyntheticallygenerateddatasetsinSection2.6.Someofthesealgorithmsareinspiredbyalgorithmsforthesetpackingproblem.Insection2.5,wedefinetheweightedk-setpackingproblemandshowthattheexchangemarketproblemcanbeseenasaspecialcaseofthesetpackingproblem.Weexploitthisconnectiontoderivetheapproximationbounds.Intherestofthepaper,wewillfinditconvenienttodealwithagraphrepresentationofmarketexchangeproblems.Givena(simpleorshort-cycles)marketexchangeprobleminstanceE=(U,I,{SIueU},{WIueU}),withusersU,itemsI,itemlistsSandwishlistsW,thecorrespondinggraphrepresentationGEisdefinedasfollows.GEisadirectededge-labeledgraphandhasanodeforeveryuserinU.Thereisadirectededge(u,v)labelediwheneveriEIisanitemsuchthatiESflWi,.ForourrunningexampleofExample2.2.1,thecorrespondinggraphisshowninFigure2.4.2.4.1AlgorithmMaximalOneheuristicalgorithmistolookforamaximalsetofcyclesinGE.SisamaximalsetofcyclesifSisconflict-freeandthereexistsnocycleCinGEwhichdoesnotappearinSanddoesnotconflictwithanycycleinS.Example2.4.1[Maximalvs.Optimal]Let?sconsiderthefollowingcyclesintherunningexample:27Chapter2.One-shotExchangeMarketsFigure2.4:GraphRepresentationofRunningExample.28Chapter2.One-shotExchangeMarketsC1=[(Alice,B(Bob,B(Amy,BC2=[(Alice,B(Bob,B(Amy,B(Mary,BandC3=[(Amy,B(Joe,BTwosetsSandS2aremaximal:S1={cand52={c2,CS}.Note:coverage(Si)={Bandcoverage(S2={B7B4BB9B2BBotharemaximalsincenocyclescanbeaddedtoeitherwithoutbreakingtheconflict-freedomproperty.Furthermore,noticethatcoverage(S1coverage(S)andcoverage(S2coverage(S1However,SiisclearlynotoptimalsinceS2coversstrictlymoreitems.IInordertofindthemaximalsetofcycles,wefirstinitializethesetofcyclesBto0.ThenforarandomnodevEV(G)weperformabreadthfirstsearch(BFS)oradepthfirstsearch(DFS)fromvtofindacycle.WhileperformingtheBFS/DFSthefirsttimethatweencounterabackwardedgewecanstopbecauseacyclehasbeenfound.BFSwillfindtheshortestcycle.Andterminateifnocyclesarefound.AddCtoB,andremovealledgesthatareinconflictwithCfromthegraph.SetCto0againandstarttheBFSfromanothernode.WerepeatthisprocedureMtimesandselecttheresultwithmaximumweight.InSection2.6,weexploretheperformanceofthisalgorithmfordifferentchoicesofM.ThecompletedescriptionofAlgorithmMaximalisdepictedinFigure2.4.1.2.4.2GreedyAlgorithmAnotherapproachistoperformagreedyalgorithm.InitializeBto0.AteachstepfindthebestexchangecycleCwiththemaximumweight.InChapter2.One-shotExchangeMarketsordertofindthebestcycle,weshouldtryallshortcyclesandthenpickthecyclewithmaximumweight.ThenaddCtothesetofcycles13.RemovealltheedgesthatareinconflictwithC.AddCto13andifnocyclesarefoundterminate.ThecompletedescriptionofAlgorithmGreedyisdepictedinFigure2.4.2.2.4.3LocalSearchAlgorithmInthisalgorithmweattempttoreplaceasmallsubsetofthecurrentsolutionbysomesetofcyclesthatresultinagreatertotalweight.Letthecurrentsolutionbe13.ForanyexchangecycleCthatisnotafreadyselected,trytoaddCandremovealltheconflictingedges.IfthetotalweightofBincreasesbyafactor/3,addCtoBandupdate13byremovingallconflictingcyclesfrom13.Dothisprocedureuntilnolocalimprovementispossible,outputBandterminate.ThecompletedescriptionofAlgorithmLocalSearchisdepictedinFigure2.4.3.2.4.4Greedy/LocalSearchInsteadofstartingtheLocalSearchalgorithmwithanemptyset,wecanseeditwithagoodsetofcycles.AvariantistorunthegreedyalgorithmtofindasetofcyclesBandthenrunthelocalsearchalgorithmstartingfromcyclesin1.3.AnalysisofthisvariantispresentedinSection2.5.30Chapter2.One-shotExchangeMarkets2.5Analysis2.5.1PerformanceInordertoproveapproximationfactorsforthealgorithmsproposedinthispaperwelinkourproblemstotheweightedk-setpackingproblem.Weshowthatthesimplemarketexchangeproblemcanbeformalizedasaspecialcaseoftheweightedk-setpackingproblem.Notethatthepurposeofthisformulationissolelyforthepurposeofderivingapproximationbounds.Intheweightedk-setpackingproblem,givenacollectionofsets,eachofwhichhasanassociatedweightandcontainsatmostkelementsdrawnfromafinitebaseset,ourgoalistofindacollectionofdisjointsetsofmaximumtotalweight.Therestrictiontosetsofsizeatmostkproperlyincludesmulti-dimensionalmatching,whichisageneralizationoftheordinarygraphmatchingproblem.Weightedk-setpackingisprovedtobeNP-hardforanyk3,evenintheunweightedcase[15],andheuristicsandapproximationalgorithmshavebeendevelopedforthisproblem.Toformulatetheone-shotexchangemarketproblemasaspecialcaseofthesetpackingproblem,wedefinetheelementsofthesetstoconsistoftheuser,theitem,andtheactofgivingorwishing.Theformulationisasfollows:First,enumerateallexchangecyclesoflengthk.Thiscanbedoneinpolynomialtimesincekisaconstant.Constructasetcorrespondingtoeveryexchangecycle.Toillustrate,consideranexchangecyclewhereuserugivesitemitouservandwishesitemjinreturn.Theelementsofthesetare:31Chapter2.One-shotExchangeMai*ets(ugivesi)denotedby(vgivesj)bedenotedbyx.(uwishesj)bedenotedby(vwishesi)bedenotedbyy,,.Thus,thesetcorrespondingtotheaboveexchangeis{xu,j,xv,j,yu,j,yv,j}Intheabovenotation,xisasymbolfor?givinganitem?andyfor?wishinganitem?.Thefirstterminthesubscriptshowstheuserinvolvedingives/wishesrelationandthesecondtermistheitembeingexchanged.Settheweightofeachsetconstructedtobethecardinalityoftheset.Foraprobabilisticvariant,settheweighttobethecardinalitytimestheproductofprobabilitiesassociatedwiththeexchartgecycle.Letw(C)denotetheweightofacycle(equivalently,set)C.Ineachoftheexchangeproblems,ourobjectiveistofindaconflict-freesetofexchangecyclesBsuchthatcEBw(C)ismaximized.Thisexactlycorrespondstoweightedk-setpacking.WeprovedinSection2.3thatthesimplestcaseofourproblemwhichisthesimplemarketingproblemisNP-complete.WealsoshowedthattheprobabilisticexchangemarketproblemisNP-complete.Here,usingtheabovereductiontothek-setpackingproblem,weobtainapproximationboundsonAlgorithmsGreedy,LocalSearchandGreedy/LocalSearch.Theapproximationboundsprovedintheliteratureforthesealgorithmsfor32Chapter2.One-shotExchangeMarketsweightedk-setpackingcarryovertoourexchangeproblemssincethelattercanbeseenasaspecialcaseofweightedk-setpacking.?AlgorithmMaximal:Itisnotobvioushowclosethesolutionofthisalgorithmwillbetotheoptimalsolution.ThereasonisthattheBFSalgorithmisperformedfromanarbitrarynodeandpicksthefirstcyclethatisfound.?AlgorithmGreedy:In[10],theauthorsshowthatperformanceofagreedyapproachtotheweightedk-setpackingproblemgivesusa2k-approximation.Thatis,intheworstcasetotalweightoftheoutputwouldbeofthetotalweightofthesetofmaximumweights.Thefactor2kisbecausefromthesetsthatareremovedineachiteration,theoptimalsolutioncancontainatmost2ksets,atmostoneforeachelementoftheselectedsetallofwhichareofweightatmostthatofourselectedset.Theyalsostatethatthisfactorcannotbeimproved.?AlgorithmLocalSearch:Usingaresultin[8]wecanshowthatthisalgorithmisa2k?1-approximation,meaningthatintheworstcasethetotalweightofthegivensolutionwouldbe1/(2k?1)ofthetotalweightoftheoptimalsolution.?LocalSearch/GreedyAlgorithm:In[10]thelocalsearch/greedyalgorithmisprovedtohaveaperformanceratioof2(2k+1)/3andthatthisratioisasymptoticallytight.33Chapter2.One-shotExchangeMarkets2.5.2RunningTimeInthefollowing,thenumberofcyclesthatarefoundisdepictedby131.Theworstcaserunningtimeoftheproposedalgorithmsareasfollows:?MaximalAlgorithm:Therunningtimeofthisalgorithmis0((IVI+El)113l).EachBFSwilltakeO(IVI+IEI)time.Intheworstcasethenumberofcyclesthatarefoundis13!.?GreedyAlgorithm:Findingthebestcycleineachsteptakes0(1V2k)time,thusthetotalrunningtimewillbe0(IVl2?LocalSearch:Inthelocalsearchalgorithm,therunningtimeofcheckingallcyclesis0(lVl2Inordertocheckifeachcycleisinconflictwiththecyclesinthecurrentsolutionatmost0(IEI)timeisneeded.Ateachstep,weperformthelocaloperationifitincreasestheweightofthesolutionbymorethana1+efactor,whereeisasmallconstant.Therefore,thenumberoflocaloperationswillbelog1OPTwhereOPTistheweightoftheoptimumsolution.Thustheworstcaserunningtimeforthelocalsearchalgorithmwillbe:Q(VlogOPT).?Greedy/LocalSearch:Therunningtimeofthisalgorithmsimplyistheadditionofthegreedyandlocalsearchalgorithm,becausetheresultsofthegreedyalgorithmwillbeinputtothelocalsearchalgorithm.2.6ExperimentalResultsWeimplementedtheMaximal,Greedy,andLocalSearchalgorithmsusingMATLAB.TheexperimentswererunonaComputerwitha2.160HzIntel34Chapter2.One-shotExchangeMarketsCore2DuoCPUand1GBofRAMunderWindowsXP.Thegoalsofourexperimentsareasfollows:?Obviously,allowingexchangecyclesoflengthmorethantwowillmakeforincreasedcoverageofusers/items.Wewishtostudytheimpactofallowingcyclesoflengthmorethantwoontheextenttowhichcoverageincreases.?Toexaminethequalityoftheresultsfoundbyalgorithms,especiallytheMaximalalgorithmwhichdoesnothaveaguaranteedapproximationfactor.?TostudythescalabilityofAlgorithmMaximalandalsotheimpactoftheparameterM(numberofrepeatedtrials)onthequalityoftheoutput.2.6.1DataSetWecouldnotgetaccesstothedataofrealonlineexchangeapplications.Hence,wegeneratedasetofsyntheticdata.Theintuitionbehindthedatagenerationisthatthepopularityofitemsinwishlistsanditemlistsfollowsomepowerlawdistributions,i.e.,therearemanyitemswhicharewishedfororprovidedbyasmallnumberofpeople,andthereisasmallnumberofitemswhichareprovidedorwishedforbymanypeople.Toachievethisgoal,first,wegeneratesomepowerlawdistributionswithagivenpowerastheparameter.Weactuallyexaminedfourdifferentpowersof0.5,1,1.5and2.Weuseoneofthesepowerlawdistributionsforthepopularityoftheitems,i.e.,thenumberofpeoplewhoownoneitem.Wealsogeneratea35Chapter2.One-shotExchangeMarketssetofitemlistsizesbasedonsomeotherpowerlawvectors(thisisjustifiedbythefactthatthesizeofwishlistsanditemlistsshouldalsofollowsomepowerlawdistribution).Wealsogenerateavectorofwishlistsizeindirectcorrelationwiththevectorofitemlistsizes.Theintuitionhereisthatifauserprovidesmoreitems,thenprobablyshehaslargerwishlistsaswell.Thisintuitionisnottrueinallcases,soweaddsomenoisetothisprocesswithasmallprobability.Now,givenapopularityvector,andthetwovectorsofthewishlistanditemlistsizes,wegeneratetherealwishlistsanditemlistsasfollows.Foreachitemtobeaddedtoanitemlistorwishlist,wegenerateanitemindependentlyfromthepopularityvector.Thisprocessensuresthattheexpectednumberofappearancesofitemsinitemlistsandwishlistsfollowsomepowerlawdistribution.2.6.2ExperimentsInordertoachieveourexperimentalgoalsabove,weperformedthefollowingexperiment.Firstwejustconsideredcyclesoflengthtwo(1=2)andobservedthenumberofitemsinvolvedincycles.Inthenextstepsweallowcyclesoflengththree(1=3),four(1=4)andthenfive(1=5)andmeasuredtheincreaseinthenumberofitemscoveredcomparedtothepreviouscases.Wedidn?tgobeyond1=5sinceasmentionedinSection3.3longcyclesarenotofinterestinthemarketexchangeproblemsstudiedinthispaper.Weranouralgorithmsonthreedifferentdatasetswith10,000,25,000and50,000users.Table2.6summarizestheresultsofthealgorithmsinformofaverage36Chapter2.One-shotExchangeMarketsamountofincreaseincoverageastheallowedcyclelengthisincreasedfrom2to5.Itisinterestingtonotethattheextentofincrementalcoveragedropsastheallowedcyclelength1isincreasedfrom2to5.Thisisconsistentforallthreealgorithms.Thiscanbeexplainedbythesmallworldphenomenonofnetworksfollowingpowerlawdistributions.Beyondacertainlength,cyclesoflongerlengthtendtopay?diminishingreturns?intermsof%increaseinthecoverage.Thefiguresinthetablecorrespondtothedatasetofsize10,000,averagedovervariousa=0.5,1.0,1.5,2.0.Weobservedlittlevarianceoverdifferentvaluesofa.%Increase2?33??44?*51MaximalAig.5.563.402.7GreedyMg.7.333.813.12LocalSearchAlg.7.713.853.35Table2.6:%Increaseincoveragewhenconsideringcyclesoflength3,4and5.Figures2.8,2.9and2.10illustrateresultsoftheexperimentsformaximal,greedyandlocalsearchalgorithmsrespectively.Inallfigures,?sizeofdataset?referstothenumberofusers.First,foranyofthealgorithms,thenumberofitemscoveredforanyfixedvalueof1decreasesastheskewfactoraincreases.E.g.,inFigure2.8,ata=0.5andI=4,about50,000itemsarecoveredbytherecommendationsgeneratedbyAlgorithmMaximalonthedatasetofsize25,000.Onthesamedatasetand1,ata=2.0,thisnumberdropstoabout15,000.Thesametrendcanbeobservedintheplotsforotheralgorithms.Thereasonthishappensisasthedataismoreskewed,fewerusersownorwishforanyreasonablenumberofitems.Thus,thenumberofuserswhocanengagein37Chapter2.One-shotExchangeMarketsfruitfulexchangesdecreaseswhichinturnbringsdownthenumberofitemscovered.Second,whiletheoretically,AlgorithmMaximaldoesnotenjoyanyprovableapproximationguarantees,thequalityofitsoutputiscomparabletothatoftheotheralgorithms.E.g.,considerFigures2.8,2.9,and2.10andexaminethenumberofitemscoveredbythealgorithmsforthefollowingsituation:1=4anda=1,1.5,anddatasetsize=25,000.Fora=1.0,themaximalalgorithmachievesacoverageofabout60,000itemswhereasbothgreedyandlocalsearchachieveabout65,000.Similarly,fora=1.5,maximalachievesabout35,000comparedtoabout41,000achievedbybothgreedyandlocalsearch.Next,Figure2.12comparestheaverageoftherunningtimesofthealgorithms.Thefigureshowstherunningtimesaveragedovervariousvaluesofa.Asexpected,therunningtimeoftheMaximalalgorithmismuchbetterthanthatofthetwootheralgorithms.TakentogetherwiththefactthatthequalityoftheoutputofAlgorithmMaximalisfoundtobecomparabletothatoftheotheralgorithms,thismakesitaseriouscontenderforfindingaconflict-freesetofexchangecycleswithgoodcoverage.Tocomparerunningtimeofthealgorithmsaccordingtodifferentvaluesofa,weplottherunningtimesofthealgorithmsondatasetsofsize10000,25,000and50,000overvariousvaluesofa=0.5,1,1.5,and2.AswecanseeinallFigures2.13,2.14,2.15,2.16,2.17,2.18,2.19,2.20,and2.21runningtimeofthealgorithmsdecreasesasthevalueofaincreases.Anotherparameterthatwasexploredwasthenumberoftimesthemaximalalgorithm(denotedasMintheSection2.4)isruninorderto38Chapter2.One-shotExchangeMarketsgetareasonableresultqualityinareasonabletime.WeexaminedM=20,50,100,120.TheresultsareillustratedinFigure2.11.Theresultquality,measuredinnumberofitemscovered,improvessignificantlywhenMisincreasedfrom20to50.From50to100,theincreasedropsandfinallyfrom100to120,theincreaseisalmostnegligible.WeselectedM=100inallourexperiments.2.7ConclusionInthischapter,westudyvariousmodelsfortheone-shotexchangemarketproblem,provethatalloftheseproblemsareNP-hardandproposeseveralheuristicandapproximationalgorithmsfortheseproblems.Weanalyzedtheapproximationalgorithmsbyshowingsomeworst-caseapproximationguarantees.Inthedeterministiccase,wemotivatedsimplemarketexchangewhereonlyexchangesintheformofswapsareacceptable.Whileforaverysimilarkidneyexchangeproblem,thisissolvableinpolynomialtime,weprovedthatthisisNP-completeinourcase.Whenlongerexchangecyclesareallowed,NP-completenessextendstooursetting.Wealsoproposedaprobabilisticexchangemarketproblemwherethereareprobabilitiesassociatedwithauserengagingwithanotherinanexchangeandwithexchangingoneitemforanother.Thehardnessresultsextendtothiscase.Byleveragingacloseconnectiontoweightedk-setpacking,wedevelopedaheuristicalgorithm(Maximal)andapproximationalgorithms(Greedy,LocalSearch,andGreedy/LocalSearch).Usingthisconnection,weshowed39Chapter2.One-shotExchangeMarketsthatknownapproximationboundsforthesealgorithmsforwightedk-setpackingcarryovertoourexchangemarketproblems?bothdeterministicandprobabilistic.Finally,weconductedadetailedexperimentationusingsyntheticallygenerateddatasets,comparingdifferentalgorithmsonoutputqualityandrunningtimeandstudyingtheextentofincreaseincoverageasmaximumcyclelengthisincreased,aswellastheimpactofdataskewoncoverage.OurresultsshowthatwhileMaximaldoesnothaveprovableapproximationguarantees,itsperformanceinpracticemaybecomparabletothatoftheotheralgorithms.ThisisinterestinggiventhatMaximalisbyfarthemostefficient.40Chapter2.One-shotExchangeMarketsAlgorithmMaximal:1.RepeatMtimes:(a)ConstructagraphGfromtheexchangemarketinstance.(b)Initializethesetofcycles13tobetheemptyset.(c)WhilethereexistsacycleingraphG:i.RunaBFSalgorithmongraphCstartingfromarandomnodetofindacycleCinthegraph.ii.AddcycleCtothesetofcyclesB.iii.RemoveedgesofCandallotherconflictingedgesofCfromgraphG.2.SelectthemaximumweightsetamongtheMsetsthatarefound.Figure2.5:DescriptionoftheMaximalAlgorithm41Chapter2.One-shotExchangeMarketsAlgorithmGreedy:1.ConstructagraphGfromtheexchangemarketinstance.2.Initializethesetofcycles13tobetheemptyset.3.WhilethereexistsacycleingraphG:(a)FindanexchangecycleCofsizeatmost2kwiththemaximumweightingraphC.(b)AddcycleCtothesetofcycles1.3.(c)RemoveedgesofCandallotherconflictingedgesofCfromgraphC.Figure2.6:DescriptionoftheGreedyAlgorithm42Chapter2.One-shotExchangeMarketsAlgorithmLocalSearch:1.ConstructagraphGfromtheexchangemarketinstance.2.InitializethesetofcyclesBtobetheemptyset.3.Ateachstep(a)LetthecurrentsetofcyclesbeB.(b)ForanyexchangecycleCthatisnotalreadypicked,i.1ytoaddC,andremoveallcyclesinBinconflictwithC.ii.IfthetotalweightofBincreases,addCtoBandremoveallconflictingcyclesfromB.(c)Ifnolocalimprovementispossible,outputBandterminate.Figure2.7:DescriptionoftheLocalSearchAlgorithm43Chapter2.One-shotExchangeMarkets10Alpha=0.5,MaximalAlgonthmioAlpha=1.0,MaximalAlgorithma,-C10a,2I=33II=414EI=5Il=5___________________CC1000025000500001000025,00050000SizeofDatasetsSizeofDatasetsx1Alpha=1.5,MaximalAlgorithmx1oAlpha=2.0,MaximalAlgorithma,a,-C-C_______?1.:_____a,_______D=4________0.5____CC1000025,00050000100002500050000SizeofDatasetsSizeofDatasetsFigure2.8:ResultsoftheMaximalalgorithmondatasetsofsize10000,25000and50000.44Chapter2.One-shotExchangeMarketsFigure2.9:ResultsoftheGreedyalgorithmondatasetsofsize10000,25000and50000.-xio4Alpha=0.5,GreedyAlgorithm80a).0a,z?0a,.0a,z1Alpha=1.0,GreedyAlgorithm150)1005Il=40500001000025,00050(SizeofDatasetsxio4Alpha2.0,GreedyAlgorithm3l?00025,000SizeofDatasetsxio4Alpha=1.5,GreedyAlgorithm)000a,2.5(U2a,1.5.0a,0.5z1000025,000SizeofDatasets500001000025,000SizeofDatasets5000045Chapter2.One-shotExchangeMarketsVC.0(U210ilpha=0.5,LocalSearchAlgorithmioA1la=1.0,LocalSearchAlgorithm(U.0(UzVa).0(UzVa).0(U225,00025,00050000SizeofDatasetsSizeofDatasetsFigure2.10:ResultsoftheLocalSearchalgorithmondatasetsofsize10000,25000and50000.5.5a3.5?4-----?4?23?,4----?---2050100120MFigure2.11:PercentageofcoveragefordifferentM?sintheMaximalalgorithm.46Chapter2.One-shotExchangeMarketsEFigure2.12:AverageRunningTimeofVariousAlgorithms.20.16E14c8C2Maximal,size=10,0000.511.52AlphaFigure2.13:RunningTimeofAlgorithmMaximalondatasetofsize10,0000overvariousaiphas.SireEEEz--z-----L2Lz547140800200-160?140c80C400Maximal,size25kMaximal,size50k0.511.52AlphaFigure2.15:RunningTimeofAlgorithmMaximalondatasetofsize50,0000overvariousalphas.Chapter2.One-shotExchangeMarketsC0.511.52?L5AlphaFigure2.14:RunningTimeofAlgorithmMaximalondatasetofsize25,0000overvariousaiphas.L3L548Chapter2.One-shotExchangeMarkets120C.100a)80IGreedy,size=10k0,511.52AlphaFigure2.16:RunningTimeofAlgorithmGreedyondatasetofsize10,0000overvariousaiphas.1400C1000800p6004000Greedy,size25k0.511.52Alpha?L5Figure2.17:RunningTimeofAlgorithmGreedyondatasetofsize25,0000overvariousaiphas.140--L2---_--492500E1500C5000Chapter2.One-shotExchangeMarketsGreedy,size50k0.511.52AlphaFigure2.18:Ri.mningTimeofAlgorithmGreedyondatasetofsize50,0000overvariousaiphas.180..12080C60C400localSearch,size=10kFigure2.19:RunningTimeofAlgorithmLocalSearchondatasetofsize10,0000overvariousalphas.____????L=3?--:----.-?k??L40.511.52Alpha50Chapter2.One-shotExchangeMarkets4000E2500,E1500C10005000LocalSearch,size25k1234AlphaFigure2.20:RunningTimeofAlgorithmMaximalondatasetofsize25,0000overvariousalphas.-__---__--??Figure2.21:RunningTimeofAlgorithmMaximalondatasetofsize50,0000overvariousalphas.---L3LocalSearch,size50k50005000-LM?L50.511.52Alpha51Chapter3OnlineExchangeMarketsOverTime3.1IntroductionInChapter2,weconsideredonlineexchangemarketsunderdeterministicandprobabilisticmodels.Theobjectiveinthoseone-shotmodelswastomaximizetheweightofcycleswhereweightofacyclecouldeitherbedefinedasthenumberofitems/usersinvolvedinanexchangecycle(intheSimpleMarketProblemandCycleMarketProblem)ortheexpectednumberofitems/usersinvolvedinthetransactionintheProbMarektProblem.Inthischapterweareconsideringonlineexchangemarketsovertimeanddesignatefollowingobjectivesaswellastheobjectivetomaximizetheexpectednumberofitemsexchanged.?Maximizingthenumber(orthetotalvalue)ofitemsexchangedinthemarket.?Minimizingtheaveragewaitingtimeofusersinthesystem.?Maximizingfairnessinthesystem,wherebyfairnesswemeantogive52Chapter3.OnlineExchangeMarketsOverTimehigherpriorityinreceivingitemstouserswhocontributemoretothesystembysharingmorevaluableitems.Inthischapterweobservethatintroducingvirtualpointsandacreditsystemcandecreasetheaveragewaitingtimebyalargemarginandalsocanhelpinmaximizingfairnessinthesystem.Inordertoimplementacompletecreditsystemandvirtualpoints,weneedtotakeintoaccountthefollowingcharacteristics:1.Participation:Motivatingusersforparticipationinthesystembygivingmoreactiveusersmoreitems.2.ProvidingPopularitems:Motivatinguserstoprovidemorepopularitemsbygivingmorecredittouserswhoprovidemorepopularitems,whereanitemismorepopularifitappearsinmorewishlists.3.Encouragingearlyparticipation:Motivatinguserstoparticipateinthesystemasearlyaspossible.4.Fairness:Assigningitemstousersinthemostpossiblefairway,i.e,givingitemstopeoplewhohavealreadycollectedmorecredit.3.2RelatedWorkRelatedworktothischaptercanbeclassifiedinthefollowingcategories:3.2.1SchedulingProblemsTheproblemsinschedulingtheorythatarerelatedtoourproblemare:53Chapter3.OnlineExchangeMarketsOverTimeMinimummakespanscheduling:Givenprocessingtimesfornjobs,P1,P2,...,p,andanintegerm,findanassignmentofthejobstomidenticalmachinessothatthecompletiontime(makespan)isminimized.MinimummakespanschedulingproblemisNP-hardaswecanreduce2-PARTITION[15]tominimummakespanschedulingontwomachines.HorowitzandSahni[211giveanFPTASforthevariantoftheproblemwhenthereareaconstantnumberofmachines.(AnalgorithmAissaidtobefullypolynomialtimeapproximationscheme(FPTAS)ifforeache>0therunningtimeofAisboundedbyapolynomialinthesizeofinstanceIand1/c.)TheminimummakespanproblemisstronglyNP-hardforarbitrarymbyareductionfrom3-PARTITION[15].Thus,therecannotexistanFPTASfortheminimummakespanproblemingeneral,unlessP==NP.HochbaumandShmoys[19]giveaPTAS((1+e)-approximationalgorithmwhichrunsinpolynomialtimeforanyfixede)fortheproblem.(AnalgorithmAissaidtobepolynomialtimeapproximationscheme(PTAS)ifforeache>0therunningtimeofAisboundedbyapolynomialinthesizeofinstanceI.)SchedulingonUnrelatedParallelMachines:Thisproblemisageneralizationoftheminimummakespanscheduling,wherethemachinesarenotidenticalandajobhasdifferentprocessingtimesondifferentmachines.Lenstra,Shmoys,andTardos[23]givea2-approximationforthisversion.Theyalsoprovedthatitisnotpossibletoapproximateitwithinafactor(3/2?e)foranye>0,unlessP=NP.Othergeneralizationsinclude,consideringprecedenceconstraintsintheschedulingofjobs.LamandSeth[27]givea(2?2/ri)-approximationfortheversionwhereeachjobhasaunit54Chapter3.OnlineExchangeMarketsOverTimeprocessingtime.WeusetheaboveproblemstoproveNP-hardnessofthefairnessmaximizationproblem3.6.3.2.2FairnessMaximizationinP2PSystemsThefirstPeer-to-Peer(P2P)networkswerebasedonthephilanthropicbehaviorofthepeers.However,newerP2PapplicationssuchasBitTorrentincorporatesomekindofincentivemechanismtoawardsharingpeers.Oneofthemainreasonsoftherecentsuccessofpeertopeer(P2P)filesharingsystemssuchasBitTorrentisitsbuilt-intit-for-tatmechanism.Forexample,atypicalBit-Torrentclientuploadstofourofitsneighborsfromwhichitreceivesthemostdownload.Theintuitionbehindsuchadesignisthatitwillencourageuploadandleadtoafairandefficientallocationofbandwidthamongthepeers.Inf40]theauthorsexploreifthebandwidthallocationconvergeswhenalltheusersadopttheabovestrategy.Suchadynamicprocessisintuitivelyfairaseachnodereturnsmoretowhoeversentitmore.Theauthorsprovethatthebandwidthallocationconvergestoamarketequilibrium.Inotherwords,simpleasthisappearstobe,itindeedleadstoanefficientallocationofbandwidthinthemarketequilibriumsense.TheP2Psystemsmentionedabovearedifferentfromoursystem.Usersinthosesystemsdon?thavelists,andthesystemsdonotgeneraterecommendations.Moreover,pointsandcreditsystemarenotdefinedexplicitly.55Chapter3.OnlineExchangeMarketsOverTime3.3ModelConsiderasetofusersUandasetofitemsI.UseruEUownsasetofitems(a.k.a.itemlist)S,andrequiresasetofitems(a.k.a.wishlist)W.EachitemiEIhasavalue?popularity?Pcorrespondingtoit,whichisthenumberoftimesitappearsinallusers?wishlists.Inourproposedsystem,thealgorithmisrunperiodicallyandthesetofpotentialfeasibleexchangesarediscovered.Usersinvolvedinthesepotentialexchangesareinformedthroughemailand/ortheiraccountwillbeupdated.Iftheyareinterestedinperformingthetransaction,theywillgetintouchwiththeotherusers.Otherwisetheywillwithdrawthetransactionandallotherinvolveduserswillbeinformed.Inanycasewhenthetransactionisdonetheexchangeditemsareremovedfromtheitemlistsandwishlists,andthesystemwillbeupdated.Thesystemisdynamicmeaningthatitchangeswithtime.Thepossiblechangesare:?anewuserjoinsthenetwork.?auserleavesthenetwork.?anitemisremovedfromauser?swishlistoritemlist:eitherofthesechangesmaybeduetoatransactiondoneortheuser?sinterestschanged.?anitemisaddedtoauser?swishlistoritemlist.Thesechangesimplythatthesetoffeasibleexchangeswillalsochangeby56Chapter3.OnlineExchangeMarketsOverTimetime.Thus,thesystemrunsthealgorithmtofindthesetofnewexchangesthathavebecomeavailableperiodically(asanexample:onceaweek).3.4MinimizingAverageWaitingTimeInthissection,weobservethatbyintroducing?virtualpoints?inthesystem,wecandecreasetheaveragewaitingtimeofusersbyalargemargin.Toimplementthisidea,wegivevirtualpointstoauserforgivingawaytheiritem,andlatergivethemanitemforredeemingtheirpoints.Asanexamplelet?sassumethatuseruhasitemiintheiritemlistanditemjintheirwishlist.Also,let?sassumeuservhasitemjintheiritemlist,howevervdoesnothaveitemiintheirwishlist.Thus,aswapisnotpossible.Theideahereisthatwerecommenditemjtouandinreturngivesomepointstov.Inthiscaseudoesnothavetowaituntilvwishesforiorafeasibleswapcomesup.Wewillelaborateonacreditsystemthatimplementsexchangingvirtualpointsinthenextsection.Itcanbeeasilyseenthat,intheworstcase,usingvirtualpointscandecreasetheaveragewaitingtimeofusersbyalargemargin.Inthefollowing,weformallyshowthatintroducingpointscandecreasetheexpectedwaitingtime,evenassumingthatallusersarriveinarandomorder.Theorem3Consideranexchangemarketconsistingofnusers,andnitems.AssumethatusersputtheiritemsatntimestepsT=1,2,...,n,andweareallowedtoassigncyclesofsizek.LetAbetheaveragewaitingtimeofusersinasystemwithoutpointsandBbetheaveragewaitingtimeofusersinasystemwithvirtualpoints.Thereareinstancesinwhichinthe57Chapter3.OnlineExchangeMarketsOverTimeworsecase,A(k?1)B.Moreover,assumingthatusersputtheiritemsarandompermutation,thereareinstanceinwhichinexpectationA=kB.Proof:Assumethatwecanassigncyclesofsizeatmostk,andletp=Considernusersinthesystemwiththeiritemlistsandwishlistsasfollows:acycleofsizekamonguserscanbeformedbyhavingkusersu,ujsuchthatfor1j<n,useru3hasitemi3inheritemlistanditemiinherwishlistanduseruhasitemiinheritemlistandi1inherwishlist.Clearly,thisinstancehasadmitsp=exchangecyclesofsizekof.Atthebeginning,usershaveemptyitemlistsandwilladditemsinarandomordertotheiritemlists.Attheendoftheprocess,useru3for1<j<nwillhaveitemi3inheritemlist.Startingfromemptyitemlists,weassumethatitemsbecomeavailable.Inotherwords,thewishlistswillbepostedatthebeginning(timeT=0),anditemsarriveontimesT=1,T=2,T=3,...,T=n,andtheyareallrequiredinordertocompletep=cyclesoflengthk.Inthecasethatweusevirtualpointsinthesystem,assoonasanitemarrives,itwillbegiventotheuserthathasthatitemonherwishlist.Thereforethewaitingtimeswouldbe1,2,...,2Bn(n+1)22258Chapter3.OnlineExchangeMarketsOverTimeIntheworstcase,allcyclesfinishinthelastkstepsoftheprocess.Thus,intheworstcase,A=kxi=k(n1)_n1)=n(n+1)k2(k?1)B.i=n?+1Now,weshowthatassumingthattheitemsarriveinarandomorder,inexpectation,AWecomputetheexpectedwaitingtimeofusersbothinthecasethatweusevirtualpointsinthesystem,andinthecasewedonot.TheexpectedvalueofBisthesameasinthepreviouscase,i.e.,B=n(;+1)Nowlet?sconsiderthecasethatwedousevirtualpointsinthesystem.LetC2bearandomvariableshowingthetimethatcycleibecomescompleted.Wealsoknowthattheexpectedwaitingtimeofallcyclesbeingcompletedisthesame:E[C1]=E[C2]=...=E[Cr].Thewaitingtimeinthiscasewouldbe:=k>C2Bylinearityofexpectations,theexpectedwaitingtimeisequaltokE[C]=kpE[C]=nE[C].59Chapter3.OnlineExchangeMarketsOverTimeNow,wecomputeeachE(C)asfollows:E[C]=k(k_iaL(nj=kkn1v?11(k)jkk1kj=kj0?(n?kTherefore,thetotalexpectedwaitingtimeisA=E[C]=nE(C)=kn(n+1)Asaresult,theratiobetweentheexpectedwaitingtimewithandwithoutvirtualpointsis4=.i3.5ACreditSystemInthissection,wedesignacreditsystemthattakesintoaccountthepropertiesthatwementionedearlier.Wedesignacreditsysteminwhicheachusericollectscreditforprovidingitems,andcanredeemcreditpointstoreceivesomeitems.LetC(t)bethecreditofuseriattimet.Eachitemj60Chapter3.OnlineExchangeMarketsOverTimehasacreditscoreP3whichcanbeafunctionofthepopularityofitemj.Initialization:Wecaninitializethecreditofeachnewuserinthesystemtozeroorasmallpositivevalue.UpdatingRules:ConsideratransactionTattimetinwhichauserigivesanitemjtoauseri?,i.e,itemjisinitemlistofiandinwishlistofi?.InthefollowingwedescribehowtochoosetransactionTandhowtoupdatethecreditofeachuseraftertransactionThappenstosatisfythedesiredpropertiesdiscussedintheprevioussection.?Participation:Tosatisfythisproperty,wemakesurethatwechooseauseri?togettheitemsuchthatC?(t)islarge(perhapsthelargest)amongalluserswhohasitemjintheirwishlist.Ingeneral,aftertransactionThappens,weupdateC(t+1)=C(t)+Pj(t)andC+1)=C(t)?P?ProvidingPopularitems:Tosatisfythisproperty,wesetP3(t)tobeafunctionofthenumberoftimesthatitemiappearsinthewishlists.?Encouragingearlyparticipation:Tosatisfythisproperty,weupdatethescoresofusersaftereachtimestepasfollows:Ck(t+1)=Ck(t)*(1+f)wherefisasmallinterestrate,i.e,=0.001.Thiswillencourageuserstoparticipateinthesystemasearlyaspossible.?Fairness:Tosatisfyfairnessinanonlineway,weshouldminimizethemaximumcreditofauserateachstep.Asaresult,inordertosatisfyfairness,wewaitforaperiodoftime(e.g.,aday)foruserstopost61Chapter3.OnlineExchangeMarketsOverTimenewitemsintheiritemlist(andwishlists),andthenassigntheitemstootherusersinthemostfairmanner.wewillformalizethisproblemformallyinthenextsection.3.6MaximizingFairnessInthissection,wecanformalizethefairnessproblemforassigningallnewitemsthroughoutafixedtimewindow(e.g.,oneday)toasetofusers.ConsideratimesteptatwhicheachuserhasacurrentcreditC2LetSbethenewsetofitemsintheitemlistofusersduringthelasttimeday.LetWbethewishlistofuseri,andPbethecurrentvalueforitemj,i.e,ifwegivejEWtouseri,C(t+1)=C?Pj.WewanttoassignitemsinsetsStouserssuchthat:?EachitemineachitemlistSisassignedtoatmostoneuser.?IfitemjSisgiventouseri?,thenjEWi?.?EachuserigetsatmostonecopyofitemjEWinhis/herwishlist.Thegoalistofindsuchassignmentthatminimizesthemaximumcreditinthenextstep,i.e,minmaxC(t+i).Theonlyissuewiththeaboveformulationisthatitispossiblethatauserkwithalargecreditprovidesomenewitemsandnotassigningtheseitemsmaygiveabettersolutionsinceifuserkinthissituationprovides2droptheparametertasitisclearfromthecontext.3ultimategoalistofindafairassignmentthatminimizesthemaximumcredit,andsubjecttothis,weminimizethesecondmaximum,andsoon,butforthesakeofsimplicityandasafirstattempt,welookattheproblemofminimizingthemaximumcredit.62Chapter3.OnlineExchangeMarketsOverTimemoreitems,hisscoreincreasesevenmore,andasaresultthemaximumscoreincreases.Herethereisatradeoffbetweentheexpectedwaitingtimeofusers(orsimilarlythenumberofitemsexchangedinthesystem)andtheabovefairnessproperty.Amiddle-waysolutiontotakeintoaccounttheaforementionedtradeoffistosaythatwewanttofindanassignmentofitemsinSj?stouserssuchthattheassignmentismaximalanditminimizesthemaximumcredit,i.e,afterassigningitemsfromitemliststowishlists,nootheritemcanbeassignedfromitemliststowishlistsofusers.Theorem4ThefairnessmaximizationproblemisNP-complete.Proof:Wegiveareductionfromaschedulingproblemwithrestrictedassignment(BIICmax).Inaschedulingproblemwithrestrictedassignment(BIICmax),wehavenjobsandmmachines,andeachjobjhasaprocessingtimeP3andcanbescheduledonasubsetUofmachines.Givenanassignmentofjobstomachines,whereeachjobjisassignedtoamachineinUj,theloadofmachinei,Listhesumofprocessingtimeofjobsassignedtoi.Thegoalistoassignjobstomachinestominimizethemakespanorthemaximumloadofeachmachine,i.e.,minassignmentmaxL.Thereisaclearreductionfromtheaboveproblemtothemaxfairnessproblem.Hereisthereduction:GivenaninstanceofBIICm,weputauserforeachofthenjobs,andalsoweputauserforeachmachinei(intotal,wehavem+nusers).Forusericorrespondingtomachinei,wehavecreditC2(t)=C=0,withemptywishlist(W=0)andalargeitemlistSwithalljobsthatcanbescheduledonmachineiinit(i.e.,S={jliEU3}).Foruserjcorrespondingtojobjintheinstance,we63Chapter3.OnlineExchangeMarketsOverTimeputtheinitialcreditC,=Pj,awishlistWj={j}andanemptyitemlist.ItiseasytoseethatanassignmentofjobstomachinesintheoriginalBIICmaxproblemcorrespondtoanexchangeofitemsinthenewinstance.Inparticular,theloadofmachineiisequaltothecreditofuseriinthenewinstance.ItiscleartoseethattheproblemofminimizingmakespanintheoriginalinstanceofBIICmaxisequivalenttothefairnessprobleminthisnewinstance,i.e,inordertominimizethemaximumloadofmachinesinBlICmax,weshouldminimizethemaximumcredit.iAsalsomentionedinSection3.2theBIICmproblemisNP-hardandnotapproximablewithinanyconstantfactorbetterthan3/2[23].BII0andthemoregeneralversioninwhichtheprocessingtimeofeachjoboneachmachineisdifferent(i.e,insteadofF,,wehaveisapproximablewithinafactor2.Thus,theabovereductionshowsthatthefairnessproblemisNP-hard,andmoreover,sincetheobjectivefunctionsofthetwoproblemsarethesame,ifwecanoptimizethefairnessproblemwithinafactorbetterthan3/2,thenwecanoptimizetheBIICmschedulingproblemwithinafactorbetterthan3/2.InSection3.8weprovethatourproblemisnotapproximablewithinanymultiplicativefactor.3.7ALinearProgrammingFormulationInthissection,wedevelopanintegerlinearprogrammingformulationofthefairnessproblem.Foratriple(i,j?,j)wherejSandjeWi?,letx?j=164Chapter3.OnlineExchangeMarketsOverTimeifweassignitemjfromi?sitemlisttouseri?,and=0otherwise.Also,weletvariabletbeavariablethatcorrespondstothecreditofuseriaftertheassignmentofthisstep,andvariabletbethemaximumofcredits,ormaxiEut.Finally,foreasyofnotation,weletUbethesetofusersandIbesetofitems.mmttt%VieU=Cj+Zi?:jEW,jEWZi?:jES,x?PjVieUEi?:jEW1Xij?j<1ViEU,jSiZi?:jES,1ViEU,jeWXii?s+i?:jES,,,i?#ii?i?j+Zih?:jEw,,,i?i?Xii?1Vi,j?EU,jESiflT?V?xjj?j{0,1}ViVjSVi?:jeW?Thefirstinequalityindicatesthattisthemaximumcreditofusers.Thesecondinequalityquantifiesthecreditofuseriaftertheassignment.Thethirdinequalitymodelstheconstraintthateachitemjintheitemlistofusericanbeassignedtosomebodyatmostonce,andtheforthinequalitymodelsthefactthateachitemjinthewithlistofusericanbereceivedbyuseri.Finally,thefifthinequalitymodelsthemaximalityofthesolution,i.e,factthatifuseridoesnotgiveanitemjeW?touseri?,theneitheruserigivesjtosomebodyelse,oruseri?getsitfromsomebodyelse.TheLPrelaxationisasfollows:65Chapter3.OnlineExchangeMarketsOverTimemmtttjVieUt=C+j?SZi?:jEW,x&,P2ZjEwi?:jESiViUZj?:jEW1<1VieU,jeSiZi?:jES2xjjj1ViU,jeW,XVi.J+i?:jESn,i?i2+1Vi,i?EU,jESflT?V01ViVjSVi?jeWiThisLPissimilartotheLPfortheschedulingproblembuthasaminussignintheinequalityforT.ItwouldbeinterestingtostudythisLPandseeifasimilarapproachworks.Inparticular,itwouldbenicetostudythebasicfeasiblesolutionsofthisLP.3.8AStrongInapproximabilityResultInthissection,weshowthatthefairnessmaximizationproblemisnotapproximablewithinanyfactor.Theorem5Theproblemoffairnessoptimizationisnotapproximablewithinanymultiplicativefactor.Proof:Weshowthatifwecanapproximatethisproblemwithinanyfactor,wecansolveanNP-completeproblem,i.e.,thepartitioningproblem.Inaninstanceofthepartitioningproblem,wearegivennnumbers66Chapter3.OnlineExchangeMarketsOverTimeal,a2,...a,withthetotalsumofB=a,,andourgoalistoverifyifthereexistsapartitionofthesenumberintotwosetssuchthateachsubsethasthetotalsumof.ItisknownthatthepartitioningproblemisanNP-completeproblem.WesaythataninstanceofthepartitioningproblemisaYESinstance,ifthereexistsasubsetofnumberoftotalsum.Otherwise,theinstanceisaNOinstance.Wegiveareductionfromthepartitioningproblemtothefairnessproblem.Infact,fromanyinstanceofthepartitioningproblem,weconstructaninstanceofthefairnessprobleminwhichtheoptimalsolutiontothefairnessproblemisgreaterthanzeroifandonlyifthepartitioningproblemisaYESinstance.Givenaninstanceofthepartitioningproblemwithnnumbersaa..a,wherea=B,weconstructaninstanceofthefairnessproblemasfollows:Weputnitemsandn+2usersintheinstanceofthefairnessproblem,nusers1,2,3,...,ncorrespondingtonnumbersinthepartitioningproblem,andtwoextrausersn+1andn+2(thatgetitemsfromthefirstnusers).Foreachuseriwhere1n,weputtheinitialcreditC=?as,wishlistW=0anditemlistS={i}.Fortwousersn+1andn+2,weputC?1=C+=B/2,emptyitemlistsS,?1=S?=0andW+NowtheoptimalsolutionforthefairnessproblemiszeroifandonlyifthepartitioninginstanceisaYESinstance.Thereasonisthattheonlywaythatthecreditofbothn+1andn+2goesdowntozeroifandonlyifbothoftheseusersgetasetofitemsoftotalcredit.Moreformally,ifthepartitioningproblemisaYESinstance,andthereexistsasetSofnumberoftotalsum,thensetSofuserscangiveitems67Chapter3.OnlineExchangeMarketsOverTimetousern+1andtherestofuserscangiveitemstousern+2,andaresultthecreditofeachuserinthenextstepiszero.Conversely,iftheoptimalresultingcreditiszero,itmeansthatbothusersn+1and11+2gotexactlytotalcreditfromusers1,2,...,ri.Thus,thesetofuserswhogaveanitemton+1constructasubsetofnumberswithtotalsumandtherefore,thepartitioningproblemisaYESinstance.Theaboveshowsthatifwecanverifyiftheoptimalsolutionforthefairnessproblemiszerooranynumberabovezero,thenwecandistinguishbetweentheYESandNOinstanceofthepartitioningproblem.Therefore,ifthereexistsana-approximationalgorithmforthefairnessproblem,itwilloutputax0=0foraninstanceofthefairnessproblemwithoptimalsolutionzero.Hence,noapproximationalgorithmexistsforthisproblem.I3.9HeuristicAlgorithmsHere,weproposetwoheuristicalgorithmstosolvethefairnessproblem;oneisasimplefastgreedyalgorithm,andoneisbasedonrandomizedroundingofthelinearprogrammingformulationdiscussedintheprevioussection.Thebasicideaoftheroundingalgorithmisastandardmethodforsolvingintegerlinearprograms.3.9.1GreedyAlgorithmAverysimpleheuristicalgorithmistoassignitemtransfersamongusersonebyone,andateachstepfindtheoneitemtransferthatminimizesthemaximumcreditafterthisitemtransfer.Inotherwords,ateachstep,we68Chapter3.OnlineExchangeMarketsOverTimeexamineallpossibleitemtransfersforitemsjESiflforanytwousersiandi?,andfindthetriplei,i?,jsuchthatafteritemtransfer,themaximumcredittheminimumpossible.Todoso,wesorttheusersinthedecreasingorderoftheircredit,andtrytransferringitemsfromusersatthebeginningofthelist.3.9.2AnLP-roundingAlgorithmConsiderthelinearprogrammingrelaxationdiscussedforthefairnessproblem.Intheintegerlinearprogramxis1ifuseigiveanitemjeSflW,itouseri?.ConsiderasolutionxtothisLP.IntheLPrelaxation,wecaninterpretthevariablexjtobetheextentatwhichuserigivesitemjtouseri?.Inotherwords,weusethevalueastheprobabilityoftransferringitemjfromitoi?.Inordertofindafeasiblesolution,weneedtoperformthefollowingroundingalgorithm.1.Initialize=0.2.SolvetheLPrelaxationandfindanoptimalsolutionx.3.ForeachuserianditemjESsuchthat=0,(a)LetZ?3=>(b)Let=ZiI:Z,j=OXiiIj(c)Amongallusersi?forwhich>0andij=0,i.Chooseoneuseri?withprobprobabilityii.Setjj=1,andS=S?{j}.69Chapter3.OnlineExchangeMarketsOverTime4.Foreachitemjandeachi?suchthatjeWj,(a)Letsetbethesetofusersiforwhichjj,jbecameoneinthisround.(b)IfILi?I=1,thenforeachi?e=0,andW=W\{j}(finalizetransfer(i?i?j)),(c)elsei.Chooseoneuseri?eT?withprobabilityii.Foreachii?andiTi?,setii?j=0,andS=SiU{j}.iii.Fori?,let=0,andW?=W\{j}(finalizetransfer(i?i?j)).5.Ifanynewitemtransferwasassignedinthelastround,gobackto3tostartanewround,otherwiseoutputandterminate.3.10ExperimentalEvaluationWeimplementedtheintegerlinearprogramformulationofthefairnessmaximizationproblem,linearprogramformulationoftheproblemusingGNULinearProgramKit(GLPK),andalsothetwoheuristics:LP-roundingandthegreedyheuristicusingMATLAB.TheexperimentswererunonaComputerwitha2.40GHzIntelCore2DuoCPUand3GBofRAMunderWindowsVista.Thegoalsofourexperimentsareasfollows:?Toexaminethequalityoftheresultsfoundbytheheuristicalgorithms70Chapter3.OnlineExchangeMarketsOverTimesinceweprovedthatthefairnessmaximizationproblemisnotapproximable.?Tostudythescalabilityoftheheuristicalgorithmsandalsotheimpactoftheparametera.TheLPrelaxationdiscussedintheprevioussectionsgivesapolynomial-timecomputablelowerboundontheoptimalvalueofthefairnessoptimizationproblem.Infact,weusethislowerboundtoevaluatetheperformanceofourheuristicalgorithms.3.10.1DatasetWecouldnotgetaccesstothedataofrealonlineexchangeapplications.Hence,wegeneratedasetofsyntheticdata.Datagenerationforthemarketsovertimeissimilartowhatwedidinthepreviouschapterforone-shotexchangemarketswhichwasexplainedinSection2.6.1.3.10.2ExperimentsThefollowingexperimentswereperformedinordertoexaminetheperformanceoftheheuristicalgorithms.Weimplementedtheintegerlinearprogramming(ILP)andalsothelinearprogramming(LP)formulationoftheproblemusingGLPKandtheLP-roundingandthegreedyheuristicusingMATLAB.Weranouralgorithmsonthreedifferentdatasetswith100,500and1000users.Thedataweregeneratedwithfourdifferentvaluesfora=0.25,0.5,0.75and1.71Chapter3.OnlineExchangeMarketsOverTimeusers=10,items=50?4?integerLinearProgram?I??LProunding?i--AlgorithmGreedy0.250.50.751Figure3.1:PerformanceoftheheuristicscomparedtotheoptimalsolutiongivenbyILPondatasetof10users.WesolvedtheILPfortwosmalldatasetsincluding10users,50itemsand20users,100items.TheILPgivesustheoptimalsolutionhoweveritsrunningtimeisexponential.WecomparetheresultsoftheLP-roundingandgreedyonsamedatasetstotheoptimum.TheresultsaredepictedinFigures3.1and3.2respectively.Figures3.3,3.4,and3.5showtheresultsoftheLP,LP-roundingandthegreedyheuristicfordatasetsofsize100,500,and1000respectively.Thenumberoftotalitemsineachcaseis5timesthenumberofusers.TheYaxisindicatesthemaximumcredit,andtheX-axisshowsaforthedifferentalgorithms.WehaveusedtheLPresultsalowerboundontheoptimalvalue.Ascanbeseen,theLP-roundinghasabetterperformancethantheotherheuristic.Also,wecanobservethatasaincreases(inmostcases),12080E6014072Chapter3.OnlineExchangeMarketsOverTimeFigure3.2:PerformanceoftheheuristicscomparedtotheoptimalsolutiongivenbyILPondatasetof20users.thealgorithms?performancealsoimproves.TherunningtimesoftheabovealgorithmsarealsodepictedinFigures3.6,3.7,and3.8fordatasetsofsize100,500,and1000respectively.Ascanbeseen,therunningtimeofthegreedyalgorithmisbetterthantheLProundingheuristic.Moreover,wecanseethatbyincreasinga,therunningtimeimproves.Anothermeasurethatweexploredwasthenumberoftransactionsperformedateachtimestep.Itisimportantthattheusersstayactiveandhaveincentivetosharetheiritems,evenwhentheyhavereceivedanitemfromtheirwishlist.Figure3.9plotsthepercentageofactiveusersinatsixconsecutivetimewindowsinasimulationdonewith100users.Ascanbeseenatthebeginningwehavethemaximumactivity.The200users=20,items=100180I40120.80LinearProgram00.25050.75a73Chapter3.OnlineExchangeMarketsOverTimeFigure3.3:Performanceofdifferentalgorithmsondatasetofsize100.reasonisthatallusersstartwithequalinitialcredits.3.11ConclusionInthischapter,weconsiderexchangemarketproblemsovertimeandstudyefficientmechanismsthatimprovetheusers?waitingtimesandalsogiveincentivetouserstobemoreactivebymaximizingfairnessinthesystem.Inordertoachievetheaboveobjectives,weintroducepointsandcreditstothesystemandweshowthatwaitingtimeswouldimprovebyusingpoints.Moreover,weshowthattheproblemoffairnessmaximizationnotonlyisNP-complete,butalsoinapproximable.Therefore,weproposetwoheuristicalgorithms:linearprogramming-basedandagreedyalgorithm.Weperformexperimentstoexaminetheperformanceandscalabilityoftheproposed2500Datasetsize=1002000.91500E100005000-+-LPIP-rounding?i--Greedy0.250.50.75a74Chapter3.OnlineExchangeMarketsOverTime-__-_Figure3.4:Performanceofdifferentalgorithmsondatasetofsize500.algorithms.Theexperimentsshowthatbothheuristicsperformmuchbetterthantheworst-caseperformance.Moreover,LP-roundingperformsbetter,howeverthegreedyheuristicismuchfaster.Datasetsize=5009000j4000o20000-4--LPLP-rounthng?i--Greedy0250.50.751(L75Chapter3.OnlineExchangeMarketsOverTimeFigure3.5:Performanceofdifferentalgorithmsondatasetofsize1000.Figure3.6:Runningtimesfordatasetofsize100.25000Datasetsize=10001500020000.900100005000aSLP-rounding?*?Greedy0.250.50.75aRunningtime,datasetsize=1003000w2000E;1500__________________________________?I?LProunding1000500?k?Greedya0.250.50.751U76Chapter3.OnlineExchangeMarketsOverTimeFigure3.7:Runningtimesfordatasetofsize500.-Figure3.8:Runningtimesfordatasetofsize1000.runningtime,datasetsize=500160008000-4?LP-rounding4000?i?Greedy20000?0.250.50.751aRunningtime,datasetsize=100030000?25000U20000E15000E?10000???I???LP-roundingI.5000?-Greedy00.250.50.751ci77Chapter3.OnlineExchangeMarketsOverTimeI1hiiFigure3.9:Numberoftransactingusersin6consecutivetimewindows.UserActivitylIP-rounding123456limesteps78Chapter4ConclusionsandFutureWorkthisthesis,wemotivatetheuseofonlineexchangemarketsasanapplicationoversocialnetworksandproposespecificmarketexchangeproblemswhereusersownitemlistsandhavealistofwishesandcanexchangeitemswithoneanother.Fortheseproblems,weproposeafewoptimizationproblems,studythecomplexityoftheseproblems,proposevariousalgorithmswithguaranteedapproximationfactorforsomeoftheseproblems,andfinallyperformexperimentalresultstoevaluatetheperformanceofseveralapproximationandheuristicalgorithms.Intheone-shotdeterministiccase,westudysimplemarketexchangesinwhichtheonlyacceptableexchangesareintheformofswaps.Whileforasimilarwell-studiedproblemcalledthekidneyexchangeproblem,thisproblemissolvableinpolynomialtime,weprovethatthisisNP-completeinourcase.Whenlongerexchangecyclesareallowed,kidneyexchangewasshowntobeNP-complete[5]andthisextendstooursetting.Wealsoproposeaprobabilisticexchangemarketprobleminwhichthereareprobabilitiesassociatedwithauserengagingwithanotherinanexchange.Thehardness79Chapter4.ConclusionsandFutureWorkresultsextendtothiscase.Byleveragingacloseconnectiontotheweightedk-setpackingproblem,wedevelopaheuristicalgorithm(Maximal)andapproximationalgorithms(Greedy,LocalSearch,andGreedy/LocalSearch).Usingthisconnection,weshowthatknownapproximationboundsforthesealgorithmsforweightedk-setpackingcarryovertoourexchangemarketproblemsbothdeterministicandprobabilistic.Weconductadetailedexperimentationusingsyntheticallygenerateddatasets,comparingdifferentalgorithmsonoutputqualityandrunningtimeandstudyingtheextentofincreaseincoverageasmaximumcyclelengthisincreased,aswellastheimpactofdataskewoncoverage.OurresultsshowthatwhileMaximaldoesnothaveprovableapproximationguarantee,itsperformanceinpracticemaybecomparabletothatoftheotheralgorithms.ThisisinterestinggiventhatMaximalisbyfarthemostefficient.Finally,weconsidersimilarexchangemarketproblemsovertimeandstudyefficientmechanismsthatimprovetheusers?waitingtimesandalsogiveincentivetouserstobemoreactivebymaximizingfairnessinthesystem.Inordertoachievetheaboveobjectives,weintroducepointsandcreditstothesystemandweshowthatwaitingtimeswouldimprovebyusingpoints.Moreover,weshowthattheproblemoffairnessmaximizationnotonlyisNP-complete,butalsoinapproximable.Therefore,weproposetwoheuristicalgorithms:linearprogramming-basedandagreedyalgorithm.Weperformexperimentstoexaminetheperformanceandscalabilityoftheproposedalgorithms.Theexperimentsshowthatbothheuristicsperformmuchbetterthantheworst-caseperformance.Moreover,LP-roundingperformsbetter,howeverthegreedyheuristicismuchfaster.80Chapter4.ConclusionsandFutureWorkAsafuturework,furtherinvestigationofthesealgorithmsonrealdatasetswouldbevaluable.Designingimprovedapproximationalgorithmsorprovingsomestrongerinapproximabilityresultsfortheoptimizationproblemsdiscussedinthisthesisaredesirable.Also,itisinterestingtostudyspecialvariantsoftheseproblemsthatappearinpractice,anddesignapproximationalgorithmswithprovablyimprovedapproximationfactor.Finallyitwouldbeinterestingtostudyincentiveissuesinthesesettings,anddesignmechanismsthatperformwellinthepresenceofstrategicuserswhomaynotrevealtheirtrueparameters(e.g.,theiritemlists).Insuchsettings,usersmaylieabouttheiritemsliststogetabetterassignment.Todealwithsuchsettings,oneneedstodesign(truthful)mechanismsthatgiveincentivetouserstorevealtheirtrueparameters.Itisalsointerestingtoexploreiftheproposedmechanismconvergestoanequilibrium.81Bibliography[1]?http://blog.compete.com/2007/01/25/top-20-websites-ranked-by-[2]http://www.oddshoe.org.[3]http://www.peerflix.com.[4]http://www.readitswapit.co.uk.[5]DavidJ.Abraham,AvrimBlum,andThomasSandholm.Clearingalgorithmsforbarterexchangemarkets:Enablingnationwidekidneyexchanges.InACMConferenceonElectronicCommerce,pages295?304,June13-162007.[6]DavidJ.Abraham,NingChen,VijayKumar,andVahabMirrokni.Assignmentproblemsinrentalmarkets.InWINE2006,pages198?213,2006.[7]0.AdomaviciusandA.Tuzhilin.Towardthenextgenerationofrecommendersystems:Asurveyofthestate-of-the-artandpossibleextensions.IEEETransactionsonKnowledgeandDataEngineering,17(6):734?749,2005.82Bibliography[8]EstherM.ArkinandRefaelHassin.Onlocalsearchforweightedk-setpacking.InESA1997,pages13?22,1997.[9]M.BlaserandB.Siebert.Computingcyclecoverswithoutshortcycles.InInProceedingsoftheS4stAnnualEuropeanSymposiumofAlgorithms,2001.[10]BarunChandraandMagnusHalldorsson.Greedylocalimprovementandweightedsetpackingapproximation.InSODA1999,pages169?176,1999.[11JW.W.Cohen,R.E.Schapire,andY.Singer.Learningtoorderthings.JournalofArtificialIntelligenceResearch,10:243?270,1999.[12]J.EdmondsandE.Johnson.Matchingeulertoursandthechinesepostmanproblem.Mathematicalprogramming,5:88?124,1973.[13]OzlemErgun,GultekinKuyzu,andMartinSavelsbergh.Collaborativelogistics:Theshippercollaborationproblem.ComputersandOperationsResearchOdysseus,2003.[14]Y.Freund,R.Iyer,R.E.Schapire,andY.Singer.Anefficientboostingalgorithmforcombiningpreferences.In15thInternationalConferenceonMachineLearning,1998.[15]M.R.GareyandD.S.Johnson.ComputersandIntractability.Freeman,NewYork,1979.83Bibliography[16]0.Goldschmidt,D.Hochbauin,C.Hurkens,andC.Yu.Approximationalgorithmsforthek-cliquecoveringproblem.SIAMJournalofDiscreteMath.,6(3):492?509,1996.[17]M.Guan.Graphicprogrammingusingoddandevenpoints.ChineseMathematics,1:273?277,1962.[18]D.HochbaumandE.Olinick.Theboundedcycle-coverproblem.INFORMSJournalonComputing,13(2):104?109,2001.[19]DoritS.HochbaumandDavidB.Shmoys.Apolynomialapproximationschemeforschedulingonuniformprocessors:Usingthedualapproximationapproach.SIAMJournalofComputing,17(3):539?551,1988.[20]IanHolyer.Thenp-completenessofsomeedge-partitionproblems.SIAMJournalofComputing,,10(4):713?717,November1981.[21]EllisHorowitzandSartajSahni.Exactandapproximatealgorithmsforschedulingnonidenticalprocessors.J.ACM,23(2):317?327,1976.[22]N.Immorlica,V.S.Mirrokni,andM.Mahdian.Cyclecoverwithshortcycles.InSymposiumonTheoreticalAspectsofComputerScience(STAGS),2005.[23]D.B.ShmoysJ.K.LenstraandEvaTardos.Approximationalgorithmsforschedulingunrelatedparallelmachines.Math.Program.,46(3):259?271,1990.84Bibliography[24]K.Gallagher.J.Parsons,P.Ralph.Usingviewingtimetoinferuserpreferenceinrecommendersystems.InAAAIWorkshopinSemanticWebPersonalization,July2004.[251R.Jin,L.Si,andC.Zhai.Preference-basedgraphicmodelsforcollaborativefiltering.In19thConferenceUncertaintyinArtificialIntelligence(UAI2003),August2003.[26]R.Jin,L.Si,C.Zhai,andJ.Callan.Collaborativefilteringwithdecoupledmodelsforpreferencesandratings.In12thInternationalConferenceInformationandKnowledgeManagement(CIKM2003),Novemeber2003.[27]S.LamandR.Sethi.Worstcaseanalysisoftwoschedulingalgorithms.SIAMJournalofComputing,6(3):518?536,1977.[28]B.P.S.MurthiandS.Sarkar.Theroleofthemanagementsciencesinresearchonpersonalization.ManagementScience,49(10):1344?1362,2003.[29]M.E.J.Newman.Thestructureandfunctionofcomplexnetworks.SIAMReviews,45(2):167?256,2003.[30]ChristosH.Papadimitriou.Onthecomplexityofedgetraversing.JournaloftheACM,23(3):544?554,1976.[31]M.J.D.Powell.ApproximationTheoryandMethods.CambridgeUniversityPress,1981.85Bibliography[32]etal.R.Andersen.Trust-basedrecommendationsystems:anaxiomaticapproach.17thInternationalWorldWideWebConference(WWW),2008.[33]B.RachavachariandJ.Veerasamy.A3/2-approximationalgorithmforthemixedpostmanproblem.SIAMjournalofDiscreteMath.,12:425?433,1999.[34]P.Resnick,N.Iakovou,M.Sushak,P.Bergstrom,andJ.Riedl.Grouplens:Anopenarchitectureforcollaborativefilteringofnetnews.InComputerSupportedCooperativeWorkConference,1994.[35]P.Resnick,N.Iakovou,M.Sushak,P.Bergstrom,andJ.Riedl.Grouplens:Anopenarchitectureforcollaborativefilteringofnetnews.InComputerSupportedCooperativeWorkConference,1994.[36]E.Rich.Usermodelingviastereotypes.CognitiveScience,3(4):329?354,1979.[37]G.Salton.AutomaticTextProcessing.Addison-Wesley,1989.[38]G.Shani,R.Brafman,andD.Heckerman.Anmdp-basedrecommendersystem.In18thConferenceUncertaintyinArtificialIntelligence,August,2002.[39]CarstenThomassen.Onthecomplexityoffindingaminimumcyclecoverofagraph.SIAMJ.Comput.,26(3):675?677,1997.[40]F.WuandL.Zhang.Proportionalresponsedynamicsleadstomarketequilibrium.InSTOC,pages354?363,2007.86Bibliography[41]C.Q.Zhang.Integerflowsandcyclecoverofgraphs.MarcelDekker,1997.87

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
United States 11 2
China 6 12
Ireland 4 0
Poland 3 0
France 2 0
Germany 2 1
Romania 1 0
City Views Downloads
Unknown 10 4
Dublin 4 0
Shenzhen 4 12
Ashburn 3 0
Mountain View 3 0
Beijing 2 0
Seattle 1 0
Craiova 1 0
New York 1 1

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0051430/manifest

Comment

Related Items