• Non ci sono risultati.

Algorithms for the verification, computation and learning of equilibria in extensive-form games

N/A
N/A
Protected

Academic year: 2021

Condividi "Algorithms for the verification, computation and learning of equilibria in extensive-form games"

Copied!
207
0
0

Testo completo

(1)

)&#.(#) # #&() #*,.#'(.) # &..,)(#6 ( ),'4#)(  #)#(!!(,#         [   

), ." 0,#ŀ.#)(6 )'*/..#)( ( &,(#(!

) +/#&#,# #( 2.(-#07 ),'

!'-).),& #--,..#)( ) 9 #) ()44) 0#-),-9 ,) 8 #)& ..# /.),9 ,) 8 )(.&& #/.) /*,0#-), ) ." ).),& ,)!,'9 ,) 8 ,&) 8 #),#(#

hfgi 7 

(2)

śŘŕŠőŏŚŕŏś Őŕ ŕŘōŚś

#*,.#'(.) # &..,)(#6 ( ),'4#)(  #)#(!!(,# #44 )(,)  #(# ih6 7hfgii 7 #&()

(3)
(4)
(5)

###

-.,.

Ļ -./3 ) -.,.!#7#(.,.#)( -#./.#)(- "- ,(.&3 ,#0 #(,-#(! ..(.#)( #( ,.#ŀ#& #(.&&#!( 1#." ." #' ) -#!(#(! /.)()')/- -) .1, !(.- & .) . )*.#7 '&&38 Ļ- -#./.#)(- , /-.)',#&3 ')& - !'- DgoE #( 1"#" ." '"(#-' -,#- ." ,/&- ( -.,.!#- 7 -,# ." "0#), ) ." !(.-8 ,.#/&, ..(.#)( #- )7 /- )( ." -./3 ) ),'& '.")- .) ."),.#&&3 !/,(7 . ." )*.#'&#.3 ) ." !(.-[ "0#),8 ' ."),3 ( '#,))()'#- *,)0# '."'.#& .))&- .) ')& -.,.!#7 #(.,.#)( -#./.#)(- ( ",.,#4 ." **,)*,#. -)&/7 .#)( )(*.-8 )10,6 ."3 ) (). *,)0# )'*/..#)(& .))&- .) ŀ( -)&/.#)(-8 Ļ#- *,)&'6 )'')(&3 && +/#&#7

,#/' )'*/..#)(6 #- #(-. (.,& #( )'*/., -#(6 1")-

#' #(&/- ----#(! ." )'*&2#.3 ) ŀ(#(! ( 2. ), **,)2#'. -)&/.#)(6 -#!(#(! 2. ), **,)2#'. &!)7 ,#."'-6 ( 0&/.#(! ." **&#.#)( ) ." &!),#."'- #( *,.#& -..#(!- DkoE8 ( ."#- ."-#-6 1 )/- )( ()(7))*,.#0 !(,&7-/' 2.(-#07 ),' !'-8 2.(-#07 ),' !'- DgoE , '), -/#.& .) ,*,-(. ,&71),& -#./.#)(- *,)0##(!  ,#", ,*,-(..#)( ."( -.,.!#7 ),' !'-6 1", ." -+/(7 .#& -.,/./, ) #-#)(7'%#(! #- -,# 2*&##.&3 ( " !(. #- &&)1 .)  , .) "(! ", '#( - 0(.-/( )&8 "#& #( 4,)7-/' 2.(-#07 ),' !'- ." '#( *,)&' #- .) -)&0 !'- ) &,! #'(-#)( B8!86 *)%, DhoEC6 #( !(,&7-/' 2.(-#07 ),' !'- .", , ).", #'*),7 .(. #--/-8 Ļ ')-. #'*),.(. #- ." ")# ) ." ')-. -/#.7 & -)&/.#)( )(*.9 #. *(- )( ." -(,#) ')&& 3 ." !'6 8!8 ." !(.-[ )'')( %()1&!6 ( #. *(-)( #.- )'*/.#&#.36 #88 ." ')/(. ) .#' ( ''),3 (7 --,3 .) -)&0 ." !'8  ( #(.# 3 .1) '#( -(,#)-6 ",.,#4 .",)/!" ." %()1&! 0#&& .) !(.-9 ." - 1", ." !(.- "0 )'')( #( ),'.#)( ( ." - 1", ."3 "0 #()'*&. #( ),'.#)(8 (.,-.#(!&36 1#." )'')( #( ),'.#)(6 ." **,)*,#. -)&/.#)( )(*.- ), 2.(-#07 ),' !'- ,ŀ( ." )(*. ) -" +/#&#,#/'6 1"#&6 1"( !(.- &,(6 ." **,)*,#7 . -)&/.#)( )(*.- ,&2 ." )(*. ) -" +/#&#,#/'8 ), *,#-&36 #( ." ŀ,-. -(,#)6 #. #- 1&& %()1( .". ." -" +/#&#,#/' #- (). -/#.&6 &&)1#(! -.,.!#- .)  ()(7 -+/(.#&&3 ,.#)(&8 Ļ !' ."),.# &#.,./, *,)0#- 

(6)

#0 (/', ) ,ŀ('(.- ) -" +/#&#,#/' ), 2.(-#07 ),' !'- .". , ." **,)*,#. -)&/.#)( )(*.-8 ), ."- -)&/.#)( )(*.- ." 0,#ŀ.#)( ( )'*/..#)( *,)&'-(  ",8 ( ."#- ."-#- 1 -")1 .". ), -)' -)&/.#)( )(*.- ." 0,#ŀ.#)( *,)&' #- -3 ( 1 -#!( &!)7 ,#."'- .) ŀ( -)' ,ŀ('(.- ) -" +/#&#,#/'8 "( ." #( ),'.#)( #- (). )'')( 0,3 !(. (- .) "0  -. ) &# - )0, ." )**)((.-[ "0#)/,8 Ļ#- &# - , /*.#(! /,#(! ." &,(#(! *,)--6 #88 1"#& ." !(.- ,7 *. ." !'8 ( ."#- ."-#- 1 #-/-- ." -/#.& -)&/.#)( )(*.- ), ."#- -(,#) ( 1 0&)* Ń#(. 0)&/.#)(7 ,3 !' ."),3 ."(#+/- ( &!),#."'- .". 1),%- 1#." ." -+/( ),' ,*,-(..#)( ) 2.(-#07 ),' !'- &7 &)1#(! ( 2*)((.#& ,/.#)( ) .#' ( -* 18,8.8 ." &!),#."'- *,-(. #( &#.,./,8

(7)

0

)'',#)

) -./#) # -#./4#)( # #(.,4#)( -.,.!# " ,(7 .'(. ,#0/.) /([..(4#)( ,-(. (& '*) &&[#(.&7 &#!(4 ,.#ŀ#& & ŀ( # *,)!.., !(.# /.)()'# *# # !#, )..#''(.8 /-. -#./4#)(# -)() )'/('(7 . ')&&. )' !#)"# DgoE #( /# #& '(#-') -,#0 & ,!)&  & -.,.!# -,#0)() #& )'*),.'(.) !&# !(7 .#8 ,.#)&, ..(4#)( î )&#44. -/&&) -./#) # '.)# ),'&# *, !,(.#, .),#'(. &[)..#'&#.à & )'*),.7 '(.) !&# !(.#8  .),# # !#)"#  & '#,))()'# ),(#-)() !&# -.,/'(.# '.'.## *, ')&&, & -#./4#)(# # #(.,4#)( -.,.!#  ,..,#44, !&# **,)*,#.# )(.7 .# # -)&/4#)(8 )'/(+/6 --# ()( ),(#-)() !&# -.,/'(.# )'*/.4#)(&# *, ,, & -)&/4#)(#8 /-.) *,)&'6 )7 '/('(. "#'.) &)&) !&# +/#&#,#6 î #(0 (.,& #( #( ),'.#6 #& /# )#..#0) #(&/ & 0&/.4#)( && )'7 *&--#.à # .,)0, /( -)&/4#)( -.. ) **,)--#'.6 *,)!.7 ., &!),#.'# -..# ) **,)--#'.#6  0&/., &[**&##&#.à !&# &!),#.'# #( -#./4#)(# ,&# DkoE8

( +/-. .-#6 # )&#44#') -/# !#)"# ()( ))*,.#0# #( ),' -.-  -)'' !(,&8 !#)"# #( ),' -.- DgoE -)() *#ę ..#  ,**,-(., & -#./4#)(# & ')() ,& ),(() /( ,**,-(.4#)( *#ę ,# # !#)"# #( ),' -.,.!#6 )0 & -.,/../, -+/(4#& && #-#)(# î 7 -,#.. -*&##.'(.  )!(# !(. " & *)--##&#.à # '#7 , -.,.!# )*) & 4#)(# &&[00,-,#)8 (., # !#)"# #( ),' -.-  -)'' 4,) #& *,)&' *,#(#*& î & ,#-)&/4#)7 ( # !#)"# # !,( #'(-#)( B*, -'*#) #& *)%, DhoEC6 (# !#)"# #( ),' -.-  -)'' !(,& # -)() &.,# #'7 *),.(.# *,)&'#8 & *#ę #'*),.(. î & -&. & *#ę ..) )(..) # -)&/4#)(9 --) #*( &&) -(,#) ')&&.) & !#))6 *, -'*#) & )()-(4 )'/( !&# !(.#6  #7 *( && -/ )''/.#&#.à6 #)î & +/(.#.à # .'*)  # ''),# (--,#  ,#-)&0, #& !#))8 )--#') #(.#ŀ, / -(,# *,#(#*&#6 ,..,#44, && )()-(4 #-*)7 (##& !&# !(.#9 #& -) #( /# !&# !(.# "(() #( ),'4#)( )'/(  #& -) #( /# --# "(() #( ),'4#)( #()'*&.8

¦ #(.,--(. )'6 )( #( ),'4#)( )'/(6 # )(..# # -)&/4#)( **,)*,#.# *, # !#)"# #( ),' -.- -)() # , 7 ŀ('(.# &&[+/#&#,#) # -"6 '(.6 +/() !&# !(.# 7 0)() **,(,6 # )(..# # -)&/4#)( **,)*,#.# ,#&--() #& )(..) # +/#&#,#) # -"8 #ę *,#-'(.6 (& *,#')

(8)

0# -(,#)6 î ().) " &[+/#&#,#) # -" ()( î ..)6 *,'.7 .() !&# !(.# # !#), -.,.!# " ()( -)() -+/(4#&7 '(. ,4#)(&#8  &..,./, # .),# # !#)"# ),(#- /( (/',) # ,Ń('(.# &&[+/#&#,#) # -" *, !#)"# #( ),' -.- " -)() # )(..# # -)&/4#)( **,)*,#.#8 , +/-.# )(..# # -)&/4#)( # *,)&'# # 0,#ŀ  )'*/.7 4#)( *)--)() --, #Ń#&#8 ( +/-. .-# ')-.,#') " *, &/(# )(..# # -)&/4#)( #& *,)&' && 0,#ŀ î #&  *,)!..#') &!),#.'# #( !,) # .,)0, &/(# ,Ń('(.# &&[+/#&#,#) # -"8 /() &[#( ),'4#)( ()( î )'/( )!(# !(. " #-)!() # /( #(-#' # ,(4 -/& )'7 *),.'(.) !&# 00,-,#8 /-. ,(4 -)() !!#),(. /,(. #& *,)--) # **,(#'(.)6 #)î '(., !&# !(.# ,#*.)() #& !#))8 ( +/-. .-# #-/.#') # *)--##&# )(.7 .# # -)&/4#)( *, +/-.) -(,#)  -0#&/**#') .(#" # .),# # !#)"# 0)&/4#)(,# Ń#(.#  &!),#.'# " -# *7 *&#() #,..'(. && ,**,-(.4#)( #( ),' -+/(4 & !#)) #( ),' -.- *,'..() /( ,#/4#)( -*)((7 4#& & .'*)  &&) -*4#) ,#-*..) !&# &!),#.'# *,-(.# #( &..,./,8

(ŀ( 0&/.#') -*,#'(.&'(. !&# &!),#.'# *,-(..# #( +/-. .-#8

(9)

)(.(.-g (.,)/.#)( g g8g Ļ #' ) ."#- 1),% 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 i g8h -," )(.,#/.#)(- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 j g8i Ļ-#- -.,/./, 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 m h ,&#'#(,#- o h8g ' ŀ(#.#)( 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 o h8h ' ( -.,.!3 ,*,-(..#)(- 8 8 8 8 8 8 8 8 8 8 gh h8i ,./,.#)( )0, -.,.!#- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 gn h8j '- 1#." *)*/&.#)(- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 gn h8k )&/.#)( )(*.- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 hf h8l )'*/..#)(& )'*&2#.3 &--- 8 8 8 8 8 8 8 8 8 8 8 hl h8m .)"-.# !'- ( -)&/.#)( )(*.- 8 8 8 8 8 8 8 hn h8n 0)&/.#)(,3 !' ."),3 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 ho h8o 7&,(#(! 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 if i .. ) ." ,. ii

,#ŀ.#)(()'*/..#)() -"+/#&#,#/',7

ŀ('(.-

io

j Ń#(.&!),#."'- ),."0,#ŀ.#)(*,)&') -+/(7 .#& +/#&#,#/' jg j8g  0,#ŀ.#)( 1"( ." ----'(. #- !#0( 8 8 8 8 8 jh j8h  0,#ŀ.#)( 1#." .1) !(.- 1"( )(&3 ." -.,.7 !3 *,)ŀ& #- !#0( 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 kk j8i &. 1),%- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 ln 0##

(10)

0###  k 2.(-#07 ),'*, .+/#&#,#/')'*/..#)(1#.".1)7 *&3, !'- mg k8g  ( *,./, !'- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 mh k8h +/#&#,#/' )(-.,#(.- ,#0.#)( 8 8 8 8 8 8 8 8 8 8 mh k8i .(,  ),'/&.#)( 8 8 8 8 8 8 8 8 8 8 8 8 8 8 mj k8j 0#- '%[- &!),#."' 8 8 8 8 8 8 8 8 8 8 8 8 8 8 ml k8k 2*,#'(.& 0&/..#)( 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 nh k8l &. 1),%- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 ok l )'*/.#(! +/#&#,# #( .1)7*&3, 4,)7-/' )(.#(/)/--.)"-.# !'- 1#." -1#."#(! )(.,)&&, oo l8g +/#&#,#/' )'*/..#)( 1#." *)&3()'#& !'- 8 8 gff l8h +/#&#,#/' **,)2#'.#)( 1#." ()(7*)&3()'#& !'-gfn l8i 2*,#'(.& 0&/.#)( 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 ggj l8j )(&/-#)(- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 ggk

,(#(! #( 2.(-#07 ),' !'-

ggo

m Ń#(. 0)&/.#)(,3 3('#- #( 2.(-#07 ),' !'- ghg m8g #-,.7.#' ,*&#.), 3('#- ), -+/(7 ),'

,*,-(..#)( 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 ghh m8h *&#.), 3('#- ,&#4.#)( +/#0&( 8 8 8 8 8 ghm m8i )(.#(/)/-7.#' ,*&#.), 3('#- ), -+/(7

),' ,*,-(..#)( 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 gih m8j (&34#(! ." -.#&#.3 )  -.,.!3 *,)ŀ& 8 8 8 8 8 8 gij n 7&,(#(!-&!),#."' ),."-+/( ),') 2.(-#07

),' !'- gio

n8g 7&,(#(! ( -+/( ),' 8 8 8 8 8 8 8 8 8 8 8 8 gjf n8h 3('#& (&3-#- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 gjl n8i 2*,#'(.& ,-/&.- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 gkh o ,(#(!1#."2.(-#07 ),'!'-#(".,)!()/-*)*7

/&.#)(- gkm

o8g )&/.#)( )(*.- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 gkn o8h +/#&#,#/' ",.,#4.#)( 8 8 8 8 8 8 8 8 8 8 8 8 8 glg o8i )'*/..#)(& ,-/&.- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 glj o8j  ( &,(#(! 3('#- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 gmj o8k  -#'*& - -./3 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 gmm

(11)

 #2 gf )(&/-#)(- ( /./, 1),% gng gf8g )(&/-#)(- 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 gng gf8h /./, 1),% 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 gnh  )..#)( gnk #&#)!,*"3 gno

(12)
(13)

(.,)/.#)(

g

Ļ -./3 ) -.,.!#7#(.,.#)( -#./.#)(- "- ,(.&3 ,#0 #(7 ,-#(! ..(.#)( #( ,.#ŀ#& #(.&&#!( 1#." ." #' ) -#!(#(! /.)()')/- -) .1, !(.- & .) . )*.#'&&38 Ļ- -#./.#)(-, /-.)',#&3 ')& - !'- DgoE #( 1"#" ." '"(#-' 7 -,#- ." ,/&- ( -.,.!#- -,# ." "0#), ) ." !(.-8 ,.#/&, ..(.#)( #- )/- )( ." -./3 ) ),'& '.")- .) ."),.#&&3 !/,(. ." )*.#'&#.3 ) ." !(.-[ "0#),8 ' ."),3 ( '#,))()'#- *,)0# ." ')-. &!(. ),'& ), -.,.!#7#(.,.#)( -(,#)- DgoE8 &&7%()1( -/-- /& *7 *&#.#)(- - )( ."- '.")- ,6 8!86 #( *"3-#& -/,#.3 Dk6 jfE6 *)%, DhnE ( #&&#, !'- DgE6 )()'# .,(-.#)(- Dik6 khE8 ' ."),3 ( '#,))()'#- *,)0# '."'.#& .))&-.) ')& -.,.!#7#(.,.#)( -#./.#)(- ( ",.,#4 ." **,)7 *,#. -)&/.#)( )(*.-8 )10,6 ."3 ) (). *,)0# )'*/.7 .#)(& .))&- .) ŀ( -)&/.#)(-8 Ļ#- *,)&'6 )'')(&3 && +/#7 &#,#/' )'*/..#)(6 #- #(-. (.,& #( )'*/., -#(6 1")- #' #(&/- ----#(! ." )'*&2#.3 ) ŀ(#(! ( 2. ), **,)2#'. -)&/.#)(6 -#!(#(! 2. ), **,)2#'. &!),#."'-6 ( 0&/.#(! ." **&#.#)( ) ." &!),#."'- #( *,.#& -..#(!- DkoE8

( ."#- ."-#-6 1 1),% 1#." ()(7))*,.#0 2.(-#07 ),' !'-8 2.(-#07 ),' !'- DgoE *,)0#  ,#", ,*,-(..#)( ."( -.,.!#7 ),' !'-6 1", ." -+/(.#& -.,/./, ) #-#)(7

(14)

Ș8 ŚŠŞśŐšŏŠŕśŚ

'%#(! #- -,# 2*&##.&3 ( " !(. #- &&)1 .)  , .) "(! ", '#( - 0(.- /( )&8 Ļ -./3 ) 2.(-#07 ),' !'- #- /-.)',#&3 ,,# )/. #( !' ."),3 3 .,(-&.#(! ." !'- 3 '(- ) ./&, ,*,-(..#)(- DkoE8 Ļ ')-. )'')( #- ." (),'& ),'8 .- 0(.! #- .". && ." ."(#+/- **&#& .) -.,.!#7 ),' !'- (  )*. &-) 1#." ."#- ,*,-(.7 .#)(8 )10,6 ." -#4 ) ." (),'&7 ),' ,*,-(..#)( !,)1-2*)((.#&&3 1#." ." -#4 ) ." !' .,6 ."/- #(! #'*,.#7 &8 ) #,/'0(. ."- #--/-6 -+/( ),' 1- *,)*)- DloE8 Ļ -+/( ),' *,)0#-  (/', ) 0(.!-9 #.- -#4 #- &#(7 , #( ." -#4 ) ." !' ., ( #. #- '), 2*,--#0 ."( ." (),'& ),'8 ( ." ).", "(6 -.(, &!),#."'# ), -.,.!#7 ),' !'- (().  )*. 1#." ." -+/( ),' ,+/#,#(! &.,(.#0  ") ."(#+/-8 Ļ (.,& -)&/.#)( )(*. #( ()(7))*,.#0 !' ."),3 #-." -" +/#&#,#/' BC8 . )(-.,#(- #-." -.,.!3 ) " !(. .)  )*.#'& !#0( ." -.,.!#- ) ." )**)((.-8 . #- 1&& %()1( .".  #- (). -/#.& ), 2.(-#07 ),' !'-6 &&)1#(! -.,.7 !#- .)  ()(7-+/(.#&&3 ,.#)(&8 Ļ !' ."),.# &#.,./, *,)0#-  (/', ) ,ŀ('(.- ) -" +/#&#,#/' ), 2.(-#07 ),' !'- .". , ." **,)*,#. -)&/.#)( )(*.- #( ." -(,7 #)- 1", ." --/'*.#)( )  B8!86 )'')( ( )'*&. #( ),'7 .#)( )0, *3)Ŀ-C , 0,#ŀ8 Ļ ')-. )'')( -)&/.#)( )(*.-, DllE9 -/!' *, . +/#&#,#/' BC DkkE 1"( #( ),'.#)( #-*, . ( -+/(.#& +/#&#,#/' BC DjgE6 +/-#7#-*, . +/#&#,#/' BC DlkE6 ( 2.(-#07 ),' *, . +/#&#,#/' BC DklE 1"( #( ),'.#)( #- #'*, .8 " -)&/.#)( )(*. #- **,)*,#. ),  -*#ŀ -#./.#)(8 ), #(-.(6  #- )'')(&3 )*. #( 3('# ,!#(#(! DhhE ( -#!(&#(! !'- DgoE6 1"#& *, . +/#&#,#/' )(*.- , *,.#/&,&3 -/#.& ), &,(#(! !(.-8 (6 /,7 #(! &,(#(! 3('#-6 !(.- 2*&), ()(7)*.#'& -.,.!#- 1#."  -'&& *,)#&#.3 DliE ( ."#- 2*&),.#)( "0- -  .,'& #( ." !(.-[ -.,.!#-8 ( ." ).", "(6 .", , '(3 ,&71),& -#./.#)(- 1", ." *#-.'# ,+/#,'(.- )  , (). -.#-ŀ8 ( ."- -(,7 #)- ."  #- (). ." **,)*,#. -)&/.#)( )(*. ( &-) #.- ,7 ŀ('(.- .". ,+/#, ." -' *#-.'# --/'*.#)(- , (). -/#.7 &8 0( 1"(  #- /- - -,#*.#0 .))& .) -./3 1". , -.& -..- ) &,(#(! 6 -)' *,)&'- ,#-6 &,(#(! !(.-"0#(! ()(7 -.& -..-6 ( .", ),  '3 "0  ()(7 h

(15)

g8g8 Ļ #' ) ."#- 1),%

-.#- .),3 -,#*.#0 *)1, DgnE8 Ļ  ),'(.#)( ,1%-)  */-" ,-,",- .,1%-) -#!( &.,(.#0 B,&2 (I,1%-), (,1%-)(7 +/#&#,#/'C -)&/.#)( )(*.- .%#(! &-) #(.) )/(. &,(#(! 37 ('#-6 8!86 ." &)- /(, ,.#)(& "0#), BC -. DmE #-  ()(7+/#&#,#/' )(*. ŀ( -  -. ) -.,.!#- .". )(.#(-." -. ,-*)(-- .) (3 '#2./, )0, #.-& ( (3 -.7,-*)(- 3('#- 1#&& -.3 1#."#( #. DijE8 #." 2.(-#07 ),' !'-6 ,7 &2#(! ." *#-.'# ,+/#,'(.- ) 6 #. #- *)--#& .) "0 -.& B+/#&#,#/'C -..- .". , (). - DgnE8 Ļ- +/#&#,#6 && -& 7)(ŀ,'#(! +/#&#,# B-C6 ,+/#, .". " !(. *&3- -.7 ,-*)(- -.,.!#- .) ", &# -6 /. ." &# - (  #(),,. )Ŀ ." +/#&#,#/' *." B1"#& ."3 , )(ŀ,' )(C8 Ļ )(*. #-*, .&3 -/#.& ), &,(#(! !(.-9 # !(.- ( (.#,&3 2*&), ." -.,.!3 *,)ŀ& -*6 ."3 1)/& "0 ),,. &# - 0,31", )( ." !' ., ( ."3 1)/& *&3 (  ), ( 6 /.6 #( *,7 .#6 &,(#(! !(.- ((). 2*&), ." 1")& -* ( .", ), ."3 ( "0 #(),,. &# - )0, -)' *),.#)( ) ." .,6 *&3#(! ."/- ( 8

g8g Ļ #' ) ."#- 1),%

( ."#- ."-#- 1 #' .) ,-- ." *,)&' ) -#!(#(! Ń#(. &!),#."'- ), ." 0,#ŀ.#)(6 )'*/..#)(6 ( &,(#(! ) +/#7 &#,# #( 2.(-#07 ),' !'-8 *#ŀ&&36 1 -./3 ." )&&)1#(! *,)&'-9 R 0,# 3#(! #  !#0( ----'(. #- ( 6 R !#0(  *,./,.#)( )0, ." "0#),& -.,.!#- ) ." !(.-6 )'*/.#(!  -.,.!3 *,)ŀ& .". #- ( 6 R -#!(#(! ( &!),#."' .) ŀ(  ,%)0 *, . +/#&#,#/' B C #( .1)7*&3, 4,)7-/' )(.#(/)/- -.)"-.# !'-1#." -1#."#(! )(.,)&6 R -#!(#(! ( **)-#. 0,-#)( ) ,*&#.), 3('#- .". &-1#." ." -+/( ),'6

R ŀ(#(!  0,#.#)( ) Q7&,(#(! &!),#."' .". #- #,.&3 **&#& .) ." -+/( ),'6

(16)

Ș8 ŚŠŞśŐšŏŠŕśŚ R ŀ(#(! ( )'*/.#(! ." **,)*,#. -)&/.#)( )(*.- #( !' 1#." *)*/&.#)(-8

g8h -,"

)(.,#/.#)(- ( ."#- -.#)( 1 -*,.&3 -,# )/, ,-," )(.,#/.#)( ), ." *,)&'- "#!"&#!". )08

,#ŀ.#)( ( )'*/..#)( ) -" +/#&#,#/'

,ŀ('(.-R "( ." ----'(. #- !#0( - #(*/.6 1 -#!( ( Ń#(. &!),#."' ,.# 3#(! .". ." ----'(. #- (  1#." ( ,7 #.,,3 (/', ) !(.-8

R "( )(&3 ." "0#),& -.,.!3 *,)ŀ& #- !#0( - #(*/.6 1 -#!( ( Ń#(. &!),#."' ,.# 3#(! .". ." -.,.!3 *,)ŀ& #- (  1#." .1)7!(. !'-: ."#- &!),#."' (  '*&)3 &-) .) ,#0 ." !(.-[ )(-#-.(. B#( ." -(- ) ,*- ( #&-)(C &# - ,)' ." -.,.!#- (  -#'7 *& 0,#.#)( (  '*&)3 ), ." 0,#ŀ.#)( )  1#." .1)7!(. !'-8 Ļ- ,-/&.- , *,-(. #( DhgE9 8 ..# ( 8 ()44)8 1 ,-/&.- )( ." 0,#ŀ.#)( ) -" ,ŀ(7 '(.- ), 2.(-#07 ),' !'-8 (  6 *!- ngi7nhf6 &(#6 *#(6 /( j7n hfgh8 8 ..# ( 8 ()44)8 Ń#(. &!),#."'- ), ." 0,#ŀ.#)( *,)7 &' ) -+/(.#& +/#&#,#/'8 /'#.. .) )/,(& ) ,.#ŀ#& (.&&#7 !( -,"8

R #0(  *,./,.#)( )0, ." "0#),& -.,.!#- ) ." 7 !(.-6 (  1#." .1)7!(. !(,&7-/' !'- (  )'*/. 2.&3 3 '(- )  0,#.#)( ) ." '%[- &7 !),#."' 1"#" ." *,./,.#)( #- )0, ." )Ń#(.- ) ." 0,#&- ( .", ), ." *,)&' #- #( PPAD8

(17)

g8h8 -," )(.,#/.#)(-R  *,)0# ( #.,.#0 -'#ŀ(#. *,)!,''#(! BC - &!),#."' .". )(0,!- .) (  1"( )." ." ,7 1, ( ." -.. .,(-#.#)(- , *)&3()'#& /(.#)(- ( ,./,(- ( ϵ7**,)2#'.  Bϵ7 C 1#." ϵ ≤ ϵ6 1", ϵ #- !#0( - #(*/.8

R  /- )/, &!),#."' .) **,)2#'. -)&/.#)(- ) ()(7*)&37 ()'#& !'-9 **,)2#'.#(! ." ,1, ( -.. .,(-#.#)(-!#0( - #(*/. 1#." *)&3()'#&-6 -)&0#(! ." **,)2#'. !'6 ( *,)0##(! ."),.#& /**, )/(- )( ." +/&#.3 ) ." -)&/.#)(- - /(.#)(- ) ." **,)2#'.#)( ,,), 1#." #(ŀ(#.3 (),'8

R  2*,#'(.&&3 0&/. ." *, ),'( ) )/, &!),#."' #( .,'- ) #.,.#)(- ( )'*/. .#'8 Ļ- ,-/&.- , *,-(. #( DoE9 8 )()'#6 8 ..#6 8 ()44)6 ( 8 -.&&#8 )'*/.#(! +/#&#7 ,# 1#." .1)7*&3, 4,)7-/' )(.#(/)/- -.)"-.# !'- 1#." -1#."#(! )(.,)&8 (  6 ),)(.)6 (6 /&3 hh7hl hfgh8

,(#(! #( 2.(-#07 ),'

!'-R  -")1 .". ." -.(, ,*&#.), 3('#- ), (),'& ),' (().  )*. 1#." ." -+/( ),'6 ." -.,.!#- *,)7 / 3 ,*&#.#)( (). #(! 1&&7ŀ( -+/(7 ),' -.,.!#-8 R  -#!( (  ") 0,-#)( ) ." #-,.7.#' ,*&#.), 37 ('#- ), -+/( ),' ( 1 -")1 .". #. #- -)/(6 ." -.,.!#- *,)/ 3 ,*&#.#)( #(! 1&&7ŀ( -+/(7 ),' -.,.!#-8

R  -")1 .". )/, ,*&#.), 3('#- #- ,&#4.#)( +/#0&(. .) ." -.(, #-,.7.#' ,*&#.), 3('#- ), (),'& ),' ( .", ), .". ." .1) ,*&#.), 3('#- 0)&0 #( ." -' 138

(18)

Ș8 ŚŠŞśŐšŏŠŕśŚ R  2.( )/, #-,.7.#' ,*&#.), 3('#- .) ." )(7 .#(/)/-7.#' -6 -")1#(! .". ." -' *,)*,.#- , -.#-7 ŀ ( 2.(#(! -.(, .))&- .) -./3 ." -.#&#.3 ) ." -.,.!#- .) )/, ,*&#.),8 Ļ- ,-/&.- , *,-(. #( DhkE9 8 ..#6 8 ()44)6 ( 8 -.&&#8 Ń#(. 0)&/.#)(,3 3('#-1#." 2.(-#07 ),' !'-8 (  6 &&0/6 -"#(!.)(6 6 /&3 gj7gn hfgi8 R  ŀ(  0,#.#)( ) ." -.(, Q7&,(#(! &!),#."' .". #- **&#& .) ." -+/( ),' ) ( 2.(-#07 ),' !'6 -")1#(! .".6 #( #.#)( .) ( 2*)((.#& ,/.#)( ) ." &,(#(! .#'-6 #. &&)1- .) &,( -.,.!3 *,)ŀ&- .". (().  &,( /-#(! ." (),'& ),' ,*,-(..#)(8 R  -")1 .".6 #( 2*..#)(6 ." .#'7&#'#. &,(#(! 3('7 #- ) )/, &!),#."' (  -,# 3 '(- )  (1 -7 +/(7 ),' ,*&#.), 3('#- 1#."  '/..#)( .,' ( .".6 1"( ." '/..#)( .,' .(- .) 4,)6 ." ,*&#.), 37 ('#- )(0,! .)  -" +/#&#,#/' 1#." *, .7#( ),'7 .#)( !'-8

R  2*,#'(.&&3 0&/. )/, Q7&,(#(! - &!),#."' **&# .) ." -+/( ),'6 )'*,#(! #.- 3('#- 18,8.8 ." 3('#- ).#( 1"( ." -.(, Q7&,(#(! &!)7 ,#."' #- **&# .) ." (),'& ),' ( 0&/.#(! ." /,3 ) )/, ,*&#.), 3('#- ')& - ." &,(#(! *,'.,-0,38

8 ..#6 8 ()44)6 ( 8 -.&&#8 7&,(#(! - &!),#."' ), ." -+/( ),' ) 2.(-#07 ),' !'-8 /'#.. .)  6 / #.36 /6 /&3 hm7ig hfgj8 R  -#!( -)' -)&/.#)( )(*.- 2.(#(!  .) *./, -#./.#)(- 1", !(.- '3  ) #Ŀ,(. B3-#(C ŀ(#. .3*- ( #(#0#/&-8 l

(19)

g8i8 Ļ-#- -.,/./,

R  -./3 ." ,&.#)(-"#*- .1( #Ŀ,(.  2.(-#)(-- ." (/', ) #(#0#/&- ( .3*- "(!8

R #." .1) !(.-6 1 ),'/&. ." *,)&'- ) ŀ(#(!  -)&/7 .#)( 1#." ŀ(#. ( #(ŀ(#. *)*/&.#)(- - .1) '#27#(.!, &#(, '."'.#& *,)!,'- B C8 /,.",'),6 1 -")1 .". ." *,)&' ) 0,# 3#(! 1".", ), ().  -)&/.#)( #- (  2.(-#)( #- #( P 0( 1"( ." #(*/. .) ." 0,#ŀ.#)( *,)&' -*#ŀ- )(&3 ." -.,.!#- ( (). ." &# - B." #-)'')( 1"( 1 )-,0 &,(#(! !(.- ( 1 -% 1".", ."#, -.,.!#- ,  -)&/.#)( ), -)' !#0( -)&/.#)( )(*.C6 1"#& -,"#(! ), (  #- PPAD7)'*&.8 /,.",7 '),6 1 #-/-- .) (/',. ." +/#&#,#8

R  -./3 ." ,*&#.), 3('#- 1#." '/&.#*& #(#0#/&-( 1 -")1 ")1 - Ŀ. &,(#(! 3('#- #( !'-1#." *, . #( ),'.#)(9 ."3 , ,"& -..- )(&3 1"( &,(#(! !(.- , */,&3 !,36 ).",1#- ."3 , -& *)#(.- ..,.#(! ( ."( ,*&&#(! ." 3('#-8 1 -',! - ." #(#0#/&- #(,-6 "(!#(! ." &,(#(! .,7 $.),#- ( &3#(! ."#, )(0,!(8

Ļ- ,-/&.- , *,-(. #( Dhi6 hj6 hlE9

."'.#& *,)!,''#(! ),'/&.#)(- .) )'*/. -.3 -..- #( .1)7 *&3, 2.(-#07 ),' !'-8 ( (.,.#0 #-#)( Ļ),3 ( ' Ļ),3 ),%-")* )  6 .&(.6 6 /&3 gg hfgf8

8 ..#6 8 ()44)6 ( 8 **#8 )'*/.#(!  -& 7)(ŀ,'#(! +/#7 &#,#/' #( .1)7*&3, 2.(-#07 ),' !'-8 *!- ong7onn6 #*#6 #1(6 hfgf8

8 ..#6 8 ()44)6 ( 8 -.&&#8 2.(-#07 ),' !'- 1#." ".7 ,)!()/- *)*/&.#)(-9 -)&/.#)( )(*.-6 +/#&#,# ",.,#4.#)(6 ( &,(#(! 3('#-8 (  6 #(. /&6 6 3 l7gf hfgi8

g8i Ļ-#- -.,/./,

Ļ ."-#- #- -.,/./, - )&&)1-8 "*., h #- #. .) !'7 ."),.# *,&#'#(,#-8 *#ŀ&&36 1 #(.,)/ ." )(*. )

(20)

Ș8 ŚŠŞśŐšŏŠŕśŚ

!' ( #.- ,*,-(..#)(-6 1 &#-. -)' #'*),.(. -)&/.#)( )(7 *.- .". 1 /- #( ."#- ."-#- ( ." ,&.#)(-"#* .1( ."'6 1 -,# ." )'*/..#)(& )'*&2#.3 &--- ) +/#&#,#/' )'*/7 ..#)(& *,)&'- .,. #( ."#- 1),% ( 1 &)- ." "*., 1#." ." -# )(*.- ) 0)&/.#)(,3 !' ."),3 ( ,#( ),'(. &,(#(!8

,. #- )/- )( ." 0,#ŀ.#)( ( )'*/..#)( ) -" +/#7 &#,#/' ,ŀ('(.-8 "*., j *,-(.- ." -#!(#(! ) ( Ń#(. &!),#."'- ), ." 0,#ŀ.#)( *,)&' ) -+/(.#& +/#&#,#/'8 ( "*., k 1 )/- )( ." *,)&' ) -#!( ( Ń#(. &!),#."' .".6 !#0(  -*#ŀ *,./,.#)( )0, ." -+/(7 ),' -.,.7 !#- )  .1)7*&3, 2.(-#07 ),' !'6 #. )'*/.- ( 8 ( "*., l 1 *,)0# ( #.,.#0  - &!),#."' .". )(7 0,!- .) (  1"( )." ." ,1, ( ." -.. .,(-#.#)(- , *)&3()'#& /(.#)(-8 ( ,. 1 ,-- ." *,)&' ) &,(#(! !(. #( 2.(-#07 ),' !'-8 ( "*., m 1 2*&), ." )*.#)( ) 0)&/.#)(,3 !' ."),3 .))&- 1#." -+/( ),' ), ." -./3 ) 2.(-#07 ),' !'- -#!(#(! (  ") 0,-#)( ) ." ,*&#.), 3('#- ), -7 +/( ),' ( 1 -")1 .". ." -.,.!#- *,)/ 3 ,*&#.#)( #(! 1&&7ŀ( -+/(7 ),' -.,.!#-8 ( "*., n 1 7 0&)* ." ŀ,-. Q7&,(#(! - &!),#."' 1),%#(! 1#." ." -+/( ),' ) ( 2.(-#07 ),' !'6 ."/- &&)1#(! ( 2*)((.#& ,7 /.#)( ) ." &(!." ) ." &,(#(! 3('#- 18,8.8 (),'& ),'8 "*., o #- #. .) ." *,)&' ) &,(#(! #( 2.(-#07 ),' !'- 1#." ".,)!()/-

*)*/&.#)(-"*., gf )(&/- ." ."-#- ( )/.&#(- -)' #,.#)(- ) /./, ,-,"8

(21)

,&#'#(,#-

h

( ."#- "*., 1 !#0 ." !'7."),.# *,&#'#(,#- (--,3 ), ." 0&)*'(. ) ." ."-#-8 ( .#)( h8g 1 #(.,)/ ." ),'& ŀ(#.#)( ) !' ( #.-,*,-(..#)( #( -.,.!# ),' ( 2.(-#0 ),'8 ( .#)( h8h 1 #(.,)/ ." '#( )*,.#)(& ,*,-(..#)(- ) ( 2.(-#07 ),' !'8 ( .#)( h8h 1 -")1 ." ,&.#)(-"#* .1( ." #Ŀ,(. ,*,-(..#)(- #(.,)/8 ( .#)( h8i 1 !#0 ." )(7 *. ) *,./, -.,.!#-8 Ļ .#)( h8j #- #. .) !'-1#." *)*/&.#)(8 ( .#)( h8k 1 &#-. ." '#( -)&/.#)( )(*.-( ." ,&.#)(-"#* .1( ."'8 ( .#)( h8l 1 -,# ." ')-. #'*),.(. )'*/..#)(& )'*&2#.3 &--- ) *,)&'- .". &13- '#.  -)&/.#)(8 ( .#)( h8m 1 -")1  /,.", ,*,-(7 ..#)( ) !'6 ." -) && -.)"-.# !'-6 ( #.- *,)*,.#-8 ( .#)( h8n 1 !#0 ." -# )(*.- ) 0)&/.#)(,3 !' ."),38 #(&&36 #( .#)( h8o 1 *,-(. ." Q7&,(#(! &!),#."' ( #.-,&.#)(-"#* 1#." ." 0)&/.#)(,3 !' ."),38

h8g ' ŀ(#.#)(

' ."),3 #- ." -./3 ) -.,.!# #-#)( '%#(!8 ), ),7 '&&36 #. #- [[." -./3 ) '."'.#& ')&- ) )(ł#. ( ))*7 ,.#)( .1( #(.&&#!(. ,.#)(& #-#)(7'%,-[[8 ."'.#&

(22)

ș8 ŞőŘŕřŕŚōŞŕőş

')&- 1, #(.,)/ .) -,# -.,.!#7#(.,.#)( -#./.#)(-: ."- ')& , && !'-8

Ļ, , #Ŀ,(. ,*,-(..#)(- ) !'8 Ļ ŀ,-. )( .". 1 #(.,)/ , ." -.,.!#7 ),' !'- .". -,# -#./.#)(- 1", && ." !(.- *&3 -#'/&.()/-&38

ŀ(#.#)( h8g B.,.!#7 ),' !'C  Bŀ(#.6 n7!(.C -.,.!#7 ),' !' #-  ./*& (N, A, u)6 1", R N #-  ŀ(#. -. ) !(.-6 R A = A1× ⋯ × An6 1", Ai #-  ŀ(#. -. ) .#)(- 0#&& .) !(. i8 " 0.), a = (a1, . . . , an) ∈ A #- && ( .#)( *,)ŀ&6 R u = (u1, . . . , un)6 1", ui∶ A ↦ R #-  ,&70&/ /.#&#.3 B), *3)ĿC /(.#)( ), !(. i8  .1)7*&3, -.,.!#7 ),' !' #( &#.,./, %()1( - [[,#-)(,[-#&''[[ #- ,*,-(. #(  h8g 8 C D c i 6 i f 6 k d k 6 f g 6 g & h8g9 2'*& ) .1)7!(. -.,.!#7 ),' !': c ( d , .#)(- 0#&& .) !(. g6 1"#& C ( D , .#)(- 0#&& .) !(. h8 Ļ 2.(-#0 ),' *,)0#-  ,#", ,*,-(..#)( ."( ." -.,.7 !# ),'8 . *,)0#- ." -+/(.#& -.,/./, ) #-#)(7'%#(! 7 #(! -,# 2*&##.&3 ( " !(. #(! &&)1 .)  , .) "(! ", '#( - 0(.- /( )&8 ŀ(#.#)( h8h B, .7#( ),'.#)( 2.(-#07 ),' !'C  *,7 .7#( ),'.#)( 2.(-#07 ),' !' DgoE #- ),'&&3 ŀ( -  ./*& (N, A, V, T, ι, ρ, χ, u)6 1",

R N #- ." -. ) !(.- B1 (). 3 i ∈ N  !(,# !(.C6 R A #- ." -. ) .#)(- B1 (). 3 Ai ⊆ A ." -. ) .#)(- )

!(. i ( 3 a ∈ A  !(,# .#)(C6 gf

(23)

h8g8 ' ŀ(#.#)( R V #- ." -. ) #-#)( ()- B1 (). 3 Vi⊆ V ." -. ) #-#)( ()- ) !(. iC6 R T #- ." -. ) .,'#(& ()- B1 (). 3 w ∈ V ∪ T  !(,# () ( 3 w0." ,)). ()C6 R ι ∶ V → N #- ." /(.#)( .". -*#ŀ- ." !(. .". .- .  !#0( #-#)( ()6 R ρ ∶ V → ℘(A) ,./,(- ." .#)(- 0#&& .) !(. ι(w) .  #-#)( () w6 R χ ∶ V × A → V ∪ T --#!(- ." (2. B#-#)( ), .,'#(&C () .) " *#, )'*)- )  #-#)( () w ( ( .#)( a 0#&& . w6 ( R u = (u1, . . . , un) #- ." 0.), ) !(.-[ /.#&#.3 /(.#)(- 1", ui∶ T → R8 L1 R1 L2 R2 l1 r1 1.1 1.2 2.1 16 1 16 1 16 1 06 0 #!/, h8g9 2'*& ) .1)7!(. *, .7#( ),'.#)( 2.(-#07 ),' !' B1 (). 3 i.j ." j7." #( ),'.#)( -. ) !(. i6 1"#& L1, R1, L2, R2, .#)(- 0#&& .) !(. g ( l1, r1, 7 .#)(- 0#&& .) !(. hC8 Ļ#- !' '3 -' +/& .)  !' 1#." .", .#)(- 0#&& .) () g8g6 L16 R1L2( R1R28  -")1

#( ." )&&)1#(! .". ."#- +/#0&( )- (). ")&8

, . #( ),'.#)( *./,- 2&/-#0&3 -#./.#)(- #( 1"#" && ." !(.- ( )-,0 && ." .#)(- /(,.%( 3 ." )**)((.-8 '7 *, . #( ),'.#)( ,&2- ."#- )(-.,#(.6 *./,#(! -#./.#)(- #(

(24)

ș8 ŞőŘŕřŕŚōŞŕőş 1"#" -)' !(. )- (). )-,0 -)' )**)((.-[ .#)(g8 '*,7 .7#( ),'.#)( !'- , - )( ." )(*. ) #( ),'.#)( -.8 ( #( ),'.#)( -. #-  )&&.#)( ) #-#)( ()- 1#." ." *,)*,.3 .".6 1"( ( !(. *&3- . )( ) ."'6 -" ((). #-.#(!/#-" ." -*#ŀ () #( 1"#" -" #- *&3#(!8  (). 3 Vi,h." #( ),7 '.#)( -. ) !(. i 1")- #(2 #- h8 (, ." --/'*.#)( .". && ." #( ),'.#)( -.- #( ." !' ., "0  #Ŀ,(. #(2 h6 1 ( /(#+/&3 #(.# 3 ( #( ),'.#)( -. 3 h8 ŀ(#.#)( h8i B '*, .7#( ),'.#)( 2.(-#07 ),' !'C ( #'*, .7#( ),'.#)( 2.(-#07 ),' !' #-  ./*& (N, A, V, T, ι, ρ, χ, u, H) 1", R (N, A, V, T, ι, ρ, χ, u) #-  *, .7#( ),'.#)( 2.(-#07 ),' !' ( R H = (H1, . . . , Hn) #(/-  *,.#.#)( Vi= ⋃h∈HiVi,h-/" .". ), && w, w∈ V i,h1 "0 ρ(w) = ρ(w)8 #." /- ) ()..#)( 1 /- .",)/!")/. ." ."-#- ρ(h) #( *& ) ρ(w) 1", w ∈ Vi,h8

 )/- )( !'- 1#." *, . ,&& DgoE 1", " !(. ,&&- && ", )1( *,0#)/- .#)(- ( && ", *,0#)/- )-,0.#)(-8 , . ,&& *&- ()(7.,#0#& )(-.,#(.- )0, ." -.,/./, ) 0,3 Vi,h8

 )'#. ."#, -,#*.#)( ",6 (). #(! (--,3 ), )/, 1),%6 ( 1 *)#(. ." #(.,-. ,, .) DgoE8  ,*),. ( 2'*& ) 2.(-#07 ),' !' #( #!8 h8g8

h8h ' ( -.,.!3

,*,-(..#)(-Ļ, , .", '#( )*,.#)(& ,*,-(..#)(- ), ( 2.(-#07 ),' !'9 (),'& ),' DlnE6 !(. ),' Djh6 klE6 ( -+/( ),' DloE6 " - )(  -*#ŀ ,*,-(..#)( ) ." -* ) ." !(.-[ -.,.!#-8

g'- 1#." /(,.#( #( ),'.#)( (  -,# - !'- 1#." #'*, .

#( ),'.#)( 1#."  -*#& *&3,6 ." (./,6 .". -&.- ()- ),#(! .)  !#0( #-.,#/.#)( *,)#&#.38

(25)

h8h8 ' ( -.,.!3

,*,-(..#)(-!(. ),'

( ." !(. ),'6 " !(. #- ,*&#. #(  (/', ) ŀ.#.#)/-!(.- ( " ) ."' #- --#!( .)  #Ŀ,(. #( ),'.#)( -.8 ( ."#- 136 " ŀ.#.#)/- !(. *&3- )(&3 . )( -#(!& #( ),'.#)( -.8  -.,.!3 #( ." !(. ),' #- )'')(&3 -# "0#),& -.,.!3 ( 1 ().  "0#),& -.,.!3 *,)ŀ& 3 σ = (σ1, . . . , σ∣N∣) 1", σi#- ." -.,.!3 ) !(. i ( 1 (). 3 σi(a) ." *,)#&#.3 --)#. 1#." .#)( a ∈ Ai8  "0#),& -.,.!3 σi--#!(- #(7 *((.&3 " #( ),'.#)( -. h ∈ Hi *,)#&#.3 #-.,#/.#)( )0, ." .#)(- ρ(h) ( .", ), #. #- -/" .". ∑a∈ρ(h)σi(a) = 18 Ļ !(. ),' #- &#(, #( ." -#4 ) ." !' .,8 2'*& h8g )(-#, ." !' *#. #( #!8 h8g6 ." !(. ),' #-9 !(. h8g l1 r1 !(. g8g L1 1, 1 1, 1 R1 1, 1 1, 1 L2 !(. h8g l1 r1 !(. g8g L1 1, 1 1, 1 R1 1, 1 0, 0 R2 !(. g8h 1", 1 --#!( " ŀ.#.#)/- !(. ." && ) ." #( ),'.#)( -. #( 1"#" ." ŀ.#.#)/- !(. *&3-8 ( 2'*& ) "0#),& -.,.!#- #-9

σ1= ⎧⎪⎪⎪⎪ ⎪⎪⎪ ⎨⎪⎪⎪ ⎪⎪⎪⎪ ⎩ σ1(L1) = 1.0 σ1(R1) = 0.0 σ1(L2) = 0.0 σ1(R2) = 1.0 σ2=⎧⎪⎪⎨⎪⎪ ⎩ σ2(l1) = 0.8 σ2(r1) = 0.2

),'& ),'

( ." (),'& ),'6  -.,.!3 *,)ŀ& #- ,*,-(. -  *,)#&#.3 #-.,#/.#)( )0, *&(-8  *&( ) !(. i6 (). 3 p ∈ Pi 1",

Pi⊆ P #- ." -. ) *&(- ) !(. i ( P #- ." -. ) && ." *&(-6

#-  ./*& ) !' ., .#)(- -*# 3#(! )( .#)( a ∈ Ai *, #(7

),'.#)( -. h ∈ Hi8  ().  (),'&7 ),' -.,.!3 *,)ŀ& 3

π= (π1, . . . , π∣N∣) 1", πi#- ." -.,.!3 ) !(. i ( 1 ().

3 πi(p) ." *,)#&#.3 --)#. 1#." *&( p ∈ Pi8  (),'&7 ),'

(26)

ș8 ŞőŘŕřŕŚōŞŕőş

-.,.!3 #- -/" .". ∑p∈Piπi(p) = 18 Ļ !(. i[- /.#&#.3 #- ,*,7

-(. -  '/&.#7#'(-#)(& ,,36 (). 3 Ui6 -*# 3#(! ."

0&/ --)#. .) 0,3 )'#(.#)( ) *&(- ) && ." !(.-8 Ļ (/', ) *&(- #( ( 2.(-#07 ),' !' B( .", ), ." -#4 ) ." (),'& ),'C #- 2*)((.#& #( ." -#4 ) ." !' .,8 2'*& h8h )(-#, ." !' *#. #( #!8 h8g8  *&( ) !(. 1 #-  *#, -*# 3#(! )( .#)( . #( ),'.#)( -. h = 1.1 ( )( .#)( . #( ),'.#)( -. h = 1.26 8!86 R1L28 Ļ (),'&7 ),' /.#&#.3 #'.,#2 ( ( 2'*& ) -.,.!#- ,9 !(. h l1 r1 !(. g L1L2 1, 1 1, 1 L1R2 1, 1 1, 1 R1L2 1, 1 1, 1 R1R2 1, 1 0, 0 π1= ⎧⎪⎪⎪⎪ ⎪⎪⎪ ⎨⎪⎪⎪ ⎪⎪⎪⎪ ⎩ π1(L1L2) = 0.5 π1(L1R2) = 0.0 π1(R1L2) = 0.0 π1(R1R2) = 0.5 π2=⎧⎪⎪⎨⎪⎪ ⎩ π2(l1) = 0.8 π2(r1) = 0.2 Ļ, 2#-.-  ,/ 0,-#)( ) (),'& ),'6 -) && ,/ (),'& ),'6 .". #- ).#( ,)' ." *,0#)/- )( 3 &.#(! ,*&#7 . -.,.!#- DlmE8 &.")/!" ,/ (),'& ),' (  '/" -'&&, ."( (),'& ),'6 #. #- 2*)((.#& #( ." -#4 ) ." !' .,8

2'*& h8i )(-#, ." !' *#. #( #!8 h8g8 Ļ ,/7(),7 '&7 ),' /.#&#.3 #'.,#2 ( ( 2'*& ) -.,.!#- ,9

!(. h l1 r1 !(. g RL11L∗ 1, 1 1, 12 1, 1 1, 1 R1R2 1, 1 0, 0 π1=⎧⎪⎪⎪⎪⎨⎪⎪⎪ ⎪⎩ π1(L1∗) = 0.5 π1(R1R2) = 0.0 π1(R1R2) = 0.5 π2=⎧⎪⎪⎨⎪⎪ ⎩ π2(l1) = 1.0 π2(r1) = 0.0 gj

(27)

h8h8 ' ( -.,.!3

,*,-(..#)(-+/( ),'

( ." -+/( ),'6  -.,.!3 #- ,*,-(. -  *,)#&#.3 #-7 .,#/.#)( )0, -+/(-8  -+/( q ∈ Qi ) !(. i #-  -. ) )(-/.#0 .#)(- a ∈ Ai 1", Qi ⊆ Q #- ." -. ) -+/(- ) !(. i ( Q #- ." -. ) && ." -+/(-8  -+/( (  .,'#7 (& B8!86 q = L1#( #!8 h8gC6 # 6 )'#( 1#." -)' -+/( ) ."

)**)((.-6 #. &- .)  .,'#(& ()6 ), ()(7.,'#(& B8!86 q = R1

#( #!8 h8gC6 # #. ((). & .) (3 .,'#(& () ), " )**)((.-[ -+/(8 " !(. "-  ŀ.#.#)/- #(#.#& -+/(6 (). 3 q∅ ( && '*.3 -+/(8 /,.",'),6 !#0(  -+/( q ∈ Qi &#(! .) -)' #( ),'.#)( -. h ∈ Hi6 1 -3 .". -+/( q′ 2.(- q B( 1 (). #. 3 q= q∣aC # ." &-. .#)( ) q #--)' .#)( a ∈ ρ(h)8  ().  -+/(7 ),' -.,.!3 *,)ŀ& 3 x = [x1, . . . , x∣N∣] 1", xi#- ." -.,.!3 ) !(. i ( 1 7 (). 3 xi(q) ." *,)#&#.3 --)#. 1#." -+/( q ∈ Qi8 &&7 ŀ( -.,.!#- , -/" .".6 ), 0,3 #( ),'.#)( -. h ∈ Hi6

." *,)#&#.3 xi(q) --#!( .) ." -+/( q &#(! .) h #- +/&

.) ." -/' ) ." *,)#&#.#- xi(q′)- 1", q′2.(- q . h6 ),7

'&&36 xi(q) = ∑a∈ρ(h)∶q∣a∈Qxi(q∣a) ), && h ∈ Hi8 +/( ),'

)(-.,#(.- (  )(0(#(.&3 -,# - Fi⋅ xi= fi6 1", Fi

#-( )**),./( '.,#2 #-( fi#- ( )**),./( 0.),6 )." 1#."

(.,#-#( {−1, 0, 1}8 Ļ- '.,#2- !/,(. .". !(. i[- -.,.!3 xi

#-1&& ŀ(8  (). 3 vi ." 0.), ) vi,h6 1", " vi,h

2*,--- ." 0&/ !(. i 2*.- ,)' *&3#(! . #( ),'.#)( -. h 1", ι(h) = i8 Ļ !(. i[- /.#&#.3 #- ,*,-(. -  -*,- '/&.#7 #'(-#)(& ,,36 (). 3 Ui6 -*# 3#(! ." 0&/ --)#. .) 0,3 )'#(.#)( ) !(.-[ .,'#(& -+/(- &#(! .) ( )/.7 )'8 Ļ -#4 ) ." -+/(7 ),' ,*,-(..#)( #- &#(, #( ." -#4 ) ." !' .,8 2.&36 2&/ ." '*.3 -+/(6 1 "0 )( -+/( q ∈ Qi*, .#)( a ∈ Ai8  *,)0# ( 2'*& ) -+/(7 ),' ,*,-(..#)(8 2'*& h8j )(-#, ." !' *#. #( #!8 h8g6 ." -+/(7 ),' gk

(28)

ș8 ŞőŘŕřŕŚōŞŕőş /.#&#.3 #'.,#2 ( ( 2'*& ) -.,.!#- ,9 !(. h q∅ l1 r1 !(. g q∅ L1 1, 1 R1 R1L2 1, 1 R1R2 1, 1 0, 0 x1= ⎡⎢ ⎢⎢ ⎢⎢ ⎢⎢ ⎢⎣ 1 0 1 1 0 ⎤⎥ ⎥⎥ ⎥⎥ ⎥⎥ ⎥⎦ x2=⎡⎢⎢⎢ ⎢⎣ 1 1 0 ⎤⎥ ⎥⎥ ⎥⎦ ." )(-.,#(.- F1⋅ x1= f1( F2⋅ x2= f2,9 F1=⎡⎢⎢⎢ ⎢⎣ −1 0 −0 0 0 −1 1 −1 0 0 0 0 −1 1 1 ⎤⎥ ⎥⎥ ⎥⎦, f1=⎡⎢⎢⎢ ⎢⎣ 1 0 0 ⎤⎥ ⎥⎥ ⎥⎦ F2= [ −−1 1 1 ]1 0 0 , f2= [ 10 ] #( #( ."#- ."-#- 1 ,+/(.&3 2*&)#. ." ),,-*)(( 7 .1( .#)(- a ∈ A ( -+/(- q ∈ Q6 1 (). 3 a(q) ." &-. .#)( ) -+/( q ( 3 q(a) ." -+/( 1")- &-. .#)( #- a8 #0(  -+/(7 ),' -.,.!36  "0#),& -.,.!3 (  -#&3 ,#0 -9 σi(a) =⎧⎪⎪⎪⎨⎪⎪⎪ ⎩ xi(q∣a) xi(q) # xi(q) #- -.,#.&3 *)-#.#0

(3 -#& *,)#&#.3 0&/ ).",1#-

&.#)(-"#*- .1( ."

,*,-(..#)(- ,#ł3 -,# ." ,&.#)(-"#*- ')(! ." )0 .", ,*,-(7 ..#)(-8 #,-.6  -+/(7 ),' -.,.!3 xi#- +/#0&(. .)  (/',

B*,#-&36  )'*. -.C ) (),'&7 ),' -.,.!#- πi( ." ,&7

.#)(-"#* #- &#(, B- DloEC8 )(6  -+/(7 ),' -.,.!3 xi

#-+/#0&(. .)  (/', B*,#-&36  )'*. -.C ) "0#),& -.,.7 !#- σi ( ." ,&.#)(-"#* #- ()(7&#(,8 ), *,#-&36 !#0( (

#( ),'.#)( -. h ∈ Hi ( && q ∈ Qi ." -+/( &#(! .)

h6 ." "0#),& -.,.!3 σi(a) ,&. .) ." .#)(- a ∈ ρ(h) (

q′ = q∣a #- σi(a(q′)) = xi(q

)

xi(q) # xi(q) > 0 ( #- ,#.,,3 ).",7

1#-8 Ļ#,6  "0#),& -.,.!3 σi#- +/#0&(. .)  (/', B*,7

#-&36  )'*. -.C ) (),'&7 ),' -.,.!#- πi( ." ,&.#)(7

-"#* #- ()(7&#(, B- DjhEC8 Ļ .", ,*,-(..#)(- "0 #Ŀ,(. gl

(29)

h8h8 ' ( -.,.!3

,*,-(..#)(-!,- ) 2*,--#0(--6 8!86 -+/(7 ),' -.,.!#-6 #Ŀ,(.&3 ,)' "0#),& ( (),'&7 ),' -.,.!#-6 ) (). -*# 3 ." 7 .#)(- ( !(. 1)/& *&3 . ." #( ),'.#)( -.- .". , ," 1#."  *,)#&#.3 ) 4,)6 ( (),'&7 ),' -.,.!#-6 #Ŀ,(.&3 ,)' "0#),& -.,.!#-6 ),,&. ." .#)(-  -#(!& !(. 1)/& *&3 . 0,3 #( ),'.#)( -.8

Ļ, #-  1&&7%()1( ,&.#)(6 - )( ." )(*. ) ,&#47 .#)(6 .1( (),'&7 ),' ( -+/(7 ),' -.,.!#-8 ( ),, .) 2*&)#. #.6 1 #(.,)/ .1) ,-/&.- ,)' DioE8

ŀ(#.#)( h8j B&#4.#)( +/#0&(.C 1) -.,.!#- ) ( !(. , ,&#4.#)( +/#0&(. # 6 ), (3 ŀ2 -.,.!#- ) ." ).", !(.-6 )." -.,.!#- ŀ( ." -' *,)#&#.#- ), ,"#(! ." ()- ) ." !' .,8 ,)*)-#.#)( h8g ), ( !(. 1#." *, . ,&&6 ), (3 (),'&7 ),' -.,.!3 .", #-  ,&#4.#)( +/#0&(. -+/(7 ),' -.,.!38  ,&& #( #.#)( .". " */, -+/(7 ),' -.,.!3 ),,7 -*)(- .)  */, (),'&7 ),' -.,.!3 #( ." ,/ (),'& ),' DioE8 #0(  "0#),& -.,.!3 σi6 1 ( ,#0 ." B,&#4.#)(C

+/#0&(. (),'&7 ),' -.,.!3 ( -+/(7 ),' -.,.!3 - )&7 &)1-πi(p) = ∏ a∈p∶p∈P σi(a) ∀p ∈ Pi Bh8gC xi(q) = ∏ a∈q∶q∈Q σi(a) ∀q ∈ Qi Bh8hC #0(  (),'&7 ),' -.,.!3 πi6 1 ( ,#0 ." B,&#4.#)(C +/#0&(. "0#),& -.,.!39 σi(a) = ∑ p∈P ∶a∈p πi(p) Bh8iC #0(  (),'&7 ),' -.,.!3 πi #( ,/ (),'& ),'6 1 ( ,#0 ." B,&#4.#)(C +/#0&(. -+/(7 ),' -.,.!39 xi(q∣a) = ∑ p∈P ∶a∈p πi(p) Bh8jC gm

(30)

ș8 ŞőŘŕřŕŚōŞŕőş

h8i ,./,.#)( )0,

-.,.!#-,'&- )0, -.,.!#- , *./, 3 *,./,.#)(-8 && li(a, ϵ) >

0." *,./,.#)( B#( .,'- ) *,)#&#.3C )0, .#)( a ∈ Ai -/"

.". limϵ→0li(a, ϵ) = 0 ( ϵ #-  *)-#.#0 0&/8  (). 3 li(ϵ) ."

*,./,.#)( )0, && ." !(. i[- .#)(-8

ŀ(#.#)( h8k B,./, -.,.!3C  *,./, -.,.!3 *,)ŀ& σ(ϵ) ) σ #-  '#2 -.,.!3 1", σi(a, ϵ) ≥ li(a, ϵ) ), && a ∈ Ai(

lim

ϵ→0σ(ϵ) = σ8

#'#&, .) "0#),& -.,.!#-6 &-) -+/(7 ),' -.,.!#- (  -/$. .) *,./,.#)(-8  (). 3 li(q, ϵ) > 0 ." *,./,7 .#)( )0, -+/( q ∈ Qi-/" .". lim ϵ→0li(q, ϵ) = 0 ( ϵ #-  *)-#7 .#0 0&/8  *,./, -.,.!3 *,)ŀ& x(ϵ) ) x #-  '#2 -.,.!3 1", xi(q, ϵ) ≥ li(q, ϵ) ), && a ∈ Qi( lim ϵ→0x(ϵ) = x8

h8j '- 1#."

*)*/&.#)(- ( ." &,(#(! -(,#)6 1 )/- )( 2.(-#07 ),' !'- .". , ,*.&3 *&3 3 #Ŀ,(. #(#0#/&- - -,# #( DgnE8 ), *,#-&36 ), " !(. B,*,-(.#(!  ,)&C6 .", #-  *)*/&.#)( ) #(#0#/&- (6 . " ,*.#.#)( ) ." !'6 )( #(#0#/& #-,1( ,)' " *)*/&.#)( ( ." #-,1( #(#0#/&- , '." ( ."( *&3 ." !'8 . " ,*.#.#)(6 #Ŀ,(. #(#0#/&- '3 *&38  )'')( 2'*& #-  ',%. #( 1"#" #&.,& (!).#.#)(-, ,,# )/.9 .", (!).#.#)(-, .1) !(.-I,)&- B#886 /3, ( -&&,C6 /. #Ŀ,(. /3,- ( #Ŀ,(. -&&,- ( '."8 .", )()'# 27 '*&- , !#0( 3 /.#)(-8

( )/, ')& DhlE6 1 &&)1 *)*/&.#)(- .)  ŀ(#. ), #(ŀ(#. ( .)  ".,)!()/- #(&/#(! #(#0#/&- ) #Ŀ,(. .3*-6 1", .3*- #Ŀ,(.#. ), ."#, *, ,(-8  (). 3 Θ = Θ1× ⋯Θ∣N∣." -. ) && ." .3*- Bθ ().-  !(,# .3*C6 1",

Θi#- ." -. ) ) !(. i8  --/' .". ." (/', )

.3*-#- ŀ(#.8  (). 3 Θ−i." -.,.!3 *,)ŀ& ) ." !(. i[- )**)7

((.-8 .#&#.3 /(.#)(- , ŀ( &-) )0, .3*- B#( #.#)( .) ." -.,.!#- ) ." !(.-C8 "( .3*- , ()(7#(.,*((.6 1 "0 ui= ui(θ, σi, σ−i) 1", θ ∈ Θi: #(-. 1"( .3*- , #(.,*(7

(. 1 "0 ui= ui(θ, θ′, σi, σ−i) 1", θ ∈ Θi( θ′∈ Θ−i8 ),

(31)

h8j8 '- 1#."

*)*/&.#)(-" .3* θ ∈ Θi6 .", #-  B*)--#&3 #(ŀ(#.C *)*/&.#)( ) #(#0#/7

&- ΛθB1 (). 3 λ  !(,# #(#0#/& ( 3 Λi." -. ) && ."

#(#0#/&- ) !(. iC8 " .3* θ ∈ Θi#- --)#. 1#."  *,)7

#&#.3 ωi,θ 1#." 1"#" ( #(#0#/& ) ." *,.#((. *)*/&.#)(

#-,1(8 0#)/-&36 ∑θ∈Θiωi,θ = 18 #'#&,&36 " #(#0#/& λ ∈ Λθ

#- --)#. 1#."  *,)#&#.3 ωi,θ,λ 1#." 1"#" ." #(#0#/&

#-,1( -/" .". ∑λ∈Λθωi,θ,λ = ωi,θ8 ), ." -% ) *,-(..#)(6

1 --/' .". " #(#0#/& "-  #Ŀ,(. #(2 λ ( .", ), 1 ( , , .) ( #(#0#/& λ ∈ Λθ3 /-#(! λ #( *& ) ⟨i, θ, λ⟩8

#'#&,&36 1 --/' " .3* "-  #Ŀ,(. θ6 .", ), 1 ( , , .)  .3* θ ∈ Θi3 /-#(! θ #( *& ) ⟨i, θ⟩8 #Ŀ,(. #(#0#/&- '3 )*. #Ŀ,(. -.,.!#-8 σλ ().-." -.,.!3 ) #(#0#/& λ8 Ļ !!,!. -.,.!3 ) ().-." #(#0#/&-) .3* θ ∈ Θi#- σθ= ∑λ∈Λθσλ⋅ ωλ6 ( ." !!,!. -.,.!3 ) !(. i #- σi= ∑θ∈Θiσθ⋅ ωθ8 - #( DgnE6 1 --/' .". !(.- "0 () #( ),'.#)( )/. ." )**)((.-8 *#ŀ&&36 1 --/'9 R " #(#0#/& "- () #( ),'.#)( )/. ." /.#&#.3 /(.#)(-) ." /(.#)(-).", !(.-: R " #(#0#/& "- () #( ),'.#)( )/. ." #(#0#/&- ) ." ).", !(.-: R 1"( /.#&#.#- , #(.,*((.6 " #(#0#/& %()1- ." .3*- ) ." )**)((.-6 /. -" )- (). %()1 ." *,.#((. *,)#&#.#- ( /.#&#.#-: R 1"( /.#&#.#- , (). #(.,*((.6 () --/'*.#)( )/. ." %()1&! ) ." )**)((.-[ .3*- #- '8 /-.)',#&36  !' 1#." .3*- #- -# 3-#(8 " #(#0#/& ),'-  &# )0, ." )**)((. ( $/-.- #. /,#(! ." *&38 ), *,#-&36 1"( /.#&#.#- , (). #(.,*((.6 " #(#0#/& λ ) !(. i "-  B*).(.#&&3 #Ŀ,(.C &# ˆσ−iλ )0, ." -.,.!3 )

!(. −i8 Ļ#- #- /- " #(#0#/& λ )- (). %()1 ." .3*-( ." #(#0#/&- ) ." )**)((.- .3*-( .", ), -" ((). ),' (3 &# )0, ." -#(!& #(#0#/& ), .3* ) ." )**)((.-8 "( /.#&#.#- , #(.,*((.6 " #(#0#/& λ ) !(. i "-  B*)7 .(.#&&3 #Ŀ,(.C &# ˆσθ λ )0, ." -.,.!3 ) .3* θ ∈ Θ−i (  B*).(.#&&3 #Ŀ,(.C &# ˆωθ λ )0, ." *,.#((. *,)#&#.3 ωθ go

(32)

ș8 ŞőŘŕřŕŚōŞŕőş

B&-) #( ."#- - #(#0#/&- "0 (). &# - )0, ." -#(!& #(#0#7 /&- ) ." )**)((.C8 2'*& h8k !(. g #- ) .", .3*- θ1.1, θ1.2, θ1.36 " 1#." *,)7 #&#.3 ω1.1, ω1.2, ω1.3 B1#." ω1.1+ ω1.2+ ω1.3 = 1C8 1) #(#0#/&-λ1.1.1, λ1.1.2, ) .3* θ1.1B1#." ω1.1.1+ ω1.1.2= ω1.1C6 1"#& )(&3 )( #(#0#/& λ1.2.1#- ) .3* θ1.2 B1#." ω1.2.1 = ω1.2C ( )(&3 )( #(#0#/& λ1.3.1#- ) .3* θ1.3B1#." ω1.3.1= ω1.3C8

h8k )&/.#)(

)(*.- -)&/.#)( )(*. #-  ),'& ,/& ), *,#.#(! ")1  !' 1#&&  *&38 Ļ- *,#.#)(- , && [[-)&/.#)(-[[6 ( -,# 1"#" -.,.!#- 1#&&  )*. 3 *&3,- (6 .", ),6 ." ,-/&. ) ." !'8 ( !' ."),3 .", , '(3 -)&/.#)( )(*.- /.6 !#0(  -*#ŀ %#( ) !'6 (). && , -/#.&8 Ļ (.,& -)&/.#)( )(*. #( ()(7))*,.#0 !' ."),3 #-." -" +/#&#,#/' BC DjoE8 . )(-.,#(- #-." -.,.!3 ) " !(. .)  )*.#'& !#0( ." -.,.!#- ) ." )**)((.-8 ) ),7 '&&3 ŀ( #.6 1 "0 .) #(.,)/ ." )(*. ) -. ,-*)(-8 #0(  (),'&7 ),' !' ( ( !(. i6 1 (). 3 π−i = (π1, . . . , πi−1, πi+1, . . . , πn) ." -.,.!3 *,)ŀ& 1#.")/. ." 7 !(. i[- -.,.!38 Ļ/- 1 ( 1,#. π = (πi, π−i)8 ŀ(#.#)( h8l B-. ,-*)(-C !(. i[- -. ,-*)(- .) ." -.,.!3 *,)ŀ& π−i#-  '#2 -.,.!3 π∗i -/" .". Ui(πi∗, π−i) ≥ Ui(πi, π−i)

), && -.,.!#- πi8 ŀ(#.#)( h8m B-" +/#&#,#/'C  -.,.!3 *,)ŀ& π = (π1, . . . , πn) #-  -" +/#&#,#/' # 6 ), && !(.- i6 πi #-  -. ,-*)(- .) π−i8   ) ( 2.(-#07 ),' !' #- ŀ( -   ) ." --)7 #. (),'& ),' DjhE8 . #- %()1( .". ." )(*. )  #- (). -.#- .),3 ), 2.(-#07 ),' !'-6 / .) .1) '#( ,1%-9

R #. &&)1- .) !(.- .) *&3 ()(7,#& .",.- DgoE6 ."#- &-.) 2*&),#(! (1 -)&/.#)( )(*.- - )( )(*. ) *,7 .#)(9 -/!'7*, . +/#&#,#/'6 -+/(.#& +/#&#,#/'6 +/-#7*, . +/#&#,#/'6 *, . +/#&#,#/' ( *,)*, +/#7 &#,#/'6

(33)

h8k8 )&/.#)(

)(*.-R #( ,&71),& -..#(!- #- ) .( #'*,.#& / .) #.- .)) ,7 -.,#.#0 --/'*.#)(- B8!8 )'')( %()1&! ) *3)Ŀ- ( -.,.!#-C6 ."#- &- !(.- .) "0 -)' B*).(.#&&3 1,)(!C &# - ( ." -)&/.#)( )(*.- )' -.3 -..- ) &,(7 #(! *,)---: ), ."- ,-)( &.,(.#0 -)&/.#)( )(*.-B*#-.'#7-C &#% -& 7)(ŀ,'#(! +/#&#,# 1, #(.,)7 /8

ŀ('(.- ) -" +/#&#,#/'

Ļ )(*. ) -/!' *, . +/#&#,#/' BC ,ŀ(- ." )(*. ) 8 ŀ(#.#)( h8n B/!' *, . +/#&#,#/' DgoEC (  #-  -.,.7 !3 *,)ŀ& .". #- (  #( 0,3 -/!'8  -/!'  *),.#)( ) ." !' ., ŀ( - )&&)1-9 #. #-)'*)- )  -#(!& ,)). ( && ." ()- ,"& ,)' ." ,)). , -/" .". ), 0,3 () w ∈ Vi,hB#(&/#(! ." ,)).C &)(!#(! .)

." -/!' ." 1")& #( ),'.#)( -. Vi,h&)(!- .) ." -/!'8

Ļ )(*. )  #- -.#- .),3 1#." *, .7#( ),'.#)( !'-6 1"#& #. #- (). 1"( #( ),'.#)( #- #'*, .8 Ļ [[(./7 ,&[[ 2.(-#)( ) ."  .) -#./.#)(- 1#." #'*, . #( ),'.#)( #- ." -+/(.#& +/#&#,#/' BC8 ( ),, .) #(.,)/ ." )(*. ) 6 1 ( .) #(.,)/ &# - ( ----'(.-8  (). 3 µi = (µi(1), . . . , µi(w)) ), 0,3 w ∈ Vi,h6 ), 0,3 h ∈ Hi ." &# - ) !(. i 1", µi(w) #- ." *,)#&#.3 1#." 1"#" !(. i

&#0- .)  . () w ∈ Vi,h1"( -" *&3- . #( ),'.#)( -. h8

0#)/-&36 1&& ŀ( &# - µi- , -/" .". ∑w∈Vi,hµi(w) = 1

), 0,3 #( ),'.#)( -. h ∈ Hi8  (). 3 µ = (µ1, . . . , µ∣N∣)

." *,)ŀ& ) &# -8 ( ----'(.6 (). 3 (µ, σ)6 #-  *#, -*# 3#(! ." &# - ( ." "0#),& -.,.!#- ) ." !(.-8 ŀ(#.#)( h8o B+/(.#& +/#&#,#/' DjgEC (  #- ( ----'(. (µ, σ) -/" .".9 R 0,3 σi #- -+/(.#&&3 )*.#'& B#( ." -(- ) %1, #(7 /.#)( DgoEC 18,8.8 µi: R 0,3 µi #- )(-#-.(. B#( ." -(- ) ,*- ( #&-)(C 18,8.8 σ−i8 hg

(34)

ș8 ŞőŘŕřŕŚōŞŕőş

Ļ ŀ(#.#)( ) )(-#-.(3 ,-),.- .) *,./, -.,.!#-8 )(7 -#-.(3 ) µ 18,8.8 σ ,+/#,- .". .", 2#-.-  *,./, -.,.!3 *,)ŀ& σ(ϵ) ) σ /" .".6 &..#(! µ(ϵ) .)  ." +/( ) &# -,#0 ,)' σ(ϵ) 3 /-#(! ." 3- ,/&6 limϵ→0µ(ϵ) = µ8 #." *, . #( ),'.#)( 0,3  #- &-) (  ( 0# 0,-8 (-.6 1"( #( ),'.#)( #- #'*, .6 ." - )(-.#./.  -/-. ) ." -8 2'*& h8l )(-#, ." !' *#. #( #!8 h8g8 Ļ */, -.,.!3 - B( -6 #(! ." -'C #-9 (σ1(L1) = 1, σ1(L2) = 1, σ2(l1) = 1), (σ1(L1) = 1, σ1(R2) = 1, σ2(l1) = 1), (σ1(R1) = 1, σ1(L2) = 1, σ2(l1) = 1), (σ1(R1) = 1, σ1(R2) = 1, σ2(l1) = 1)8

Ļ # ) *, .#)(6 #(.,)/ 3 &.( #( DklE6 #- -.,#.&3 ),7 ,&. 1#." ." # ) *,./, -.,.!38 -#&&36  -.,.!3 *,)7 ŀ& #- *, . 1"( #. #- )*.#'& 0( 1"( .", , *,./,.#)(-8 Ļ )'')( #(.,*,..#)( ) ." *,./,.#)(- #- - )( ." # .". !(.- ) (). *, .&3 *&3  -.,.!36 /. ."3 ( .,'& 1#."  0,3 -'&& *,)#&#.38 Ļ, , .", )(*.- ) *, .#)(8 ŀ(#.#)( h8gf B),'&7 ),' *, . +/#&#,#/' DklEC  -.,.!3 *,)ŀ& π #-   # .", 2#-.-  *,./, -.,.!3 *,)ŀ& π(ϵ) ) π -/" .". πi(p, ϵ) ≥ li(p, ϵ) ( πi #-  -. ,-*)(- .) π−i(ϵ) ), 0,3 ϵ ≤ ϵ ), -)' ϵ > 08 0,3 !' '#.- . &-. )(  (6 ), 0,3 )'#(.#)( ) 0.),- ) *,./,.#)( li(ϵ)6 .", #-  *).(.#&&3 #Ŀ,(. 8 ),'&7 ),' *, .#)( (  *./, &-) 3 *)-#(!  !(,# B /&&3 '#2C *,./,.#)( )0, ." -+/(- ) ." -+/( ),'8 ŀ(#.#)( h8gg B/-#7*, . +/#&#,#/' DlkEC  -.,.!3 *,)ŀ& σ #-   # .", 2#-.-  *,./, -.,.!3 *,)ŀ& σ(ϵ) ) σ -/" .". σi,a(ϵ) ≥ li(a, ϵ) ( 0,3 σi #-  -. ,-*)(- .) σ−i(ϵ) ), 0,3

ϵ≤ ϵ ), -)' ϵ > 08 (   0,3 !(. .%- #(.) )/(. )**)((.-[ .,'&-6 /. (). ."#, )1(8 0,3 !' '#.- . &-. )(  ( ), 0,3 )'#(.#)( ) li(ϵ) .", #-  *).(.#&&3 #Ŀ,(. 8 Ļ /."),--")1 #( DjnE .". +/-# *, .#)( (  *./, 3 /-#(!  -*#ŀ &-- ) *,./,.#)(- 1#." ." -+/( ),'8 ( ."#- -6 1 (). 3 xi(ϵ) ." *,./, -+/( ),' -.,.!3 ( 3 xi(q, ϵ) ." hh

(35)

h8k8 )&/.#)(

)(*.-*,./, -.,.!3 )0, q ∈ Qi8 && li(ϵk) ." )Ń#(.- ) ϵk

#( li(ϵ)8h /-# *, .#)( (  *./, #'*)-#(! .". ), 0,3

*#, ) -+/(- q, q′∈ Q

i1", q′2.(- q ." '#(#'/' !,

) k -/" .". li(q′, ϵk) #- -.,#.&3 *)-#.#0 #- -.,#.&3 -'&&, ."( ."

'#(#'/' !, ) k -/" .". li(q, ϵk) #- -.,#.&3 *)-#.#08 ŀ(#.#)( h8gh B2.(-#07 ),' *, . +/#&#,#/' DklEC  -.,.7 !3 *,)ŀ& σ #- (  # .", 2#-.-  *,./, -.,.!3 *,)ŀ& σ(ϵ) ) σ -/" .". σi(a, ϵ) ≥ li(a, ϵ) ( 0,3 σi#-  -. ,-*)(- .) σ(ϵ) ), 0,3 ϵ ≤ ϵ ), -)' ϵ > 08 Ļ#- )(*. -.,(!."(- ." )(*. ) 6 )(-.,#(#(! σi.)   -. ,-*)(-6 #( #.#)( .) σ−i(ϵ)6 &-) .) σi(ϵ)8 - )06 0,3 !' '#.- . &-. )(  ( ), 0,3 )'#(.#)( ) li(ϵ) .", #-  *).(.#&&3 #Ŀ,(. 8 . #- (). %()1( 1".", ." )(-.,#(.- ) (  (  ),'/&. 1#." ." -+/( ),'8 ), *,#-&36 #. #- 1&& %()1( .". ." /- ) #.#0 *,./,.#)(-)0, ." -+/( ),'6 -/" - .")- ), ." 6 (().  /- ), ( 8 Ļ#- #- /- !#0( (3 #.#0 *,./,.#)( )0, ." -+/(-6 #. #- (). *)--#& .) ,#0  *,./,.#)( )0, ." "07 #),& -.,.!#- .". #- #(*((. ) ." -.,.!3 #.-& B- #. 1)/&  ,+/#, 3 ." ŀ(#.#)( ) C8 )10,6 #. #- (). %()1( 1".", &.,(.#0 *,./,.#)(- (  /-8 2'*& h8m )(-#, ." !' ,*,-(. #( #!8 h8g8 Ļ -. ) 7 - )#(#- 1#." ." -. ) -8 Ļ */, -.,.!3 - ,9 (σ1(L1) = 1, σ1(L2) = 1, σ2(l1) = 1), (σ1(R1) = 1, σ1(L2) = 1, σ2(l1) = 1)8 ).# .". (σ1(R1) = 1, σ1(R2) = 1, σ2(l1) = 1) ( 6 /. #-().  8 Ļ#- #- /-6 )/(.#(! ), (3 *,./, σ2(l1, ϵ)6 ." /.#&#.3 2*. 3 !(. g ,)' '%#(! .#)( R2B#886 σ2(l1, ϵ) < 1C

#--.,#.&3 -'&&, ."( ." /.#&#.3 -" 2*.- ,)' '%#(! .#)( L2B#886 gC8

Ļ /(#+/  #-9 (σ1(L1) = 1, σ1(L2) = 1, σ2(l1) = 1)8 (6 )/(.#(! &-) (3 *,./, -.,.!3 σ1(L2, ϵ)6 ." /.#&#.3 2*. 3 !(. g ,)' '%#(! .#)( R1B#886 σ1(L2, ϵ) < 1C #- -.,#.&3 -'&&, ."( ." /.#&#.3 -" 2*.- ,)' '%#(! .#)( L1B#886 gC8 Ļ # ) *,)*,(-- #(.,)/- #.#)(& )(-.,#(.- )0, ." *,./,.#)( 18,8.8 ." .", *,0#)/- )(*.-9 # .1) .#)(-6 -3 h(&)!)/-&36 1 /- li(q, ϵk) .) )(-#, ." *,./,.#)( ,-.,#. .) -7 +/( q6 ( 1 /- xi(ϵk) ( xi(q, ϵk) - ), ." - ) "0#),& -.,.!#-8 hi

(36)

ș8 ŞőŘŕřŕŚōŞŕőş

a, a′6 !#0 #Ŀ,(. 2*. /.#&#.3 .) !(. i6 ."( ." *,./,7 .#)( )0, ." 1),- .#)(6 -3 a6 '/-.  li(a, ϵ) ≤ ϵ ⋅ li(a′, ϵ)8 (

).", 1),-6 ." .,'& ) ( !(. )0, #.- 1),- .#)(- '/-.  -'&&, ."( ." .,'& )0, #.- -. .#)(-8 1) #Ŀ,(. )(7 *.- ) *,)*, +/#&#,#/' 2#-.9 ." (),'&7 ),' *,)*, +/#&#,#/' B,C ,ŀ(#(! ."  ( ." 2.(-#07 ),' *,)*, +/#&#7 ,#/' B,C ,ŀ(#(! ." 6 #Ŀ,#(! ), ." -.,.!3 ,*,7 -(..#)( .) 1"#" ." )(*. ) *,)*,(-- #- **&#8 - - - - - -,- ,-#!/, h8h9 &.#)(-"#*- .1( ." -)&/.#)( )(*.-8  ,#ł3 -/,03 ." ,&.#)(-"#*- .1( ." -)&/.#)( )(*.-B- #!8 h8hC8 && ." )0 -)&/.#)( )(*.- ,ŀ( ."  ( ."  B2*. ), ." C8 - )(-.#./.  -/-. ) 7 -8 - ( - , -/-.- ) -8 &.")/!" ." )(*. )  ( -' .)   ,ŀ('(. ) ." )(*. ) 6 ." #-(). ." - DjlE8 (6 ." -. ) - #- #-(). -.,#.&3 #(&/ #( ." -. ) -6 /. -)' - '3 ().  - - #-/-- &)1 #( 2'*& h8n8 #(&&36 ,- )(-.#./.  -/-. ) -( ,- )(-.#./.  -/-. ) -8 2'*& h8n )(-#, ." !' ,*,-(. #( #!8 h8i6 1", .1) 7 !(.- "))- 1") 1#&&  ." !(. B#886 ['[ ), ." [).",[C .". 1#&& .%  #-#)( B#886 [R[I[r[ ), [W[I[w[C8 Ļ !' *,-(.-  "( ()8 Ļ 7 - , (σ1(O) = 1, σ1(R) = 1, σ2(m) = 1, σ2(r) = 1), (σ1(M) = 1, σ1(R) = 1, σ2(o) = 1, σ2(r) = 1)8 Ļ /(#+/  #- (σ1(M) = 1, σ1(R) = 1, σ2(m) = 1, σ2(r) = 1)8 hj

(37)

h8k8 )&/.#)( )(*.-O M o m o m 1 2 1 2 r w r w R W R W 1.1 2.1 2.2 1.2 N          #!/, h8i9  #- (./, B1 2 #-  *,)#&#.3C:  (  , )/.)'-9 )." *&3,- *, ,  .) 8 ( ."#- !'6 *,)*)- #( DjlE6 ." -. ) - #- (). #(&/ #( ." -. ) -8

&2.#)(- ) -" +/#&#,#/'

Ļ )(*. ) -& 7)(ŀ,'#(! +/#&#,#/' BC DgnE ,&2- 6 *./,#(! -..#(!- 1", )**)((.-[ /.#&#.#- ( .3*- , /(%()1(8 ( ),, .) #(.,)/ ." )(*. ) 6 1 ( .) #(.,)/ ." &# )0, ." )**)((.-[ -.,.!#-8  (). 3 ˆσ−i ." !(.

i[-&# )0, ." )**)((.-[ -.,.!#- σ−i8 0#)/-&36 1&&7ŀ(

&# - ˆσi- , -/" .". ∑a∈ρ(h)σˆi(a) = 1 ), 0,3 #( ),'.#)( -.

h∈ Hi8  (). 3 ˆσ = (ˆσ1, . . . , ˆσ∣N∣) ." *,)ŀ& ) &# -8

ŀ(#.#)( h8gi B& 7)(ŀ,'#(! +/#&#,#/' DgnEC (  #-  *#, (σ, ˆσ) -/" .".9

R ), 0,3 !(. i6 σi#-  -. ,-*)(- .) ˆσ−i6

R ), 0,3 !(. i6 ˆσ−i#- +/& .) σi)( ." +/#&#,#/' *."8

#'#&,&3 .) ( 6 (  #-  *#, (σ, ˆσ) 1", σ , -. ,7 -*)(-- .) ˆσ8 #Ŀ,(.&36 ˆσ (  1,)(! )Ŀ ." +/#&#,#/' *." B#(-. ."3 '/-.  ),,.I)(ŀ,' )(C8 Ļ/-6 0,3  #- ( 6 1"#& (  '3  (). ( 8

(38)

ș8 ŞőŘŕřŕŚōŞŕőş

h8l )'*/..#)(& )'*&2#.3

&---1) ) ." ')-. #'*),.(. )'*&2#.3 &--- , P B*)&3()'#&C ( N P B()(.,'#(#-.# *)&3()'#&C8 Ļ ),', #- ." &-- ) *,)7 &'- .". (  -)&0 Ń#(.&36 -/" - ŀ(#(! -"),.-. *."- #( (.1),%-6 *,- )(.2.7 , !,'',-6 '.,#2 '/&.#*&#.#)(6 -),.7 #(!6 ( -) )(8 . )(.#(- && ." *,)&'- .". (  -)&0 3  .,'#(#-.# /,#(! '"#( #( *)&3()'#& .#'8 Ļ &.., #- ." &-- ) *,)&'- 1")- -)&/.#)(- (  0,#ŀ +/#%&36 3  7 .,'#(.# )/,#(! '"#( #( *)&3()'#& .#'6 /.  -)&/.#)( )/( #( *)&3()'#& .#' 3  ()(.,'#(#-.# )/,#(! '"#(6 8!86 8 Ļ *,)&'- #( N P ,./,(  I (-1,8

"( &#(! 1#." *,)&'- 1")- (-1, #- (). I (7 -1,6 /. #. #- ." 0&/ )  /(.#)(6 ).", )'*&2#.3 &--- , /-8 Ļ ŀ,-. #- FP B /(.#)( *)&3()'#&C .". #- ." &-- ) /(7 .#)( *,)&'- .". (  )'*/. 3  .,'#(#-.# )/,#(! '7 "#( #( *)&3()'#& .#' B#. #-  /(.#)( *,)&' 0,-#)( ) ." 7 #-#)( *,)&' &-- PC8 Ļ -)( #- FN P B /(.#)( ()(.,7 '#(#-.# *)&3()'#&C8

),'&&36 &. R ⊆ Σ∗× Σ  *)&3()'#&7.#' )'*/.&6

*)&3()'#&&3 &( ,&.#)(6 .". #-6 .", 2#-.-  *)&3()'#& p -/" .". ), (3 x ( y -.#- 3 (x, y) ∈ R #'*&#- ∣y∣ ≤ p(∣x∣)8 Ļ -," *,)&' --)#. 1#." R #-9 #0( #(*/. x ∈ Σ6 ,./,( 

y∈ Σ∗-/" .". (x, y) ∈ R6 # -/"  y 2#-.-6 ( ,./,( ." -.,#(! [[()[[ ).",18 FN P ." &-- ) && -/" -," *,)&'-8 FP #-." -/&-- ) FN P )(.#(#(! && .")- -," *,)&'- .". (  -)&0 #( *)&3()'#& .#'8

Ļ, #- ().", #(.,-.#(! &-- .". )(.#(- -)' #'*),.(. *,)&'- #- T FN P B.).& /(.#)( ()(.,'#(#-.# *)&3()'#&C6 .". &#- .1( FN P ( FP ( )(.#(- ." *,)&'- 1",  -)&/.#)( #- !/,(. .) 2#-.8 . #- &, .". FP ⊆ T FN P ⊆ FN P6 ( #. #- )*( 1".", ."- #(&/-#)(- , -.,#. DkfE8 /. .&&#(! 1".", R #- .).& #- /(#&6 -) T FN P #-  [[-'(7 .#[[ &-- B#886 #. "- () !(,# )'*&. *,)&'C8 ), ."#- ,-)( '(3 -3(..# -/&--- ) T FN P 1, #(.,)/9 PLS6 PPA6 PPP6 PPAD8 && ." *,)&'- #( ."- &--- , .).& -," ( ." *,)) ) 2#-.( #- - )(  -*#ŀ &'' ), " &--8 ( ),, .) -")1 .". -)' *,)&'- #-/-- #( ."#- ."-#- &)(! .)  -*#ŀ )'*/..#)(& )'*&2#.3 &--6 1 ( .) #(.,)/ ),7 '&&3 ." &-- PPAD8

Riferimenti

Documenti correlati

Spazio percorso in funzione del tempo e grafico della velocità; come dal grafico della velocità si possono ricavare lo spazio percorso e la legge oraria. Risoluzione

[r]

[r]

The image of the cell, displayed by the TV monitor, is covered with interference fringes, which represent the phase variation between the subtracted frames due to

In fact, as shown in Morgan and Scalzo (2007), if a continuous preference relation defined on a topological space – that is a complete and transitive binary relation such that

Dati i numeri decimali A=64, B=-63 e C=51, si determini il minimo numero di bit necessario per rappresentare contemporaneamente i suddetti numeri in complemento a due e se ne dia

In addition, three rhombuses denote the main sources of external information for the age- and gender-structure of the population, the ECB policy interest rate (in the

Il valore di mercato dell’attivo del conto patrimoniale delle Amministrazioni Pubbliche è stato, infatti, stimato in 1.800 miliardi (tavola 1), un importo seconda e la