Gradualism in voluntary contribution games due
to very small uncertainties
著者
Yusuke Samejima
journal or
publication title
The Economic Review of Toyo University
volume
40
number
2
page range
173-199
year
2015-03
Gradualislninvoluntarycontributiongalnes
duetoveryslnalluncertainties
YusukeSamejima
Abstract WeimproveontheresultbySamajimal20131andshowthatintwo-playervoluntarycontributiongamesas analyzedbyCompteandJehiel[2003},verysmalluncertaintiesaboutopponentplayers'valuationsofcompleting aprojectcancausegradualisminaccumulationofcontributions'OurstudydiffersfromCompteandJehiel{20031 inthatourgamesareplayedinincompleteinfbrmationenvironmentswherethereisachancefbreachplayerto beeitherahighvaluationtypeoralowvaluationtype.Insuchenvironments,Samejimal20131showsthat,ifthe priorprobabilityoftheopponentplayerbeingahigh-typeisbelowacertainupperbowzdfOrbothplayers,andif playersaresufficientlypatient,thereexistsaperfectBayesianequilibriuminwhichstep-by-stepcontributionsare realizedalongtheequilibriumpath.ThisgradualaccumulationofcontributionsisnotobservedinCompteand Jehiel'sequilibriumincompleteinfbrmationenvironments.Inthepresentpaper,weremovetheupperbound conditiononthepriorprobabilitiesinSamejima[20131.Ourresultindicatesthatverysmalluncertaintiesabout valuationsheldbytheopponentplayerscanbeasourceofthegradualism. 1．Introduction Contributiongameshavebeenstudiedinvariousaspectsintheliterature.AdmatiandPerryll9911have investigatedgamesinwhichcontributionsfbrajointprojectaresunk・Theyshowthatthereexistsa subgame-perfectequilibriuminwhichcontributionsaremadeinsmallstepsalongtheequilibriumpath. Suchgradualaccumulationofcontributionsisreferredtoasgm伽α"sm.Theirresultofgradualismis obtainedundertheassumptionsthatacostfUnctionfbrtheprojectisarbitrarilyconvexandvaluations oftheprojectarethesamebetweentwoplayers.Theyhavesuggestedthatthesunkcharacterof contributionsisasourceofthegradualism.RevisitingAdmatiandPerry'scontributiongames:CompteandJehiel[20031havepointedout thattheirresultofgradualismdependsontheconvexityofthecostfUnctionandthesymmetryof thevaluations.CompteandJehielhaveintroducedalinearcostfUnctionandasymmetricvaluations intoAdmatiandPerry'scontributiongames、andshowthatthereexistsauniquesubgame-perfect equilibrium,inwhichatmosttwolargecontributionsarerealized.So)thegradualismobservedin AdmatiandPerry[1991]hasdisappearedduetothelinearcostfUnctionandtheasymmetricvaluations. IntheproofofCompteandJehiel'sresult,theyheavilyusetheassumptionundercompleteinfOrmation environments:Eachplayerknowshisopponent'svaluationoftheproject. Seekingaftersourcesofgradualism,Samejima[20131hasintroduceduncertaintiesaboutvaluations intoCompteandJehiel'smodel.'InSamejima'smodel,thereisachancefOreachplayertobeeither ahighvaluationtypeoralowvaluationtype.EachplayerisinfOrmedofhisownvaluationbutnot ofhisopponent'svaluation:Hejustknowsthepriorprobabilityofhisopponentbeingahigh-type. Samejimashowsthat,ifthispriorprobabilityisbelowacertain叩perbowzdfbrbothplayers,andif playersaresufficientlypatient,thenthereexistsaperfectBayesianequilibriuminwhichstep-by-step contributionsarerealizedalongtheequilibriumpath. Inthepresentpaper,weimproveontheresultbySamejima[20131:Weremovetheupperbound conditiononthepriorprobabilities.Weregardthisconditionasalimitationtosomeextentbecause theupperboundbecomeslowerasthedifferencebetweenthevaluationsheldbyahigh-typeanda low-typebecomeslarger. Toillustratethelimitationimposedbytheupperboundcondition)webrieHydiscussthemodel. Supposethattwoagentsland2wanttocompleteajointprojectthatrequiresatotalamountKof contributions.Oncompletionoftheproject,eachagentobtainsabenefit,whichiseitherahighvalue HoralowvalueL.EachagentiknowsthepriorprobabilityFjofhisopponentjbeingahigh-type. TheconditionK<2Lisassumedsothatcompletingtheprojectisefficientevenifbothagentsarelow-types.Samejimal20131showsthatthereisanequilibriuminwhichtwoagentscontributealternately insmallstepsuntiltheprojectiscompletedifR<2L/(H+L)fbrj=1,2,wheretherighthandside oftheinequalityistheupperbound・Fbrexample,givenK=99,H=150,andL=50,theupper boundisl/2,whichisinfactalimitation, However,thepresentpaperhassucceededinremovingtheupperboundcondition.Accordingto 'MiyagawaandSamejima[20091havealsointroduceduncertaintiesaboutvaluationsintoCompteandJehiel's model・Intheirmodel,oneplayerhasachancetobeeitheraノzigﾉlvaluationtypeorazerovaluationtype, andtheotherplayerhasachancetobeeitheralouﾉvaluationtypeorazerovaluationtype.So,theirwayof introducinguncertaintiesdiffersfromthatofSamejima{20131.
ourresult,evenifP,=0.9999anda=0.0001,thatis,evenifagentlisalmostahigh-typeand agent2isalmostalow-typebuttherestillremainverysmalluncertainties、andifagentsaresufficiently patient)thenthereexistsaperfectBayesianequilibriuminwhichstep-by-stepcontributionsarerealized. Furthermore、fOranycontributionsequence,wecanfindanequilibriumthatrealizesthecontribution sequenceuptothestepjustbefOrethelaststepfOrcompletingtheproject. Sinceanycontributionsequencecanberealizedalongsomeequilibriumpathinourmodel,thereis achancethatalmostequalcost-sharingisachieved.ThisisabigdifferencefromtheresultbyCompte andJehiell20031:Iftherearenouncertaintiesaboutvaluationsheldbytheopponentplayers,then unfaircost-sharingisrealizedinmostcases.Fbrtheabovenumericalexample,ifagentlisahigh-typeandagent2isalow-typewithnouncertainties,thenagentlbearsallthecostsKandagent2 contributesnothingintheuniquesubgame-perfectequilibrium.Thiscost-sharingisunfair. Theremainingpartofthispaperisorganizedasfbllows・Section2explainsamodeloftwo-player contributiongamesunderincompleteinfbrmation・Section3provesthatthereexistsaperfectBayesian equilibriuminwhichgradualismisobserved.Section4providessomeconcludingremarks. 2．TheModel Weinvestigatetwo-playervoluntarycontributiongamessimilartotheonesstudiedbyCompteand Jehiell20031. Twoagents,agentsland2、aretheplayersofthegame.Theycontributealternatelytocomplete aproject,whichcostsK>0.Uponanimmediatecompletionoftheproject,agentiobtainsabene6t VI,whichiscalledagentj'sUα加α虎onoftheproject.Atthebeginningofthegame,thenaturedecides whethereachagenti'svaluationisahighvalueHoralowvalueL,thatis,VIE{H,L}where H>L>0.So,agenti'svaluationVIalsorepresentshistl/pe:AgentiwithVI=Hisa/zd9ﾉz-tweand agentiwithVI=Lisalouﾉ-tWe.LetRE(0,1)denotethepriorpro6(MM"thatVi=Hisdrawnby thenature.WeassumethatP,andeareindependent.Furthermore,weassumethatP,andaare commonknowledgewhiletherealizedvalueofVIisknownonlytoagenti. Thegameisplayedinperiodst=1,2,.…whereagentlmovesinperiodswithoddnumberswhile agent2movesinperiodswithevennumbersuntiltheprojectiscompleted.Letm(t)denotetheyno"er inperiodt,thatis,m(t)=1iftisapositiveoddnumberwhilem'(t)=2iftisapositiveevennumber. Letc:ど0denotetheamountofco71伽加"onbyagentjinperiodt.Sincetwoagentstaketurnsin makingcontributions,c#=0ifi≠、(t)：Thisconstrainton(Cf，c;)togetherwithc9＝c:＝Ofbr notationalconvenienceiscalledtheたas伽j伽fOr(ci,c;).Attheendofperiodt,(ci,c;)isobserved
bybothagents.Let t
"'=K-E(cI+c5)
T==O bethe7℃、α伽伽9qmountnecessaryfbrcompletionoftheprojectattheendofperiodt.Notethat "0=Kand((I,0,"',"2､...)isanon-increasingsequence.WhentheremainingamountreachesO,the projectiscompletedandthegameends.LetTdenotetheperiodq/compJetionoftheproject,thatis, Tistheleastnaturalnumberthatsatisfiesthecondition"T=0.Iftheprojectisnotcompletedfbrever duetoaninsufficientamountofcontributions,thenweletT=○○．Weassumethatcontributionsare non-refUndableeveniftheprojectisnotcompleted.So,contributionsbecomesunkcostsfbragents. Letﾉzt=(a'0,"',…〃t')denoteallistorl/atthebeginningofperiodt.Wedenote/lt+'by(/lt,:lyt). Agenti'sbehaviorstmte卯sfisafUnctionthatspecifiesaprobabilitydistributionovercontribution amountsfOreachtypeofiandfbreachhistory:si(c#￨Vi,")istheprobabilityofchoosingc#givenI/iand /zt=(a'0,"',…,"t')with"t'>0.2Bythefeasibilityfbr(ci,c;),werequirethatsi(01I/I,Izt)=1if j≠m(t). Onreachingahistoryﾉ,t=("o,"',...,"t-')with"t-'>0,agentjholdsa6e"afpi("),which representstheprobabilitythatagentiassignstotheeventwherehisopponentisahigh-typegiven/zt. Wecallpiagenti'sbe"afん71ctio".Giventhecommonprior(P,,B),weassumethatp,(/D')=Band p2(ﾉ'')=P,. Bothagentsdiscountbenefitsandcontributionsusingadiscof〃んctor6E(0,1).Whenagenti's typeisVI,hispayofffbracontributionsequencec={(ci:c;)}Loisgivenby ＴＺ卸 Ui(vI,c)=6T-'I/I- 6t-'cCf' WeassumethatagentsmaximizeexpectedpayoffS.Letui(slVI,/zt,pi)bethee"ecte(I肌yQ"ofagenti withtypeI/Iunderastrategypro61es=(s,,s2)onconditionthathereachesahistory"withabelief pi("). WelookfbrperfectBayesianequilibriaofthegame.WefbllowFudenbergandTirolell991a,1991b] fOrthedefinitionoftheequilibria.Inthepresentmodel,ape7jbctBql/esmne""6rMn(s,p)isapair ofastrategypro61es=(s,,s2)andabelieffUnctionprofilep=(pl,p2)thatsatisfiesthefbllowingtwo conditions. SequentmJRα伽､α伽.Fbrall",j=m(t),j≠j,I/I,ands{,wehaveui(sII/I,",pi)≧ui((s{,sj)￨vI,",pi) 2Fbrthedefinitionsofstrategiesandbelieffunctions,werequirethat"t-'>0becauseotherwise,thegame musthaveendedbefbreperiodt.ReqsonqMitl/.Bayes,ruleisusedtoupdatebeliefSwheneverpossible:Fbralli,j≠j:"=("0,…,〃t-'); and(ci,c;)satisfyingthefeasibility,ifpi(ﾉ,t)sj(c;￨"")>0or(1-pi("))sj(c;￨L,")>0,then pi(")sj(c;￨H,") pi((/'t,"t))= pi(ht)sj(c;￨H")+(1-pi(ht))sj(c;￨L,") where"t="t-'-(ci+c;)>0 Wenotethatthereasonabilityconditiondoesnotimposeanyconstraintonagenti'sbeliefpi((","t))
ifsj(c;IH,")=sj(c;￨L")=0.ThatisjfitisagentjthatmovesatlltandifjchoosesCithat
shouldhavezeroprobabilityfbrbothtypesofjaccordingtosj,thenagenti'sbeliefatllt+'=(",5ct) canbecompletelyarbitrary. 3.TheResult LetRE(0,1)begivenfOrj=1,2.WeassumethatK<2L)whichmeansthatevenifboth agentsarelow-types｡totalbenefitsexceedthecost.Chooseanycontributionsequence{(61,63)}I=0s
a
t
i
s
f
y
i
n
g
t
h
e
f
e
a
s
i
b
i
l
i
t
y
a
n
d
t
h
e
f
b
l
l
o
w
i
n
g
c
o
n
d
i
t
i
o
n
s
:
5
#
>
0
i
f
j
=
m
(
t
)
,
E
I
=
｣
で
；
<
L
f
b
r
a
l
l
i
)
a
n
d
ZI=0(61+63)=KDefineahistory"+]=(mo,"1,…､毎t)correspondingto{(61,63)}I=o.Since
Ei+6;>0fOrt=1,2,…,t､wehaveK=Zo>"1>…>"t-'>"t=0.Furthermore,de伽eah
i
s
t
o
r
y
"
=
(
m
0
,
"
1
,
…
"
毎
f'
)
c
o
r
r
e
s
p
o
n
d
i
n
g
t
o
{
(
6
1
,
6
3
)
}
q
N
o
t
e
t
h
a
t
t
h
e
p
r
o
j
e
c
t
i
s
n
o
t
c
o
m
p
l
e
t
e
d
onreachingthehistory".Wewanttoshowthatthereexistsanequilibriuminwhichthehistory Fitisrealizedalongtheequilibriumpath.Thatis,wewanttoshowthatthereexistsanequilibriumt
h
a
t
r
e
a
l
i
z
e
s
t
h
e
c
o
n
t
r
i
b
u
t
i
o
n
s
e
q
u
e
n
c
e
{
(
司
､
亀
)
}
『
三
;
､
w
h
i
c
h
m
a
y
e
x
h
i
b
i
t
g
r
a
d
u
a
l
i
s
m
s
i
n
c
e
t
h
e
c
h
o
i
c
e
o
f
{
(
6
1
,
6
3
)
}
I
=
0
i
s
a
r
b
i
t
r
a
r
y
t
o
a
c
e
r
t
a
i
n
e
x
t
e
n
t
.
Theorem."6E(0,1)@ssu"cie庇"Z/J(z7yeofﾉ1entﾉ'eree"sts(Mper/bctBql/esmne9M肋γ畑m(s:p) mf"伽c向tﾉ'el'istorl/Jitis7尼α"ze(i(MIon,9tlleeqM肋γ伽､加仇 Toprovethetheorem,wefirstchoose5E(0,1)satisfyingthefbllowingconditionsfbralliandI/;１１１１
１２３４
● １ 一ｔ ■ｊ ● ◆ ● ＱＪ ２ ７ １ 一一 ７ −ｔ ｔ ９“ ７〃恥Ⅱ
ａ ｊ ● 一Ｊ ｒ ？２伽
１ １ １ ｉ、 ｜’ｔ ｊ ２ ｔ ｜勿 一６ １１ｍＨ
１允一帥
＋ＬＨ〃
柄副一
１聰一価Ⅲ
２１１３
’６一Ｊ−６
くンンン
Ｋ王の手ｑ手ｑ
＋韮ｔ
｜羊ｑｌｒ｜〃 ，逗言ｔＺ言１ｊ
ＨＨ
１ｊ
’６一ｊ ｌ ｌｌｌ
晩聰
ｉ、ｆ、 １ １＋＋
ｔ ｔ −ｔ −ｔ ｌ６−６Lemmal."5E(0,1)is剛版cientll/I(We,t/Ben58(zt"esα〃胡eco""jonS(1)-(4)fbralliand I/I Pγ℃QfTherighthandside(RHS,hencefOrth)oftheinequality(1)convergestoI/I+Las6converges tol.SinceK<2L=I/i+L,thecondition(1)holdsfbrlarge6. Asfbrtheinequality(2),RHSconvergestoOas5convergestol.Since;+53>0bythechoice
o
f
{
(
E
i
,
6
5
)
}
I
=
0
,
t
h
e
c
o
n
d
i
t
i
o
n
(
2
)
h
o
l
d
s
f
b
r
l
a
r
g
e
5
.
Asfbrtheinequality(3),weconsiderthelefthandside(LHS,hencefbrth)subtractedbyRHS.As 5convergestol,(LHS-RHS)convergesto t 一ｔ(vI-E
T＝二tア
で
『
，
ご)-(I/I-L)=L-丁＝二tw
h
i
c
h
i
s
p
o
s
i
t
i
v
e
s
i
n
c
e
E
I
=
,
6
#
<
L
b
y
t
h
e
c
h
o
i
c
e
o
f
{
(
E
i
:
6
;
)
}
I
=
o
S
o
,
b
h
e
c
o
n
d
i
t
i
o
n
(
3
)
h
o
l
d
s
f
O
r
l
a
r
g
e
5
Asfbrtheinequality(4),wenotethatas6convergestol,(LHS-RHS)convergestothefOllowing 一ｔ Ｔ・Ｚ −Ｃ Ｚ言一ｔ ｊｊ Ｔ２ −Ｃ ＋ 丁句ｌ −Ｃ Ｅ﹃ １ ｔ Ｋ Ｉ t t=(K-Z(司+53))+Eご=EEy
γ==0 丁 = = t γ = = t=3
6
7
− t − 1 z γ==tSincewemayassumet=f-1fOrtheinequality(4),wehaveZ="
So,thecondition(4)holdsfbrlarge6. >0bythechoiceof{(でi,E;)}I=0. □ Wenextdefineastrategyprofiles=(s,,s2)andabelieffUnctionprofilep=(p,,p2).Recallthat si(c:￨VI,/zt)representstheprobabilityofchoosingc#ど0givenI/IE{H,L}and/zt=("0,"'､…､"t-') with"t'>0.Wealsorecallthatpi(")representstheprobabilitythatagentiassignstotheevent wherehisopponentisahigh-typegiven/lt. TodescribethestrategiesandthebelieffUnctions,letusdefineatieU伽o『んnctjor,d(")asfOllows. Givenahistory"=("0,al',…,"t 1)with"t-'>0if〃アー元γfbrall'r=0,1,…,t-1､thenlet d(")=0;Otherwise,letd(/zt)=m(f)wherefistheleastTthatsatisfies"T≠盃ｱ.Ifd(/lt)=0,then wesaythat/ztison-"thandthereisnodeviator;Otherwise,wesaythat/ltisq""t/zandagentd(") isthedeU伽07､.IfiztisoffLpathandi≠d(/lt),thenwecallagentithepums向er.Wenotethatif"is offLpath，itmustbethecasethatt>2becauseﾉz'isalwayson-pathduetothefactthat"0=Z0=K. Strategysifbrj=1,2.thatsi(OIVI,/mt)=13bythefeasibilityfOr(ci,c;).Wheni､n(t),thefbllowingdescriptionsde6ne si(･￨vI,ht). Theon,-pα仇cqse.Ifd(llt)=0,thenwedefinesi(.￨VI,/,t)asfOllows.4 Ift=5-1,thenletsi(c:￨VI,")=1fOrc:=61.
I
f
t
=
f
a
n
d
I
/
I
=
H
,
t
h
e
n
l
e
t
s
i
(
c
#
￨
V
I
,
"
)
=
1
f
b
r
c
:
=
E
!
.
5
I
f
t
=
f
a
n
d
V
I
=
L
,
t
h
e
n
l
e
t
s
i
(
c
W
I
I
/
I
,
/
z
t
)
=
1
f
b
r
c
#
=
ざ
−
(
1
-
6
ー 6)
H
.
T/ledeU伽Or9SC(ZSe・Ifi=d(/zt),thenwedefinesi(.￨VI,/nt)asfbllows. IfVI=Hand"t-'=53L+(1-53)",thenletsf(cWIVI,")=1fbrc#="t-'. IfVI=Hand"t-'>33L+(1-53)H,thenletsi(c#￨VI,")=1fbrc#=0. IfVI=Land"t-'≦(1-5)L,thenletsi(cIIVI,llt)=1fOrcf="t'. IfVI=Land(1-5)L<"t '≦(1-5)H,thenletsi(cflI/I,")=1fOrc#=0. IfVI=Land(1-5)H<"t'=5L+(1-5)H;thenletsi(cflVI,llt)=1fbrc#=:rt'-(1-5)H. IfVI=Land"t'>5L+(1-5)H,thenletsi(cflVI,/zt)=1fbrc!=0. Tﾉle伽畑sﾉler'sc(zse.If"isoffpathandi≠d(")thenwedefinesi(･￨VI,/lt)asfbllows. If"t-1≦(1-5)H,thenletsi(cilVI,/zt)=1fbrc:=zt'. If(1-5)H<"t '=5L+(1-5)H,thenletsi(c#￨I/I,")=1fOrc#=0. If"t '>5L+(1-5)H,thenletsi(c#￨VI,")=1fOrc#="t '-3L-(1-5)H. BelieffUnctionpifbri=1,2. Letl,t=("0,"',…,"t一')with"t '>0begiven.Fbrt=1{letPl(ll')=BandP2(ﾉ'')=P,. Fbrt>2，wedefinepi(/mt)asfbllows.Whenj=m(t-1)｣etpi(")=pi(" ').Whenj=m(t),the fOllowingdescriptionsdefinepi("). T7zeon-p(Itﾉlcase.Ifd(/lt)=0,thenletpi(llt)=Pjwherej≠j. TﾉledeU伽07､'SC(ISe・Ifi=d(ﾉlt),thenletpi(")=Pjwherej≠i. me肌冗紬er'sc(zse.If/ztisoffLpathandj≠d(")､thendefinepi(")asfOllows. If"t-1≦(1-5)H,thenletpi(/,t)=0. If(1−5)H<"t-'≦5L+(1-5)H,thenletpi(/,t)=1. Ifalt '>3L+(1-5)H,thenletpi(")=0. 3Thisexpressionimplicitlystatesthatsi(c#￨VI,/lt)=0fbrc#>0. 4ThefOllowingthreecasesareexhaustivebecauseift>f,thenitmustbethecasethatd(/ut)≠0． 5NotethatEF="'-'bythedefinitionsofff-'and{(EI,5;)};=" 6WenotethatE『−(1-6)H>6f−(1-52)H>0duetothecondition(2)inLemmaltogetherwiththe factthat弓=0inthiscase.Wenowprovethat(s,p)satis6essequentialrationalityintheseriesoflemmas.TakeanyiE{1,2}, vIE{H,z,}､tE{1,2,…}}andl,t=(a,0,"',…:"t1)with"t'>0,andfixthemfbrthearguments inLemmas2throughl3.Let{(cT,c5)}E;bethecontributionsequencecorrespondingto/lt.When weconsideracontributionsequencefbrperiodtandbeyond,{(cI$c5)}L&,wedenotethecombined sequencebyc={(c1,c3)}LofOrnotationalconvenience.Weassumethatcsatisfiesthefeasibility, andwenotethat,byitsconstruction,cisconsistentwith". Letgibeagenti'soptimalstrategyonconditionthat(sj,I/I,",pi)isgiven: giEargm3xui((s;,sj)II/I,",Pf) sI Z Wewanttoshowthatui(slVI,/lt,pi)どui((gi,sj)II/M,",pi)inexhaustivecases,whichimpliesthat ui(sIvI,l't,pi)どui((sI,sj)￨VI,",pi)fbralls{. Lemma2.WJlen"entimof)es9"entmQBL"tﾉﾙ/zistorl/,t加加s,f"/zen/ztisqL皿tﾉ,α""=m(t), α〃dがzt−1≦(1-5)vi,tﾉ'enui(slVI,/'t,pi)≧ui((5i,sj)￨I/I,〃仙). Pγ℃qfWhenagentifOllowssi,hechoosesc#="t'withprobabilityoneinperiodjregardlessof histypeandwhetherheisthedeviatororthepunisher,andthegameendswithhispayoff t − 1 γ・２ ︽し １ 丁 ’６ 逗司 ui(slvI,",p,)=5t-1(vI−zt-') -Letc={(c1,c5)}Lobesuchthatpositiveprobabilityisassignedtocbytheprobabilitydistri -butiongeneratedbypi(")and(5i:sj)given/lt.Weshowthatagenti,spayofffbrcdoesnotexceed ui(sII/I,",pi)inexhaustivecases,whichimpliesthatui(sII/1,llt,pi)Zui((5i,sj)￨I/I,l't,pi). Ifc#どぉｵｰ1,thenthegameendsinperiodtaccordingtoc,andwehave t − 1 t − 1
=a
r
-
%
『
≦
5
t
-
'
(
聰
−
鰯
'
-
'
)
-
E
ァ:＝0 丁=二0 Ui(VI,c)=5t-'(I/I-c:)- 5ｱｰ'c『＝ui(sMﾉ't,pi), wheretheweakinequalityholdssincec#≧鰯t’G Ifc#<frt',thenthegamecontinueswithalt="t'-ciaccordingtoc.Inthiscase,themost preferredscenariofOragentjisthatagentjcontributesalltheremainingamount"tandcompletes theprojectinperiod(t+1).Evenifthisscenarioappliestoc, t − 1 t − 1ﾗ
ｰ
ｺ
5
ｱ
-
1
C
r
≦
5
&
-
'
(
V
I
-
錘
t
-
'
)
−
ア
テーニ0 丁=二0 UI(VI,c)=5t-'(5VI-c#)- jT-’ccW！=＝uuii((sslIII//1I,,ﾉ0t,pi),wheretheweakinequalityholdssincecf≧0and"t-'さ(1-5)vI □ Lelnnma3.W/Denq9entimOfJes(zStﾉletie”α加γ,t加伽s,uj/ze"=m(t)=d(/zt)≠j,(m(J"VI=H (mn(I(1-5)H<"t-'=5L+(1-5)H,t/'er'ui(sIvI",pi)どui((5i,sj)IvI,",pi). ProqfWhenhigh-typedeviatorifOllowssi,hechoosesci="t'withprobabilityoneinperiodt andthegameendswithhispayoff Ｔ・Ｚ 〆︶ １ − Ｔ −６ Ｅ﹃ １ ｔ ui(sIH,ILt,pi)=5t-'(H−〃＃−1)− Letc={(cI､c5)}Lobesuchthatpositiveprobabilityisassignedtocbytheprobabilitydistribution generatedbypi(llt)=Fjand(5i,sj)given".Weshowthatdeviatori'spayofffbrcdoesnotexceed ui(sIH,",Pi)inexhaustivecases,whichimpliesthatui(slH,",pi)≧ui((5i,sj)￨H,",pi).
I
f
t
h
e
p
r
o
j
e
c
t
i
s
n
o
t
c
o
m
p
l
e
t
e
d
a
c
c
o
r
d
i
n
g
t
o
c
,
t
h
a
t
i
s
,
i
f
E
L
o
(
c
r
+
c
I
)
<
K
,
t
h
e
n
w
e
h
a
v
e
γ・Ｚ Ｃ １ 丁 ’６ 樫Ｅ劃 １ノ ー ｔ 鰯 Ｈ ｊ ｌ６ １ ｉ ＋ Ｌ −６ ｉｌ １ ｔ −６ く一、八 ．茜″﹂ ｐ Ｔ・？Ｃ９
勺１ａｔ ムルァｑノ
Ｈ −６包亟司心
４ １ ０ く一テ・Ｚ Ｃ Ｔ・Ｚ君ｌ Ｃ Ｔ １ −６ 画Ｚ司包Ｅ﹃ Ｔ −６ ｊ ｌ Ｔ・ＺＣｔ
鰯 １ Ｔ Ｈ ｌ６ＴＥ言靴
ｔ −６ Ui(H,c)= ＜ wherethesecondweakinequalityholdssince"t-】g5L+(1-5)H.So,intheremainingpartofthe proofofthelemma,weconsiderthecaseswheretheprojectiscompletedaccordingtoc. Wenextshowthatc:≧zt-】 -(1-6)H・If砥丁>(1-6)HfbranyTZt,thenwehavez
ｱ
〈
鰯
t
-
'
=
5
L
+
(
1
-
5
)
H
,
a
n
d
p
u
n
i
s
h
e
r
j
c
h
o
o
s
e
s
c
;
+
｣
=
0
i
n
p
e
r
i
o
d
(
T
+
1
)
a
s
d
e
s
c
r
i
b
e
d
i
n
t
h
e
punisher,scaseofthestrategybecauseotherwise,zeroprobabilityisassignedtoc.Sincetheprojectis completedaccordingtocwhilepunisherjnevercontributesaslongastheremainingamountexceeds (1-5)H:itmustbethecasethatdeviatordpaysatleastthedifferencebetween"t'and(1-5)H, possiblyinonetimeorinseveraltimes.Ifdeviatorishouldpayanamountnecessaryfbrreaching someremainingamountfnomorethan(1-6)H,itisoptimalfOrhimtodosoinonetime,because punisherj'sstrategydoesnotdependonthepathfrom"t'tofbutontheremainingamountfitself, andbecausedelayingcompletionoftheprojectlowersthediscountedbenefit.TherefOre,wemusthave cf≧鰯t-'-(1-5)H. Ifc:之諺t−',thenthegameendsinperiodtaccordingtoc,andwehave t − 1 t − 1叉
"戸一一、尻
5
T
-
'
c
r
=
u
i
(
s
I
H
,
/
u
t
,
p
i
)
,
一 一 、 3T-'c『≦5t-'(H−Z‘−1)−UI(H,c)=5t-'(H-cf)-wheretheweakinequalityholdssincecf≧zt−’● If"t-1>c澄砥t一'-(1-5)H,thegamecontinueswithalt=frt'-c#≦(1-6)Haccordingtoc.
T
h
e
n
,
p
u
n
i
s
h
e
r
j
c
h
o
o
s
e
s
c
;
+
'
=
"
!
i
n
p
e
r
i
o
d
(
t
+
1
)
a
s
d
e
s
c
r
i
b
e
d
i
n
t
h
e
p
u
n
i
s
h
e
r
'
s
c
a
s
e
o
f
t
h
e
s
t
r
a
t
e
g
y
becauseotherwise,zeroprobabilityisassignedtoc.So$thegameendsinperiod(t+1),andwehave t − 1 t−1U
I
(
H
,
c
)
=
5
t
-
'
(
5
H
-
c
！
)
−
尻
5
ｱ
ｰ
'
c
『
≦
5
t
-
'
(
H
-
"
t
-
'
)
-
ZW
-
'
c
r
=
"
,
(
s
l
H
〃
､
p
i
)
,
丁==0 丁==o wheretheweakinequalityholdssincecりど鰯t-'-(1-5)H. □ LelnIna4.Whe""en"moT)es(zst/le(ietmtor,t加加s'uﾉﾉﾙeM=m(t)=d(")≠',a"ifI/i=H qy,(I5L+(1_5)H<:rt_1=53L+(1_53)H,t/zenui(slVI,〃､pi)之ui((gi:sj)￨vI,/'t,pi). ProqfWhenhigh-typedeviatorifbllowssi,hechoosesc:=qlt'withprobabilityoneinperiodt andthegameendswithhispayoff t − 1ア5T-'c7
ui(sIH,/'t,pi)=5t-'(H−〃t-') -γ ＝ 0 Letc={(cI,c5)}Lobesuchthatpositiveprobabilityisassignedtocbytheprobabilitydistribution generatedbypi(llt)=Pjand(gi,sj)givenht.Weshowthatdeviatori'spayofffbrcdoesnotexceed ui(sIH〃〃i)inexhaustivecases,whichimpliesthatui(sl",/zt,pi)どILi((5i,sj)￨H,",pi).I
f
t
h
e
p
r
o
j
e
c
t
i
s
n
o
t
c
o
m
p
l
e
t
e
d
a
c
c
o
r
d
i
n
g
t
o
c
,
t
h
a
t
i
s
,
i
f
E
L
o
(
c
I
+
c
5
)
<
K
,
t
h
e
n
w
e
h
a
v
e
T t − 1 t−1=W
-
'
c
『
-
=W
-
'
c
『
≦
0
−
E
r
5
-
r
:
-
c
'
;
c
<
7
<
;
5
'
#
-
-
:
'
(
(
H
H
-
_
"
"
t
'
-
-
'
)
,
-
)
E
_
E
5
=
T
-
'
c
7
=
"
i
(
s
l
H
､
"
,
p
i
)
Ui(H,c)= 丁 = = t T = 二 0 丁二＝0 丁三＝0 wherethestrictinequalityholdssince"t-'=53L+(1_53)H<H・So,intheremainingpartofthe proofofthelemma,weconsiderthecaseswheretheprojectiscompletedaccordingtoc.I
f
c
#
<
"
t'
-
5
L
-
(
1
-
5
)
H
,
t
h
e
g
a
m
e
c
o
n
t
i
n
u
e
s
w
i
t
h
"
t
=
f
r
t'
-
c
I
>
5
L
+
(
1
-
5
)
H
a
c
c
o
r
d
i
n
g
t
o
c
.
T
h
e
n
,
p
u
n
i
s
h
e
r
j
i
n
p
e
r
i
o
d
(
t
+
1
)
c
h
o
o
s
e
s
c
;
+
'
=
"
t
-
5
L
-
(
1
-
5
)
H
a
s
d
e
s
c
r
i
b
e
d
i
n
t
h
e
p
u
n
i
s
h
e
r
'
s
c
a
s
e
ofthestrategybecauseotherwise、zeroprobabilityisassignedtoc.Accordingtoc,thegamefUrtherc
o
n
t
i
n
u
e
s
w
i
t
h
"
t
+
'
=
5
L
+
(
1
-
5
)
H
.
F
b
r
t
h
e
c
o
n
t
i
n
u
a
t
i
o
n
g
a
m
e
f
i
f
o
m
p
e
r
i
o
d
(
t
+
2
)
,
i
t
i
s
o
p
t
i
m
a
l
f
b
r
high-typedeviatoritofOllowsibyLemma3・So,wehave Ｔ・２ Ｃ １ Ｔ ｌ６ Ｅ卸 １ ＋ ｔUI(H,c)≦ui(slH,(が,"t,"t+'):pi)=5t+'(H−Zt+')-t − 1 t − 1
=
5
t
+
'
(
H
-
5
L
-
(
1
-
5
)
H
)
-
c
f
+
'
-
c
リ
ー
ア
5
ｱ
ｰ
1
C
r
≦
5
‘
−
1
(
5
3
H
-
5
3
L
)
−
E
3
ｱ
ｰ
'
c
『
丁 ＝ 0 丁 ＝ 0 t − 1=
5
I
-
'
(
H
-
"
t
-
'
)
-
E
5
r
-
'
c
r
=
u
i
(
s
l
H
"
｡
p
i
)
、
丁==0 wheretheweakinequalityonthesecondlineholdssincec#≧0andc;+]＝0、andtheweakinequality onthethirdlineholdssince"t-]=53L+(1_53)H. IfcI≧alt-'-5L-(1-5)H:thenthesameargumentsasintheproofofLemma3canshowthat c#≧〃t1-(1-5)H.Furthermore,byrepeatingtheargumentsintheproofofLemma3fbrthecases c:ど"t-'and"t-1>c:≧妙t-'-(1-5)H,weobtainUM(Hc)≦ui(sIH,〃↑pi).D LenIIna5．W7zenage""moUes(zstﾉzede""tor.t加加s‘1"ﾉDer'j=m(t)=d(")≠j,(MM"I/I=H (md"t-1>53L+(1_53)H,tl,er,ui(sIVI,ﾉ't,pi)≧ui((息恥sj)￨vI,",pi). ProqfWhenhigh-typedeviatorifbllowssihechoosesc#=0withprobabilityoneinperiodtandthegamecontinueswith"t=zI,t-'>53L+(1-53)H>3L+(1-5)H.Whenpunisherjfbllowssj
g
i
v
e
n
/
n
t
+
'
=
(
"
Ⅲ
"
t
)
､
h
e
c
h
o
o
s
e
s
c
;
+
'
=
{
r
!
-
5
L
-
(
1
-
5
)
H
w
i
t
h
p
r
o
b
a
b
i
l
i
t
y
o
n
e
i
n
p
e
r
i
o
d
(
t
+
1
)
a
s
describedinthepunisher'scaseofthestrategy.ThegamefUrthercontinueswithayt+'=5L+(1-5)H, andhigh-typedeviatori,fbllowings!givenilt+2=(llt:"':"t+'),choosesci+2="t+'withprobability oneinperiod(t+2)andthegameends.So,wehave Ｔ・Ｚ ︽し １ 丁 ’６ 村Ｅ﹃ 一 ｊ Ｌ ３ −６ ｜ 〃 ３ −６ ｉＩ １ ｔ ｌ６ ｌ− Ｔ？Ｉ Ｃ １ γ ’６ 樫Ｅ﹃ γ・２ＣｉＪ
１ ｊ Ｈ 丁 伺ｎ劃｜刊 １、﹄＋
１ ＋ Ｌ鰯〆ｗ
ｔ ２ ２ −６ｌ６ＨＨ
２ ２ −６−６ Ｊ１１ｉｌ １ １ ｌ ｔ ｔ −６−６ 一一 一一 ｊ ●、〃し Ｐ ９ ｔ ＪＪ ﹃← ７ Ｈ Ｓ ・ｆ ｕ Letc={(cr,c5)}Lobesuchthatpositiveprobabilityisassignedtocbytheprobabilitydistribution generatedbypi(")=Band(5i:sj)given/lt.Weshowthatdeviatori'spayofffbrcdoesnotexceed ui(sIH,ﾉlt,pi)inexhaustivecases,whichimpliesthatui(slH,/lt:pi)≧ui((gi,sj)￨H,",pi).I
f
t
h
e
p
r
o
j
e
c
t
i
s
n
o
t
c
o
m
p
l
e
t
e
d
a
c
c
o
r
d
i
n
g
t
o
c
,
t
h
a
t
i
s
,
i
f
E
L
｡
(
c
I
+
c
5
)
<
K
,
t
h
e
n
w
e
h
a
v
e
T t − 1 t − 1 t − 1U
m
(
H
c
)
＝
−
E
3
『
-
'
c
『
_
E
3
ｱ
ｰ
l
c
r
≦
O
−
Z
5
ｱ
ｰ
'
c
7
<
5
t
-
'
(
5
3
H
-
5
3
L
)
-
E
5
ｱ
-
'
c
r
=
u
i
(
s
l
H
,
h
t
,
p
i
)
ア ー 二 t 丁 = = 0 T = 二 0 丁 = 二 0 So,intheremainingpartoftheproofofthelemma,weconsiderthecaseswheretheprojectiscompleted accordingtoc. Ifc#<"t '-5L-(1-5)H,thenthesameargumentsasintheproofofLemma4canshowthat"t+'=5L+(1-5)Hand γ・Ｚ Ｃ １ 丁 で、﹀丁・Ｚ
銅Ｅ司北，
ｊ’｜がｚ
ｐ ７洲制Ｅ司珊
ｔ ’０℃・ＺＱ︶ＣｆＩ
Ｈ．Ｚ
ｕｉｌ１
１＋＋
ｔｑＴ８ ｃ ｔ −６ｌ−卜包
刷一Ｍ樫画司
１ ＋ １ ｔ〃Ｑ
ｌ３
７ ｔ〃アム一ＣＯ
７−ｃハＵ ｔ ｈ Ｈ く，Ｈ尿
Ｈ／Ｉ／Ｉ
／Ｉ＋１
ｓ１
雌孑ぶ
く一 一一 く一 ｊ Ｃ ， Ｈ ｕ wheretheweakinequalityonthethirdlineholdssincec#≧0andc!+'=0. IfcIZ"t '-5L-(1-5)H,thenthesameargumentsasintheproofofLemma3canshowthat ci三〃t'-(1-5)H.Furthermore,byrepeatingtheargumentsintheproofofLemma3fOrthecases c!ど鰯t-1and"t-1>c；Z鰯t-'-(1-5)H,weobtain t − 1 t − 1U
i
(
H
,
c
)
≦
5
t
-
'
(
H
-
"
t
-
'
)
−
尻
5
7
-
'
c
r
<
5
t
-
'
(
5
3
H
_
5
3
L
)
_
7W
-
'
c
cr
‘c7=ui(slH:/'*,pi), 丁=二0 丁=二O wherethestrictinequalityholdssince"t-'>33L+(1_53)H. □ Lennrna6．W月e冗a9en,timoT)es(zstﾉﾙe(I剛ator,t加州s,QUIDeM=m(t)=(I(")≠j,(md"I/I=L aM(1-5)L<"t-'≦(1-6)H,tﾉ'enui(slI/I,/'t,pi)三ui((gi,sj)￨1/I,",pi). ProqfWhenlow-typedeviatorifOllowssi,hechoosesc:=0withprobabilityoneinperiodtand thegamecontinueswith"t="t-'≦(1-5)HWhenpunisherjfOllowssjgivenﾉzt+'=(","t),h
e
c
h
o
o
s
e
s
c
;
+
'
=
"
t
w
i
t
h
p
r
o
b
a
b
i
l
i
t
y
o
n
e
i
n
p
e
r
i
o
d
(
f
+
1
)
a
s
d
e
s
c
r
i
b
e
d
i
n
t
h
e
p
u
n
i
s
h
e
r
'
s
c
a
s
e
o
f
t
h
e
strategy,andthegameends.So, t − 1屍
5
ｱ
ｰ
'
c
『
丁==0 ui(slL;ﾉ'f,pi)=5tL -Letc={(cI,c5)}Lobesuchthatpositiveprobabilityisassignedtocbytheprobabilitydistribution generatedbypi(llt)=Band(5i,sj)givenllt.Weshowthatdeviatori'spayofffOrcdoesnotexceed ui(slL,",pi)inexhaustivecases､whichimpliesthatui(slL,",Pi)どui((5i,sj)IL,/'t,pi). Ifc#ど〃t-',thenthegameendsinperiodtaccordingtoc,andwehave t − 1 t − lE
5
T
-
'
c
r
<
5
t
L
-
E
5
T
-
'
c
7
=
"
,
(
s
l
L
冴
仙
)
、
T : ＝ 0 γ = = 0 Ui(L,c)=5t-'(L-c#)-wherethestrictinequalityholdssince(1-5)L<"t'≦c:Ifcf<"t',thegamecontinueswith"t="t'-c#≦(1-5)Haccordingtoc.Then,punisherjin
p
e
r
i
o
d
(
t
+
1
)
c
h
o
o
s
e
s
c
;
+
'
=
"
!
a
s
d
e
s
c
r
i
b
e
d
i
n
t
h
e
p
u
n
i
s
h
e
r
､
s
c
a
s
e
o
f
t
h
e
s
t
r
a
t
e
g
y
b
e
c
a
u
s
e
o
t
h
e
r
w
i
s
e
,
zeroprobabilityisassignedtoc.So,accordingtoc]thegameendsinperiod(t+1):andwehave t − 1 t − 1U
i
(
L
､
c
)
=
5
t
-
'
(
5
L
-
c
#
)
-
E
s
"
-
L
r
≦
5
'
L
-
=W
-
'
c
7
=
"
i
(
s
l
L
,
'
'
t
,
p
i
)
、
アニー0 ﾃﾆｰo wheretheweakinequalityholdssincec#Z0. □ Lernrna7.WFze7z(z9e71,"mofJes(Ist/zedeUmtor,t加伽s｡MewM=m(t)=(I(")≠j,anddfVI=L αγ'd(1-5)H<"t-'≦5L+(1-5)",ther'ui(sII/I,/'t,pi)≧ui((5i,sj)￨I/I,";pi). Pγ℃QfWhenlow-typedeviatorifbllowss#,hechoosescリ="t'-(1-5)Hwithprobabilityonein periodtandthegamecontinueswithalt=(1-5)".Whenpunisherjfbllowssjgivenllt+'=(/lt,"t),h
e
c
h
o
o
s
e
s
c
;
+
'
=
"
t
w
i
t
h
p
r
o
b
a
b
i
l
i
t
y
o
n
e
i
n
p
e
r
i
o
d
(
t
+
1
)
a
s
d
e
s
c
r
i
b
e
d
i
n
t
h
e
p
u
n
i
s
h
e
r
'
s
c
a
s
e
o
f
t
h
e
strategy,andthegameends.So, t − 1 t − 1E
5
r
-
'
c
r
=
5
t
-
1
(
5
L
+
(
'
-
5
)
H
-
"
t
-
1
)
-
E
r
-
'
c
r
丁==0 丁=二0 ui(sIL,ﾉ't,pi)=5t-'(5L-("t-'-(1-5)H)) -Letc={(cI,c5)}Lobesuchthatpositiveprobabilityisassignedtocbytheprobabilitydistribution generatedbypi(ﾉlt)=Fjand(5i,sj)givenllt.Weshowthatdeviatori'spayofffbrcdoesnotexceed ui(slL;",pi)inexhaustivecases,whichimpliesthatui(sIL,",pi)どui((gi:sj)￨L",pi).I
f
t
h
e
p
r
o
j
e
c
t
i
s
n
o
t
c
o
m
p
l
e
t
e
d
a
c
c
o
r
d
i
n
g
t
o
c
,
t
h
a
t
i
s
,
i
f
Z
L
｡
(
c
I
+
c
5
)
<
K
t
h
e
n
w
e
h
a
v
e
ｊ ｐ ｔ 向 Ｌ Ｓ ●句〃し ル ー 一一 丁・Ｉ Ｃ １ 丁◇Ｉ Ｃ Ｔ １ −６回逗温欧司
０ く一恥ｊ 丁・Ｚトレ Ｃ 〃 １ 丁 −６画Ｅ﹃肥
１ 丁・２／Ｉ、 Ｃ １ ＋ Ｔ Ｌ ｌ６ｌ６ＴＥ言判
ｔ 一Ｊ UI(L,c)= ＜ wheretheweakinequalityonthesecondlineholdssince"t-Ⅱ=5L+(1-5)H.So:intheremaining partoftheproofofthelemma,weconsiderthecaseswheretheprojectiscompletedaccordingtoc. Wenextshowthatcfど鰯t ］ -(1-6)H.If"T>(1-6)HforanyT≧t,thenwehavez
γ
<
"
t'
<
5
Z
,
+
(
1
-
5
)
H
,
a
n
d
p
u
n
i
s
h
e
r
j
c
h
o
o
s
e
s
c
;
punisher'scaseofthestrategybecauseotherwise､zeroprobabilityisassignedtoc.Sincetheprojectis completedaccordingtocwhilepunisherjnevercontributesaslongastheremainingamountexceeds (1-5)H,itmustbethecasethatdeviatordpaysatleastthedifferencebetween"t'and(1-5)H,possiblyinonetimeorinseveraltimes.Ifdeviatorishouldpayanamountnecessaryfbrreaching someremainingamountfnomorethan(1-6)H,itisoptimalfOrhimtodosoinonetime,because punisherj'sstrategydoesnotdependonthepathfrom"t'tofbutontheremainingamountfitself, andbecausedelayingcompletionoftheprojectlowersthediscountedbene6t.Therefbre,wemusthave cfど:rt-'-(1-5)H. Ifc:三〃t-',thenthegameendsinperiodtaccordingtoc,andwehave Ｑ︲Ｊ ｊ Ｔ・Ｚ ●ん″Ｌ Ｃ ｐ ｌ ７ ｔ 向 丁
画面剴椰
ｑＦＩ らの口四 ｕｊ｜’
１ 丁・Ｚ ｔ ｃ〃１
’Ｔ
Ｌ’６
打倒画司
ｔ ｌ６ く一戦ｊ γ・Ｚ一Ｃｔ
〃 １ 丁 包画司一Ｍ１１
“ｒ・Ｚ／Ｉ、Ｃ＋
Ｌ｜凡
１ １ ｔ ｔ −６’６’一く
ｊ Ｃ ｑｒＪ Ｌ ｉ 叺 wheretheweakinequalityholdssincec#≧〃&'andthestrictinequalityholdssinceL<5L+(1-5)H. If"t-1>cf≧〃t'-(1-5)H,thegamecontinueswith"t="t'-c：≦(1-5)Haccordingtoc.T
h
e
n
､
p
u
n
i
s
h
e
r
j
c
h
o
o
s
e
s
c
;
+
'
=
"
i
n
p
e
r
i
o
d
(
t
+
1
)
a
s
d
e
s
c
r
i
b
e
d
i
n
t
h
e
p
u
n
i
s
h
e
r
,
s
c
a
s
e
o
f
t
h
e
s
t
r
a
t
e
g
y
becauSeotherwise､zeroprobabilityisassignedtoc.So:thegameendsinperiod(t+1),andwehave=
r
-
"
"
;
:
-
'
(
5
L
+
(
,
-
M
-
"
#
-
:
,
-
=
E ‘
Ⅲ
U
i
(
I
,
,
c
)
=
5
t
-
'
(
5
L
-
c
W
)
-
=W
-
'
c
『
≦
5
t
-
'
(
5
L
+
(
'
-
5
)
H
-
"
t
-
'
)
-
E
"
-
Ⅲ
c
7
c,＝t"(slL,〃仙),=
u
i
(
s
I
L
,
テニー0 丁二＝O wheretheweakinequalityholdssincec#≧鰯t’ -(1-6)H. □ Lenlrna8・WILenagen伽刀lof)esqst/ledeU伽o7､,t加伽s,IUIMeM=m(t)=d(/'t)≠､7,αM〃I/I=L α伽"t-'>5L+(1-5)H,tﾉ'e"ui(sII/I,",pi)どui((5i:sj)IvI:ht,pi). ProqfWhenlow-typedeviatorifOllowssihechoosesc#=0withprobabilityoneinperiodtand thegamecontinueswithalt="t'>5L+(1-5)H.Whenpunisherjfbllowssjgiven"+'=(","t),h
e
c
h
o
o
s
e
s
c
;
+
]
=
鰯
‘
−
6
L
-
(
1
-
6
)
H
w
i
t
h
p
r
o
b
a
b
i
l
i
t
y
o
n
e
i
n
p
e
r
i
o
d
(
t
+
1
)
a
s
d
e
s
c
r
i
b
e
d
i
n
t
h
e
punisher'scaseofthestrategy.ThegamefUrthercontinueswith"t+'=5Z,+(1-5)H,andlow-type deviatori,fOllowings#given/,t+2=(がりzt,"t+'),choosesc;+2="t+｣-(1-6)Hwithprobability oneinperiod(t+2),andthegamecontinueswith"t+2=(1-5)H.WhenpunisherjfOllowssjgiven"
+
3
=
(
"
,
"
t
,
"
t
+
'
,
z
t
+
2
)
,
h
e
c
h
o
o
s
e
s
c
;
+
3
=
"
t
+
2
w
i
t
h
p
r
o
b
a
b
i
l
i
t
y
o
n
e
i
n
p
e
r
i
o
d
(
t
+
3
)
a
s
d
e
s
c
r
i
b
e
d
inthepunisher'scaseofthestrategy,andthegameends.So,wehave t − 1屍5T-'cr
ui(slL,月t,pi)=5t-'(53L-52("t+'-(1-5)H))-γ ＝ 0Gradualisminvoluntarycontributiongamesduetoverysmalluncertainties t − 1 t − 1
尻
5
ｱ
-
'
c
r
=
0
-
Za
r
-
'
c
r
T＝二0 丁二二0 =5t-1(53L_53L)_ Letc={(cI,c5)}Lobesuchthatpositiveprobabilityisassignedtocbytheprobabilitydistribution generatedbypi(ht)=Band(島､sj)given/zt.Weshowthatdeviatori'spayofffbrcdoesnotexceedu
i
(
s
I
L
,
が
.
p
i
)
i
n
e
x
h
a
u
s
t
i
v
e
c
a
s
e
s
,
w
h
i
c
h
i
m
p
l
i
e
s
t
h
a
t
u
i
(
s
l
Z
,
〃
,
p
i
)
≧
u
i
(
(
g
i
,
s
j
)
I
L
,
"
,
p
i
)
.
I
f
t
h
e
p
r
o
j
e
c
t
i
s
n
o
t
c
o
m
p
l
e
t
e
d
a
c
c
o
r
d
i
n
g
t
o
c
｡
t
h
a
t
i
s
,
i
f
E
L
o
(
c
I
+
c
5
)
<
K
,
t
h
e
n
w
e
h
a
v
e
T t − 1 t − 1U
i
(
L
,
c
)
=
-
g
3
5
T
-
'
@
『
−
7
3
5
T
-
'
c
『
≦
0
-
W
T
-
'
c
｢
=
"
,
(
s
I
M
t
"
i
)
T=二t T二二0 γ==0 So,intheremainingpartoftheproofofthelemma､weconsiderthecaseswheretheprojectiscompleted accordingtoc. Ifc#<"t-'-5L-(1-5)H,thegamecontinueswithzt=grt'-c;>5L+(1-5)Haccordingtoc.T
h
e
n
,
p
u
n
i
s
h
e
r
j
i
n
p
e
r
i
o
d
(
t
+
1
)
c
h
o
o
s
e
s
c
;
+
'
=
"
&
-
5
L
-
(
1
-
5
)
H
a
s
d
e
s
c
r
i
b
e
d
i
n
t
h
e
p
u
n
i
s
h
e
r
'
s
c
a
s
e
ofthestrategybecauseotherwise、zeroprobabilityisassignedtoc.Accordingtoc,thegamefurther continueswith"t+'=5L+(1-5)H.Fbrthecontinuationgamefromperiod(t+2),itisoptimalfbr low-typedeviatoritofOllowsibyLemma7・So,wehave γ・Ｚ ︽し １ 丁 ’６ 蝿Ｅ鄙 １ノ ー ＋ ｔ 〃 ｊ ゆめ″四Ｈｐ
、−ノｔ−６ん
Ｌ １Ｌ Ｓ ｉｌｉ、 ●勺″シ＋ｕ
Ｌ ｌ− −６ ／１１Ｔ・Ｚ １ Ｃ＋１
｜に、﹀壬ｔ昨画面﹃
ｉ ｌ Ｏ ＋〃く一
ｔ り丁・ｆ ｔ Ｃｚ１
，︲一 ｔ、６Ｔ
″、−６仏蜘Ｚ﹃
Ｓ ●の〃しｕｎＵ
く一一一 ｊ Ｃ Ｌ ｕ wheretheweakinequalityonthesecondlineholdssincec:≧0andc!+'=0. Ifc#ど錘t '-5L-(1-5)H,thenthesameargumentsasintheproofofLemma7canshowthat c#≧おt'-(1-5)H.Furthermore,byrepeatingtheargumentsintheproofofLemma7fOrthecases c＃≧鯵t-'and"t-'>c#ど"t-'-(1-5)",weobtain t − 1 t − 1U
i
(
z
,
,
6
)
≦
5
t
-
'
(
5
L
+
(
1
-
5
)
H
−
鰯
t
-
'
)
_
E
5
T
-
'
c
r
<
0
-
E
5
T
-
'
c
r
=
"
i
(
s
l
L
,
〃
伽
)
,
γ==0 丁二二0 wherethestrictinequalityholdssince:rt'>5L+(1-5)H. □ Lennmma9.Wﾉze凡a9entimoT)es(Ist/zepumsller,t加州souﾉﾉ'end=m(t)≠(I(")=j,q'zd"vI=L (md(1-5)L<a't-'≦(1-5)H,が↓enui(sIvI,",pi)≧ui((gi:sj)IvI,",pi). P7℃Qflnthiscase,pi(/1t)=0,sopunisheribelievesthatdeviatorjisalow-type.Whenpunisherifbllowssi,hechoosesc!="t｣withprobabilityoneinperiodtandthegameendswithhispayoff t - 1
u
i
(
s
I
L
,
〃
､
p
i
)
=
5
t
-
'
(
L
−
鰯
t
-
'
)
-
E
r
-
'
c
Cf･｢
丁=二0 Letc={(cI,c5)}Lobesuchthatpositiveprobabilityisassignedtocbytheprobabilitydistribution generatedbypi(")=0and(5,,sj)given".Weshowthatpunisheri'spayofffbrcdoesnotexceed ui(slL,",pi)inexhaustivecases,whichimpliesthatui(sIL,/lt,pi)≧ui((5i,sj)￨L,〃仙).I
f
t
h
e
p
r
o
j
e
c
t
i
s
n
o
t
c
o
m
p
l
e
t
e
d
a
c
c
o
r
d
i
n
g
t
o
c
､
t
h
a
t
i
s
,
i
f
E
L
o
(
c
I
+
c
5
)
<
K
,
t
h
e
n
w
e
h
a
v
e
γ・２ Ｃ −Ｆｎｕ 劃工司 Ｈ −６ Ｌ ｌ６泳艸
一〃
丁７
’６Ｌ
門Ｅ司個
一ｕ
ハＵ｜｜ く一ＴＱ Ｔ・Ｚ１１Ｃ一
旬１Ｔ
ｌ−６
割欧弘甚司
γ一‘可Ｃｔ
ｌ勿
汚一
一６Ｌ
ＴＥ目却
一子
Ui(L,c)= ＜ wherethestrictinequalityonthefirstlineholdssinceL>6i+E;>(1-52)H>(1-5)Hbythec
h
o
i
c
e
o
f
{
(
i
,
&
)
}
F
=
o
a
n
d
b
y
t
h
e
c
o
n
d
i
t
i
o
n
(
2
)
i
n
L
e
m
m
a
l
,
a
n
d
t
h
e
w
e
a
k
i
n
e
q
u
a
l
i
t
y
o
n
t
h
e
s
e
c
o
n
d
lineholdssince"t-'≦(1-6)H.So､intheremainingpartoftheproofofthelemma,weconsiderthe caseswheretheprojectiscompletedaccordingtoc. Wenextshowthatc#Z麺t ’ -(1-6)L.Ifzア>(1-6)Lfbranyγ≧t,thenwehave"
ア
＜
z
t
−
Ⅱ
≦
(
1
-
5
)
H
,
a
n
d
l
o
w
-
t
y
p
e
d
e
v
i
a
t
o
r
j
i
n
p
e
r
i
o
d
(
T
+
1
)
c
h
o
o
s
e
s
c
;
γr+'=0asdescribedin thedeviator'scaseofthestrategybecauseotherwise,zeroprobabilityisassignedtoc.Sincethe projectiscompletedaccordingtocwhilelow-typedeviatorjnevercontributesaslongastheremain-ingamountexceeds(1-6)L,itmustbethecasethatpunisheripaysatleastthedifferencebetween cct'and(1-5)L,possiblyinonetimeorinseveraltimes.Ifpunisherishouldpayanamountnec-essaryfbrreachingsomeremainingamountfnomorethan(1-5)L,itisoptimalfOrhimtodosoin onetime,becauselow-typedeviatorj'sstrategydoesnotdependonthepathfrom"t'tofbuton theremainingamountfitself,andbecausedelayingcompletionoftheprojectlowersthediscounted bene6t.TherefOre､wemusthavec:ど鰯t-'-(1-5)L. Ifc#≧"t-',thenthegameendsinperiodjaccordingtoc,andwehave t − 1 t − 1=W-'c『≦5t-1(L-"t-')-尻
5
T
-
'
c
r
=
u
i
(
s
l
L
,
"
,
p
i
)
,
γニー0 丁二=0 Ui(L:c)=5t-'(L-ci)-wheretheweakinequalityholdssincec!≧露t-1.T
h
e
n
,
l
o
w
-
t
y
p
e
d
e
v
i
a
t
o
r
j
i
n
p
e
r
i
o
d
(
t
+
1
)
c
h
o
o
s
e
s
c
;
+
'
=
"
,
a
s
d
e
s
c
r
i
b
e
d
i
n
t
h
e
d
e
v
i
a
t
o
r
'
s
c
a
s
e
o
f
t
h
e
strategybecauseotherwise,zeroprobabilityisassignedtoc.So,thegameendsinperiod(t+1),and wehave t − 1 t − 1U
i
(
L
,
c
)
=
5
t
-
1
(
5
L
-
c
#
)
−
両
5
T
-
'
c
『
≦
5
t
-
1
(
L
−
zt
-
'
)
-
E
3
γ
-
‘
c
7
c,＝ui(slL〃,”，=
u
i
(
s
I
L
,
"
,
p
i
)
,
γ=二0 丁=二o wheretheweakinequalityholdssincec#≧〃tⅡv -(1-5)L. □ LenmlnalO.W7ze7z(zgentimoT)esastﾉlepumsﾉler,t加州S7uﾉﾉzewM=m(t)≠d(")=j,αγ'dif (1-5)H<"t-'三5L+(1-5)H,t/'enui(slI/I,l't:pi)≧ui((gi,sj)￨I/I,",pi). Pγ℃Qflnthiscase,pi(")=1,sopunisheribelievesthatdeviatorjisahigh-type.Whenpunisheri fOllowssi,hechoosesc;=0withprobabilityoneinperiodtandthegamecontinueswithfrt="t'= 5L+(1_5)H<53L+(1_53)H.Whenhigh_typedeviatorjfOllowssjgivenilt+'=(ﾉlt,alt),hechoosesc
;
+
｣
=
"
w
i
t
h
p
r
o
b
a
b
i
l
i
b
y
o
n
e
i
n
p
e
r
i
o
d
(
t
+
1
)
a
s
d
e
s
c
r
i
b
e
d
i
n
t
h
e
d
e
v
i
a
t
o
r
'
s
c
a
s
e
o
f
t
h
e
s
t
r
a
t
e
g
y
,
a
n
d
thegameends.So, t − 1u
i
(
s
l
v
I
〃
､
p
i
)
=
伽
一
元
5
ｱ
-
1
C
『
γ=二O Letc={(cI,ca)}Lobesuchthatpositiveprobabilityisassignedtocbytheprobabilitydistribution generatedbypi(")=land(5,,sj)given/lt.Weshowthatpunisheri'spayofffbrcdoesnotexceed ui(sII/I,",pi)inexhaustivecases,whichimpliesthatui(slVI,llt,pi)どui((5j,sj)￨I/I,",pi). Ifc；≧zt-',thenthegameendsinperiodtaccordingtoc,andwehave Ui(I/;,c)=5t-1(I/I-cI) -t − 1 t − 1ﾗ
ｰ
ｺ
6
ｱ
-
'
c
r
<
5
t
V
I
-
ア
5
T
-
'
c
r
=
u
i
(
s
I
v
I
,
/
'
t
,
p
i
)
アニー0 丁二=0 wherethestrictinequalityholdssince(1-5)VI<"t'三c:. Ifc;<"t',thegamecontinueswith"t="t'-c#≦5L+(1_5)"<53L+(1_53)Haccordingt
o
c
T
h
e
n
:
h
i
g
h
-
t
y
p
e
d
e
v
i
a
t
o
r
j
i
n
p
e
r
i
o
d
(
t
+
1
)
c
h
o
o
s
e
s
c
;
+
'
=
"
&
a
s
d
e
s
c
r
i
b
e
d
i
n
t
h
e
d
e
v
i
a
t
o
r
'
s
c
a
s
e
ofthestrategybecauseotherwise,zeroprobabilityisassignedtoc.So,accordingtoc,thegameends inperiod(t+1)]andwehave t − l t − 1U
i
(
v
I
､
c
)
=
5
f
-
'
(
5
V
I
-
c
f
)
-
F
W
-
'
c
7
≦
5
t
V
I
-
夛W
-
'
c
cr
,c7=ui(sIvI:/'t;pi), T ＝ 0 丁 ＝ O wheretheweakinequalityholdssincecf≧0. □Lexnrnall．W/ze”a9en,"moUesastﾉzepums向eγ､t加州s,uj/zeni=m(t)≠d(ht)=j,αM〃 "t-'>5L+(1-5)H,t/'enui(sIvI,〃仙)≧ui((5i,sj)￨vI,/zt,pi). Proqflnthiscase,pi(ht)=0,sopunisheribelievesthatdeviatorjisalow-type.Whenpunisherj fOllowssi,hechoosescf="t'-5L-(1-5)Hwithprobabilityoneinperiodtandthegamecontinues with"t=5L+(1-5)H.Whenlow-typedeviatorjfbllowssjgiven"+'=(","t),hechooses ;+｣="t-(1-5)Hwithprobabilityoneinperiod(t+1)asdescribedinthedeviator,scaseof cj thestrategy.ThegamefUrthercontinueswithalt+'=(1-5)H,andpunisheri,fbllowingsigiven /lt+2=(IIt,"t]zt+'),choosesc:+2="t+'withprobabilityoneinperiod(t+2)andthegameends. So,wehave Ｔ・Ｚ Ｃ １ 丁 −６
伺逗司惣
一Ｔ
ｊ−６
川“Ｚ﹃
ｌ６ ｊ制１１ｉＩｌ
ｔ ｚ Ｌ−６Ｈ
１ノ ー ’６ｔ．｜
〃イー
ｉ’別ノ
１ｌ６
Ｈｊ１
’６ ＋向いＬ
−６帆肝
２ ２ ’６−６ｉ、ｉ、 １ １ ｔ ｔ −６’６ ｊ ｐ ｔ １ Ｊゞ 晩 Ｓ ・Ｚ ｕ Letc={(cI,c5)}Lobesuchthatpositiveprobabilityisassignedtocbytheprobabilitydistribution generatedbypi(")=0and(gi,sj)given".Weshowthatpunisheri'spayoHfbrcdoesnotexceed ui(slI/;,が仏)inexhaustivecases,whichimpliesthatui(slI/;,",pi)どui((5i,sj)￨vI,l't,pi).I
f
t
h
e
p
r
o
j
e
c
t
i
s
n
o
t
c
o
m
p
l
e
t
e
d
a
c
c
o
r
d
i
n
g
t
o
c
,
t
h
a
t
i
s
,
i
f
逗
是
o
(
c
I
+
c
5
)
<
K
,
t
h
e
n
w
e
h
a
v
e
１ ．２ Ｐ ｔ 向 ７ 恥 Ｓ ●、〃し ｕ 一一 丁・２ ︽し Ｔ・２ １Ｃｌ
１ Ｔ −６卸欧弘笹﹃
γ・Ｚ Ｃ−勺
１１’
一Ｆ０Ｋｔ勿
丁卸Ｅ﹃腓Ｈ
’｜の一の
０く一１１
丁・２、ⅡＩノ、Ｉノｃ２
２ １ −６ｌ６ Ｔｌ６１１
画Ｚ司刊州
ＬＬ
−６−６ 丁・ＺＣ＋＋
１聰晩
Ｔ’６デヂ
ｒＺ言丸１
１−子子
Ui(I/I,c)= ＜ ＜ wherethestrictinequalityonthesecondlineisduetothecondition(1)inLemmal､andtheweak inequalityonthethirdlineholdssince"t-'gK・So,intheremainingpartoftheproofofthelemma, weconsiderthecaseswheretheprojectiscompletedaccordingtoc. Wenextshowthatc:Z"t '-5L-(1-5)H.If鉱丁>6L+(1-6)HfOranyTどt,thenlow-typed
e
v
i
a
t
o
r
j
c
h
o
o
s
e
s
c
y
+
'
=
0
i
n
p
e
r
i
o
d
(
T
+
1
)
a
s
d
e
s
c
r
i
b
e
d
i
n
t
h
e
d
e
v
i
a
t
o
r
'
s
c
a
s
e
o
f
t
h
e
s
t
r
a
t
e
g
y
b
e
c
a
u
s
e
otherwise,zeroprobabilityisassignedtoc.Sincetheprojectiscompletedaccordingtocwhilelow-type deviatorjnevercontributesaslongastheremainingamountexceeds(6L+(1-6)H);itmustbethe casethatpunisheripaysatleastthedifferencebetweenfrt'and(5L+(1-5)H),possiblyinonetimeorinseveraltimes.IfpunisherjshouldpayanamountnecessaryfOrreachingsomeremaining
amountinomorethan(5L+(1-5)H)､itisoptimalfOrhimtodosoinonetime,becauselow-type deviatorj'sstrategydoesnotdependonthepathfrom"t'tofbutontheremainingamountfitself、
andbecausedelayingcompletionoftheprojectlowersthediscountedbenefit.TherefOre,wemusthave
c#≧鰯t-'一庇−(1-6)H.
If"t-'-(1-5)H>c:≧〃t '-5L-(1-5)H,thegamecontinueswith:rt=zt '-cisuchthat (1-5)H<"tg5L+(1-5)Haccordingtoc.Givenht+'=(","t),low-typedeviatorjinperiod(t+1)
