2−E−7
1996年度日本オペレーションズ・リサーチ学会春季研究発表会
AnOptimalSelectionandReplacementPolicy RelatedtotheDurationProblem
O1303783 愛知大学 玉置光司 TAMAKIMitsushi l．Introiluction
Weconsiderhereavariationofthesequentialobservationandselectionproblemca11edIheduration
problemtreated byFbrguson，Hardwick，andTamaki・The basicframeworkofthenoinformation durationproblemisdescribedasfollo、VS・nCandidatesappearOneatatimeinrandomorderwithal1n！
permutationscquallylikely・Ifwecouldobservethema11，WeCOuldrankthemabsolutelywithnoties from・besttoworst・However，eaChtimeacandidateappearS，WeOnlyobservetherankofthecandidate relativetothose precedingheranddecide，based soIclyontheobservedrank，Whethertochoosea Candidateornot．Therewardtothedecisionmaker（abbreviatedbyDM）isthelengthoftimeheisin POSSeSSionofarelativelybestcandidate，Whoiscalledaneligiblecandidate，ThusDMwillonlyselect aneligiblecandidate，reCeivlngOneunitofrewardashedoessoandanadditionaloneforeachnew
Observationaslongastheselectedcandidateremainseligible．TheobjectiveofDMistomaximizethe
expeCtedrewardearned．Beforeconsideringourproblem，WeglVealemmaforlateruse・
LEMWIA B
Assumethatr（X），0≦X≦1，isadifferentiableunimodalfunctionwithend
altainsitspeakata，Wherer（a）＞0．AIsoleto【andβberespeCtivelythesmal1erandthel左rgerr00tOfthe
equationr（X）＝0．
Then，if入x，y＝X／y2，0＜X＜y＜1，thefunctionalequation
〈 r
1
鼠
r（Ⅹ）＝maX （X），
r（y）九x，ydy
0≦X≦1 hasacontinuoussolutionortheform l／≦ X ≦ 0 ≦ X ≦ b
0，β≦X≦1
Whereb（α≦b≦a）istheumiquerootxoftheequation r（）′）入x，ydy・
r（Ⅹ）＝
ヱ・Optimalselectiomandreplacememtproblem
Theproblemweconsiderhereiscomposedoftwosubproblems，Selectionproblemandreplacement
PrOblem・DMeamstherewardproportionaltotimedurationspentWithaneligiblecandidate，thusthe Selection problem arises when DM hasnocandidate−DMmust decide when to select an eligible
CandidatethatappearS．AssoonasaneweligiblecandidateappearSafterselection，theprcsentcandidate turnsouttobeineligibleandnofurtherrewardisearned．Thusthereplacementproblemariseswhen
DMhasacandidate−DMmustdecidewhetherornottoreleasethepresentcandidatebypaylngher
COnSOlationmopeyc（≧0）andsimultaneouslygetaneweligiblecandidate・WhenDMdecidesnotto
release，herecelVeSnOreWarduntilthefinaltimeorthenextcligiblecandidateappearS，inwhichcase，
DMagainfacesthereplacementproblem，Theo句ectiveistofindaprocedurewhichmaximizesthe expeCtednctreward．
Forsimplicity，WeCOnSiderheretheasymptoticcase，1ettingntendtムinfinity．Let更（幻denotethe
StateWhereDMhasnocandidate（keepsacandidate）andfacinganeligiblecandidateat
．
貢（勾．
Thenwehavethefol］owlngequations．
−278−
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.
r（Ⅹ）＝赫−X＋g（）′））伊（1−Ⅹ）けx，yd拒）入xヰ
〈
1−tl／
Vノ d
X ヽ人 ︶ y ︵ g
l ﹂ト上
・∫（y
X）入x，ydy＋（1−X
g（Ⅹ）＝maX ーC
Thesearesimpliriedto
rl（Ⅹ），￡ー（｝り入x，yd）′）
．r（X）＝maX where
g（X）＝maX
g（y）入x，ydy，r2（X）＝−C−XIogx・
rl（X）＝−Xlogx＋
ThesecanbcsoIvedtoyieldtherollowln畠1emmas．
LEMMA2
AssumethatDMisatstate貢．Thentll′OCaSeSaredistinguisheddependingonthevalueorc．
Casel（C≧eTl）：Noreplacementoccurs．
Case2（0≦C＜e−1）‥Letβ（＞e−1）bethelargerrootoftheequatioりr2（X）＝0，anddefin占x氷＝e−2／β，then repJacementoccursirandonlyirx事≦X≦β．
LEMMA3
AssumethatDMisatstate言．Thenwehave
Casel（C≧e−1）‥Selectionismadeirandohlyife：2≦X≦l・Theexpectednetrewardis2e−2．
c。Se2（0≦。＜e−・）：LeL入＝1．1。g p・・＝1−。／β，anddefinex＊＊＝eXPし（1十
thenselectionismadeifandonlyifx楽★≦X≦l．ThcexpeCtednetrewardis一（x＝logx米＊＋X‡logx＊＋・C）．
Summarizlngtheabovclemmas，Wehavethemainresult．
THEOREM4
Casel（C≧e￣1）：Theoptimalprocedurepassesoverthecandidatesthatappearbeforee−2andthen
Selectthefirsteligiblecandidate・Noreplacementoccursandtheexpectednetrewardis2e−2・
Case2（0≦C＜e−1）：Theoptimalprocedure
．
inix＊，β）（neithert（X）early？rtOO・1afe）・Theexpectednetrewardis−（x＃＊logx＊＊・X＊logx＊・C）・
Remark： When consolation moneyis zero，i．e．，C ＝ 0，β＝1，X＊＝e−2≡0．1353，and X＊＊＝eXd−（1＋仰））≡0．O799．Thusthemaximumnetrewardis2e−2＋（1＋f7nxd−（1＋仰郡）⊆
0．4725．
Re鮎rence
T．S．Ferguson，J．P．HardwickandM．Tamaki（1992） Maximizingthedu；ationofowningarelatively besto句ect 一ContemporaryMathematics125，37−57．
−279−
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.
