The full text on this page is automatically extracted from the file linked above and may contain errors and inconsistencies.
Working Paper Series
Computing Moral-Hazard Problems
Using the Dantzig-Wolfe Decomposition
Algorithm
WP 98-06
This paper can be downloaded without charge from:
http://www.richmondfed.org/publications/
Edward S. Prescott
Federal Reserve Bank of Richmond
&RPSXWLQJ 0 RUDO+D]DUG 3UREOHPV 8VLQJ WKH ' DQW]LJ:ROIH
' HFRPSRVLWLRQ $OJRULWKP
( G ZD U G 6 3 U H V F R W W
e
5HVHDUFK 'HSDUWPHQW
)HGHUDO 5HVHUYH %DQN RI 5LFKPRQG
: R U NLQ J 3 D S H U
-X Q H
$EVWUDFW
/LQHDU SURJUDPPLQJ LV DQ LPSRUWDQW PHWKRG IRU FRPSXWLQJ VROXWLRQV WR SULYDWH LQIRUPD
WLRQ SUREOHPV
7KH PHWKRG LV DSSOLFDEOH IRU DUELWUDU\ VSHFLpFDWLRQV RI WKH SUHIHUHQFHV DQG
WHFKQRORJ\ 8QIRUWXQDWHO\ DV WKH FDUGLQDOLW\ RI XQGHUO\LQJ VHWV LQFUHDVHV WKH SURJUDPV TXLFNO\
EHFRPH WRR ODUJH WR FRPSXWH
7KLV SDSHU GHPRQVWUDWHV WKDW PRUDOKD]DUG SUREOHPV KDYH D
VWUXFWXUH WKDW DOORZV WKHP WR EH FRPSXWHG XVLQJ WKH 'DQW]LJ:ROIH GHFRPSRVLWLRQ DOJRULWKP
7KLV DOJRULWKP EUHDNV WKH OLQHDU SURJUDP LQWR VXESUREOHPV JUHDWO\ LQFUHDVLQJ WKH VL]H RI SURE
OHPV WKDW PD\ EH SUDFWLFDOO\ FRPSXWHG &RQQHFWLRQV WR G\QDPLF SURJUDPPLQJ DUH GLVFXVVHG
7ZR H[DPSOHV DUH FRPSXWHG 5ROH RI ORWWHULHV LV GLVFXVVHG
, QWU RGXFWLRQ
7KLV SDSHU FRPSXWHV VWDWLF PRUDOKD]DUG SUREOHPV XVLQJ WKH 'DQW]LJ:ROIH GHFRPSRVLWLRQ DO
JRULWKP
7KH PHWKRG LV DSSOLFDEOH WR VLQJOH DJHQW SUREOHPV DQG VRPH PXOWLSOH DJHQW SUREOHPV
ZKHUH D VRXUFH RI SULYDWH LQIRUPDWLRQ LV DQ DJHQW V DFWLRQ 7KH WHFKQLTXH LV GHPRQVWUDWHG LQ WKH
FODVVLF SULQFLSDODJHQW PRUDOKD]DUG SUREOHP DQG YDULDQWV RI LW
, XVH WKH UHYHODWLRQ SULQFLSOH IUDPHZRUN GHYHORSHG LQ 0\HUVRQ
7RZQVHQG
DQG 3UHVFRWW DQG
,Q WKLV IUDPHZRUN ORWWHULHV DUH LQFOXGHG LQ WKH FRQWUDFW VSDFH
$V D FRQVH
TXHQFH WKH FKRLFH YDULDEOH LQ WKH FRQVWUDLQHG PD[LPL]DWLRQ SURJUDP LV D SUREDELOLW\ GLVWULEXWLRQ
RYHU WKH XQGHUO\LQJ VHWV RI WKH UHOHYDQW YDULDEOHV UDWKHU WKDQ GHWHUPLQLVWLF IXQFWLRQV :KHQ WKH
FDUGLQDOLW\ RI HDFK XQGHUO\LQJ VHW LV pQLWH WKH SURJUDP LV D OLQHDU SURJUDP
7KHUH DUH WZR FRPSXWDWLRQDO DGYDQWDJHV WR WKH OLQHDU SURJUDPPLQJ IRUPXODWLRQ
)LUVW WKH
WKHRU\ RQ FRPSXWLQJ OLQHDU SURJUDPV LV ZHOO GHYHORSHG DQG WKHUH DUH QXPHURXV OLQHDU SURJUDPPLQJ
e7
WKH
KH
D XWKR U Z
D XWKR U D QG GR
R XOG OLN H
WR
WKD QN
QR W QH F H VVD ULO\
-H o /D F N H U IR U KH OSIXO F R PPH QWV 7
UH qH F W WKH
Y LH Z
V R I WKH
)
6\ VWH P
H GH UD O 5H VH UY H
KH
Y LH Z
%D QN
V H [ SUH VVH G KH UH
D UH
R I 5LF KPR QG R U WKH
VR OH O\
)
WKR VH
R I
H GH UD O 5H VH UY H
FRGHV DYDLODEOH 6HFRQG SUREOHPV ZLWK DUELWUDU\ VSHFLpFDWLRQV RI SUHIHUHQFHV DQG WKH WHFKQRORJ\
FDQ EH FRPSXWHG
8QOLNH WKH DQDO\WLFDO OLWHUDWXUH WKHUH LV QR QHHG WR PDNH KLJKO\ UHVWULFWLYH
DVVXPSWLRQV RQ SUHIHUHQFHV DQG WHFKQRORJ\ 7KH GLVDGYDQWDJH WR XVLQJ OLQHDU SURJUDPV LV WKDW DV
WKH FDUGLQDOLW\ RI WKH XQGHUO\LQJ VHWV LQFUHDVH WKH OLQHDU SURJUDP TXLFNO\ JURZV LQ VL]H PDNLQJ
FRPSXWDWLRQ LQIHDVLEOH HLWKHU EHFDXVH RI PHPRU\ RU VRIWZDUH OLPLWDWLRQV
,Q WKLV SDSHU , GHPRQVWUDWH WKDW WKH PRUDOKD]DUG SUREOHP FDQ EH HoHFWLYHO\ FRPSXWHG
XVLQJ WKH 'DQW]LJ:ROIH GHFRPSRVLWLRQ DOJRULWKP 7KH PRUDOKD]DUG SUREOHPV FRQWDLQV EORFNV RI
FRQVWUDLQWV DQG YDULDEOHV RQH SHU DFWLRQ WKDW DUH RQO\ FRQQHFWHG E\ D IHZ FRQVWUDLQWV $ OLQHDU
DQG FDQ EH FRPSXWHG XVLQJ WKH 'DQW]LJ:ROIH
GHFRPSRVLWLRQ DOJRULWKP 8VLQJ WKLV DOJRULWKP , FRPSXWH D OLQHDU SURJUDP ZLWK YDULDEOHV
DQG FRQVWUDLQWV
7KH GHFRPSRVLWLRQ DOJRULWKP LV FORVHO\ UHODWHG WR G\QDPLF SURJUDPPLQJ (DFK EORFN RI FRQ
VWUDLQWV LV FRPSXWHG VHSDUDWHO\ OLNH WKH VHFRQGVWDJH RI D WZRVWDJH G\QDPLF SURJUDP 7KH UHVXOWV
RI WKHVH FRPSXWDWLRQV DUH VXPPDUL]HG E\ VWDWH YDULDEOHV WKDW DUH WKHQ XVHG LQ D PDVWHU SURJUDP
WKDW LQFOXGHV WKH FRQQHFWLQJ FRQVWUDLQWV 8QOLNH D G\QDPLF SURJUDP KRZHYHU WKH DOJRULWKP LW
HUDWHV EHWZHHQ WKH PDVWHU SURJUDP DQG WKH VXESUREOHPV 7KLV LWHUDWLYH SURFHVV DYRLGV WKH QHHG
WR FDOFXODWH WKH HQWLUH YDOXH IXQFWLRQ
SURJUDP ZLWK WKLV VWUXFWXUH LV FDOOHG
EORFN DQJXODU
(FRQRPLF UHDVRQV IRU ORWWHULHV
7KH OLWHUDWXUH GRHV QRW XVXDOO\ LQFRUSRUDWH ORWWHULHV LQWR SULYDWH LQIRUPDWLRQ SUREOHPV 2QH SRV
VLEOH UHDVRQ IRU WKHLU DEVHQFH LV WKH OLWHUDWXUH V HPSKDVLV RQ DQDO\WLFDO UHVXOWV ORWWHULHV FRPSOLFDWH
WKH DQDO\VLV $QRWKHU SRVVLEOH UHDVRQ LV WKDW WKH\ DUH QRW JHQHUDOO\ DQ H[SOLFLW IHDWXUH RI FRQWUDFWV
:KLOH H[SOLFLW UDQGRPL]DWLRQ LV QRW QHFHVVDULO\ IUHTXHQWO\ REVHUYHG LQ FRQWUDFWV QHLWKHU DUH
WKH FRPSOLFDWHG GHWHUPLQLVWLF FRQWUDFWV WKDW DULVH LQ PRGHOV ZLWKRXW ORWWHULHV ,I D FRQWUDFWXDO
GHYLFH LV SRWHQWLDOO\ XVHIXO LW VKRXOG EH LQFOXGHG LQ WKH FRQWUDFW VSDFH XQOHVV WKHUH LV DQ HFRQRPLF
UHDVRQ IRU H[FOXGLQJ LW )XUWKHUPRUH GHJHQHUDWH ORWWHULHV DUH D SURSHUW\ RI RSWLPDO FRQWUDFWV
IURP VRPH VSHFLpFDWLRQV RI SUHIHUHQFHV DQG WHFKQRORJ\ )RU WKHVH VSHFLpFDWLRQV DQ\ ORWWHULHV LQ
WKH RSWLPDO VROXWLRQ DUH D UHVXOW RI WKH GLVFUHWH JULG )RU D VXrFLHQWO\ pQH JULG WKH VROXWLRQ ZLOO
EH D YDOXDEOH DSSUR[LPDWLRQ RI WKH FRQWLQXXP FDVH
6RPH W\SHV RI ORWWHULHV KRZHYHU PD\ UHSUHVHQW HFRQRP\ZLGH HoHFWV UDWKHU WKDQ VSHFLpF
FRQWUDFWXDO GHYLFHV 7KHLU DEVHQFH IURP FRQWUDFWV LV OHVV RI DQ REMHFWLRQ )RU H[DPSOH FRQVLGHU
DQ HFRQRP\ ZLWK D FRQWLQXXP RI H[ DQWH LGHQWLFDO DJHQWV ZKR IDFH DQ HFRQRP\ZLGH UHVRXUFH
FRQVWUDLQW (DFK DJHQW V HoRUW LV SULYDWH LQIRUPDWLRQ 0DWKHPDWLFDOO\ WKLV SUREOHP LV LGHQWLFDO
WR D SULQFLSDODJHQW SUREOHP ZKHUH WKH SULQFLSDO LV ULVNQHXWUDO DQG KLV UHVHUYDWLRQ OHYHO RI XWLOLW\
LV ]HUR 7KH GLoHUHQFH LV LQ LQWHUSUHWDWLRQ /RWWHULHV LQ WKLV HFRQRP\ UHSUHVHQW HTXLOLEULXP
IUDFWLRQV RI WKH SRSXODWLRQ ,I LQ HTXLOLEULXP WKH VROXWLRQ WR WKH PRUDO KD]DUG SUREOHP LV D
ORWWHU\ RYHU DFWLRQV WKHQ WKH ORWWHU\ ZRXOG UHSUHVHQW D IUDFWLRQ RI WKH SRSXODWLRQ ZRUNLQJ HDFK
DFWLRQ 7KH LPSOHPHQWDWLRQ RI WKH DFWLRQ ORWWHULHV QHHG QRW EH E\ DQ H[SOLFLW FRQWUDFWXDO SURYLVLRQ
EXW FRXOG UHVXOW IURP DQ XQPRGHOHG PDUNHW IHDWXUH
0DFURHFRQRPLF SDSHUV E\ +DQVHQ DQG 5RJHUVRQ XVH ORWWHULHV LQ D PRGHO ZLWK D
FRQWLQXXP RI DJHQWV LQ RUGHU WR PRGHO WKH GLVFUHWH QDWXUH RI ZRUN 3UHVFRWW DQG 7RZQVHQG
DQG /HKQHUW LQWHUSUHW SULYDWHLQIRUPDWLRQ PRGHOV LQ VLPLODU IUDPHZRUNV /HKQHUW
pQGV WKDW LQ D 6RORZ JURZWK PRGHO ZLWK PRUDO KD]DUG OHDYLQJ RXW ORWWHULHV VXEVWDQWLDOO\ FKDQJHV
WKH JURZWK DQG GLVWULEXWLRQ HoHFWV LQ WKH HFRQRP\ $ pQDO SUDFWLFDO DGYDQWDJH RI ORWWHULHV LV WKDW
LPSRUWDQW VHWV DUH FRQYH[ DOORZLQJ IRU VRPH SULYDWH LQIRUPDWLRQ SUREOHPV WR EH GHFHQWUDOL]HG DV
FRPSHWLWLYH HTXLOLEULD 6HH IRU H[DPSOH 3UHVFRWW DQG 7RZQVHQG
:K\ FRPSXWH"
7KH OLWHUDWXUH KDV HPSKDVL]HG DQDO\WLFDO SURSHUWLHV RI SULYDWH LQIRUPDWLRQ PRGHOV DQG DV D FRQVH
TXHQFH LW KDV UHVWULFWHG LWVHOI WR QDUURZ DVVXPSWLRQV RQ WHFKQRORJ\ ,Q SDUWLFXODU WKH OLWHUDWXUH
XVXDOO\ DVVXPHV WKDW SUHIHUHQFHV DUH VHSDUDEOH LQ FRQVXPSWLRQ DQG HoRUW DQG WKDW WKH WHFKQRORJ\
VDWLVpHV WKH PRQRWRQH OLNHOLKRRG UDWLR SURSHUW\ DQG WKH FXPXODWLYH GLVWULEXWLRQ IXQFWLRQ FRQGL
WLRQ DVVXPSWLRQV VXrFLHQW WR XVH WKH pUVWRUGHU DSSURDFK 7KHVH DVVXPSWLRQV DUH YHU\ UHVWULFWLYH
DQG GR QRW QHFHVVDULO\ GHVFULEH GDWD )RU HFRQRPLHV ZLWKRXW WKHVH DVVXPSWLRQV FRPSXWLQJ FDQ
KHOS DVFHUWDLQ WKH TXDOLWDWLYH SURSHUWLHV RI FRQWUDFWV 3UHVFRWW DQG 7RZQVHQG FRQWDLQV
VHYHUDO VXFK H[DPSOHV
&RPSXWLQJ KRZHYHU LV SUREDEO\ PRVW LPSRUWDQW IRU XVLQJ SULYDWH LQIRUPDWLRQ PRGHOV WR
DQVZHU TXDQWLWDWLYH TXHVWLRQV %R\G DQG 6PLWK LV DQ H[FHOOHQW H[DPSOH RI WKLV 7KH\
H[DPLQHG WKH YDOXH RI VWRFKDVWLF YHUVXV GHWHUPLQLVWLF DXGLWLQJ LQ WKH FRQWH[W RI WKH FRVWO\ VWDWH
YHULpFDWLRQ PRGHO 7KLV PRGHO GDWHV EDFN WR 7RZQVHQG DQG KDV EHHQ H[WHQVLYHO\ XVHG LQ
WKH DXGLWLQJ FRUSRUDWH pQDQFH EDQNLQJ DQG PDFUR OLWHUDWXUHV ,W KDV UHFHLYHG D ORW RI DWWHQ
WLRQ EHFDXVH ZKHQ YHULpFDWLRQ LV UHVWULFWHG WR GHWHUPLQLVWLF VWUDWHJLHV GHEW FRQWUDFWV DUH RSWLPDO
7KLV DSSHDOLQJ SUHGLFWLRQ KDV OHG PDQ\ SDUWLFXODUO\ LQ PDFURHFRQRPLFV WR XVH WKLV PRGHO 8Q
, Z LOO SUH VH QW D Q H [ D PSOH Z LWK WKH VH
IH D WXUH V OD WH U LQ WKH
SD SH U
IRUWXQDWHO\ D ZHOONQRZQ DQDO\WLFDO UHVXOW LV WKDW VWRFKDVWLF YHULpFDWLRQ GRPLQDWHV GHWHUPLQLVWLF
YHULpFDWLRQ
7R DQVZHU WKH TXHVWLRQ RI KRZ PXFK EHWWHU VWRFKDVWLF YHULpFDWLRQ LV WKDQ GHWHUPLQLVWLF YHU
LpFDWLRQ %R\G DQG 6PLWK FDOLEUDWHG D FRVWO\ YHULpFDWLRQ PRGHO XVLQJ EDQNUXSWF\ GDWD
7KH\ FDOFXODWHG WKDW WKH JDLQV IURP VWRFKDVWLF YHULpFDWLRQ DUH RQO\ RQ WKH RUGHU RI
RI D pUP V YDOXH $VVXPLQJ WKDW WKH FRVW RI LPSOHPHQWLQJ VWRFKDVWLF DXGLWLQJ LV QRQWULYLDO DV
WKH\ GR WKHQ WKH FRPPRQO\ REVHUYHG GHEW FRQWUDFWV ZRXOG EH RSWLPDO 7KH TXHVWLRQ WKH\ DVNHG
ZDV D TXDQWLWDWLYH RQH DQG WKH\ QHHGHG WR FRPSXWH VROXWLRQV LQ RUGHU WR DQVZHU LW
7KH &RPSXWDWLRQDO ([SHULPHQW
, HYDOXDWH WKH DOJRULWKP E\ WKH VL]H RI WKH SURJUDPV DQG WKH WLPH QHHGHG WR FRPSXWH WKHP
7KHUH LV D TXHVWLRQ RI ZKHWKHU ORWWHULHV RYHU JULGV DUH D JRRG DSSUR[LPDWLRQ WR ORWWHULHV RYHU
FRQWLQXXP , GR QRW DGGUHVV WKLV LVVXH EHFDXVH WKH DQVZHU WR WKLV TXHVWLRQ GHSHQGV WKH HFRQRPLF
DSSOLFDWLRQ )XUWKHUPRUH GLVFUHWH JULGV DUH VRPHWLPHV WKH PRVW QDWXUDO HFRQRPLF VSHFLpFDWLRQ
7KH PHWKRGV GHYHORSHG LQ WKLV SDSHU KRZHYHU GR DOORZ SUREOHPV ZLWK pQHU JULGV WR EH FRPSXWHG
WKDQ SUHYLRXVO\ SRVVLEOH $V D FRQVHTXHQFH VRPH SUREOHPV WKDW RQFH ZHUH LQDGHTXDWHO\ DGGUHVVHG
GXH WR JULG OLPLWDWLRQV DUH QRZ PDQDJHDEOH
7KH SDSHU SURFHHGV E\ GHYHORSLQJ QRWDWLRQ IRU WKH PRUDO KD]DUG SUREOHP 7KLV QRWDWLRQ LV
XVHG WR ZULWH WKH PRUDO KD]DUG SUREOHP DV D OLQHDU SURJUDP 2IWHQ , ZLOO UHIHU WR WKLV SURJUDP
DV WKH JOREDO SUREOHP 1H[W WKH 'DQW]LJ:ROIH GHFRPSRVLWLRQ DOJRULWKP LV GHYHORSHG ,Q P\
GHVFULSWLRQ , HPSKDVL]H WKH FRQQHFWLRQV WR G\QDPLF SURJUDPPLQJ DQG GLVFXVV WKH UROH RI DFWLRQ
ORWWHULHV $IWHUZDUGV WZR H[DPSOHV WKDW GR QRW VDWLVI\ WKH XVXDO DVVXPSWLRQV PDGH LQ WKH OLWHU
DWXUH DUH FRPSXWHG 6ROXWLRQV DQG FRPSXWDWLRQDO UHVXOWV DUH UHSRUWHG )LQDOO\ H[WHQVLRQV RI WKH
WHFKQLTXH WR PRUH FRPSOLFDWHG PRGHOV DUH GLVFXVVHG
7 KH 0
RU DO+ D]DU G 3 U REOHP
7KHUH DUH VHYHUDO VWDJHV WR WKH PRUDO KD]DUG SUREOHP RQFH WKH SULQFLSDO DQG WKH DJHQW KDYH
DJUHHG WR D FRQWUDFW
7KH SULQFLSDO UHFRPPHQGV DQ DFWLRQ
7KH DJHQW WDNHV D KLGGHQ DFWLRQ
6H H
IR U H [ D PSOH
7 R Z QVH QG
D QG 0 R R N KH UMH H
D QG 3QJ
7KH SXEOLFO\ REVHUYHG RXWSXW LV UHDOL]HG DQG
&RQVXPSWLRQ LV GLVWULEXWHG WR WKH DJHQW
/HW & 4 DQG $ EH WKH VHWV RI FRQVXPSWLRQV RXWSXWV DQG DFWLRQV UHVSHFWLYHO\ 'HQRWH
HOHPHQWV RI WKHVH VHWV DV F
~ d d
& T
2IWHQ 3
&
d 4 d $
4 DQG D
$ 7KH VHW RI IHDVLEOH SRLQWV LV 3
&
4
$
7KH DJHQW V SUHIHUHQFHV DUH GHpQHG RYHU 3 E\ WKH XWLOLW\ IXQFWLRQ X F D
7KH SULQFLSDO FRQVXPHV WKH VXUSOXV UHFHLYLQJ XWLOLW\ Z T
bF
7KH DFWLRQ WDNHQ E\ WKH DJHQW
M
DoHFWV WKH SUREDELOLW\ GLVWULEXWLRQ RI RXWSXW DFFRUGLQJ WR WKH IXQFWLRQ S T D
3URJUDP ZLWKRXW ORWWHULHV
,Q WKH VWDQGDUG IRUPXODWLRQ RI WKH SULQFLSDODJHQW SUREOHP ORWWHULHV DUH QRW DOORZHG 7KH SULQFLSDO
GHWHUPLQLVWLFDOO\ UHFRPPHQGV DQ DFWLRQ DQG WKH FRPSHQVDWLRQ VFKHGXOH F T
LV DOVR GHWHUPLQLVWLF
7KH SUREOHP LV ZULWWHQ XQGHU WKH DVVXPSWLRQ WKDW 4 FRQWDLQV D pQLWH QXPEHU RI HOHPHQWV DV
PD[
D F T
VW
;
;
M
S T D Z T
bF
T
M
S T D X F T D
T
D VROYHV PD[
;
D
a
y8
DQG
M
S T D
a X F T D
a
T
7KH pUVW FRQVWUDLQW JXDUDQWHHV WKH DJHQW 8 XWLOV ,W LV FDOOHG D SDUWLFLSDWLRQ FRQVWUDLQW RU VRPH
3
WLPHV D UHVHUYDWLRQ XWLOLW\ FRQVWUDLQW
VWUDLQW
,W FDQ DOVR EH ZULWWHQ
T
3
7KH VHFRQG FRQVWUDLQW LV WKH LQFHQWLYH FRPSDWLELOLW\ FRQ
M
S T D X F T D
y
T
M
S T D
A X F T D
A
FRQWLQXXP WKHUH LV DQ XQFRXQWDEOH QXPEHU RI WKHVH FRQVWUDLQWV
DA $
:KHQ $ LV D
$V D FRQVHTXHQFH WKHUH LV D
VXEVWDQWLDO OLWHUDWXUH FRQFHUQHG ZLWK FRQGLWLRQV XQGHU ZKLFK LW LV YDOLG WR UHSODFH WKH LQFHQWLYH
FRPSDWLELOLW\ FRQVWUDLQWV ZLWK WKH PXFK VLPSOHU pUVWRUGHU FRQGLWLRQ WR WKH DJHQW V PD[LPL]DWLRQ
SUREOHP 6HH IRU H[DPSOH 5RJHUVRQ
3URJUDP ZLWK ORWWHULHV
%HIRUH LQWURGXFLQJ ORWWHULHV , DVVXPH WKDW WKH VHWV & 4 DQG $ HDFK FRQWDLQ D pQLWH QXPEHU RI
HOHPHQWV 7KLV DVVXPSWLRQ LV RQO\ QHFHVVDU\ IRU FRPSXWDWLRQ QRW WR XVH ORWWHULHV )XUWKHUPRUH
M
, DVVXPH WKDW S T D
!
D T WKDW LV HDFK RXWSXW KDV QRQHPSW\ VXSSRUW
7KLV DVVXPSWLRQ LV
QRW QHFHVVDU\ IRU WKH WHFKQLTXHV XVHG LQ WKLV SDSHU EXW LW VLPSOLpHV WKH QRWDWLRQ
6H H
0 \ H UVR Q
3UH VF R WW D QG 7 R Z QVH QG
D QG 7 R Z QVH QG
SUR J UD P
IR U R WKH U GH U LY
D WLR QV R I WKH
OLQH D U
:KHQ ORWWHULHV DUH DOORZHG LQWR WKH FRQWUDFW VSDFH WKH SULQFLSDO FKRRVHV SUREDELOLW\ GLV
WULEXWLRQV RYHU UHFRPPHQGHG DFWLRQV DQG FRPSHQVDWLRQ VFKHGXOHV
7KH SULQFLSDO V SUREDELOLW\
GLVWULEXWLRQ RYHU WKH VHW RI UHFRPPHQGHG DFWLRQV $ LV GHVFULEHG E\ } D %HFDXVH LW LV SRVVLEOH IRU
GLoHUHQW UHFRPPHQGHG DFWLRQV WR EH UHFRPPHQGHG WKH FRPSHQVDWLRQ VFKHGXOH LV QRZ FRQGLWLRQHG
E\ WKH UHFRPPHQGHG DFWLRQ DV ZHOO DV WKH RXWSXW 7KH FRPSHQVDWLRQ VFKHGXOH LV WKH FRQGLWLRQDO
M
SUREDELOLW\ GHQVLW\ IXQFWLRQ } F T D
,W VKRXOG EH QRWHG WKDW GHWHUPLQLVWLF FRQWUDFWV DUH VWLOO
IHDVLEOH LQ WKLV FRQWUDFW VSDFH 7KH\ DUH VLPSO\ GHJHQHUDWH SUREDELOLW\ GLVWULEXWLRQV
7KH WZR VRXUFHV RI UDQGRPL]DWLRQ SURYLGH GLoHUHQW EHQHpWV 5DQGRPL]DWLRQ LQ FRPSHQVDWLRQ
PD\ LPSURYH ZHOIDUH LI XWLOLW\ IXQFWLRQV KDYH FRQYH[ SRUWLRQV
,W PD\ DOVR ZHDNHQ LQFHQWLYH
FRQVWUDLQWV LI SUHIHUHQFHV DUH QRQVHSDUDEOH )RU H[DPSOH LI WKH DFWLRQ DoHFWV ULVNDYHUVLRQ WKHQ
UDQGRPL]DWLRQ LQ FRPSHQVDWLRQ PD\ EH DQ HoHFWLYH ZD\ WR LPSOHPHQW DFWLRQV 5DQGRPL]DWLRQ LQ
WKH UHFRPPHQGHG DFWLRQ PD\ DOVR LPSURYH ZHOIDUH WKRXJK QRW LQ WKH VDPH ZD\ /DWHU ZKHQ WKH
G\QDPLF SURJUDP LV LQWURGXFHG , ZLOO GHPRQVWUDWH KRZ DFWLRQ ORWWHULHV LPSURYH ZHOIDUH
3ODFLQJ } D
M
DQG } F T D
GLUHFWO\ LQWR WKH SUHYLRXV SURJUDP GRHV QRW FUHDWH D OLQHDU SURJUDP
:LWK VRPH DOJHEUDLF PDQLSXODWLRQV KRZHYHU LW FDQ EH WXUQHG LQWR D OLQHDU SURJUDP ZKHUH WKH
MRLQW GLVWULEXWLRQ } F T D
LV WKH FKRLFH YDULDEOH 7KH MRLQW GLVWULEXWLRQ LV UHODWHG WR WKH SULQFLSDO V
FKRLFH YDULDEOHV E\ WKH LGHQWLW\
M
} F T D
M
} F T D S T D } D
7HFKQRORJ\ FRQVWUDLQWV
7KH SULQFLSDO FKRRVHV } D
M
DQG } F T D QRW } F T D :LWK WKH DGGLWLRQ RI VHYHUDO FRQVWUDLQWV
KRZHYHU WKH FKRLFH RI } F T D
LV HTXLYDOHQW WR RQO\ FKRRVLQJ WKH PDUJLQDO DQG FRQGLWLRQDO GHQVLW\
IXQFWLRQV 7KHVH FRQVWUDLQWV DUH
T
z D
z
;
} F T
z D
z
M
S T
zD
z
F
,I D } F T D
WKDW VDWLVpHV
;
} F T D
z
F T
LV FKRVHQ WKH SULQFLSDO KDV LPSOLFLWO\ FKRVHQ } D
M
DQG } F T D
EXW
M
QRW WKH H[RJHQRXV S T D
,QFHQWLYH FRQVWUDLQWV
%\ WKH UHYHODWLRQ SULQFLSOH WKH UHFRPPHQGHG DFWLRQ D QHHGV WR EH D VROXWLRQ WR WKH DJHQW V GHFLVLRQ
;
;
SUREOHP )RU DQ\ DFWLRQ UHFRPPHQGHG ZLWK SRVLWLYH SUREDELOLW\ } D
F T
M
M
} F T D S T D X F D
y
M
M
} F T D S T D
A X F D
A
F T
! D PXVW VDWLVI\
DA $
2Q WKH ULJKWKDQG VLGH RI
WKH GHYLDWLQJ DFWLRQ D
A HQWHUV LQWR XWLOLW\ DQG WKH WHFKQRORJ\
,W
GRHV QRW HQWHU LQWR WKH FRPSHQVDWLRQ VFKHGXOH EHFDXVH WKH UHFRPPHQGHG DFWLRQ QRW WKH DFWLRQ
DFWXDOO\ FKRVHQ E\ WKH DJHQW LV WKH LQSXW LQWR WKH FRPSHQVDWLRQ VFKHGXOH
M
7R PDNH WKHVH FRQVWUDLQWV OLQHDU LQ } F T D pUVW VXEVWLWXWH } F T D
;
WKH LQFHQWLYH FRQVWUDLQWV WR REWDLQ
M
} F T D X F D
y
;
F T
M
7KH WHUP } F T D
S TMD
A
S TMD
M
} F T D
F T
M
M
S T D
A
S T D
X F D
A
M
LQWR
DA $
LV WKH MRLQW SUREDELOLW\ WKDW WKH DJHQW UHFHLYHV WKH SDLU
D ZDV UHFRPPHQGHG EXW WKH DJHQW LQVWHDG WDNHV DFWLRQ D
A
M
} F T D S T D
F T
JLYHQ WKDW
7KH VHFRQG VWHS LQ PDNLQJ WKHVH
FRQVWUDLQWV OLQHDU LV WR PXOWLSO\ ERWK VLGHV RI WKH HTXDWLRQ E\ } D 7KH LQFHQWLYH FRQVWUDLQWV DUH
WKHQ
;
} F T D X F D
F T
%HFDXVH } D
y
;
} F T D
F T
M
S T MD
S T D
A
X F D
A
D
D
A
D
$ d $
IRU DFWLRQV WKDW DUH QHYHU UHFRPPHQGHG WKHVH FRQVWUDLQWV DUH WULYLDOO\ VDWLVpHG
E\ DFWLRQV WKDW DUH UHFRPPHQGHG ZLWK ]HUR SUREDELOLW\ )LQDOO\ EHFDXVH WKH FDUGLQDOLW\ RI $ LV
pQLWH WKHUH LV D pQLWH QXPEHU RI LQFHQWLYH FRQVWUDLQWV
3UREDELOLW\ FRQVWUDLQWV
;
7KH IROORZLQJ VHW RI FRQVWUDLQWV HQVXUHV WKDW } F T D
} F T D
DQG
LV D SUREDELOLW\ PHDVXUH
F T D
} F T D
y
F T D
7KH SULQFLSDODJHQW SUREOHP ZLWK ORWWHULHV LV
3URJUDP 3DUWLFLSDWLRQ &RQVWUDLQW 3UREOHP
;
;
PD[
}
VW
} F T D Z T
bF
F T D
} F T D X F D
y 8
F T D
(TXDWLRQ
DQG
LV WKH SDUWLFLSDWLRQ FRQVWUDLQW
)XUWKHUPRUH WKLV SURJUDP LV D OLQHDU SURJUDP
7KHUH LV D pQLWH QXPEHU RI OLQHDU FRQVWUDLQWV DQG WKHUH LV D OLQHDU REMHFWLYH IXQFWLRQ
3URJUDP FDQ EH XVHG WR FRPSXWH WKH 3DUHWR IURQWLHU E\ VROYLQJ WKH SURJUDP IRU HDFK IHDVLEOH
8 ,Q D OLQHDU SURJUDP WKH VHW RI IHDVLEOH VROXWLRQV LV FRQYH[ DQG WKH REMHFWLYH IXQFWLRQ LV ZHDNO\
FRQFDYH 7KHVH WZR IHDWXUHV LPSO\ WKDW WKH VSDFH RI IHDVLEOH XWLOLWLHV LV DOVR FRQYH[ &RQVHTXHQWO\
WKH 3DUHWR IURQWLHU FDQ DOVR EH FRPSXWHG XVLQJ WKH 3ODQQHU V SUREOHP
7KH 3ODQQHU V SUREOHP
PDNHV WKH REMHFWLYH IXQFWLRQ D ZHLJKWHG VXP RI XWLOLWLHV DQG UHPRYHV WKH SDUWLFLSDWLRQ FRQVWUDLQW
7KLV DOWHUQDWLYH IRUPXODWLRQ LV LPSRUWDQW IRU WKH DOJRULWKPV GHYHORSHG LQ WKLV SDSHU
WKHUPRUH WKH 3ODQQHU V SUREOHP LV HDVLHU WR FRPSXWH
)XU
&RQVHTXHQWO\ LW LV VRPHWLPHV D PRUH
DGYDQWDJHRXV IRUPXODWLRQ )RU WKHVH UHDVRQV , DOVR ZULWH RXW WKH 3ODQQHU V SURJUDP
/HW y
> @ EH WKH DJHQW V ZHLJKW
7KH 3ODQQHU V SURJUDP LV
3URJUDP 3ODQQHU V 3UREOHP
PD[
}
;
} F T D
>yX F D
by Z TbF @
F T D
VW
> @ WKH 3DUHWR IURQWLHU FDQ EH
7KLV SURJUDP LV DOVR D OLQHDU SURJUDP %\ VROYLQJ LW IRU HDFK y
FDOFXODWHG
)LQDOO\ LW VKRXOG EH QRWHG WKDW WKHUH LV \HW D WKLUG PHWKRG IRU FDOFXODWLQJ WKH 3DUHWR IURQ
WLHU
7KH UHPDLQLQJ PHWKRG LV WR VZLWFK WKH SULQFLSDO V DQG DJHQW V XWLOLW\ LQ WKH 3DUWLFLSDWLRQ
FRQVWUDLQW SURJUDP DQG WKHQ VROYH WKH SUREOHP IRU WKH IHDVLEOH UDQJH RI SULQFLSDO V XWLOLW\ :
/DWHU LQ WKH SDSHU , ZLOO SUHVHQW DQ H[DPSOH ZKHUH WKLV IRUPXODWLRQ LV PRVW DSSURSULDWH IRU WKH
HFRQRPLF SUREOHP
&RPSXWDWLRQ
$ OLQHDU SURJUDP LQ VWDQGDUG IRUP LV ZULWWHQ
PD[ H[
[y
VW
ZKHUH H LV D
$ LV DQ
7
KH
P
dQ
dQ
OLWH UD WXUH
E
YHFWRU [ WKH FKRLFH YDULDEOH LV DQ
Q
d
YHFWRU E LV DQ
PDWUL[ RIWHQ FDOOHG WKH FRHrFLHQW PDWUL[ DQG
UD UH O\
PR VW QD WXUD O H F R QR PLF
F R QY H [
$[
XVH V WKH
3OD QQH U V IR UPXOD WLR Q
VSH F LpF D WLR Q 6H F R QG Z
VH W ,Q WKLV OD WWH U F D VH WKH
7
KH UH
D UH
LWKR XW OR WWH ULH V WKH
3OD QQH U V SUR EOH P Z
LOO QR W WUD F H
WZ
R
)
YHFWRU DQG
LUVW LW LV QR W QH F H VVD ULO\
F R QVWUD LQWV GR
H QWLUH
d
UHODWHG WR WKH VHW RI DFWLRQV
UH D VR QV
LQF H QWLY H
R XW WKH
QRW
P
3D UH WR
QR W QH F H VVD ULO\
IUR QWLH U
WKH
GH pQH
D
$
3UREOHPV ZLWK LQHTXDOLW\ FRQVWUDLQWV FDQ EH FRQYHUWHG LQWR VWDQGDUG IRUP E\ WKH XVH RI VODFN
YDULDEOHV
7KH pUVW VWHS WR FRPSXWLQJ D VROXWLRQ LV WR FUHDWH WKH FRHrFLHQWV DQG WKH VHFRQG VWHS LV WR
VROYH WKH UHVXOWLQJ OLQHDU SURJUDP 7KH ODWWHU VWHS UHTXLUHV WKH XVH RI OLQHDU SURJUDPPLQJ FRGH
0DQ\ FRGHV LQFOXGLQJ WKH RQH , XVH LQ WKLV SDSHU DUH EDVHG RQ WKH VLPSOH[ DOJRULWKP
%HFDXVH
RQH YHUVLRQ RI WKH VLPSOH[ DOJRULWKP WKH UHpQHG VLPSOH[ DOJRULWKP XQGHUOLHV WKH 'DQW]LJ:ROIH
GHFRPSRVLWLRQ LW LV QHFHVVDU\ WR EULHq\ GHVFULEH WKLV DOJRULWKP
5HpQHG VLPSOH[ DOJRULWKP
&RQVLGHU WKH V\VWHP RI OLQHDU HTXDWLRQV
)RU VLPSOLFLW\ DVVXPH WKDW
P Q
OLQHDUO\ LQGHSHQGHQW FROXPQV
7KH
$[
%
ZKHUH WKHUH DUH
DQG WKDW WKH UDQN RI
EDVLF
YDULDEOHV DUH WKH
FROXPQV WKH UHPDLQLQJ YDULDEOHV DUH FDOOHG
LQWR FRHrFLHQWV RQ WKH EDVLV
E
QRQEDVLF
$
LV
P
P
P
HTXDWLRQV DQG
[
YDULDEOHV
$ EDVLV RI WKLV V\VWHP LV
P
YDULDEOHV WKDW FRUUHVSRQG WR WKHVH
7KH FRQVWUDLQW PDWUL[ FDQ EH SDUWLWLRQHG
DQG FRHrFLHQWV RQ WKH UHVW RI WKH FROXPQV
QRQVLQJXODU WKHUH LV D VROXWLRQ WR WKH HTXDWLRQ
Q
%b E
'
%HFDXVH
7KLV VROXWLRQ LV IHDVLEOH LI
%
LV
[ y
$ SURSHUW\ RI WKLV VROXWLRQ LV WKDW DOO QRQEDVLF YDULDEOHV DUH QHFHVVDULO\ ]HUR ZKLOH WKH EDVLF
YDULDEOHV PD\ RU PD\ QRW EH ]HUR
VHW RI VROXWLRQV WR
$[
*HRPHWULFDOO\ EDVLF VROXWLRQV DUH WKH H[WUHPH SRLQWV RI WKH
E
,I DQ RSWLPDO VROXWLRQ WR D OLQHDU SURJUDP H[LVWV WKHQ WKHUH LV D EDVLF IHDVLEOH VROXWLRQ WKDW LV
RSWLPDO 6LPSOH[EDVHG DOJRULWKPV VHDUFK DPRQJ WKH EDVLF VROXWLRQV IRU DQ RSWLPDO IHDVLEOH RQH
6WDUWLQJ ZLWK D EDVLF IHDVLEOH VROXWLRQ WKH DOJRULWKP GHWHUPLQHV LI HQWHULQJ D QRQEDVLF YDULDEOH
LQWR WKH EDVLV LQFUHDVHV WKH REMHFWLYH IXQFWLRQ ,I VXFK D YDULDEOH LV IRXQG WKH DOJRULWKP UHPRYHV
D EDVLF YDULDEOH IURP WKH EDVLV DQG HQWHUV WKH QHZ YDULDEOH LQWR WKH EDVLV
,I DW VRPH SRLQW QR
VXFK QRQEDVLF YDULDEOH LV IRXQG WKHQ WKH EDVLF IHDVLEOH VROXWLRQ LV RSWLPDO
*HRPHWULFDOO\ WKH
DOJRULWKP PRYHV WKURXJK DGMDFHQW IHDVLEOH H[WUHPH SRLQWV XQWLO LW UHDFKHV DQ RSWLPDO RQH
*LYHQ D IHDVLEOH EDVLF VROXWLRQ OHW
H%
DQG
H'
EH WKH SRUWLRQV RI WKH REMHFWLYH IXQFWLRQ FRUUH
VSRQGLQJ WR WKH EDVLF YDULDEOHV DQG QRQEDVLF YDULDEOHV UHVSHFWLYHO\ 7KH IRUPXOD WKDW WKH UHYLVHG
VLPSOH[ DOJRULWKP XVHV WR GHWHUPLQH LI WKH REMHFWLYH IXQFWLRQ FDQ EH LQFUHDVHG LV
5H F H QWO\ WKH UH
KD Y H
EH H Q LPSR UWD QW GH Y H OR SPH QWV LQ LQWH ULR U SR LQW D OJ R ULWKPV
LPSOLH V WKD W IR U VPD OOH U SUR EOH PV VLPSOH [
PH WKR G D UH
6H H
D Q\
F R PSD UD EOH
PH WKR GV D UH
ID VWH U LQ SUD F WLF H
'
H' b H% %b '
LVF XVVLR Q LQ WKH
OLWH UD WXUH
EXW IR U OD UJ H U SUR EOH PV LQWH ULR U SR LQWV
LI QR W VXSH ULR U
OLQH D U SUR J UD PPLQJ
WH [ WER R N
IR U D
GH VF ULSWLR Q R I VLPSOH [
VR XUF H
D OJ R ULWKPV
/XH QEH UJ H U
LV D
J R R G
RU HTXLYDOHQWO\
H' b z'
H% %b
ZKHUH z
DUH WKH GXDO YDULDEOHV
RU VLPSOH[ PXOWLSOLHUV RQ WKH FRQVWUDLQWV
,I DQ\
HOHPHQW RI WKLV YHFWRU LV SRVLWLYH WKHQ LQWURGXFLQJ WKH FRUUHVSRQGLQJ QRQEDVLF YDULDEOH LQWR WKH
EDVLV LQFUHDVHV WKH YDOXH RI WKH REMHFWLYH IXQFWLRQ
7KH DOJRULWKP WKHQ GHWHUPLQHV ZKLFK EDVLF
YDULDEOH VKRXOG EH UHSODFHG LQ WKH EDVLV E\ WKH QRQEDVLF YDULDEOH
SURFHVV XQWLO
H' b z' x
7KH DOJRULWKP UHSHDWV WKLV
7KH EDVLF YDULDEOHV WKDW VDWLVI\ WKLV FRQGLWLRQ DUH DQ RSWLPDO VROXWLRQ
&RPSXWDWLRQ OLPLWDWLRQV
7KHUH DUH WZR OLPLWDWLRQV IRU FRPSXWDWLRQ 7KH pUVW LV WKH VWRUDJH UHTXLUHG IRU WKH SUREOHP
DQG WKH VHFRQG LV WKH VSHHG RI WKH FRGH
1HHGOHVV WR VD\ LQFUHDVLQJ WKH VL]H RI WKH SUREOHP
LQFUHDVHV WKH VWRUDJH UHTXLUHG DQG JHQHUDOO\ LQFUHDVHV WKH WLPH LW WDNHV FRGH WR VROYH WKH SUREOHP
2QH VWUDWHJ\ LV WR FDOFXODWH WKH PDWULFHV
H $
DQG
E
DQG WKHQ GLUHFWO\ HQWHU WKHP LQWR
WKH OLQHDU SURJUDPPLQJ FRGH :KLOH IRU VRPH SUREOHPV WKLV LV pQH PHPRU\ OLPLWDWLRQV TXLFNO\
PDWWHU $V WKH FDUGLQDOLW\ RI 3 LQFUHDVHV WKH VL]H RI WKH OLQHDU SURJUDP LQFUHDVHV ,I Q[ GHQRWHV
WKH FDUGLQDOLW\ RI VHW ; WKHQ WKH QXPEHU RI YDULDEOHV LQ WKH SURJUDP LV Q
SOXV QD QD
b
VODFN YDULDEOHV 7KH QXPEHU RI FRQVWUDLQWV LV QD QD
b
QF QT QD YDULDEOHV
QD QT )RU H[DPSOH
LI WKHUH DUH FRQVXPSWLRQV RXWSXWV DQG DFWLRQV WKHQ WKHUH DUH YDULDEOHV
VODFN YDULDEOHV DQG FRQVWUDLQWV 6RPH FRPPHUFLDO FRGHV PD\ EH DEOH WR KDQGOH WKLV
VL]H RI SUREOHP EXW LW ZRXOG VWLOO UHTXLUH DQ HQRUPRXV DPRXQW RI PHPRU\ DQG FRPSXWDWLRQ IDU
H[FHHGLQJ WKH FDSDELOLWLHV RI P\ VRIWZDUH DQG KDUGZDUH
,Q WHUPV RI PHPRU\ UHTXLUHPHQWV WKH DFWLRQ VHW $ LV WKH PRVW FRVWO\ WR LQFUHDVH LQ WHUPV RI
WKH VL]H RI WKH SURJUDP
,QFUHDVLQJ WKH QXPEHU RI HOHPHQWV LQ WKLV VHW LQFUHDVHV WKH QXPEHU RI
LQFHQWLYH FRQVWUDLQWV DQG WHFKQRORJ\ FRQVWUDLQWV DV ZHOO DV WKH QXPEHU RI YDULDEOHV
,QFUHDVLQJ
WKH QXPEHU RI RXWSXWV LV DOVR FRVWO\ EXW XQOLNH DFWLRQV GRHV QRW DoHFW WKH QXPEHU RI LQFHQWLYH
FRQVWUDLQWV
,QFUHDVLQJ WKH QXPEHU RI FRQVXPSWLRQV LV WKH OHDVW FRVWO\ EHFDXVH WKH VL]H RI WKH
FRQVXPSWLRQ VHW RQO\ DoHFWV WKH QXPEHU RI YDULDEOHV
'DQW]LJ:ROIH 'HFRPSRVLWLRQ
$V GHVFULEHG LQ WKH SUHYLRXV VHFWLRQ WKH FDUGLQDOLW\ RI WKH JULGV LV WKH SULPDU\ OLPLWDWLRQ WR FRP
SXWLQJ VROXWLRQV
,Q WKLV VHFWLRQ , VKRZ WKDW WKH PRUDO KD]DUG SUREOHP KDV D VSHFLDO VWUXFWXUH
WKDW FDQ EH FRPSXWHG XVLQJ D YDULDQW RI WKH 'DQW]LJ:ROIH GHFRPSRVLWLRQ DOJRULWKP 7KLV DOJR
ULWKP EUHDNV WKH JOREDO SURJUDP LQWR VXESUREOHPV
7KH VXESUREOHPV DUH FRPSXWHG VHSDUDWHO\
JUHDWO\ ORZHULQJ WKH SUREOHPV V PHPRU\ UHTXLUHPHQWV
,Q WKH FRXUVH RI GHYHORSLQJ WKH DOJRULWKP VLPLODULWLHV WR G\QDPLF SURJUDPPLQJ ZLOO EH GLV
FXVVHG 7KLV FRQQHFWLRQ LV HPSKDVL]HG IRU WZR H[SRVLWLRQDO UHDVRQV )LUVW WKH G\QDPLF SURJUDP
PLQJ LQWHUSUHWDWLRQ ZLOO PDNH FOHDU WKH YDOXH RI DFWLRQ ORWWHULHV 6HFRQG PDQ\ UHDGHUV DUH IDPLOLDU
ZLWK G\QDPLF SURJUDPPLQJ 'HVSLWH WKH VLPLODULWLHV WR G\QDPLF SURJUDPPLQJ KRZHYHU WKHUH LV
DQ LPSRUWDQW GLoHUHQFH WKDW OLHV DW WKH KHDUW RI WKH DOJRULWKP V HrFLHQF\ 7KH DOJRULWKP DYRLGV
FRPSXWLQJ WKH HQWLUH YDOXH IXQFWLRQ
([DFWO\ KRZ WKH DOJRULWKP GRHV WKLV ZLOO EH GLVFXVVHG LQ
VRPH GHWDLO ODWHU EXW WKHUH LV DQ LQWHUHVWLQJ LQWHUSUHWDWLRQ LQ WHUPV RI VHDUFKLQJ RYHU WKH VSDFH
RI 3ODQQHU V ZHLJKWV
X X X
$
$
$
XQ
$Q
)LJXUH 6WUXFWXUH RI 3URJUDP FRQVWUDLQW PDWUL[
)LJXUH GHVFULEHV WKH VWUXFWXUH RI WKH FRQVWUDLQW PDWUL[ RI 3URJUDP WKDW LV WKH PRUDO
KD]DUG SUREOHP ZKHUH WKH SULQFLSDO V XWLOLW\ LV PD[LPL]HG VXEMHFW WR WKH DJHQW UHFHLYLQJ KLV
UHVHUYDWLRQ XWLOLW\ OHYHO
(DFK
$L
LV WKH SRUWLRQ RI WKH FRHrFLHQW PDWUL[ RQ WKH FRQVWUDLQWV DQG
YDULDEOHV WKDW DUH UHOHYDQW RQO\ WR DFWLRQ DL ,Q WHUPV RI 3URJUDP WKH FRQVWUDLQWV FRUUHVSRQGLQJ
WR EORFN
$L
DUH WKH LQFHQWLYH FRQVWUDLQWV IRU DQ DJHQW UHFRPPHQGHG DFWLRQ DL DQG WKH WHFKQRORJ\
FRQVWUDLQWV FRUUHVSRQGLQJ WR DFWLRQ DL &RHrFLHQWV LQ
DFWLRQ DL WKDW LV } F T DL
YDULDEOHV } F T DM M
$L DUH WKRVH RQ YDULDEOHV GLUHFWO\ LQYROYLQJ
$OO RWKHU FRHrFLHQWV LQ WKLV URZ DUH ]HUR EHFDXVH WKH YDOXHV RI
L GR QRW DoHFW WKH IHDVLELOLW\ RI WKHVH FRQVWUDLQWV
7KH UHPDLQLQJ WZR FRQVWUDLQWV FRQQHFW RU OLQN WKH EORFNV RI FRQVWUDLQWV 7KH WRS RQH LQ WKH
PDWUL[ LV WKH SDUWLFLSDWLRQ FRQVWUDLQW WKH
XL
DUH YHFWRUV RI FRHrFLHQWV GHWHUPLQLQJ XWLOLW\ WKH
DJHQW UHFHLYHV LI DFWLRQ DL LV WDNHQ 7KH VHFRQG FRQVWUDLQW LV WKH SUREDELOLW\ PHDVXUH FRQVWUDLQW
7KH FRHrFLHQWV LQ WKLV FRQVWUDLQW DUH RQH DV LQGLFDWHG E\ WKH YHFWRU
)LQDOO\ LW VKRXOG EH QRWHG
WKDW WKH FRQVWUDLQW PDWUL[ IRU WKH SODQQHU V IRUPXODWLRQ LV REWDLQHG E\ UHPRYLQJ WKH SDUWLFLSDWLRQ
FRQVWUDLQW
$ FRQVWUDLQW PDWUL[ WKDW FDQ EH GLYLGHG LQWR EORFNV ZLWK RQO\ D IHZ FRQQHFWLQJ FRQVWUDLQWV LV
FDOOHG
EORFN DQJXODU
'DQW]LJ DQG :ROIH
pUVW GHYHORSHG DQ DOJRULWKP WKDW WDNHV DGYDQWDJH
RI WKLV VWUXFWXUH 'HVFULSWLRQ RI WKH PHWKRG FDQ EH IRXQG LQ PDQ\ OLQHDU SURJUDPPLQJ WH[WERRNV
VXFK DV %HUWVLPDV DQG 7VLWVLNODV
7KH EORFNDQJXODU VWUXFWXUH RI WKH FRQVWUDLQW PDWUL[ DOORZV WKH SUREOHP WR EH VHSDUDWHG LQWR
VXESUREOHPV RQH IRU HDFK EORFN WKDW DUH RQO\ FRQQHFWHG E\ WKH FRQQHFWLQJ FRQVWUDLQWV
0XFK
OLNH D G\QDPLF SURJUDP WKH VXESUREOHPV DUH DQDO\]HG VHSDUDWHO\ WR FDOFXODWH XWLOLWLHV WKDW WKH
SULQFLSDO DQG DJHQW PD\ UHFHLYH LI DFWLRQ DL LV UHFRPPHQGHG 7KHQ WKH PD[LPDO FRPELQDWLRQ RI
WKHVH XWLOLWLHV LV FKRVHQ LQ D ZD\ WKDW VDWLVpHV WKH FRQQHFWLQJ FRQVWUDLQWV
(DFK VXESUREOHP L LV D VPDOO SUREOHP FRQVLVWLQJ RQO\ RI YDULDEOHV UHODWHG WR DFWLRQ DL WKH
$L
EORFN RI FRQVWUDLQWV SOXV DQ DGGLWLRQDO FRQVWUDLQW WKDW WKH YDULDEOHV VXP WR RQH 7KLV ODWWHU
FRQVWUDLQW QRUPDOL]HV WKH VXESUREOHP V DOORFDWLRQ LQWR
RI WKH ULJKWKDQG VLGH YDULDEOHV
RI XWLOLW\
E
H[ SRVW
XWLOLW\ WHUPV %HFDXVH WKH YDOXHV
DUH ]HUR WKLV QRUPDOL]DWLRQ GRHV QRW DoHFW WKH UHODWLYH YDOXHV
7KH VXESUREOHP V FRQVWUDLQWV UHDUUDQJHG DUH
;
DA $
T
z
;
} F T DL
X F D
;
F T
} F T
z DL
b S TzMD b
L
F
F T
b S TMDA
S T MD
y
X F D
A
M
} F T DL S T
z DL
Tz
;
} F T DL
F T
DQG D QRQQHJDWLYLW\ FRQVWUDLQW
WKDW VDWLVpHV WKHVH FRQVWUDLQWV LV D FRQYH[ VHW ZLWK D pQLWH
7KH VHW RI DOORFDWLRQV } F T DL
QXPEHU RI H[WUHPH SRLQWV
6LQFH WKLV VHW LV ERXQGHG E\ WKH ODVW FRQVWUDLQW WKH VHW LV D FRQYH[
KXOO RI WKHVH H[WUHPH SRLQWV &DOO WKLV VHW RI H[WUHPH SRLQWV 3L
$
GGLQJ
WKLV F R QVWUD LQW WR
GH F R PSR VLWLR Q D OJ R ULWKP 7
EXW D OVR
LWV F R QWULEXWLR Q WR
SUR J UD P
WR
G\ QD PLF
7
KH
WKH
KH
VXESUR EOH P LV D
VWD QGD UG IR UP Z
WKH
SUR ED ELOLW\
UH D VR Q , GH SD UW IUR P WKH
SUR J UD PPLQJ D
WH F KQLT XH
GH SD UWXUH
R XOG F D OF XOD WH
PH D VXUH
IUR P WKH
VWD QGD UG GH Y H OR SPH QW R I WKH
QR W R QO\
F R QVWUD LQW
7
KH UH
WKH
Z
R XOG D OVR
VWD QGD UG SUH VH QWD WLR Q LV WKD W P\
PR VW H F R QR PLVWV D UH
OR WWH ULH V
ID PLOLD U Z
'
D QW] LJ :R OIH
VXESUR EOH P V F R QWULEXWLR QV WR
EH
D
GLoH UH QF H
Y D ULD QW PD N H V F OH D U WKH
LWK D QG LW GH PR QVWUD WH V WKH
XWLOLWLH V
LQ WKH
PD VWH U
F R QQH F WLR QV
UR OH
R I D F WLR Q
)HDVLEOH SULQFLSDODJHQW XWLOLW\ SDLUV IRU WKLV VXESUREOHP DUH FDOFXODWHG E\ HYDOXDWLQJ WKH
REMHFWLYH IXQFWLRQ DQG SDUWLFLSDWLRQ FRQVWUDLQW RYHU WKH FRQYH[ KXOO RI 3L %HFDXVH WKHVH XWLOLW\
IXQFWLRQV DUH OLQHDU KRZHYHU WKLV VHW FDQ EH UHSUHVHQWHG DV WKH FRQYH[ KXOO RI WKHLU XWLOLW\ IXQFWLRQV
HYDOXDWHG DW HDFK SRLQW LQ 3L /HW ;L EH WKH VHW RI XWLOLWLHV HYDOXDWHG DW 3L DQG FDOO DQ HOHPHQW LQ
WKLV VHW [L (DFK SRLQW [L LV D WZRGLPHQVLRQDO YHFWRU OLVWLQJ WKH SULQFLSDO V DQG DJHQW V XWLOLWLHV
, XVH WKH QRWDWLRQ [ZL DQG [XL WR GHVFULEH WKH SULQFLSDO V DQG DJHQW V XWLOLW\ UHVSHFWLYHO\
2QFH WKH XWLOLW\ SRLQWV DUH HQXPHUDWHG IRU HDFK VXESUREOHP WKH PDVWHU SURJUDP FDQ EH VROYHG
/HW } [L
EH WKH SUREDELOLW\ RI FKRRVLQJ [L 7KH PDVWHU SURJUDP LV
0DVWHU 3URJUDP
PD[
}
;
VW
y
;
} [L [ZL
[L L
;
y 8
;
} [L [XL
[L L
} [L
[L
L
[L L
ZKHUH WKH WZR FRQVWUDLQWV FRUUHVSRQG WR WKH FRQQHFWLQJ FRQVWUDLQWV LQ )LJXUH
LV D OLQHDU SURJUDP MXVW DV ZDV WKH RULJLQDO IRUPXODWLRQ
} F T DL
KDYH EHHQ UHSODFHG E\
[XL [ZL
DQG WKH
$
L
7KLV SURJUDP
7KH GLoHUHQFH LV WKDW WKH YDULDEOHV
FRQVWUDLQWV KDYH EHHQ UHSODFHG E\ WKH
UHVWULFWLRQ WKDW [L
;
WKDW WKH } F T DL
HPEHGGHG LQ [L LV WKH VDPH YDOXH DV ZRXOG UHVXOW IURP 3URJUDP )LQDOO\ WKH
L
$OVR QRWLFH WKDW WKH VFDOLQJ GRQH LQ WKH VXESUREOHP LV UHVFDOHG KHUH VR
RSWLPDOLW\ FRQGLWLRQ LV
L
[XL
b zZ [ZL x zS
ZKHUH zZ LV WKH GXDO YDULDEOH IRU WKH SDUWLFLSDWLRQ FRQVWUDLQW DQG zS LV WKH GXDO YDULDEOH IRU WKH
SUREDELOLW\ PHDVXUH FRQVWUDLQW
$ VLPSOH H[DPSOH LOOXVWUDWHV WKH EDVLF LGHD EHKLQG WKH SURJUDP
WZR DFWLRQV $
ID DJ
&RQVLGHU DQ HFRQRP\ ZLWK
)LJXUH LV D JUDSK LQ XWLOLW\ VSDFH WKDW GHVFULEHV <L WKH VHWV RI IHDVLEOH
XWLOLWLHV IRU HDFK SRVVLEOH DFWLRQ WKDW PD\ EH LPSOHPHQWHG 7KH DJHQW V XWLOLW\ LV RQ WKH [D[LV DQG
WKH SULQFLSDO V XWLOLW\ LV RQ WKH \D[LV 7KH VHW < ERXQGHG E\ WKH VROLG OLQH DQG WKH D[HV LV WKH
VHW RI IHDVLEOH XWLOLWLHV REWDLQDEOH LI DFWLRQ D LV UHFRPPHQGHG 3RLQWV LQ WKH VHW ; DUH VFDWWHUHG
s3
Utility of principal
Y2
s5
s1
s2
s
4
Y1
U
Utility of agent
)LJXUH )HDVLEOH XWLOLW\ SDLUV IRU HDFK LPSOHPHQWDEOH DFWLRQ
DORQJ WKH ERXQGDU\ RI < 7KH VHW < ERXQGHG E\ WKH GRWWHG OLQH DQG WKH D[HV LV VLPLODUO\ GHpQHG
IRU DFWLRQ D 7KHVH VHWV DUH LQGHSHQGHQW RI HDFK RWKHU EHFDXVH RI WKH EORFNDQJXODU VWUXFWXUH RI
WKH FRQVWUDLQWV :KLOH WKHVH VHWV DUH FRQYH[ WKHLU XQLRQ QHHG QRW EH DV LQ WKH H[DPSOH
)LJXUH GHVFULEHV WKH SUREOHP IDFHG E\ WKH SURJUDP DIWHU WKH VXESUREOHP XWLOLWLHV KDYH EHHQ
FDOFXODWHG
7KH PDVWHU SURJUDP FDOFXODWHV WKH RSWLPDO FRPELQDWLRQ RI SRLQWV IURP ; DQG ;
WKDW VDWLVpHV WKH WZR FRQVWUDLQWV
FRQYH[ KXOO RI ;
6
;
7KH VHW RI IHDVLEOH DOORFDWLRQV LQ WKH PDVWHU SURJUDP LV WKH
ZKLFK LV HTXDO WR <
6
< ,Q )LJXUH WKH K\SKHQDWHG OLQH LQGLFDWHV WKH
ERXQGDU\ RI XWLOLW\ SRLQWV WKDW DUH IHDVLEOH EXW DUH QRW LQ ; RU ;
7KH RSWLPDO FRPELQDWLRQ RI SRLQWV ZLOO EH D ORWWHU\ SRVVLEO\ GHJHQHUDWH
,I WKH RSWLPDO
VROXWLRQ LQYROYHV SRLQWV IURP PRUH WKDQ RQH VHW WKHQ DQ DFWLRQ ORWWHU\ LV D SURSHUW\ RI WKH
VROXWLRQ $V )LJXUH VXJJHVWV VXFK D ORWWHU\ PD\ RFFXU LI WKH XQLRQ RI < DQG < LV QRW FRQYH[
7KH GLVFUHWHQHVV RI WKH DFWLRQ JULG PD\ FDXVH VXFK D QRQFRQYH[LW\ EXW DV GHPRQVWUDWHG ODWHU
LQ DQ H[DPSOH PRUH VXEVWDQWLYH DVSHFWV RI WKH SUREOHP VXFK DV WKH WHFKQRORJ\ PD\ DOVR FDXVH
VXFK D QRQFRQYH[LW\
)LJXUH DOVR LOOXVWUDWHV WKH ORVV IURP GLVDOORZLQJ DFWLRQ ORWWHULHV LQ WKH FRQWUDFW VSDFH :LWKRXW
DFWLRQ ORWWHULHV WKH FRUUHVSRQGLQJ PDVWHU SURJUDP ZRXOG UHVWULFW LWVHOI WR FRQVLGHULQJ SRLQWV WKDW
JLYH DW OHDVW 8 XWLOV LQ VHWV < RU <
7KH SRLQW V LV WKH EHVW VXFK SRLQW LQ < DQG V LV WKH
EHVW VXFK SRLQW LQ < VR WKH SURJUDP ZRXOG FKRRVH V EHFDXVH LW JLYHV WKH SULQFLSDO KLJKHU XWLOLW\
%HFDXVH WKH DFWLRQ FKRLFH LV GHWHUPLQLVWLF WKH SDUWLFLSDWLRQ FRQVWUDLQW PXVW KROG LQ D VHQVH
SRLQWZLVH ,Q FRQWUDVW WKH SURJUDP ZLWK DFWLRQ ORWWHULHV ZRXOG FKRRVH V D FRQYH[ FRPELQDWLRQ
RI SRLQWV V DQG V 7KLV SRLQW JLYHV WKH DJHQW 8 XWLOV LQ H[SHFWDWLRQ DQG LV 3DUHWR VXSHULRU WR
V
&RPSXWDWLRQDOO\ WKH PDVWHU SURJUDP LV D VWHS EDFNZDUGV
'HVSLWH WKH UHGXFWLRQ RI WKH
SUREOHP WR WZR FRQVWUDLQWV WKH QXPEHU RI YDULDEOHV KDV LQFUHDVHG E\ DQ LQFUHGLEOH DPRXQW IDU
WRR PDQ\ WR HQXPHUDWH
7KH PDVWHU SURJUDP DOVR GHPRQVWUDWHV ZK\ FRPSXWLQJ D G\QDPLF
SURJUDP LV QRW D JRRG VWUDWHJ\ HLWKHU $ G\QDPLF SURJUDP ZRXOG VROYH IRU D YDOXH IXQFWLRQ WKDW
LV WKH QRUWKHDVWHUQ IURQWLHU RI HDFK VXESUREOHP LQ )LJXUH DQG WKHQ VROYH WKH PDVWHU SURJUDP
6ROYLQJ IRU WKH YDOXH IXQFWLRQ KRZHYHU ZRXOG UHTXLUH VROYLQJ D KXJH QXPEHU RI VXESUREOHPV
SUREDEO\ QRW PXFK EHWWHU WKDQ HQXPHUDWLQJ DOO RI WKH YHUWLFHV
'DQW]LJ:ROIH GHFRPSRVLWLRQ
7KH 'DQW]LJ:ROIH GHFRPSRVLWLRQ DOJRULWKP VXUPRXQWV WKH SUREOHP SRVHG E\ WKH ODUJH QXPEHU
RI YDULDEOHV E\ RQO\ FDOFXODWLQJ YDOXHV RI [L DV WKH\ DUH QHHGHG
7KH LGHD LV WKDW PRVW H[WUHPH
SRLQWV DUH QRW YLVLWHG E\ WKH VLPSOH[ URXWLQH &RQVHTXHQWO\ PRVW RI WKH FROXPQV LQ WKH PDVWHU
SURJUDP WKDW LV WKH H[WUHPH SRLQWV RI WKH VXESUREOHPV GR QRW HYHU QHHG WR EH FRPSXWHG
7KH DOJRULWKP VWDUWV ZLWK DQ LQLWLDO IHDVLEOH VROXWLRQ WR WKH PDVWHU SUREOHP
a
/HW ;
L
~
;L
EH D VHW FRQVLVWLQJ RI WKH H[WUHPH SRLQWV RI WKLV IHDVLEOH VROXWLRQ 1H[W WKH DOJRULWKP VROYHV WKH
PDVWHU SUREOHP EXW ZLWK WKH UHVWULFWLRQ WKDW [L
;aL
7KLV LV D YHU\ VPDOO OLQHDU SURJUDP WKDW KDV
D EDVLF IHDVLEOH VROXWLRQ E\ DVVXPSWLRQ 7KH RSWLPDOLW\ FRQGLWLRQ
DQG WKH FRHrFLHQWV RI WKH QRQEDVLF YDULDEOHV
F'
DQG
IURP WKH VROXWLRQ WR WKH PDVWHU SUREOHP EHFDXVH z
'
QHHGV WKH GXDO YDULDEOHV z
7KH GXDO YDULDEOHV DUH HDVLO\ FRPSXWHG
%b E
EXW FRHrFLHQWV RQ WKH YDVW QXPEHU
RI QRQEDVLF YDULDEOHV KRZHYHU DUH QRW NQRZQ DW WKLV SRLQW
,W LV DW WKLV VWHS WKDW WKH DOJRULWKP VDYHV RQ VWRUDJH UHTXLUHPHQWV
5DWKHU WKDQ FDOFXODWLQJ
WKH FRHrFLHQWV RQ HDFK RI WKH QRQEDVLF YDULDEOHV WKDW LV FDOFXODWLQJ WKH KXJH QXPEHU RI H[WUHPH
SRLQWV RI HDFK VXESUREOHP LW FDOFXODWHV IURP HDFK VXESUREOHP WKH H[WUHPH SRLQW WKDW PD[LPL]HV
WKH REMHFWLYH IXQFWLRQ 7KHVH H[WUHPH SRLQWV DUH FRPSXWHG E\ VROYLQJ WKH IROORZLQJ VXESUREOHP
IRU HDFK L
6XESUREOHP 3URJUDP
PD[
} F T DL
VXEMHFW WR
y
;
} F T DL
X F DL
bz
ZZ
T
bF
F T
e
7KH VROXWLRQ WR WKLV SUREOHP LV DQ [L
[ ;
; ZKHUH
L
x [e b z
e
7KLV UHVXOW LV LPSRUWDQW EHFDXVH WKH RSWLPDOLW\ FRQGLWLRQ
L
[ ; [ b z
L
L
XL
Z [ZL
xz
WKHQ LW LV VDWLVpHG E\ DOO [L
S
[XL
L
bz
Z [ZL
Z [ZL
XL
IRU WKH PDVWHU SUREOHP LV
L
e
7KHUHIRUH LI IRU HDFK L WKH RSWLPDOLW\ FRQGLWLRQ LV VDWLVpHG E\ [L
;
L
DQG WKH VROXWLRQ WR WKH PDVWHU SUREOHP LV RSWLPDO
,I WKH RSWLPDOLW\ FRQGLWLRQ LV QRW VDWLVpHG WKHQ WKH VROXWLRQ WR WKH PDVWHU SUREOHP LV QRW LQ
a 7KH DOJRULWKP WKHQ SURFHHGV E\ DGGLQJ WR HDFK ;
a WKH SUHYLRXVO\ FDOFXODWHG VROXWLRQV WR WKH
;
L
L
VXESUREOHPV 7KHQ WKH PDVWHU SUREOHP LV UHVROYHG DQG WKH DOJRULWKP FRQWLQXHV XQWLO D VROXWLRQ
LV IRXQG
7KH DOJRULWKP LV SRZHUIXO EHFDXVH LW GRHV QRW FDOFXODWH DOO RI WKH H[WUHPH SRLQWV RI HDFK
VXESUREOHP 'XULQJ HDFK LWHUDWLRQ LW FDOFXODWHV RQO\ WKH H[WUHPH SRLQWV QHHGHG WR pQG WKH VROXWLRQ
WR WKH VXESUREOHP )XUWKHUPRUH PRVW RI WKH FRPSXWDWLRQ LV SHUIRUPHG RQ WKH VXESUREOHPV ZKLFK
DUH VXEVWDQWLDOO\ VPDOOHU WKDQ WKH 3URJUDP ,I WKH DOJRULWKP GRHV QRW UHTXLUH D ODUJH QXPEHU
RI LWHUDWLRQV LW VKRXOG EH HoHFWLYH
&RQQHFWLRQ WR 3ODQQHU V SUREOHP
7KHUH LV D FRQQHFWLRQ EHWZHHQ WKH DOJRULWKP DQG WKH 3ODQQHU V SUREOHP WKDW SURYLGHV LQWXLWLRQ
LQWR WKH DOJRULWKP V ZRUNLQJV %HIRUH GLVFXVVLQJ WKLV FRQQHFWLRQ LW LV QHFHVVDU\ WR GHYHORS VRPH
LPSOLFDWLRQV RI WKH DOJRULWKP IRU WKH 3ODQQHU V SUREOHP
,Q WKH 3ODQQHU V SUREOHP 3URJUDP WKHUH LV QR SDUWLFLSDWLRQ FRQVWUDLQW FRQQHFWLQJ WKH
VXESUREOHPV &RQVHTXHQWO\ WKH RSWLPL]DWLRQ FRQGLWLRQ LV
y[XL
by [ x z
ZL
S
%HFDXVH WKHUH LV RQH FRQVWUDLQW WKH GXDO YDULDEOH LV WULYLDO WR FDOFXODWH
IRU WKLV SUREOHP WKH EDVLV FRQVLVWV RQH YDULDEOH
OLQHDU SURJUDPPLQJ y[XL
by [
ZL
,Q WKH PDVWHU SURJUDP
7KHUHIRUH XVLQJ WKH IXQGDPHQWDO WKHRUHP RI
zS ZKLFK LV WKH RSWLPDOLW\ FRQGLWLRQ
&RQVHTXHQWO\
n2
n4
Y
2
Utility of principal
n3
Y1
n1
U
Utility of agent
)LJXUH 3RLQWV FRPSXWHG DW VXFFHVVLYH LWHUDWLRQV
HDFK VXESUREOHP RQO\ QHHGV WR EH VROYHG RQFH 7KH UHVXOWV DUH WKHQ FRPSDUHG WR GHWHUPLQH ZKLFK
DFWLRQ RU DFWLRQV LV RSWLPDO
$Q LPSOLFDWLRQ RI WKLV UHVXOW LV WKDW WKHUH H[LVWV D VROXWLRQ WR WKH
3ODQQHU V SUREOHP WKDW LV GHJHQHUDWH LQ DFWLRQ ORWWHULHV
5HWXUQLQJ WR WKH 3DUWLFLSDWLRQ FRQVWUDLQW SURJUDP WKH RSWLPL]DWLRQ FRQGLWLRQ LV [XL
bz
Z [ZL
7KLV WHUP FDQ EH LQWHUSUHWHG LQ WHUPV RI D 3ODQQHU V SUREOHP ZKHUH WKH 3ODQQHU V ZHLJKW RQ WKH
DJHQW LV RQH DQG WKH 3ODQQHU V ZHLJKW RQ WKH SULQFLSDO LV
bz
Z
7KH YDULDEOH zZ LV FDOOHG D VLPSOH[
PXOWLSOLHU DW DQ RSWLPXP LW LV WKH /DJUDQJLDQ PXOWLSOLHU 7KH SDUWLFLSDWLRQ FRQVWUDLQW LV JUHDWHU
WKDQ RU HTXDO WR LQ WKLV SUREOHP VR WKLV PXOWLSOLHU LV QHJDWLYH
&RQVLGHU )LJXUH ZKLFK LV VLPLODU WR )LJXUH $V EHIRUH < DQG < DUH WKH VHWV RI IHDVLEOH
XWLOLW\ SDLUV IRU VXESUREOHPV RQH DQG WZR UHVSHFWLYHO\ 7KH DOJRULWKP VWDUWV ZLWK H[WUHPH SRLQWV
a
WKDW FDQ EH XVHG WR IRUP D IHDVLEOH VROXWLRQ 2Q WKH pUVW LWHUDWLRQ OHW ;
L
IHDVLEOH VROXWLRQ LV D FRQYH[ FRPELQDWLRQ RI Q DQG Q
WKH GXDO
IQ QJ ZKHUH WKH
7KH DOJRULWKP SURFHHGV E\ FDOFXODWLQJ
,Q WKLV SUREOHP zZ LV WKH VORSH EHWZHHQ WKH SRLQWV
7KH DJHQW V 3ODQQHU V ZHLJKW LV
DQG WKH SULQFLSDO V LV zZ 7KH ZHLJKWV DUH QRW QRUPDOL]HG WR VXP WR RQH LQ RUGHU WR IDFLOLWDWH
FRPSDULVRQ ZLWK WKH RSWLPDOLW\ FRQGLWLRQ RI WKH PDVWHU SURJUDP
1H[W WKH VXESUREOHPV DUH VROYHG ZLWK WKH QHZ ZHLJKWV 7KH VROXWLRQV WR WKHVH VXESUREOHPV
\LHOG SRLQWV Q
;
DQG Q
;
,I WKH RSWLPDOLW\ FRQGLWLRQ LV QRW \HW VDWLVpHG WKHVH SRLQWV
a DQG ;
a DQG WKH DOJRULWKP FRQWLQXHV (DFK LWHUDWLRQ WKH VXESUREOHPV DUH VROYHG
DUH DGGHG WR ;
XVLQJ XSGDWHG 3ODQQHU V ZHLJKWV 8QGHU WKLV LQWHUSUHWDWLRQ WKH DOJRULWKP LV VHDUFKLQJ WKURXJK WKH
VSDFH RI 3ODQQHU V ZHLJKWV IRU WKH ZHLJKWV WKDW GHOLYHU WKH RSWLPDO IHDVLEOH VROXWLRQ )XUWKHUPRUH
HDFK RI WKHVH FDOFXODWLRQV SLFNV SRLQWV DORQJ WKH 3DUHWR IURQWLHUV RI WKH VXESUREOHP
,Q WHUPV RI G\QDPLF SURJUDPPLQJ WKH 3DUHWR IURQWLHUV RI WKH VXESUREOHPV DUH WKH VWDWH
YDULDEOHV
WKH DJHQW V XWLOLW\ DQG WKH DFWLRQ
DQG WKH YDOXH IXQFWLRQ HYDOXDWHG DW WKH VWDWH YDULDEOHV
WKH SULQFLSDO V XWLOLW\ 7KH DOJRULWKP LV VHOHFWLYHO\ HYDOXDWLQJ SRLQWV DORQJ WKH YDOXH IXQFWLRQ
&RPSDUHG ZLWK G\QDPLF SURJUDPPLQJ WKH HoHFWLYHQHVV RI WKH DOJRULWKP GHSHQGV RQ WKH QXPEHU
RI WLPHV WKH YDOXH IXQFWLRQV DUH HYDOXDWHG )RU WKH H[DPSOHV , FRPSXWH LQ WKH QH[W VHFWLRQ WKH
DOJRULWKP RQO\ HYDOXDWHV WKH YDOXH IXQFWLRQ D IHZ WLPHV EHIRUH LW pQGV WKH RSWLPDO VROXWLRQ
( [DPSOHV
7KLV VHFWLRQ FRPSXWHV VROXWLRQV WR WZR HFRQRPLHV
7KH H[DPSOHV DUH GHVLJQHG WR LOOXVWUDWH WKH
FDSDELOLWLHV RI WKH G\QDPLF SURJUDPPLQJ PHWKRGV GHYHORSHG LQ WKLV SDSHU
7KH pUVW H[DPSOH
XVHV WKH 'DQW]LJ:ROIH GHFRPSRVLWLRQ DOJRULWKP WR VROYH D SDUWLFLSDWLRQ FRQVWUDLQW SUREOHP 7KH
H[DPSOH GHPRQVWUDWHV WKH UROH WKDW DFWLRQ ORWWHULHV PD\ SOD\
7KH VHFRQG H[DPSOH ORRNV DW D
3ODQQHU V SUREOHP WR HYDOXDWH WKH TXDOLWDWLYH SURSHUWLHV RI WKH RSWLPDO FRQWUDFW LQ D SUREOHP
ZKHUH WKH DJHQW FRQWUROV WZRGLPHQVLRQV RI WKH SUREDELOLW\ GLVWULEXWLRQ RI UHWXUQV
&RPSXWDWLRQ
$OO FRPSXWDWLRQDO UHVXOWV UHSRUWHG LQ WKLV VHFWLRQ ZHUH GRQH RQ D 5LVF ZRUNVWDWLRQ ZLWK
0% RI 5$0 7KH SURJUDPV ZHUH FRPSXWHG XVLQJ FRGH ZULWWHQ LQ 0DWODE Y DQG F
7KH
SURJUDPV FUHDWHG WKH FRQVWUDLQWV LQ 0DWODE DQG WKHQ FDOOHG WKH OLQHDU SURJUDPPLQJ URXWLQH DV D
IXQFWLRQ
7KH URXWLQH , XVHG LV OS VROYH YHUVLRQ ZKLFK LV ZULWWHQ LQ F
DV FRPSLOHG FRGH EXW LW LV HDVLHU WR SURJUDP LQ
0DWODE LV QRW DV IDVW
0RVW RI WKH QXPHULFDO ZRUN LQYROYHV WKH OLQHDU
SURJUDPPLQJ URXWLQH 7KH URXWLQH OS VROYH LV D OLQHDU SURJUDPPLQJ URXWLQH EDVHG RQ WKH VLPSOH[
URXWLQH ,W XVHV VSDUVH PDWUL[ WHFKQLTXHV WR VDYH RQ PHPRU\ DQG FRPSXWDWLRQDO FRVWV
( [DPSOH $FWLRQ /RWWHU LHV
&RQVLGHU DQ HFRQRP\ ZLWK D FRQWLQXXP RI DJHQWV RI PHDVXUH RQH HDFK RI ZKRP KDV WKH VDPH
SUHIHUHQFHV DQG KLV RZQ SURGXFWLRQ WHFKQRORJ\ (DFK DJHQW PD\ RQO\ VXSSO\ HoRUW RQ KLV RZQ SORW
DQG KLV HoRUW LV KLGGHQ IURP HYHU\RQH HOVH 2XWSXW LV SXEOLFO\ REVHUYHG KRZHYHU 7KH SUREDELOLW\
GLVWULEXWLRQ RI D SURMHFW V UHWXUQ LV RQO\ D IXQFWLRQ RI WKH DJHQW V HoRUW
7KH HFRQRP\ LV D FORVHG HFRQRP\ VR QR UHVRXUFHV PD\ qRZ LQ RU RXW
%HFDXVH WKHUH LV D
FRQWLQXXP RI DJHQWV DQG SURMHFW UHWXUQV DUH LQGHSHQGHQW WKHUH LV QR DJJUHJDWH XQFHUWDLQW\ 7KH
;
UHVRXUFH FRQVWUDLQW IRU WKH HFRQRP\ LV
} F T D
F
b T x
F T D
)RUPDOO\ WKLV FRQVWUDLQW LV LGHQWLFDO WR WKH XWLOLW\ IXQFWLRQ RI D ULVNQHXWUDO SULQFLSDO
0\ JRDO LV WR VROYH IRU DOORFDWLRQV WKDW WUHDW WKH DJHQWV
;
H[ DQWH
LGHQWLFDO VR , PD[LPL]H WKH
H[SHFWHG XWLOLW\ RI WKH UHSUHVHQWDWLYH DJHQW 7KH DOORFDWLRQ SUREOHP LQ WKLV HFRQRP\ LV
PD[
}
VXEMHFW WR D UHVRXUFH FRQVWUDLQW
SUREDELOLW\ PHDVXUH FRQVWUDLQW
y
} F T D X F D
F T D
LQFHQWLYH FRQVWUDLQWV
WHFKQRORJ\ FRQVWUDLQWV
DQG D
7KH SUREOHP LV IRUPDOO\ HTXLYDOHQW WR PD[LPL]LQJ WKH XWLOLW\
RI WKH DJHQW VXEMHFW WR WKH SULQFLSDO UHFHLYLQJ D UHVHUYDWLRQ OHYHO RI XWLOLW\
*ULG
7KH JULGV DUH
&
4
$
3UHIHUHQFHV
$JHQWV
SUHIHUHQFHV DUH X F D
I J
I J
I J
F
bD
8WLOLW\ LV FRQFDYH LQ FRQVXPSWLRQ DQG FRQYH[
LQ HoRUW
7HFKQRORJ\
7KH GLVWLQFWLYH IHDWXUH RI WKLV H[DPSOH LV WKH WHFKQRORJ\
,W FRQWDLQV D UDQJH RI DFWLRQV ZLWK
LQFUHDVLQJ UHWXUQV WR VFDOH DQG DQRWKHU UDQJH ZLWK GHFUHDVLQJ UHWXUQV WR VFDOH
GHQVLW\ IXQFWLRQ RI WKH KLJK RXWSXW T
S T
M
D
7KH SUREDELOLW\
JLYHQ WKH DFWLRQ LV
b b
Db
D
D
7KH SUREDELOLW\ GHQVLW\ IXQFWLRQ RI WKH ORZ RXWSXW T
M
D
y
LV VLPSO\ S T
M
D
D 7KH SUREDELOLW\ GHQVLW\ IXQFWLRQ LV EHVW XQGHUVWRRG E\ H[DPLQLQJ )LJXUH
bS
T
1
0.9
p(q=1.5|a)
0.8
0.7
probability
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.2
0.4
0.6
0.8
1
action
1.2
1.4
1.6
1.8
2
)LJXUH 3UREDELOLW\ RI WKH KLJK RXWSXW JLYHQ WKH DFWLRQ IRU ([DPSOH
&RPSXWDWLRQ
7KHUH DUH FRQVXPSWLRQ JULG SRLQWV RXWSXW JULG SRLQWV DQG DFWLRQ JULG SRLQWV
7R
VROYH WKLV SURJUDP GLUHFWO\ QRW XVLQJ GHFRPSRVLWLRQ ZRXOG UHTXLUH VROYLQJ D SUREOHP ZLWK
YDULDEOHV DQG FRQVWUDLQWV :KLOH WKLV LV QRW D ODUJH SURJUDP E\ PDQ\ VWDQGDUGV LW FDXVHG
0DWODE WR UXQ RXW RI PHPRU\ %\ FRQWUDVW XVLQJ WKH GHFRPSRVLWLRQ DOJRULWKP UHTXLUHV FRPSXWLQJ
OLQHDU SURJUDPV ZLWK YDULDEOHV DQG FRQVWUDLQWV SHU LWHUDWLRQ
0\ FRGH pUVW FUHDWHG WKH FRQVWUDLQW PDWUL[ IRU HDFK VXESUREOHP DQG VDYHG WKHP WR GLVN 1H[W
DQ LQLWLDO IHDVLEOH SRLQW ZDV REWDLQHG E\ VROYLQJ HDFK VXESUREOHP XVLQJ ZHLJKWV RI
DQG
,I D VROXWLRQ H[LVWV IRU WKH SUREOHP WKHVH H[WUHPH SDLUV RI 3ODQQHU V ZHLJKWV SURGXFH D OHYHO RI
a D VROXWLRQ WR WKH PDVWHU
WKH UHVRXUFH FRQVWUDLQW DERYH DQG EHORZ ]HUR :LWK WKHVH SRLQWV LQ ;
L
SURJUDP ZLOO H[LVW 2Q WKH pUVW SDVV WKURXJK WKH VXESUREOHPV RQO\ QLQH RI WKH VXESUREOHPV ZHUH
IRXQG WR KDYH D IHDVLEOH VROXWLRQ
1RW VXUSULVLQJO\ WKH LQIHDVLEOH RQHV ZHUH DFWLRQV LQ WKH VKDUSO\
LQFUHDVLQJ UHWXUQV DQG WKH VKDUSO\ GLPLQLVKLQJ UHWXUQV UDQJH RI $
7KH DOJRULWKP NHSW WUDFN RI
IHDVLEOH VXESUREOHPV DQG RQO\ FRPSXWHG WKHP RQ VXEVHTXHQW LWHUDWLRQV 7R XVH WKH GHFRPSRVLWLRQ
b
DOJRULWKP , VHW D VWRSSLQJ FULWHULRQ RI
RQ WKH RSWLPXP FRQGLWLRQ
7KH SURJUDP VROYHG TXLFNO\ 7KH WRWDO WLPH LW WRRN WR VROYH WKLV SURJUDP XVLQJ WKH GHFRPSR
VLWLRQ DOJRULWKP ZDV FSX VHFRQGV DQG LW RQO\ WRRN WKUHH LWHUDWLRQV WR FRQYHUJH $OPRVW KDOI
RI WKH WLPH FSX VHFRQGV ZDV XVHG E\ 0DWODE WR FUHDWH WKH FRQVWUDLQW PDWULFHV (DFK LWHUDWLRQ
ZDV UHODWLYHO\ TXLFN RQ WKH RUGHU RI WR FSX VHFRQGV 7KH UHDVRQ IRU WKLV LV WKDW RQO\ WKH QLQH
VXESUREOHPV ZLWK IHDVLEOH VROXWLRQV QHHGHG WR EH FRPSXWHG
2Q WKH pUVW LWHUDWLRQ ZKHQ DOO
ZHUH FKHFNHG WKH SURJUDP WRRN FSX VHFRQGV
6ROXWLRQ
7KH VROXWLRQ WR WKH SUREOHP LQFOXGHV D ORWWHU\ RYHU WKH ORZHVW DFWLRQ DQG D UHODWLYHO\ SURGXFWLYH
DFWLRQ 7KH ORWWHU\ LV
} D
} D
6OLJKWO\ PRUH WKDQ SHUFHQW RI WKH SRSXODWLRQ LV DVVLJQHG WKH ORZ HoRUW DQG QHDUO\ SHUFHQW
DUH DVVLJQHG WKH KLJK HoRUW
)RU HDFK RI WKH WZR DVVLJQHG DFWLRQV WKHUH LV D FRPSHQVDWLRQ VFKHGXOH
)RU WKH ORZ DFWLRQ
WKH VFKHGXOH LV
M
D
M
D
} F
T
} F
T
1R LQFHQWLYH FRQVWUDLQW ELQGV IRU ORZHVW DFWLRQ LQ WKLV SUREOHP VR DQDO\WLFDOO\ WKHUH VKRXOG EH
IXOO ULVNVKDULQJ DFURVV WKH WZR RXWSXWV $V SUHGLFWHG E\ WKHRU\ ULVNVKDULQJ LV QHDUO\ SHUIHFW LQ
WKLV H[DPSOH $Q\ GLoHUHQFH KHUH LV GXH WR QXPHULFDO DSSUR[LPDWLRQ
)RU WKH KLJKHU DFWLRQ D
WKHUH LV DQ LQFHQWLYH SUREOHP
&RQVHTXHQWO\ FRQVXPSWLRQ
QHHGV WR GHSHQG RQ RXWSXW 7KH FRPSHQVDWLRQ VFKHGXOH IRU SHRSOH UHFRPPHQGHG WKLV DFWLRQ LV
M
D
M
D
} F
T
} F
T
} F
M
T
D
7KH FRQVXPSWLRQ ORWWHU\ WKDW RFFXUV LI WKH ORZ RXWSXW LV UHDOL]HG LV RI QR HFRQRPLF FRQWHQW ,W LV
VROHO\ D UHVXOW RI WKH JULG
,Q WHUPV RI )LJXUH DJHQWV UHFRPPHQGHG WKH ORZ DFWLRQ DUH UHFHLYLQJ D XWLOLW\ SRLQW LQ VHW
< DQG WKH RWKHU DJHQWV DUH UHFHLYLQJ D XWLOLW\ SRLQW LQ VHW <
'HVSLWH WKH FRQYH[LW\ LQ HoRUW
GLVXWLOLW\ WKH LQFUHDVLQJ UHWXUQV LQ SURGXFWLRQ DUH VR VWURQJ LQ WKLV HFRQRP\ WKDW LW LV ZRUWK
VSOLWWLQJ WKH SRSXODWLRQ LQWR DJHQWV ZKR ZRUN ORZ DQG KLJK DPRXQWV
$ VXUSULVLQJ FRPSXWDWLRQDO IHDWXUH RI WKH UHVXOWV ZDV WKH ORZ QXPEHU RI LWHUDWLRQV EHWZHHQ
WKH PDVWHU DQG VXESUREOHP SURJUDPV
,Q JHQHUDO SUREOHPV PD\ WDNH PRUH LWHUDWLRQV WR pQLVK
, DOVR FRPSXWHG WKH SUREOHP ZKHUH WKH HFRQRP\ RZHV UHVRXUFHV WR WKH UHVW RI WKH ZRUOG WKDW
LV :
b
)RU WKLV SDUDPHWHU VSHFLpFDWLRQ DOO DJHQWV DUH UHTXLUHG WR ZRUN D UHODWLYHO\ KLJK
DPRXQW 7KH UHDVRQ LV WKDW WKH SURJUDP QHHGV WR H[WUDFW UHVRXUFHV WR WUDQVIHU WR WKH UHVW RI WKH
ZRUOG
%HFDXVH DJHQWV ZRUN WKH KLJK DPRXQW WKH FRPSHQVDWLRQ VFKHGXOH LV RXWSXW GHSHQGHQW
DQG ORRNV PXFK OLNH WKH VFKHGXOH IRU WKRVH ZRUNLQJ KLJK DPRXQWV LQ WKH SUHYLRXV H[SHULPHQW
$VLGH IURP WKH GHJHQHUDF\ LQ DFWLRQ ORWWHULHV WKH PDLQ GLoHUHQFH EHWZHHQ WKLV DQG WKH SUHYLRXV
H[SHULPHQW LV WKDW WKLV SUREOHP WRRN LWHUDWLRQV WR FRQYHUJH 7KH H[WUD LWHUDWLRQV DGGHG VRPH
WLPH WR WKH FRPSXWLQJ D VROXWLRQ FDXVLQJ WKH SURJUDP WR VROYH LQ FSX VHFRQGV
( [DPSOH 7 ZRGLPHQVLRQDO DFWLRQ FKRLFH
,Q WKLV H[DPSOH , VWXG\ D SULQFLSDODJHQW SUREOHP ZKHUH WKH DJHQW FKRRVHV WKH PHDQ DQG YDULDQFH
RI D SURMHFW V UHWXUQ 7KH DJHQW LV ULVN DYHUVH DQG UHFHLYHV GLVXWLOLW\ LI KH LQFUHDVHV WKH PHDQ RU
ORZHUV WKH YDULDQFH RI WKH SURMHFW V UHWXUQ
7KH SULQFLSDO LV ULVNQHXWUDO LQ FRQVXPSWLRQ EXW KH
LV H[WUHPHO\ DYHUVH WR ORZ UHWXUQV $ SRVVLEOH LQWHUSUHWDWLRQ LV WKDW WKH SULQFLSDO ORVHV FRQWURO RI
WKH SURMHFW LI UHWXUQV DUH EHORZ D FHUWDLQ DPRXQW PD\EH EHFDXVH KH KDV WR PDNH D GHEW SD\PHQW
:LWK WKHVH SUHIHUHQFHV WKH SULQFLSDO GHVLUHV D KLJK PHDQ ORZ YDULDQFH HoRUW GHFLVLRQ E\ WKH DJHQW
, IRUPXODWH WKLV SUREOHP DV D 3ODQQHU V SURJUDP 0\ LQWHUHVW LV WKH TXDOLWDWLYH SURSHUWLHV RI
WKH RSWLPDO FRQWUDFW DQG VLQFH WKH 3ODQQHU V SURJUDP LV HDVLHU WR FRPSXWH , IROORZ WKLV VWUDWHJ\
7KH 3ODQQHU V ZHLJKW ZDV VHW WR LQ WKLV H[DPSOH
*ULGV
/HW $P DQG $Y URXJKO\ UHIHU WR WKH PHDQ DQG VWDQGDUG GHYLDWLRQ RI WKH SURMHFW UHVSHFWLYHO\
7KH JULGV DUH
I J
I J
I J
$P
I J
$Y
$
$P d $Y
&
4
0.1
(a ,a )
m v
(a ,a )
m v
(am,av)
(am,av)
0.09
0.08
=
=
=
=
(1.1,0.30)
(0.9,0.45)
(0.7,0.60)
(1.1,0.60)
0.07
probability
0.06
0.05
0.04
0.03
0.02
0.01
0
0
0.2
1
output
2
)LJXUH 3UREDELOLW\ GHQVLW\ IXQFWLRQ IRU VHOHFWHG DFWLRQV
7KH JULG RI DFWLRQV LV D WZRGLPHQVLRQDO YHFWRU
3UHIHUHQFHV
3UHIHUHQFHV DUH
X F DP DY
F
Z F T
b DP
DY
T b F b
T x
T bF
T !
DQG
7KH DJHQW LV ULVNDYHUVH DQG GLVOLNHV KLJK PHDQ DQG ORZ YDULDQFH DFWLRQV
7KH SULQFLSDO LV ULVN
QHXWUDO EXW ZLWK DQ H[WUHPH DYHUVLRQ WR ORZ RXWSXW
7HFKQRORJ\
7KH WHFKQRORJ\ LV D URXJK DSSUR[LPDWLRQ WR D QRUPDO GLVWULEXWLRQ )RU HDFK
DP DY WKH SURE
DELOLW\ GHQVLW\ RI RXWSXW LV REWDLQHG E\ HYDOXDWLQJ WKH QRUPDO GLVWULEXWLRQ IRU DOO 4 DQG WKHQ
QRUPDOL]LQJ VR WKDW
3
T
S TMDP DY
)LJXUH VKRZV WKH GLVWULEXWLRQ IRU D VHOHFWLRQ RI WKH
DFWLRQ SDLUV
6ROXWLRQ
%HFDXVH RI WKH SULQFLSDO V DYHUVLRQ WR ORZ RXWSXWV WKH SULQFLSDO ZDQWV DQ DFWLRQ WKDW PLQLPL]HV
WKH SUREDELOLW\ RI RXWSXWV OHVV WKDQ
$FFRUGLQJO\ WKH VROXWLRQ LV D GHJHQHUDWH ORWWHU\ ZLWK
1.8
c(q)
1.6
1.4
consumption
1.2
1
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
output
1.2
1.4
1.6
1.8
2
)LJXUH &RQVXPSWLRQ VKDULQJ UXOH IRU ([DPSOH
SUREDELOLW\ RQH RQ WKH DFWLRQ SDLU
DP DY
PHQWV WKLV DFWLRQ SDLU QHHGV WR GR WZR WKLQJV
7KH FRPSHQVDWLRQ VFKHGXOH WKDW LPSOH
)LUVW LW KDV WR HQVXUH WKDW WKH DJHQW GRHV QRW
WDNH D ORZ PHDQ DFWLRQ 6HFRQG WKH VFKHGXOH KDV WR VWRS WKH DJHQW IURP WDNLQJ D KLJK YDULDQFH
DFWLRQ ,Q WKLV SUREOHP WKHVH DUH SRWHQWLDOO\ FRQqLFWLQJ JRDOV )RU H[DPSOH ORZ FRQVXPSWLRQ IRU
KLJK RXWSXWV UHZDUGV KLJK YDULDQFH DFWLRQV DQG SXQLVKHV ORZ PHDQ DFWLRQV 7KH SURJUDP ZHLJKV
DOO RI WKH LQFHQWLYH HoHFWV DQG LPSOHPHQWV WKH KLJK PHDQ ORZ YDULDQFH DFWLRQ E\ SXQLVKLQJ WKH
DJHQW IRU ORZ DQG KLJK RXWSXWV DQG UHZDUGLQJ KLP IRU LQWHUPHGLDWH RXWSXWV )LJXUH VKRZV WKH
RSWLPDO FRPSHQVDWLRQ VFKHGXOH ZKLFK LV QRQPRQRWRQLF
&RPSXWDWLRQDO UHVXOWV
7KLV SURJUDP LV D ODUJH OLQHDU SURJUDP ZLWK YDULDEOHV DQG FRQVWUDLQWV
6ROYLQJ LW
XVLQJ WKH 'DQW]LJ:ROIH GHFRPSRVLWLRQ DOJRULWKP UHTXLUHV VROYLQJ OLQHDU SURJUDPV ZLWK
YDULDEOHV DQG FRQVWUDLQWV
,W WRRN FSX PLQXWHV WR FRPSXWH WKLV SUREOHP 6OLJKWO\ PRUH
WKDQ FSX PLQXWHV ZDV VSHQW FUHDWLQJ WKH FRQVWUDLQWV 7KH UHVW RI WKH WLPH ZDV VSHQW VROYLQJ
WKH VXESUREOHPV
7KH DOJRULWKP JUHDWO\ LQFUHDVHV WKH QXPEHU RI DFWLRQV WKDW FDQ EH LQFOXGHG LQWR WKH SUREOHP
)
R U WKLV SUR EOH P WKH
PH PR U\
OLPLW R Q WKH
QXPEH U R I D F WLR QV , F R XOG F R PSXWH
F R QVWUD LQWV
J OR ED OO\
Z
D V $
W
D F WLR QV , UD Q LQWR
200
180
160
140
time
120
100
80
60
40
20
0
0
10
20
30
40
number of actions in grid
50
60
70
)LJXUH &RPSXWDWLRQ WLPH LQ FSX PLQXWHV DV D IXQFWLRQ RI WKH VL]H RI WKH DFWLRQ JULG
7KH QDWXUH RI WKH VXESUREOHPV VXJJHVW WKDW WKH WLPH WR FRPSXWH VROXWLRQ LV URXJKO\ OLQHDU LQ WKH
QXPEHU RI DFWLRQV $V WKH QXPEHU RI DFWLRQV LQFUHDVHV RQH PRUH VXESUREOHP QHHGV WR EH FRPSXWHG
ZKLOH HDFK VXESUREOHP RQO\ LQFUHDVHV E\ RQH FRQVWUDLQW )LJXUH VKRZV WKH FRPSXWDWLRQ WLPH LQ
FSX PLQXWHV DV D IXQFWLRQ RI WKH VL]H RI WKH DFWLRQ JULG
7KH [D[LV OLVWV WKH QXPEHU RI DFWLRQV
ZKLOH WKH \D[LV OLVWV WKH FSX PLQXWHV UHTXLUHG WR FRPSXWH HDFK SUREOHP
D VXEVHW RI $ ZDV XVHG
,Q HDFK H[SHULPHQW
)LJXUH GHPRQVWUDWHV WKDW IRU WKLV H[DPSOH WKH WLPH UHTXLUHG ZKLOH
FRQYH[ LV FORVH WR OLQHDU
( [WHQVLRQV
$Q\ OLQHDU SURJUDP ZLWK D EORFNDQJXODU FRQVWUDLQW PDWUL[ FDQ EH FRPSXWHG XVLQJ WKH 'DQW]LJ
:ROIH GHFRPSRVLWLRQ DOJRULWKP 6HYHUDO LPSRUWDQW H[WHQVLRQV RI WKH PRUDOKD]DUG SUREOHPV UHWDLQ
WKLV VWUXFWXUH LQFOXGLQJ VRPH PXOWLSOHDJHQW PRGHOV DQG PRGHOV ZLWK SURGXFWLRQ LQSXWV
)RU D PXOWLSOHDJHQW PRGHO WR EH EORFNDQJXODU GHFLVLRQV PDGH E\ RQH DJHQW FDQ RQO\ DoHFW
RWKHU DJHQWV WKURXJK WKH FRQQHFWLQJ FRQVWUDLQWV $Q H[DPSOH WKDW VDWLVpHV WKLV FRQGLWLRQ LV RQH
ZKHUH DJHQWV WHFKQRORJLHV DUH LQGHSHQGHQW DQG WKHUH LV D ULVNQHXWUDO SULQFLSDO ZKR KDV DFFHVV
WR RXWVLGH IXQGV 0DWKHPDWLFDOO\ HTXLYDOHQW LV WKH SUREOHP ZKHUH WKHUH LV D pQLWH QXPEHU RI
DJHQW W\SHV HDFK RI ZKRP LV D IUDFWLRQ RI WKH SRSXODWLRQ WKDW IDFH DQ HFRQRP\ZLGH UHVRXUFH
FRQVWUDLQW OLNH LQ ([DPSOH
$QRWKHU LPSRUWDQW FODVV RI PRGHOV WKDW WKH WHFKQLTXH FDQ EH DSSOLHG WR LV PRUDOKD]DUG
PRGHOV ZKHUH WKHUH LV DOVR D SXEOLFO\ REVHUYHG LQSXW LQWR WKH WHFKQRORJ\ ,Q WKHVH PRGHOV WKHUH
ZRXOG EH RQH VXESUREOHP SHU HoRUWLQSXW SDLU 7KH FRQQHFWLQJ FRQVWUDLQWV ZRXOG GHSHQG RQ WKH
VSHFLpFDWLRQ RI WKH SUREOHP )RU H[DPSOH LI WKHUH ZDV D FORVHG HFRQRP\ WKDW QRW RQO\ IDFHG D
FRQVXPSWLRQ UHVRXUFH FRQVWUDLQW OLNH LQ ([DPSOH EXW DOVR D UHVRXUFH FRQVWUDLQW RQ WKH
DPRXQW RI WKH LQSXW DYDLODEOH WR WKH HFRQRP\ WKHQ WKHUH ZRXOG EH DQ DGGLWLRQDO FRQQHFWLQJ
FRQVWUDLQW 7KH DGGLWLRQDO FRQQHFWLQJ FRQVWUDLQW ZRXOG FUHDWH RQH PRUH GXDO YDULDEOH LQ WKH
PDVWHU SURJUDP DQG DGG D WHUP WR WKH REMHFWLYH IXQFWLRQ FRUUHVSRQGLQJ WR WKH YDOXH RI LQSXW
UHVRXUFH FRQVWUDLQW ,I LQVWHDG WKH LQSXW LV SXUFKDVHG E\ WKH SULQFLSDO DW VRPH SULFH WKHQ WKH
PDVWHU SURJUDP ZRXOG RQO\ KDYH D UHVRXUFH FRQVWUDLQW DQG SUREDELOLW\ PHDVXUH FRQVWUDLQW MXVW
OLNH WKH PDVWHU SURJUDP LQ ([DPSOH
&RQFOXVLRQ
/LQHDU SURJUDPPLQJ LV DQ LPSRUWDQW WRRO IRU FRPSXWLQJ SULYDWHLQIRUPDWLRQ SUREOHPV 7KH
PHWKRG FDQ EH XVHG IRU SUREOHPV ZLWK DUELWUDU\ VSHFLpFDWLRQV RI SUHIHUHQFHV DQG WHFKQRORJ\
7KH 'DQW]LJ:ROIH GHFRPSRVLWLRQ DOJRULWKP H[SDQGV WKH FDSDELOLWLHV RI OLQHDU SURJUDPPLQJ E\
JUHDWO\ LQFUHDVLQJ WKH VL]H RI SUREOHPV WKDW PD\ EH FRPSXWHG 7KH DOJRULWKP ZDV GHPRQVWUDWHG
E\ FRPSXWLQJ VROXWLRQV WR WZR H[DPSOHV %RWK H[DPSOHV GHSDUWHG IURP WKH VWDQGDUG WHFKQRORJ\
DVVXPSWLRQV PDGH LQ WKH OLWHUDWXUH
5HIHU HQFHV
>@ %HUWVLPDV 'LPLWULV DQG -RKQ 1 7VLWVLNOLV
,QWURGXFWLRQ WR /LQHDU 2SWLPL]DWLRQ
%HOPRQW
0DVVDFKXVHWWV $WKHQD 6FLHQWLpF
>@ %R\G -RKQ + DQG %UXFH ' 6PLWK ?+RZ *RRG DUH 6WDQGDUG 'HEW &RQWUDFWV" 6WRFKDVWLF
YHUVXV 1RQVWRFKDVWLF 0RQLWRULQJ LQ D &RVWO\ 6WDWH 9HULpFDWLRQ (QYLURQPHQW
%XVLQHVV
-RXUQDO RI
>@ 'DQW]LJ * % DQG 3 :ROIH ?7KH 'HFRPSRVLWLRQ 3ULQFLSOH IRU /LQHDU 3URJUDPV 2SHUDWLRQV
5HVHDUFK
>@ +DQVHQ *DU\ ' ?,QGLYLVLEOH /DERU DQG WKH %XVLQHVV &\FOH -RXUQDO RI 0RQHWDU\ (FRQRPLFV
>@ /HKQHUW $QGUHDV ?6RORZ *URZWK 0RGHOV DQG 0RUDO +D]DUG 0DQXVFULSW
>@ /XHQEHUJHU 'DYLG *
,QWURGXFWLRQ WR /LQHDU DQG 1RQOLQHDU 3URJUDPPLQJ
5HDGLQJ 0DV
VDFKXVHWWV $GGLVRQ:HVOH\ 3XEOLVKLQJ &RPSDQ\ ,QF
>@ 0RRNKHUMHH 'LOLS DQG ,YDQ 3QJ ?2SWLPDO $XGLWLQJ ,QVXUDQFH DQG 5HGLVWULEXWLRQ 4XDU
WHUO\ -RXUQDO RI (FRQRPLFV
0D\
>@ 0\HUVRQ 5RJHU % ?2SWLPDO &RRUGLQDWLRQ 0HFKDQLVPV LQ *HQHUDOL]HG 3ULQFLSDO$JHQW 3URE
OHPV
-RXUQDO RI 0DWKHPDWLFDO (FRQRPLFV
-XQH
> @ 3UHVFRWW (GZDUG & DQG 5REHUW 0 7RZQVHQG ?3DUHWR 2SWLPD DQG &RPSHWLWLYH (TXLOLEULD
ZLWK $GYHUVH 6HOHFWLRQ DQG 0RUDO +D]DUG (FRQRPHWULFD -DQXDU\ D
>@ 3UHVFRWW (GZDUG 6 DQG 5REHUW 0 7RZQVHQG ?7KHRU\ RI WKH )LUP $SSOLHG 0HFKDQLVP
'HVLJQ 0DQXVFULSW
>@ 5RJHUVRQ 5LFKDUG ?,QGLYLVLEOH /DERU /RWWHULHV DQG (TXLOLEULXP
(FRQRPLFV
-RXUQDO RI 0RQHWDU\
-DQXDU\
>@ 5RJHUVRQ :LOOLDP ?7KH )LUVW2UGHU $SSURDFK WR 3ULQFLSDO$JHQW 3UREOHPV (FRQRPHWULFD
>@ 7RZQVHQG 5REHUW 0 ?,QIRUPDWLRQ &RQVWUDLQHG ,QVXUDQFH 7KH 5HYHODWLRQ 3ULQFLSOH ([
WHQGHG
-RXUQDO RI 0RQHWDU\ (FRQRPLFV
>@ 7RZQVHQG 5REHUW 0
7KH 0HGLHYDO 9LOODJH (FRQRP\ $ 6WXG\ RI WKH 3DUHWR 0DSSLQJ LQ
*HQHUDO (TXLOLEULXP 0RGHOV
3ULQFHWRQ 1- 3ULQFHWRQ 8QLYHUVLW\ 3UHVV
@FedFRASER