资源描述:
《Learning on a Budget-Posted Price Mechanisms for Online Procurement》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、XLearningonaBudget:PostedPriceMechanismsforOnlineProcurementAshwinkumarBadanidiyuru,CornellUniversityRobertKleinberg,CornellUniversityYaronSinger,GoogleWestudyonlineprocurementmarketswhereagentsarriveinasequentialorderandamechanismmustmakeanirrevocable
2、decisionwhetherornottoprocuretheserviceastheagentarrives.Ourmechanismsaresubjecttoabudgetconstraintandaredesignedforstochasticsettingsinwhichthebiddersareeitheridenticallydistributedor,moregenerally,permutedinrandomorder.Thus,theproblemswestudycontribu
3、tetotheliteratureonbudget-feasiblemechanismsaswellastheliteratureonsecretaryproblemsandonlinelearninginauctions.Ourmainpositiveresultsareasfollows.Wepresentaconstant-competitivepostedpricemechanismwhenagentsareidenticallydistributedandthebuyerhasasymme
4、tricsubmodularutilityfunction.Fornonsym-metricsubmodularutilities,undertherandomorderingassumptionwegiveapostedpricemechanismthatisO(logn)-competitiveandatruthfulmechanismthatisO(1)-competitivebutusesbiddingratherthanpostedpricing.1.INTRODUCTIONInanonl
5、ineprocurementmarketagentsarriveinasequentialordertooffertheirservice,andabuyerdecideswhetherornottoprocuretheserviceastheagentarrives.Naturally,eachagentwishestobecompensatedforherservice,whilethebuyerinturnhaslimitedresourcesandaimstoprocuretheservic
6、esthatmaximizeherutility.Thecomplexitiesofsuchmarketsoriginateinthesevereinformationallimitationsofthebuyer:theagents’truecostsforprovidingtheirserviceareunknowntothebuyerandmaybeexaggerated,andthesequentialmannerinwhichagentsappearrequiresmakingdecisi
7、onswithoutfullknowledgeofthemarket.Inaddition,themechanismmaybelimitedinthewayitcancollectinformationfromagents,andmustinfertheircostsfromimplicitsignals.Toaddressthefirstinformationallimitation,mechanismdesigntheoryadvocatesfortruthfulmechanisms,which—
8、throughcarefuldesignofpaymentandallocationrules—incentivizeeveryparticipatingagenttorevealhertruecostforperformingtheservice.Inprocurementmarkets,thechallengeisthentodesigntruthfulmechanismsthatyieldafavorableoutcomeforthebuyerunderlimi