fairly allocating contiguous blocks of indivisible items warut suksompong资料.pdf

该【fairly allocating contiguous blocks of indivisible items warut suksompong资料 】是由【赖大文档】上传分享，文档一共【10】页，该文档可以免费在线阅读，需要了解更多关于【fairly allocating contiguous blocks of indivisible items warut suksompong资料 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。DiscreteAppliedMathematicsxxx(xxxx)xxxContentslistsavailableatScienceDirectDiscreteAppliedMathematicsjournalhomepage:ate/damFairlyallocatingcontiguousblocksofindivisibleitems?WarutSuksompongputerScience,UniversityofOxford,UnitedKingdomarticleinfoabstractArticlehistory:Inthispaper,,,envy-freeness,Availableonlinexxxxandequitabilityarenotguaranteedtoexistevenwithoutthecontiguityrequirement,Keywords:-freeness?:Howcanwedivideasetofresourcesamonginterestedagentsinsuchawaythattheresultingdivisionisfair?ursinavarietyofsituations,includingstudentssplittingtherentofanapartment,couplesdividingtheirpropertiesafteradivorce,,suchascakeandland,,likehousesandcars,areindivisible—,,threeoftheoldestandbest-knownofwhichareproportionality,envy-freeness,,-freeifeveryagentthinksthatherbundleisatleastasgoodasthebundleofanyotheragent,,whenresourcesaredivisible,allocationsthatsatisfythethreenotionssimultaneouslyalwaysexist[1].Ontheotherhand,,,.,,whenwedivideofficesbetweenresearchgroupsonthesamefloor,,whenweallocateretailunitsonastreet,?ApreliminaryversionofthispaperappearedinProceedingsofthe10thInternationalSymposiumonAlgorithmicGameTheory,-mailaddress:warut.******@:///.-218X/?:,Fairlyallocatingcontiguousblocksofindivisibleitems,DiscreteAppliedMathematics(2019),https:///.(xxxx)xxxTable1Comparisonofourresultsonthepriceoffairnesstopreviousresultsin[2,10].(thiswork)Non-contiguous[10]UtilitarianEgalitarianUtilitarianLowerUpperLowerUpper?+1?+1Proportionalityn1n1n1n3===Equitability2forn21forn22forn2∞>∞>∞>√forn√2forn2forn2?n?n+?n3n+7?(1)?1Envy-freeness221o(1)29Onn2DivisibleContiguous[2]Non-contiguous[10]UtilitarianEgalitarianUtilitarianLowerUpperLowerUpper√?√√√nn+??Proportionality221o(1)1(n)O(n)+2Equitabilityn?1+1n1(n1)n√?n√4n√nn+?n??1Envy-freeness221o(1)2(n)n2inthetemporalsense,,,,weshowthatinlightofthecontiguityrequirement,,foreachnotionwedefineanapproximateversionthatdependsonanadditivefactor?≥?-proportionaliftheutilityofeachagentisatmost?awayfromher‘‘proportionalshare’’,?-envy-freeifeachagentenviesanyotheragentbyatmost?,and?-equitableiftheutilitiesofanytwoagentsdifferbyatmost?.Denotingthemaximumutilityofanagentforanitembyumax,weestablishtheexistenceofacontiguousumax-proportionalallocationandacontiguousumax-equitableallocationforanynumberofagents,acontiguousumax-envy-freeallocationfortwoagents,andacontiguous2umax-envy-,?1·ofagentsaswellasforenvy-,forproportionalitythefactorcanbeimprovedtonumaxifweknowthenumbernofagents,,theapproximationfactorsforproportionalityandequitabilitywithanynumberofagentsandforenvy-,,whentherearenagentsandmitems,thenumberofarbitraryallocationsisnm,whilethenumberofcontiguousallocationsforafixedorderofitems(m+n?1)!onalineisatmostn?,weinvestigatetheefficiencylossofcontiguousallocationsduetofairnessconstraintsusingthepriceoffairnessconceptinitiatedbyCaragiannisetal.[10].,whileahighpriceoffairnessimpliesthateventhemostefficient‘‘fair’’,AumannandDombb[2]focusedoncontiguousallocationsofdivisibleitemsandconsideredbothutilitarianandegalitarianwelfare,whereutilitarianwelfarereferstothesumofagents’,pletethepicturebyprovidingtightoralmosttightboundsonthepriceoffairnessforcontiguousallocationsofindivisibleitems,,oftenrepresentedbyacake,withthemotivationthatonewantstoavoidgivinganagenta‘‘unionofcrumbs’’.Inparticular,DubinsandSpanier[16]exhibitedamoving-árováetal.[12]showedthatforanyorderingoftheagents,acontiguousequitableallocationthatassignscontiguouspiecestotheagentsinthatorderexists;however,CechlárováandPillárová[13]-freeness:Stromquist[25,26]provedthatacontiguousenvy-[27]usedtechniquesinvolvingSperner’slemmatoestablishtheexistenceofacontiguousenvy-freeallocationandmoreoverconsideredtherelatedproblemofrentPleasecitethisarticleas:,Fairlyallocatingcontiguousblocksofindivisibleitems,DiscreteAppliedMathematics(2019),https:///.(xxxx),thealgorithminTheorem1isadiscreteanalogoftheDubins–Spanierprotocol,whileTheorem3mirrorstheanalogousresultinthedivisiblesettingbyAumannandDombb[2].Recently,Bouveretetal.[8]studiedtheallocationofindivisibleitemsonalinewiththecontiguityconditionandshowedthatdeterminingwhetheracontiguousfairallocationexistsisNP-hardwhenthefairnessnotionconsiderediseitherproportionalityorenvy-.[3]-hardtofindtheoptimalcontiguousallocation,.[5]andCohleretal.[14]alsoconsideredtheobjectiveofmaximizingwelfare,butundertheadditionalfairnessconstraintofproportionalityandenvy-freeness,,Bilòetal.[6]studiedapproximateenvy-freeallocationsandobtainedimprovedresults,whileIgarashiandPeters[18],thehighestutilityofanagentforanitem,.[20]showedthatwithoutthecontiguityrequirement,aumax-envy-.[11]usedtheterm‘‘envy-freenessuptoonegood’’,,Caragiannisetal.[10],whoinitiatedthislineofresearch,[17]likewiseconsideredthesettingofdivisiblechoresbut,similarlytoourworkandthatofAumannandDombb[2],òetal.[7],afewrecentworkshaveshownthateveninsettingswhereitemsdonotnaturallylieonaline,-HaleviandSuksompong[24]andKyropoulouetal.[19]usedthismethodtodevisealgorithmsforallocatingitemsamonggroupsofagents,whereasOhetal.[23]={1,2,...,n}denotethesetofagents,andM={1,2,...,m}∈Nhassomenonnegativeutilityui(j)foritemj∈,defineui,max:=maxj∈Mui(j):=maxi∈Nui,′=∑(.,[9,11,15,22]),(M)j∈M′ui(j)foranyagentiandanysubsetofitemsM′?=(M,...,M)isapartitionofallitemsintobundlesfor1∑∈Nui(Mi)andtheegalitarianwelfareofMismini∈Nui(Mi).,werefertoasettingwithagents,items,;=,...,≥1·∈?≥(M1Mn)issaidtobeproportionalifui(Mi)nui(M),the?≥1·??∈1·allocationissaidtobe-proportionalifui(Mi)nui(M)(M)=(M1,...,Mn)issaidtobeenvy-freeifui(Mi)≥ui(Mj)foralli,j∈?≥0,theallocationissaidtobe?-envy-freeifui(Mi)≥ui(Mj)??foralli,j∈=(M1,...,Mn)issaidtobeequi