Algorithmic Mechanism Design: Eine Einführung GERMAN

Informatik im Fokus Herausgeber: Prof. Dr. O. Günther Prof. Dr. W. Karl Prof. Dr. R. Lienhart Prof. Dr. K. Zeppenfeld ...

Author: Jürgen Steimle

26 downloads 584 Views 3MB Size Report

This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!

Report copyright / DMCA form

DOWNLOAD PDF

Informatik im Fokus

Herausgeber: Prof. Dr. O. Günther Prof. Dr. W. Karl Prof. Dr. R. Lienhart Prof. Dr. K. Zeppenfeld

Informatik im Fokus

Rauber, T.; Rünger, G. Multicore: Parallele Programmierung. 2008 El Moussaoui, H.; Zeppenfeld, K. AJAX. 2008 Behrendt, J.; Zeppenfeld, K. Web 2.0. 2008 Hoffmann, S.; Lienhart, R. OpenMP. 2008 Steimle, J. Algorithmic Mechanism Design. 2008 Bode, A.; Karl, W. Multicore-Architekturen. 2008

Jürgen Steimle

Algorithmic Mechanism Design Eine Einführung

123

Jürgen Steimle Technische Universität Darmstadt Fachbereich Informatik Hochschulstr. 10 64289 Darmstadt [email protected]

Herausgeber: Prof. Dr. O. Günther Humboldt Universität zu Berlin

Prof. Dr. R. Lienhart Universität Augsburg

Prof. Dr. W. Karl Universität Karlsruhe (TH)

Prof. Dr. K. Zeppenfeld Fachhochschule Dortmund

ISBN 978-3-540-76401-4

e-ISBN 978-3-540-76402-1

DOI 10.1007/978-3-540-76402-1 ISSN 1865-4452 Bibliograﬁsche Information der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliograﬁe; detaillierte bibliograﬁsche Daten sind im Internet über http://dnb.d-nb.de abrufbar. © 2008 Springer-Verlag Berlin Heidelberg Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte, insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von Abbildungen und Tabellen, der Funksendung, der Mikroverﬁlmung oder der Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen, bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik Deutschland vom 9. September 1965 in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich vergütungspﬂichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des Urheberrechtsgesetzes. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Text und Abbildungen wurden mit größter Sorgfalt erarbeitet. Verlag und Autor können jedoch für eventuell verbliebene fehlerhafte Angaben und deren Folgen weder eine juristische Verantwortung noch irgendeine Haftung übernehmen. Einbandgestaltung: KünkelLopka Werbeagentur, Heidelberg Gedruckt auf säurefreiem Papier 987654321 springer.com

! " # $!

% &

'! ( ) # #

* " ! ) + # ! ! " , !

-

&. / / ! 0 ! ! 1 ) 2 " 3 1 !

1 " & ! 2- ! . 2 - , 1 # - 3 - 2 ( "( - " -

1 # 2 - 3 - ! / " # / 0 4 / 2 2 - 5 ) ! 5 # -! 6778

9

69 ; $ 66 /< "( 6= 6=9 0 ( t 6=6 o 6== $ ! u 6=? s 6=@ ! f #( 6=> M 6? !() < 6?9 !() 6?6 < 6@ 1 !( 6@9 $1

: 97 9= 9> 9> 9: 67 6= 6@ =7 =6 =6 =: ?7 ?9

6@6 " 1 6@= 1 6@? A 1 !( 6> B C 1 6>9 3 B 6>6 BC1 6>= / 3 ! 6: ,(E) 6:9 ,(E) - 6:6 /

?? ?@ ?> ?: ?D @= @> @D @D >6

>@ =9 "( >> =6 ,(E) :9 =69 4( 2& ( 2 ! := =66 " ) (!) :> =6= (( E :: == ,(E) 0 ( 8@ ==9 1(

8: ==6 # 8D =? , (E) D= =?9 1( D? =?6 # ( ( 977 =?= , 979 97= ?9 # < "( 97> ?99 / 97>

?96 999 ?9= 2 # , 99= ?6 ,!( 99? ?69 99> ?66 ) 1 998 ?6= ! " , () 967 ?= - # < 966 ?=9 !() 96= ?=6 B " 96> ?== " , () 96D ?? ,(E) 9=> ??9 $! (E) 9=> ??6 - # < 9=8 ??= / () 9?9 ! "# 9?@ $ % 9@= & % 9>@

$ # # - !& ,(E) # $! ! 4 (E ; ( 0! "! & # & # C C ( ! A

!& ,(E)

F ( ! # 0 < ! - ! 4 5 / G H 0 # # B! & ) 0!

- "! G -! ( ; 1 B ! ! ! # ( / & & < $ "( # ! - & < <(!) - C/5 " ! B -

. & < ((! ( ,(

-! B ( ! - / - ) I ! 1 '! ! ( 5 / / "& 1 :7 J < K6L M ! 0 ( I -! F - ! ! ! ! / - -! (

N O 5 ( & ! ( / & % -

-! / -! - % ! -

B P -! - '! ! ) -! - ) A " ! " 1! $ '! ! ( # ! 2 G - -! B ! , ) # A . 3 1 '! % & , - ?7 * N,- ! A ( F ( ! O # 1

* ! ( $! ! " - # !

,(E) '! ( #! ! )

! & < K>D ?: =9 =: =@ = =8 D= D>L < / ( $! K?? D6 ?7L - 1- K@@ ?= DL Q ( R ! A) ( ( ! ! < P F -

Q(

R - ( - " ( - ( ( ) -! !

- ! "( - (E Q( R !

! - B A- 0 ( ; -! '%

" / < # ( ! ()

) I 0! & I A " , ; - , S 1 E( / E & !

,- ! - A ( ! G 0! ( -! A) # ! 4 - - A (

A ) , -! 0! / - A , ( A ) - - ) 1 / - '! A ! 0! & , & / Q( R ! I 0! ! , ! " # '

" ! ; 2 " ! -

2& )! - ! / - ( G () B &% 0 ) C( NCO G ;

& "( # ; - ( ) 1 ! ! C( ! ! ! N

O - ,( - "( /< ! ) 1 & ( ,!( - # ! ,(E)- # ,( '! ( "( / !( 2&

1 ! - ! $! # . ! ,( "

G (! / / $! G / - 2& )!

! # ! ,( < "( ! ,(

% $) ! / E B

" 1 / # ! ( - # <

A ! !

" 1 / (

& - & " # & 1 - - # 2 0

,( ( - " - B ) ,(

# ; - 2 & - ( ! ,( 6: ! ,(E) - # ! ) " - - A A -! ! & - B !

!

( ,!( - & ! "( ! "( ) I ! ! "( /< # ! 5 I ) 2 K>7 ,( 6=L ! I ! % ) # ( ( , 1! % # -! ( 0 ! B - 1 '! ) # ( A ! ,T ! ( # ! & & ( " !

4

( # / - ! 4 ! ! # - 1 '! && ; 1 E

!

"

- & $ ; ) I ! - ; ! E ( - " & 5 I ! 1 ! T -! ( # 5) ! P B & / ; U -! ,- ) '! & - 4 & A ; / F% ! ; ! ! ! - 1 ) 1 ! ) 4 - A / '!

( # &% G & '! % ! ; - ! ! ! ( #

! '!

#

!

; ) ! - )

-! % - - ( ! I & ) - A '! 2& (

'! 2& ! "( < / B ( " / E K9=L P

e1

e3 n1/n

1

e5

s 1

e2

t

0 n2/n

e4

! $ %& ' 1 1 ( G = (V, E) 69 , c : E → R , e , N A)

O ! ( - , n $ , s ! , t

( ) * +

/ 5 4 & A - $ 1 ( ) - ! , ! # "( , e2 e3 , F& 9 , e5 , , e1 e4 , F& " $ - , A ( n2 $ - , e1 - $ , F& 12 Optimum

e1

e3 n1/n

1

e5

s

t

0 n2/n

1

e2

e4

Eigennützig

e1

e3 n1/n

1

e5

s 1

e2

t

0 n2/n

e4

,-

. . /%

!

" " 4( - 1 F) A - , e1 − e3 F) A e2 − e4 ) N 66 O * , cs,t = 1, 5 A

-! , . U A - , e1 − e5 − e4 ) N 66 O ce ≤ ce ce ≤ ce & , cs,t = 2 A ! ) 2& ! ! N! 6@O 1 & #

) I & , ( % & /( - - B ) !

"

% K:=L / ,( ! /

! " (( E / # 4 - " ) ) ! ) I ( # "( ) c = 34 * A

&. c (! B & B ,( Opt

1

4

3

N ash

s,tN ash s,tOpt

2

( 0 %& %1 $ -

! ! ( A - "( - " ! , e5 ! )! "! F& 9 -! B ( 1

1

! F) A F) A ) A "( ! '!! . - ! -! B - ! < 1 - ) I

1 "( /<

/ $! - - ! A K>DL T E(!

- /< K98 =9 =: =@ =D =8 ?: = 8L 1 - ( ) 0 ( - - ! / 1 ( ! '! ! B - ! "

!

K6@ 69 ,( 6?=L B 0( /<

! - E < K66L 1 1 ( G = (V, E) $! ( ) ( S a ! b - $! "! ! 4 & , ! , G & 0! # , B ! 0!

/ 5 4 & ! ! 0 ( " A ( % , - F , c : E → R , G , A) ! A "( - 1 ( I 6= - A a b . / I ! E - 5 ; ( ! G ( / a b 1 ) , 5 - / ! , , , A ) I - " A & .

( 0 %& %1 $ -

e3 3

e1 2

e4

e7

2

e6 1

a

1

e10

b

4

e2

e8

3 4

2

6

e9

e5

2 - 2/ 0 %& %&3

-!

- & ! - ( G - ! / G ) - 5 ; ! ! ! , ! 5

B ! ! /"( 0 A ! ) ( ) - ! E( ! * " A " ! )! A ! " 1 0 - % " ! P 3 " ; ( A ! ! A ( 0 (

!

-! 0 ; A ! B ) // F 0 4 0 ! $!

) A a b A )

(( ) t

" / n / I ! E - B 3 - !

- B ! " B B ! ! B ! ! ! - #! ! B N! " K>6 :8LO B 5 ! ) B * ( # - 2& / # i Ni ∈ {1, . . . , n}O

( !

4

Typ t1 = 2

e1 2

a

e2

3

Typ t2 = 3

! 56- 3 0 %& %1 ti ∈ T ! P T = R # // ( 0 ( ti , i A $ , N 6?O # "(

( , e1 ! 0 ( t1 = 2 , e2 0 ( t2 = 3 A t - 0 ( (t1 , . . . , tn ) t−i - 0 ( (ti , . . . , ti−1 , ti+1 , . . . , tn ) . # $ B t - (ti , t−i) - . 0 ( / # ! " ! 1 ( G &%

(( o

-

- - #! ( 4 5 #

! o1:

a

b

o2:

a

b

a

b

a

b

o3:

...

o4:

3 3 0 % & %1 o N P O - & O ! ) ( /"( O A a b & 6@ o1 ( - ! / 1 ( 6= /

- & A % # ,( ) ! ) ! #! ! ( # 0 ( ) &

s ! ) o -! !

0 ( ! T

! pi - !

( !

"

I ! ! 6> Agent 1 t1 1. Wähle Strategie s1(t1)

2. Deklariere s1(t1)

...

...

4. Zahlung p1

Mechanismus 2. Deklariere sn(tn)

Agent n tn

4. Zahlung pn

3. Bestimme Ergebnis o

1. Wähle Strategie sn(tn)

Auswirkung

! 0+ I /< ) P ; ) 1 , A

#

!

( , ) . - / a b ; , - ! / ! - $ A / ) %

(( *%#+ u

& % & - $ ! $ ! - !" ui : O × T → R N P O - - 0 ( ti & o A ! $ ! i 0 ( ti ( ) $ ! ! E P i ( ) o1 - o2 ui(o1 , ti ) > ui(o2 , ti) A

- $ ! ( !

! $ ! 0 ( 0 ( ) $ ! !

# ! B $) V $ ! $ ! 1 N A) O

( !

! $ ! 1! pi $ vi N P O - o 1 V $ ! P ui (o, pi , ti ) = vi (o, ti ) + pi

vi : O×T → R A - o ∈ O - i pi ! ½ en Nutz

–

Aufwand

+ Finanzielle Entschädigung

! 7 *

( ( $( 2 8 9

:; 2/ * # "( /< - vi P 1

0-: ; 0 s 3% 2+ g ) 2+ pi 9 3 ; % 7 * 2+ :9 3% :+ 0 /+ < ui (s, ti ) = vi (g(s), ti )+ pi (s)(

! ⎧ ⎪ ⎨−ti

). o i $ ⎪ ⎩ 0 ( A $ A - ( A ; A ! & , pi > |vi | $ ! ( G ( I % ; 6: A $ 7 # $ ! - !

$ ! A - - (! V " P $ ! - ! ! A ! ! ) , . % "

&" . "! pi T A vi Q o - ( A vi pi ! R ( - & #

vi =

( !

(( & s

A ! A 0 ( ) $ 0 ( &% ! $ ! !

&. A ) A U ; 0 ( / ( P ( i ) si ∈ Σ - A ) 0 ( W , F ) - ( ( i ) . &% ( , A I )

0 ( N(O - ( P si : T × Σ n−1 → Σ # ) "( - " ) 0 ( I P si : T → Σ " - - ( $ " 1 & ! 6@ # ) 0 ( ) I (! ) ! si ! " /"( Σ ! % ! " 0 ( 1

!

A / a b " ' ! 0 ( tˆi = si (ti ) A ! P Σ = T 0 ( ). 0 ( i A ( ( , F& > 0 ( ti = 6 & & , !

! " tˆi = 8 / I !

&. 1 )! - (E 0 ( " ! "( 1 N O

# 1 ! ! " ! " 1 F " % 1 & ! 1 " - A ; ( " & 1 ! " - 1 !

n ; i 0 ( ti = 100 E 977 - 1 ! ! pk & 1( pk+1,i 1 i

p1 ≤ p2 ≤ . . . pn si & ( P

⎧ pk+1,i = pk + 1 ⎪ ⎪ ⎪ ⎨

( !

pk ≤ 99 " si = ⎪ pk+1,i = pk pk 1 ⎪ ⎪ ⎩ ; $P # !

( I (s1 , . . . , sn ) s ( I . i (s1 , . . . , si−i , si+1 , . . . , sn ) s−i ! B s (si , s−i ) - 5 !

" , # ! 1

((! &% #+ f ,

A ! ; Q R ! . U . ! Q R ! # I ! % " f : T n → O I Q R - A ; " <

- B ! ! ( Q 9 0 ( 97 6 0 ( 8

!

o1 W X R # / < Q R ( - ! A ! , a b ) , , . 0 ( ! 0 ( 0 ( I -! P A 0 ( &% ) - ! ! ! -! B ! I Q R !

P 4 -! ! ) - 0 ( &% )

! " "( /< Q R ( ! A a b ) , ) " , " & ! 3 E ) / !( - "( - E ( !(P QA 0 (( I t o -

( !

4

) f (t) = oR A

E ) '!! " <) -%%

" "( B 1 " $ A 1 - ; v1 = 6 v2 = 10 v3 = 8 1 i (i ∈ {1, 2, 3}) vi = 0 A

& ; U 1 1 ! ( -

&. A vi # "( 6 A % A i vi E . (! . ( /-%%0( % ! %

" f (t) ) '! ( (* %+ o *

$ vi

, * - - . t = (t1 , . . . , tn ) %+ f (t) = o * o ∈ O / n i=1

vi (o, ti ) ≥

n

vi (o , ti )

i=1

% ' ) (! * (! ! % " -

A - '!

A vi $ ! ui

!

A 1! U 1 Q R !

; Q R ;

A " 3 "( Q R /< A $ F ; A vi A $ , '! ! ) , E ni=1 vi '

$! i pi ' ! ( . 2 . ! " A $ - " ; - "( F ) . & 5) 3 P 0 " ! ( - 0 (( I t = (t1 , ..., tn ) n ; F& 7 P i=1 pi (t) = 0

( !

"

- - 1Y ) 0 A # " / I " E! " A 1 ! B , 1

A $ ! ui - i ( A # A $ - i $ # - 0 & & & ! - ! 0 5 !

) I 0 - A ( /< ! . - , ! & ! - $!

( ( / I 0 - $ ! 0

&.

$

#

!

! f ( - 0 ( t = (ti , t−i) P ui (f (ti , t−i ), ti ) ≥ ui (ti ) ui (ti ) $ ! - i 0 ( ti $ -

((2 M

" & 1! ! 5 !

B Q R !

I ! (

I Σ %+ " g ) o ∈ O % . I - 1 " pi - 1 ! ( F ( N

O A 1 QR N ; O ; Σ g ; pi ! ) -! B ! - - g ) ! f - ( # / ! N 6@ -

O A ! B - I - B & I P

( !

. ( /0( + n

t1 , . . . , tn ∈ T % O- % ' M = (Σ, g(·), p1 (·), . . . , pn (·))

Σ * %+ " g : Σ n → O 1 " pi : Σ n → R i ∈ {1, . . . , n}-

A ( A pi ;

A ; B ; (p1 , . . . , pn )

p ! p pi - ; - A ,E "! A - /9 ) I - // @= ! I

!

- 1 . ) & ( 0 ( ) - & & NO ) < & NE ( O

B " - ! " # $ % $

A I " ! ( P -! ! ( 0 (

! ! & % < / ! ! 0 ( & -

) # ;

0 (

(( %+

I 0 ( ! 1 ( - <

( +- 3 : 0 13

! ! . !" + ! ! ! - - F ! K?D =67 %L - ! * 677: A ( ! !() ,!( - - - & N

O 0 ( !" + ' ! ! ). ! . 0 (

! ) -!

). ) / I E !( %

0 ( $ ! - E !( ! ! ! ). " +

'3 4+ +

5 / !( !() ! "( 1 ! " B 2! ! - V ! ) " ! " ! 1 5 1

! Englische Auktion

Vickrey-Auktion

Zuschlag

Zuschlag

Preis Preis

Gebote

10

8

5

10

8

5

+ + 6%+ - ( - ! " 0 ( 3 " & 1 ! ! - " 9 !

2!! A 97 0 ( t1 = 10 " 6 0 ( t2 = 8 N 68 O " ( - 0 ( - ! P A " 6

t2 = 8 & " 9 0 ( ! " tˆ1 = 9 - ; - 2!! ! / A ) !( 0 ( - 5) B ( 3 ! ) I & < & - ! - P

( +- 3 : 0 13

B " 9 t2 A 8 tˆ1 = 7 " 6 ; - 2!! - " 9 & A G '! B A B

KD9L - '! / !(

; " & 1 / !& 1 < N 68 O 0 ( ). !

B "( - !( B 1 - - " (P 4 - 9 A 977 t1 = 10 - 9 1 tˆ1 1 A ! & 1 tˆ∗ 5 & )P tˆ∗ < t1 ! " tˆ∗ = 9 N 6D9O - 9 4 & A

9 & 4 - 5 A

&. tˆ - ; ! / !& 1 tˆ∗ = 9 A- tˆ∗ - ;

tˆ1 = t1 tˆ∗ > t1 ! " tˆ∗ = 11 N 6D6O 9 !

) - A tˆ∗ = 11 9

!

10

^

t1

t*

verliert Zuschlag

9

t^1

11

10

^ t*

t1

3. Andere Gebote sind gleich hoch

10

10

t^1

t*

^

t1

egal (da bei Zuschlag gilt: Wert=Kosten)

2. Andere Gebote sind höher

egal (Preis bleibt 9)

1. Andere Gebote sind niedriger

Zuschlag, egal (kein Zuschlag) aber zu teuer

t^1

+ 8 ! + tˆ1 3 + 6%+ =tˆ∗ 8 3 ; t1 56-> - P ; A- tˆ∗ - ; ! ! - ! / ) - tˆ∗

tˆ1 = t1 tˆ∗ = t1 N 6D=O # 9 ! & 1 $ ! ! 1 3

! " ) - ; ) A

tˆ1 = t1 A ) 2&

0 (

( +- 3 : 0 13

4

; B / ! ! & ) 0 ( !() ) # ( B / !& 1 < - - Q& " R ; ) - & & !()

5 ! ) & ; ! 0 ! "( B 2!! < - 1 & " ! ! ) ) - F& !& 1 & Q3 ! R & ( ! ( N$) ! 6>=O pi

(( & 1

B !() B ! P & ! - B& ) E ). 0 ( $ ! 2 & ! A - ( ) N

!

$ ! E O 1 $ ! - E # - ( ! ! # 1 ) ! B - E ! 1 1 - i 0 ( ti - s−i & si si E P ui(si , s−i, ti ) ≥ ui (si , s−i , ti ) - - 1 !( ( 6@ ! I 1 ( E

1 # 1 ) I ,!( !P # 1 E - )

-

( - ( B - - ! . #

. ! "

. B " - " - B

( +- 3 : 0 13

"

(

,(E) ! 0 A - " -

!( B , 1 - - ! F ! . + . ( /& 0(

3 ! ( 4* " % ' )

' * + $ * ) " tˆi = s(ti ) = ti * + - 5 )* 2 i

, ! ui * ) " -

!() ) 1 ! " " 1 N 6@O I A ! 5 5 ) U ! N K>7 8:: LO ! V $ ! '! ! ( ; G B C 1 I 6>6

#

!

. ,( 5 P < ! B % - 1 (( & ; ( $ ! 1 (( !

&. ( , & . + 4 # , - - B &% ! ) & ' #

# 1 !( - (

I 1 !( B ( ! # 1 !( 1 B !

- B ) ! ,( 2 ( ! - () " 1

!( ! - 5 B ) ! I 6= 1 !( / - -

(

+ -

1 !( ( K>7 ,( 8 6=L ! I ,!( 697 Gleichgewichtskonzepte Nötige Kenntnisse über Mitspieler

Dominantes

stärker keine

Erwartungswerte über die Strategien

Bayessches Nash

schwächer

Kenntnisse über die konkreten Strategien

! 3

+ -

(!( * 5

,!( $1 K>@L $ 1 i si

) $ ! - 0 ( " - ""

s−i - E A - ( ) ( I "

% 1

!

( I s = (s1 , . . . , sn ) $1 - i " ! ) si - ) ( s−i = (s1 , . . . , si−i , si+1 , . . . , sn ) - si = si P¾ ui (si (ti ), s−i (t−i ), ti ) ≥ ui (si (ti ), s−i (t−i ), ti )

$ ( ! ) I $1

E B ! - ( E! $1 & Strategie Spieler 1

Strategie Spieler 2

D

E

F

a

5, 2

1, 3

2, 5

b

3, 1

5, 5

3, 1

c

2, 5

1, 3

5, 2

0- * %

,!( $1 "( P ( ! 2

0 ! 9 * %

( ? @ / @

; % ; /; 3 %

( ! 3 ; 0 % ;

' ; 3 ; A :

; 2/ -

3 (

(

+ -

( ) & 699 ! $ ! - A) ( ( 9

( 6 - ( 9 $ ! @ - ( 6 $ ! 6 ,& ( - ( B ! ) $1 (b, E) 1 P , ( 1 ( I (

( A & / E ) &

) - U " - ( ) & ( , ) B - ) ) # ! I & ) < - ( ! / ! # / ! ( ) 1

/ 1 !( ( $1 " 696 / " & 96 5 4 % 4 "

! Strategie Spieler 1 Bahnhof Oper Strategie Spieler 2

Bahnhof 50, 50 Oper

0, 0

0, 0 50, 50

0- * %

4( % - 5 A E ! $1 5 ! % - / $1 ) 1 ) ) ,!( $1 - " 1 !(

. A ) ,

,(E) "

$1 , 6 K:=L $1 - # !

(!( ' 5

$1 ( -

# - ( - & ! 1

(

+ -

( " ,

,!( ) # " 1 ! , ( $1 * ) si $ ! 0 ( ( E ( I s = (s1 , . . . , sn ) " 1 - i "! ) si - si ∈ Σ P E[ui (si (ti ), s−i (t−i ), ti )] ≥ E[ui (si (ti ), s−i (t−i ), ti )]

E[ui (si (ti), s−i (t−i ), ti )] $ ! - A 0 (( I t

(!( 5 &

1 1 !( , - ( & si E & $ ! &

) 0 ( t−i ) s−i ( # 1 - "! ) si - si ∈ Σ s−i ∈ Σ n−1 P ui (si (ti ), s−i (t−i ), ti ) ≥ ui (si (ti ), s−i (t−i ), ti )

!

1 ! $1 ( 1 / ( 1 $ ! ui . $ " 1 N O B ( ) ( 1 ) , ( & - A - ( & 1 !( 1 # ) I ! A 1

!( ; ,(E) 1

!( - -

(!( 7 5+%

A 1 !( - A ) ! B ) A 1 !(

- 1 !(

- ( ) *

A 1 & (

( + 6%B + % %

4

# / E & ,!( ) & < - ( B - 1 A A - ( & ! " 1 $1 ! F ! K@9L ! & '! ! N O "

!

V / ) ! E & !( ) " 1

K6? :L ! )! " 1 & N K>7L 8D@ O 3 1 !( ,!( & ! " , !( E ( $1 ?66 ( )*+'

M = (Σ, g(·), p1 (·), . . . , pn (·)) // & Σ 6=? Σ = T I A - g ; p1 , . . . , pn I

# 6?6 B

% !() - 0 ( ! - " -

!

! .

1 !( - B ,

- - - "( /< ) - $ I // 66 - '! ( o ∈ O ni=1 vi (o, ti ) E I ; E - N- !O / ) - // E ( ! " K6@ 69 ,( 6?=L A - ! 1 5) " A a b ! I 6 "7 "' NBC1O KD9 9: ?>L , ( - ! A ! ) B ; B ! BC1

( + 6%B + % %

"

(2( 8 # 4+ +

" B ! <

! ! N! ! O

) & ;

! ;

G - G / Q& " R 3 - B & / ! ! ) & A - A ! " - / ! )! ! / % ! , - / , ) - / , ! F) ) & ) , ( - - / , ! - / - / ) 2 ! / 5) ; " "( I - " "

%P

#

! e3 3

e1

e4

2

e7

2

e6 1

a

1

e10

b

4

e2

e8

3 4

2

6

e9

e5

! / % &2 - . ( /k 6# 0( % k a b a b* + k + -

# "(

( 69= - / , c1 = 6 A- , e1 ! ) - / & ,P - - , (e2 , e5 , e9 ) ) , c2 = 13 9 / , e1 ) & , 2 + c2 − c1 = 2 + 13 − 6 = 9 & - / - / A ) - ( A ! ! ! ! )! " &

P 69? ! & & - - ! / A- & "

( + 6%B + % %

^ t3,max = 5 ^ t1,max = 9

^ t6,max = 3

e3 3

e1 2

e4

e7

2

e6 1

a

1

e10

b

4

e2

e8

3 4

2

6

e9

e5

! ' 8 ! + A

) , - ! / - ; " c2 − c1 - / !! ! ! " P ( " 0 < 1 A- , ) < -

/ ) F - / , > - 9 / , 9= 9 0 1 : ! )! ! ! B 1 ! )! ; P E

! - / / ! )

) , ; !! ;

!

B 1 ! - ' ! / !( ' # - 1 &

G

0 (

0 ( i ! % ! ! ,

- i / !- , - / , i 7 # ! , - / a b 1 ( G cG , - / , i , 7 ! cG|t =0 - i / ! cG|t =∞ / - , i - / , - ; P 8/ i - / pi (t) = cG|t =∞ − cG|t =0 N69O 9/ i

i

i

pi (t) = 0

i

- /<

( I ; 1 69 ; ) 0 ( % !

!( s(t) = t - 0 (( I t $ !() & <

( + 6%B + % %

!

; - ! I ) P . (! /& 60(

' MSP = (Σ, g(·), p1 (·), . . . , pn (·)) : / Σ = T = R %+ " g(·) + ' a b !"* + 2 i si (ti )

- 0 ! • 1 "

• •

pi (·) =

⎧ ⎪ ⎨cG|ti =0 − cG|ti =∞ ⎪ ⎩

0

i

(2( 9 4:

; C 6 "7 "' NBC1O KD9 9: ?>L BC1 '! - V $ ! (!) ! " ! " & ! -

!

- vi (·) ) '! BC1 ( N K>7 8:D LO . (2 /4+ : + 0( % 67' "

' # !" - 5 %+ " +

g(t) ∈ o∈O max

n

vi (ti , o)

i=1

5 1 "

pi (t) =

vj (o, tj ) + hi (t−i )

j=i

+ hi + + " t−i -

/ ! BC1 & P j=i vj (tj , o) ;

I ( 1 69 −cG|t =0 Y hi (t−i ) cG|t =∞ # BC1 ) "! i 0 ( 1 A 0 ( 1 T ( "! N( O T j = i ; - 1 A 1 - ! i

i

( + 6%B + % %

B ; ( A ) ; - ! E Q R -! # - 1 &

$ ! E ! 0 (

! $ < BC1 A hi . NO " + # ; - // I h−i A cG|t =∞ (! BC1 ) F C K9:L . C C A BC1 ! ! , ( ! (! # E / ( E '!! F ! ( 0 ( $ < K>DL - ! !)P k 0 n < ;( ! ( - 0 n < & A ! '! ! A E 1 ! " Q'!R i

!

/ -

!(

(2( 6 8 %

; BC1 / < ! ; & A , / 3 !

/< 0 ! & ! K=9L // ) I !

. 3 ! - P " / ( 1 - / 1). BC1 0 j ! )! ! % ! Δj ! ,

- j / - / !

! 3 ! kj=1 Δj ! k ! 1 * 1 &. k Δj 3 ! 5) B ,

- / 69@ ! - "(

( " - ! / "! - , . ! " ( & , 3 ! !

( + 6%B + % %

4

Tatsächliche Kosten (Typ)

2

+

3

+

1

=

6

Bezahlung

9

+

5 e3

+

3

=

17

3

e1 2

e4

e7

2

e6 1

a

1

e10

b

4

e2

e8

3 4

2

6

e9

e5

- +8 B C3 % 3 2

) ! I 3 ! <

#

! E ! - // ! // 1 ( ! / a b )

! c(P ) + 12 k(c(Q) − c(P )) ! ! c(P ) , - ! c(Q) !- ! / k ! , P K=9L . ! 1 ( ) 1

!( " 1 E & ) , !

! √

BC1 k ) , ! # ( ) 3 ! - & - #

( ! 3 ! ) K=@L ! ! , / E

) , K@=L / 3 ! ) ( ! ! " ) & (E ; - BC1 - !() ) ) " Q R /< 2

4 ! ! 2& / " ) ! 5 ! E "

! '! K==L C K9>L ) I BC1 ! '! ! & ! ! ) < & " ) - ) ! E " 3 ! BC1

)! ! ! ; ! ! 3 !

(4 ! D-

':

"

K=7L ! / < ; Θ(n) ! & , 1 ( - $/ 5 , ! I (!) (( E ,

-. %

- ( ! C( ,(E) 2 ! ! " 2 . #

T B &% $ < K>DL )

(;( #<

/ K:?L - ,(E) ,(E)V ! N 69>OP 9 %+ P , +

P 0 ( 5) (E " " ( / - 4 ! # / -

#

!

Agent

Typbestimmung

Kommunikation

Mechanismus

Ergebnisbestimmung

Strategieberechnung

! D-

':+ 3 , 1 ! # & ! " 1 (E " & B ) ! / ! /! - / $/) ( - 1( ! , + P - ( B ! " 6 ; "%+ P , %+ +

P ,( E) " g ; pi

(4 ! D-

':

" " , P

,(E) ! ! ( ! -

! " -

! , - ( & ,(E) # / $ ,(E)

! 5 ! ( ; , / E( & , $/ , / - ( ! ( 5 / = $/ , $/ $ '! ( # ,(E)! ! - - - $ < K>DL ,(E ) . (; /6 0( %

' ( ; * %+ " g 1 " pi 1 ++ -

- ( ! ( " - ( , & ,(E) 0 ( (

!

! ( ) $/) I P . (= /*6 0( % ' $/) * %+ " g 1 " pi -

A / "

; 5 / ! / - )

(;( & 6

,(E) - ,(

- /< ( ! ) A I 6@ ,(E)( , +

B 5 0 ( ! , A $ - , $! A , + / - N 6?6O

(4 ! D-

':

" " ,

$ I 0 ( 1 0 ( ; ; / !( ! " E - ( 1 " ! " =6 " ( ;

$

, (E) C

&. ; ! - " ;

/" , " , - ! / 1 ( E n + 1 /" " & K6@ 69 ,( 6?=L - - , ci = ti ! I - ! / $! O(m log(m)+n) m ! , n , n+1 ) , %+ +

O(m2 log(m) + mn) ( I ( 6: F K?:L ; O(n log m) - /<

,(E)( '! (

!"

# ,( - /< & ( 1( ( E

! $/ E( , # * ) # ! / )! '! #(

# ,( ! / #( ! B &%

)! Q R ! '! #( ! I - ) ,( "( /

%- 6

D-

':

A " Q R

P / - ! - B

& ( $ "

B

,( " & 1 ! + 4 =9 ,

1 ! )

! A 4 < ( 1 ) 4 & ! " < ! " B C(

!! 2 ) /< ,( I P A , ! & 1 - $

- , , " , 4 ( )! - & - ) ! & & '!! / !(

( ! $ - +3 +

4

Die kombinatorische Auktion

Linke und rechte Socke

Linke Socke

Biete 10

Biete 0

Rechte Socke

Biete 0

$ +3 + +8 3 2 D3 ,3A + 3 3 ! ! 4 (( E B

- ) I ! '! K9@L " $ M = {1, ..., m} 4 n " ! & O = {(S1 , . . . , Sn ) ∈ M n |∀i, j : i = j ⇒ Si ∩ Sj = ∅}

Si ; "- 4 i ( 4% I 4 G / !( 4 ' " 1). 6= 0 ( ti NV O $ ! ;

"- S ; pi ui (S, pi , ti ) = vi (S, ti ) + pi vi : 2M × T → R+

%- 6

D-

':

- A , 4 M - i 1 - $ vi (S, ti ) ! vi (S) A ; vi (∅) = 0 A A vi (S) A . . E ) A vi (S) 4 ) i ; j = i # ) ; (! ; ! I ; ! A vi E P S ∗ = arg

max

S=(S1 ,...,Sn )

n i=1

vi (Si )

A " 1 , 4 ! ! 4U , 4

! ) ! " & " - ! 1 F& 7 - - , 97 " "

" 5) - ! # < ! ! ! !

" - ,!( vi (A ∪ B) > vi (A) + vi (B) %!+ " 37 4 ! 4 ! - " A ! & ! " "

-

( ! $ - +3 +

"

0 & ; # " ! " ! &

- "

" < ! ! # & < . vi (A ∪ B) < vi (A) + vi (B) %!+ " 3+ + 4 ! ( ( & 6 "" 364 1B & ! B C 1 B B - ! 4 ,( - ! ) 0 ( Bi = (bi,1 , . . . , bi,j ) 1 & , 4 2m 1 ( 1 bi,j = (Si,j , vˆi (Si,j )) A vˆi (·) 1 -

A vi (·) ( & G ,( G 0 ( 0 ( ( "(P ! 4 M = Z

0 [ 0 ( & 1 ( P

4#

%- 6

D-

':

Bi = ({

}, 0), ({ }, 0), ({0 }, 20), ({ 0 }, 19), ({ 0 }, 19), ({ }, 10), ({ 0 }, 35), (∅, 0)

A 0 ( Bi - o ; pi 1B - - & ( '! " - V $ ! K:?L 1B 1( N =6OP 9 %+ +

P * ( ! 2& ( $/ 6 +

P - - 2m 1 ! 0 ( A * 1 5) 2& $/ / =

" P - - 5 4 S ⊆ M 1 b - E 2m 5 ! - # E( ! ! 4 , / '! 3 1

( D-

': 33

Agent

Kommunikation

4

Mechanismus

Ergebnisbestimmung

Typbestimmung

!

!

!

exponentiell viele atomare Gebote

exponentielle Informationsmenge

NP-hart

! &3

3 % 2/ +3 + ( F !( ) ! ; 2& / - ( ( ) 2 )! - ,( 3 -. % /$ $

B ! ,(E) )! - < !

,(E)

4

%- 6

D-

':

Agent

Kommunikation

Typbestimmung

! NP-hart

Mechanismus Ergebnisbestimmung

-> Verzicht auf polyn. Laufzeitgarantie (S. 73) -> Beschränkung auf Spezialfälle (S. 76) -> Approximationen (S. 77)

: 2/ E 33 3 +3 + < # A#1F0 0 /C,#$1 ! ( $/ K89L 5 6 = *6 & '! 2 ! I / ( &

! - (( E ( 2 ! & K8=L # )! N ==O & / ( & ( A C2 ! &

- / ! E

( D-

': 33

4

5) (!) / ( ; ( & & # ! & / !

. (!) ) N ! ! A C2 !O (( E # & ( ( > $? $#%

B ! 2& ( / ! & ( ( & 2& - - & M ! 4 " - ( - =? - "( ! 4 {1,2,3,4}

Ebene 1

2 {1},{2,3,4}

3

4

{2},{1,3,4}

{1},{2},{3,4}

{3},{1,2,4}

{1},{3},{2,4}

{4},{1,2,3}

{1},{4},{2,3}

{1,2},{3,4}

{2},{3},{1,4}

{1,3},{2,4}

{2},{4},{1,3}

{1,4},{2,3}

{3},{4},{1,2}

{1},{2},{3},{4}

!

: & $ - ,3A +

4

%- 6

D-

':

& N) / O ) / / 5 / * 0 ) / " - / E A "

. / ) / & A ! 0 " " - 0 & 1 # - ) / F ! ) - ; "

% ( ; - ! ) / E( ! 4 K8=L # =? ? 4 9@ / ! ) P 8 4 ?9=D / 96 4 - ? & / ! ; 4 N ) !O - ( & E A - / ) ! / !( 6 A E - () ;

! ) E A v(S) - 0 S \\ ] 9 A -

&. 0

( D-

': 33

4

( A ! -

P E A

S ) 1 - ( S 1 - ! 5 S E A - 5

- E ( - A /

( " 0 m ! 4 M

- 2 ! Ω(2m )

/

A C2 ! O(3m ) ! K8=L ) ! (E -

. ! 4 " / ! 1 &. 67 =7 4

2& !( 2 ! " C2 !

(E @ + ( I ( $/ & F ( A C1 K8?L

C 2 ! ! ! ! $ " & 2m 0

M 1 # 1 ! ! /

/ 2 ! ) ! 1

4

%- 6

D-

':

( ( ' + # &%#

! 5 $/ / " ) (!) / / ! & & (!) & ! ! B - ( ! C

3 0 ( N =?O (!) - & ) - !

& '!! 5 ) 0 ( - & "( A , 4 - , / / ! ,

& (! / ! / !

& ( & (!) ( ( 5 - 1 & ! 4 K8=L ( ; O(m3 ) Nm ! ! 4O 5 4 & / $/ ( 2& / ! & 4 M 1 ! ) # 4 & / ; O(m + n) & K8?L n ! " -

( D-

': 33

44

( (!) ( K8=L ( (

# ! F ! 2& I $/ $/) / , (( E & / ! ) - 2 ! " $/ ) / ( 2 ! ! (( E A & ( - ( ( E - A C2 !

(( E C 2 ! ! A + 4:

# ,( BC1 - , '! B

- '! ( P ) & '! ! 6>6 I BC1; # ) ( ( E 1 BC1 !

NEO ! (( E ! !

4

%- 6

D-

':

67+ '

K:7L ! 4% BC1 ( BC1 - BC1 (( E ) ! - < K:7L N =@O VCG-Mechanismus

VCG-basierter Mechanismus

Zahlungen nach VCG

Zahlungen nach VCG

Exakter Algorithmus zur Ergebnisbestimmung

Approx. Algorithmus zur Ergebnisbestimmung

Strategisch robust

Meist nicht strategisch robust

B%3 3 ! P A < ). 0 ( ti $ ! i & 0 ( E & " (( E !

( D-

': 33

4"

) (( E g (ti, t−i ) & ( g(ti , t−i) - ! $ ! - # - ( ! 0 ( tˆ1 0 ( ).

( BC1 A BC1 ( < BC1 ( ! # 2 - / & )! BC1 ! ) - ) 1 , A ! ) ! )! ! G ) I

) G B

BC1 ! (!I ! ! BC1; & BC1; (!I Q R ! (( E !() ! A B ! !

#

%- 6

D-

':

)+ #< 4:" "

$ < K:7L ). 0 ( BC1 ( ! ) BC1 A BC1 0 ( %

! A - - B - ; BC1 N 6>6O & $ ! ! - '! ( I

-

0 ( ! )! (( B ) - 0 ( 5) ! -

& 0 ( - (( - ) '! (( " & '!

( D-

': 33

(( ,!( 1 ( - ) ! $ ! )

! "

( ! $ < " ) ! ! 1 ) ! ). 0 ( ). 0 ( ( ! ) 1 - ( - + ! - - ,!( !

+ 3 + 4 5 #( ! ( - &

- (( BC1 B BC1 A - B - : ", 5"

G / E ! ( G ! K@>L < A !

%- 6

D-

':

< BC1 (( E ! 1 BC1 ) ! < " E $ ! 0 ( ). 0 (

/( 1 ! ! ) $/) !! 4( ( 2/<E " !! 2& ! ) / & B & !! 4( ( 4 ) " 4 " !

)

( <E / & ! - ! - 4 ! & )! <E 1!! !

4 ! 2& ( $ <E 1!!

P E

!! 2& ( ; , E !! ; !

) A !! 2&

( D-

': 33

A I ; BC1; !! 2& ( I ( 2 ! ( ! - - ) 1 (( E √ O( m)

Nm ! ! 4O ( !I ! N O

#< + +

& ). 0 (

( ! ! - (!I ! , ! I < (( E -

( ! ! 2 & 2 K@8L - )! - (! + K>= @L + ! 1 -

%- 6

D-

':

! N5 O 4 3

/ $/ K@8L (( E ! -

% X $ K>=L / ! (√m)(( E Nm ! ! 4O , < 1 B 2/<E K@L (( E <E

! ; ( ; ! & (1 + )(( E (! " K6D =? @? 6:L + + A v 4 - - 0 S, T ⊆ M ! 4 m P v(S ∪ T ) + v(S ∩ T ) ≤ v(S) + v(T ) e ! ( K6DL - ( e−1 ) (( E 2/<E

<

! K68L " 5 (( E -

- (( E 1 - (! A 1−e K@?L " (! ' "

E( 4

! $ 6(( E K6>L - " K9?L O(m1/B )(( E

( D-

': 56-3

Nm ! ! 4 B ! 4 O - ) 1

! K68L (( E )

/ ! B ( (( E O(√m) A 1 − ( 2 ! !( (( E / !

-. % 0*$

A ! / ! (E G ,(E) 0 ( A ! " ,( 6 "" ( & - 1 - 2m 5 M ! 4 1 ! 0 ( - 0 ( - E ( 1 "

! 1 ) , (E) " ! "

1 - 5) $/ ) /! 5) $/) (

%- 6

D-

':

Agent

Typbestimmung

Kommunikation

Mechanismus Ergebnisbestimmung

! -> Gebotsprogramme (S. 87) exponentiell viele -> Iterative Mechanismen (S. 89) atomare Gebote

: 2/ E 56-3 3 +3 + - 1 - ;

/ ! - ( ! 1 ( - ( " ( ) & ! - ! - ! " ) 0 ( % & 2 " ( ! # - 0 ( & # #

( D-

': 56-3

4

! ( 0 ( 0 ( ( F( (!I! (!I - < - A ! ) ! ! ((

F( ! 0 ((!I - - 1 - & ! - (!I! / 0 ( +

/

- - 1 ! 1 (

(!I 0 ( ( " 1 ! ! - P . (!I 0 ( ( " 1 ! ) "

! ! 1! 1(

) B " ( - ) a(S) & A v(S) - S ! 4

%- 6

D-

':

- ) A - 0 S ⊆ M 1(

(E & ! " < + a(S1 , . . . , Sk )/ A "- Si ⊆ M & A - U : + a(S, p)/ # A v(S) - "- S

&. N O A pU ,

+ a(S, p, δ)/ 2 A v(S) - "- S , δ A pU + 0 a(pS , . . . , pS )/ A "- Si & I / pS U A & 0 ( ! " K:? ::L K96L ! I " ( /

! ) 1 - & "- ! 1( (E -! ! & " 1 5)

$ ! B (E

( ( ; & K:9L - ( ! 1 ,(E) 0 ( 1 (( E " ) (! ) & 1

i

k

( D-

': 56-3

"

1(

& F ( K:?LP 0 ( ( ) ( (!I! & ! " B 1 E( - F ! ( ! 1(

- ! 1 ( % - ! ! 1(

& & " ! " 0 (

- / " ( ! ! (( ,

) # 0 ( ) $ ! - # ) ! & A 1(

! ) ( 0 ( - ( ! I # ! " & ! 1(

0 ( & ! 1

"#

%- 6

D-

':

(

" 0 E ( # - & ! "(P # ! 4 1) B " & 1 ; ) - / !& 1 ! vi 1 v1 < v2 < v3 - " ; E F& 1 - v2 ! - ! v1 < v2 v3 > v2 = ; ! / v2 ^ " ( - (! ! " I 0 K:>L - ( # 1( - "- & 1 -

"- & 1( & , & ( - " ( 1( "- & ( "- ) - "- # 1( ) F& !& 1 ! !- , ! # ) & / - ! N/ O !

( D-

': 56-3

"

1 "- ( ! / ; ! 2 ! & '!!P "

&. ) & '!! # = 0 ) ( A) 0 1 & (( E C K9DL BC1; '!

" $ I K96L (( E 1 B =: < "- ! "- S ⊆ M A ( 4 E "- E A "- & A ( ( B " $ " 4 " 1 - M ! 4 1 & A ! #

M " & 1 ( ! √ (

min{n, 4 m}(( E Nn ! " m ! 4 M O ! .

"

%- 6

D-

':

(( E ( & A CA ( , !

M ,3A + F

N $ ( 2 (S , . . . , S ) M $ ( ∗ 1

∗ n

0 T ← M 3

3 ,3A + ( 0 K ← N 3

3 $ ( 0 S1∗ ← ∅, . . . , Sn∗ ← ∅ - 3(

@ A $ i K $/ Si ; . - ,3A + ' ; ( ( v (S)

Si ∈ arg maxS⊆T i|S| 0 i $ '

. - ,3A +( 0 Si∗ = Si , K = K\i, T = T \Si T = ∅ K = ∅ @ A $ . vi (M ) 2/

+-

$/

∃i ∈ N vi (M ) > i∈N vi (Si∗ ) 3

,3A + $ i

&

6% 2/ +3 + GH

( D+ +-

':

"

! - . %

! / ( #( % ,(E) , ! N ,(E) & , ! ! ,( - O A (! - - / -

0 ( - & # /

Agent

Kommunikation

Typbestimmung

Mechanismus

Ergebnisbestimmung

! -> Gebotssprachen (S. 94) exponentielle Informationsmenge

E 3- 2/ E%

D+

"

%- 6

D-

':

/ ) I , ) B T # ( !

0 ( - ! - / ! 0 ( - & 5 S ⊆ M / p - 1 (S, p) !

+ " ! - ! ! 4 E( !

1 ) , ( - 1( 1 & '! ! - ((

$ K>:L E(! / ! 0 ( / + F ) 1( & B 1 & ! - 1! 5 ( ! " # ( - 1 & ! ) ,T (E ( 5

; 1 ! (

( D+ +-

':

"

- ( 1( 1 ( , N ! " n ! 4 mO ! - $ K:9L ! / & P ) ( /B; C0( m ! ! <+2"- % + +* 2 = " ! " " + " m , ! 0 += -

A ! m ! 4 ! 1 v(S) - S ⊆ M P 0 -

⎧ ⎪ ⎨0 vi (S) = 1 ⎪ ⎩ 0

\\ _ +6 \\ ` +6 1 \\ ] +6 = A 7 9 ! ) ) 1! & 1 v(S) 2( ) * 1

) " - & " 2) m E( m m/2 A 1( 1

E( , - & 1( 1 - 1 ( m m/2

"

%- 6

D-

':

2) # K>:L 1( ( D>1

B 1( a4<( * ! 1 - a4<4( -( P (S1 , p1 ) a4< (S2 , p2 ) a4< . . . a4< (Sk , pk ) 1 ( 1 ({0B 0}, 500) a4< ({F}, 1000) @77 - , () 9777 - ( F ;

- E a4< -( 1 ; - 5 & 1 9777 ! ! a4<( ) & 1 - & 5 M 1 ! A a4<( ) '! 1( >1

1 4<1( ! 1 4<4( -( P

( D+ +-

':

"4

4< (S2 , p2 ) 4< . . . 4< (Sk , pk ) - " ; -

! 1 ( " ) ! ! $ ! " 4<1 ({0B 0}, 500) 4< ({ }, 400) & ; - 1 - ! ) D77 - 4 ! ! # ) 4<1( '! a4<1( ) 1 4<( 1 &. a4<( E( 1 &. 1 &. 1 I ! 1 (S1 , p1 )

) ( ( $ 0 2 > S ⊆

M 0 |S| + * <: + =) m + * ?<: + =) 2m -

1 4<( . - P ! - 4 mi ∈ M 1 (mi , 1) -( 1 4< 4<1 1 &. m " a4<( & ; - 1 - - ) 5 E(! - & 5 S ⊆ M 1 (S, |S|) ! 1 a4< -( a4<1 1 &. 2m 0 -

"

%- 6

D-

':

4<( $ P # 1 - 4<( ) 1 ! - 1 P p(S ∪ T ) < p(S) + p(T ) % I 4<( ! 1 (S, pS ) 4< (T, pT ) - S ∪ T ( 1 ! ! & 1 ! ! - 1 - - A # ) I! "( a4< 4<( ) 1 (( ! - ) ( !

>1E& 6 F+

, 4< a4<( 4<+a4<( a4< 4<4( & ( ) ) 4<+a4<( ( ) 1 (! ! ( $ 4:L 1( '! ( ) - / & a4<1 B 4<

( D+ +-

':

""

1 - 1 4<+a4<( 4<1 / M !

4 ! - ! 4 ! " - , 1 a4< ! - x / M P (S1 , p1 ) a4< (S2 , p2 ) ⇔ (S1 ∪ {x}, p1 ) 4< (S2 ∪ {x}, p2 ) 1 ({0B 0}, 500) a4< ({F}, 1000) 4:L *%5 ++

# K>8L ) $ & 0 ( 1 ( " B $! ! " # -! # (!) ) I 1 - 4 2 $!

( "( " ( A , s $!

( ! , t A , - & , 1 ! &

##

%- 6

D-

':

1( I , s t / p ! ! ( - 1 ( - / - 1 ( ! ! - B

&. " (( , + &

( A 1( ! # ( 1 ) A - A a(S) - S ⊆ M ! -

1 - "- S ! ; # ( 1 . A 1 1( U½ !( P . ( /6 B2;C0( % + ) (

( * , * +

% + + b + + > <+2" S ⊆ M b " 1

! 2 - 3

3- * + + ; ++ 2

3% : (

( D+ +-

':

#

+ v(S) ' S ! =) + +-

4% a4<( ( ( # A C - 1 ; ! 4<( ( ( " A v(S) 4<1 (S1 , p1 ) 4< (S2 , p2 ) 4< . . . 4< (Sk , pk ) E 4( ( S k " ! 1 (Si , pi) A =6

! / $/ - ( 4<( ( ( ( ( ( a4<( ! ) / E ( )

( # ( , K>8L / E / ! P # ( $/ / (( +#5

A . ! , ==6 - ! ( ! ) 1 (

(( E

#

%- 6

D-

':

N n ! m ! 4 O K96L $ ! K:6L $-! ! , ( - '! E ( A )

&. ! E( " , (

- '! 5 ; ) ! & min{n, m1/2− }

# $

# ,( ! ! ) -! ( - - & , ! - "

# )V < ! " , " ) " ! 1 C( / / <

, - - ! < ( ) ) K=DL # (! !() " "

(E) &

. /(

#

!3 !

T B &% K=:L

- " ) - ! -! B 0 ( # " - / # ; ! N 6=O ! ( ! ( ! B P " ! , , - - - ! ! , , ! -

- B , ! ! ( . & ) , ! & , ) $ B ! / -! ! ( N ,( 6O -

!

) 0 ( 0 ;

!3 !

#

# / / $! . ! , $! $ $! ! 5 Q R ! !

-! ( . " ! 0 ( T ,!( !() 0 (

" & A $ ( T ! A - ( . ,(E). 6: - ! - - - ( - . ( , < ) - ( )! / () " ! ( / ! -! & ! / ! ! & ! -

! , ! , ( ). .

! ! E / (

#

!3 !

! ( ,( P / ,( "( "( < / G )

- # < !

"( ,( 6 " 1 / N"1/O - # < # ! $ - "( ,!( ( . ! ( ,!( ! " , () "( - "1/ - . ,(E) ,( 6 - ( "( ! 1 ( ( 6

# ; 0! # 5 ! " ! $! 0cc $! F 0! NO ! ( 0 ( !

( 1 $ -

#4

" < $ # - ! P ; < ; < - # <

0! B # < ! 0 ! # ! ; " 1 / N"1/O K:DL "1/ ! /B / $!

( !

( A 0! ! 0! ! ( 0! , - ; / ! ( / 0! ! - - ! 0 a

b

c

d

Netz Uni Freiburg

Dt. Forschungsnetz

Transatlantic Carrier

Netz MIT

tb = 6

tc = 22

Kosten der Weiterleitung

! 3 3 5 ( ) *

2 * ; D

#

!3 !

! N ?9 - '! $! 0 , & 0 ! & & ! , ) "

$ ! ( ( / ) - 1 '! ,( 6 1 ! ( # 1 ! -! B '!

/( K=@ =>L / K8:L 1

A "1/ K?@L # 1 ( G = (V, E) V , 1 ( N "

% W,X W X W X

O # NO ! B ! ! , e ∈ E

- * , v ∈ V , I!

( 1 $ -

#"

1 ( ! ! ! , E & , " 1 / -! < / , ( A - ! A ! 0 ! ! ) NF(O ( A , ) ( & A ) "1/ A

- / F(/ " A 0 , 0 - A 0 ! , A # 1 ! ! , F( ) , ! , & ; B # < , , , $ $ ! $

- , c : V → R , , - A $ ! ( ½ A ti , A 0 ( , F& = 0 ( ti = 3 A "( ,( 6 1

. ; 3 C3 * /3 D e ∈ E - ; 5 3 ; + D (

#

!3 !

& 0 ( ( si 5) !

0 ( tˆi = si (ti ) 0 ( ti ?6 ! "(

( - "1/ L " ! ,

( 1 $ -

) " ( & , " V , 1 ( "! ) !

$ - a, b ∈ V Tab N P ( O ! / , a b & Ii (t, a, b) # i , t 0 - / a b NA 9O NA 7O 0 - ! Ia (t, a, b) = Ib (t, a, b) = 0 $ ! 6= $ ! A ; A , - ui = −

Tab Ii (t, a, b)ti + pi

a,b∈V

; < "( ,( 6 '! ! , $ ! () ! , V (t) =

a,b∈V

Tab

Ik (t, a, b)tk

k∈V

V (t) )V ! , / a b - a, b ∈ V ! ( ( #

" "1/ ! /P

!3 !

" 0 ( I N, ( #O - ! A ! , ; N, ( ##O • - 1 ( $ ! & 0 / " 1 / & 1 ( " B ) 1 ( , ( " - / , ( # "1/ 0 ( * $ 0 ( $ ) $ $ 0 ( - $ A 0 - () ;

% / ) 0 , - 0 $ # , ( ## , - / ! , - $ - ) ; 0 # O(n2 ) #! // ! & # - 1 ( , ( * , $ " I P # , •

( 1 $ -

$ $ - A ; ( - A ; # $ , 1 ( N$) ! " ?=6O " . $

- A ! & ; $ ! # ! # - ( $ & ( ( $+ ,# F

$ E , - ( < ; : + , i ) , cij - / ! , j = i - / B viaij "! / ! V , ) 1 + ) -

- / A ; 0 - $ / F& ; , S ; $ N ?=9O - - , 1 ( ! A ! ( - , ( - / A ( # -

( ( - ; - 0 - $

!3 !

- ). ) " ;

; B 0 ( 0 ?9 - a " (

( ?6 0 ( , , ( < 0 ! - A !

, ! ; ! ( , i - 0 b h

0 ! 1 F& @ A $ - A

i 0 ! - # ; , b ; F& ? , h ; F& = A ! A $ ) - ( & 0 !

- #

A ! ,( 6 ; ( ! . '! ! 0 ( " $ ( -! ! ( & ! " " ; T !

( ! D -

$ - 5 3

; 3 $&% 3 2/ 1 - ; 2/ - 33( (( !" #$ &t & via c I # ' 'I # I # JK JK JK J3K J3; K x

ax

ax

% &p I 'I I JK JK JK JK J; K ax

; & 4 & $ 0 ,!( !() ). 0 ( ,!( )! $

"

- / K8:L , !( -! ( ! . ! !() I ! " ( ) " - ; I , () $

G ! "

!3 !

, () G ! - ( ! # ! ) !

- - - # < ) ( ( &

( & B ,( 6 I ! 0 ( . B " $ / ,( si ∈ Σ P NO # - ei NO " bi NO $ wi N ?=O ! P si (ti ) = (ei (ti ), bi (ti ), wi (ti ))

P

" 5

;

ei (ti ) - E ! - N ( O # - 0 ( - 5 ,( 6 - ! I # "( )

( ! D - Teilstrategien

MechanismusEigenschaften

Informationsenthüllung

Anreizkompatibilität

Berechnung

Berechnungskompatibilität

Nachrichtenweiterleitung

Kommunikationskompatibilität

4

! $ 2 % ; + + , $ # - ( & ! # & A ; T 0 bi (ti) - E < ! " ; (!I T & A $ " & ( ! " ; T & - ! wi (ti ) - E ! A $

!3 !

F & $ ( ! ) - ( B - F smi (ti ) = m m (em i (ti ), bi (ti ), wi (ti )) ( ! # - emi (ti ) - 0 ( ti ). ( $ wim (ti ) & $ ) ! ( "

bmi(ti ) & " ! - (!I B ( (sm1 (t1 ), . . . , smn (tn )) ! sm (t) / K8:L I P M = (Σ, g(·), p1 (·), . . . , pn (·), sm (·))

( ( 5 5

" ! - 1 " 1 & A - - !E /

1 + +

, ( ! -

( ! D -

"

- & ) !E () - ) 1 !( E ( $1 . ( / * 50( %

. s∗ = (s∗1 ,. . . , s∗n ) E ( $ 1 * i* si ∈ Σ . t / ui (s∗i (ti ), s∗−i (t−i ), ti ) ≥ ui (si (ti ), s∗−i (t−i ), ti )

1 ! I $1 1 P " $1 - - 1 s∗i ∈ Σ - + s−i ∈ Σ n−1 & si ∈ Σ ( - ( 0 ( " 1 1 s∗i - 0 (( I t−i ( I s−i ( 0 ( ( ( ! & " E ( $1 - - 1 s∗i - 0 ( ( I t−i ( j = i 1 s∗j (tj ) ) 0 ( ( !E - A ) $1

#

!3 !

, - 0 ( ) ) ( & A -! - ) - ( - 1 ) 1 !( / ) - " - ! , ! B ! & I P . ( /9# B=;C0( % '

M = (Σ, g(·), p1 (·), . . . , pn (·), sm (·)) * sm ! 3 4 , -

" ( $ ! - & 0 ( ( E ( ( %G ' ++

( sm 5 #

( 0 ( "

$ - - / K8:L !() ,!( " , ()

( ! D -

,!( !() # - N OP !" + - i 0 (( I t P E E ( $1 i &

$ !

( # - emi (ti ) 3 ( # - 0 ( ). ! I ,( 6 - I !( ) - - +" + E ( $1 E & $ !

( " bmi (ti ) ( " ; A 0 , - & A $ ! ( . "

" " + ( $ wi (ti ) & $ !

( $ - ! $ ) ! - A 1 NA 1 E , ! A

!3 !

1 O , ,!(

! & < ! / , (

( , - # < ! ! ! 23 1

< < - , ) F ! - ! F # ! "( - # <

5 ! ! ¾ B

" ! P # - ,() ! 5 "T ! 5 ei bi wi ! . ) I " , () ! " - ( ! & $ ! 5 I K8:L ! I 2

@/ $ ; ; GH 8 (

(

2/ 1

" 0 ( P 9 " ( ! 6 " " () = " , () " - ( / - # "1/ - # < - 0 & 2& )! (( %+

- " - # < - ! ) ! ( ! A - ; pi I

- 0 ( ). ! # ,( 6 B C 1 NBC1O 0 ! , ( ; - ! < ; ) # 9 - - A 1 ( I - A , a ∈ V b ∈ V \{a} A 6>9 < ; A i , 0 - A a b " ! % ! , i / , / i ( ; 7 t|i=∞ = (t1 , . . . , ti−1 , ∞, ti+1 , . . . , tn )

t|i=0 = (t1 , . . . , ti−1 , 0, ti+1 , . . . , tn )

; "1/ < N ?9O . -

< P pi,ab =

j∈V

Ij (t|i=∞ , a, b)tj −

Ij (t|i=0 , a, b)tj

N?9O

j∈V

4 - A $ 0! ) () 0! - A ) a () b $

(

2/ 1

B ; " (

( ?? 0 - $

, a ! , e N O 6 ) , , c - / , c - 0 $ "! F& ,

- c / !- , / c - c / N O - , b h 1 F& @ pc,ae = 5 − 0 = 5 A a ( N! () O i ti = 5

e

h

te = 4

th = 2

c

b

tc = 2

tb = 3

a ta = 3

d tf = 3

td = 4

f

tg = 5

g

$ - $&% -

!3 !

; - A $! ! & $ ) 1 N?9O ! P pi =

Ta,b pi,ab

N?6O

a,b∈V

Ta,b ! / , a & N 999O A ; !

0 ( ). ,() K=>L !

& ; <

b

(( 4 '

# ! - I A ; ( ( " G G ! ) " ( & ) 4 ' #+

- A

! a, b ∈ V !

" 1 /

(

2/ 1

4

F( , - 0 $

, ( # , - . , 1 ( . $ - , " i ) < 0 ! - A ! j = i ) 2 - A ! , ( - , - / " ) P * ) $ - , e ∈ E E $ 0 < ; $ ! ! 1 ; " A - ! ) ! - )! ! " ( - ) $ 5( < 0 - ! A & - / ! A ! B / , N 2 0 ?9 99@O () d A d 1 (

!3 !

, - A

2 0 ( 4 ' " #+

$ - /

- ; A K=>L - ; pi ?=9 I ; i - A $ 1 N?6O ! A pi ! $ ; pi,ab ( / a b A ; pi,ab S a ; b $ ) - A ( , i ∈ V ! - , via2 - / N 99@O A - , i n(n − 1) & A pi,ab # , - " - ! A " A ;

! - * a ;

pi,ax N- i, x ∈ V O ; , i 0 - A a x - ! $ - A ! , x 0 ,

A pi

(

2/ 1

"

"( - ; 0 ?9 99@ pax ! B pk,ax " ! ; - A ! , i ;

- A - 0 b h ; pb,ax = 4 ph,ax = 3 5 ; ; G ) < 0 G $ $ ! " ) A < 0 ( ! A pi,ax a ! ) ! - )! A ∞ ! # G $ 5( 0 G A ; $ * / $ 1 ( ( 1 ! F A A ( A d d E ! , k / a b - a, b, k " (E & - 2 K=>L (( ' ++

A ! " ;

! ,

#

!3 !

(!I -

- ( " $

- " ( $ ( - )! ! - ) ( "

A $ ! 5 "( - # < . ! (

( 0 ( & - ( F ! ( -! B . - $! " ! ) %

! ! " , ()

! - , ! ! ( / K8:L 0 / < ! C/ B

(

2/ 1

, " - (

( , , / ! "

; ) - " C , - B $ - * , Q R , ! C - $ C , F ( - " F ( - ( 0 F ( ! / / C , B , ! "

- N ,

( ( ! - O F ( " ). ( " - ! #! ! 0 F ( / - C , " , ). / - 0 ! - B ( " - NC/ O & " , ( & ! $ / , # & # - ( , ( <

!3 !

C , " F ( - # F ( $ ) ! ) C , F ( C , - ! "

0 0 ) F ( . ) $ C , - ( - A ) 1 !( - 1 ) E ($1 ! $ j = i " ( A - A- i "

- - ! #! - " - - # (! - i ) "

! - #! E

B G & G $ ! B ! - A 1

) (

, & - ! ) ! )

(

2/ 1

E ($1 ! )! " P ; ) ! /

& ; ! 1 ! T . 5 A - ; ! ( - C , ! A ! ( ) ! # ! < 0 " - ! & , C , -

# - < 0 F (

#! $

C , P , $ ! , C

. " < "

P ,!( , ( ( - "1/ K=>L . - ! ) F " 1 ) ! , ! U , - ( ( U / " ! < !

!3 !

B - (E " - "

; , " $! , ) % ( ) ! K::L " , () ! C 4( ! / !( /

"

" " # ! ! 0 %

F " , () B (

( $ B 0 B - $ - N! " KD> D@LO (! ( C( KD?L

. # - / ( C( / F - & & ; (

( )! ! & i ( # ti ! ! 2& 1( & - i fi(t1 , t2 , . . . , tn ) !

(

2/ 1

( # ) * i fi (. . . ) # -

j = i A 2 / ( " ; ! #! - ( C( ! &

! *-

( ,!( !

< " ! Y - 2 ! B &% ) K9L B

! 1 (( , $ ! & 2! & ( & B ! ! 1 ( - ! #!

( ! #! N . "O B ! B (

( B - Q !R " ( ) A ! , B 0

! B - " $1 (!

!3 !

) - E ( $1

. ( - ( - #! K@6L ! ) , (

( !

! ! & " ! & !

,!( A NEO " ) N(O ! - - ( ( & !! -. % (( *%5 ++

1 " ,(E) - ,( 6: - /( - K=@ =>L , (E) - (P 9 " , 6 1! $ N ! ,O = E ; $ - ! B N O ? E $

&.

( ! D-

':

4

( K=DL (

( ! ! () $! (E) - & ! & ( $/) / $! (E)

! '! " B

&. # F) F) 1

!( ) $! (E) " @ ! - - K=:L ! " < ( " ! / K=DL "

% ,(E) QF) R ( )! 5 ! Q R Q) R - ,(E) - $ < K>D >>L - ! - " < !( 1 ,(E) ! % ,(E)

+ "! ! ! "" + K=>L (

!3 !

# ) ! !

/ B ! ! - B

B - - # # ( G ! ( G ! ! P A

! I /

&.

! & ! ! / ( ) $! (E) 1 &. / $! (E) - # < ! " 1 / (( #< , 1

# - # < ). ! $! (E) A ) , ( < ; " ! ) ,(E) " 1 / ; K=@L k E 1 , V n ! , d 1 ( G # " ) ,

( ! D-

':

"

$ E $ < 0 $ ) E ) ) < 0 1 &. O(nd)

5( A $ $ , ) E k $ A ) & < 0 - ! A ; & " ( , O(k · nd) < 0 & d " ) " ( , O(k · nd2 ) / " - , e ∈ E 1 ( ; $ # - , O(d) $ - 1! $ O(|E|d) A ( ! - !( - # < K=@L - K8:L " ! ) " 1 K=@L C , , (

( A " , ( # - 0 ( ) 0 ( , ) 0 E k $ # - , , ( # -

#

!3 !

) , - / ) E k $ , $ 1 &. O(n)

O(kn) , ) A , ) $ 5($ ! , d

- " A ( , O(knd) / - , O(1) $ ( , O(d) 1! $! $ ) O(|E|d) # , ( ## < ; F ( ! $ " 1 / $ < 5( 5( ; $

&. " (

&. ! 5)

&. ; " & "1// K=@L 1 - - BC1; - ! / ! , - ! / , |P−i (t, a, b)| ! , - i / a b "1/ d = maxa,b,i∈V |P−i (t, a, b)| # A C dd = Ω(n) ) " !

&. /

( ! D-

':

! !

B ) dd - (( #

( ! d ≈ 8 d ≈ 11 , !! ! !

/ A B ) ,(E) / K8:L ,!( N ! C , , (

(O )! U / K8:L - P * , $ - - C , " F ( * " C , O(k)

- " ( , ) O(k2 nd2 ) $ ( 2 $ O(k) F ( $ C , A (

( 3 0 " ( I 1 ! . - ( 0 - P - & B / -

(( 6 ++

$! (E) I - / ! ! 0 ?6 5

!3 !

. B %* ++-

': 3 - % &+

L ()* +,$ -'$ -' '. /0 / 0

$ % O(knd2 ) +-

': * O(d) - M+ * O(|E|d) * % O(nd) 8N

O(knd2 )

O(k2 nd2 )

O(d)

O(kd)

O(|E|d)

O(k|E|d)

O(nd)

O(nd)

d 1 &. d G G # ,(E) K=@L 1 &. "1// - " , " 1 / ) ) ) # ( ( ( ! - ( & " K8:L ( $

&. O(k) (E k E 1 , V A k A C O(n) $! (E) ! / + 5 # 1 ( ! E

( ! D-

':

,

) ) ( ( ! ! , ) " #

( - ; ! * K?9L S E ,

! 1 ( ) 766 k ) n ! ) G - / ( ) < ,(E) ; , % 5 ! ,

?6 "

, (

( ! . , # ,() ! "1/ ! ,() ) / - ! # ; & - # < ,( ( - ! ,!( 4 E / " 2& # ! )

; ) " ! , ; - 0 ( A

- 5 ) - /

!3 !

/ ( $ ! 5) ( ! . ! !

P 1 ( 1

! ! "1/ -! < / 2C< -

((

- (

-! B " , ! $ ! # ) ! F

I % ) ;

% & '

( !& ,(E) C( ( # # B P - & E $ !

B 0 # / - / B ) / B -! ) / ! 1 -

) 2

-! B - # & < ! , -! B F

- -! ( ! ! - ! - 1! ! !

- ! . !( ! ( - B # / 5 # ( ! 5 (E ; ( (

,(E) 2 ) I / < ) 0! * 0 ! - A $ "

< 1 - / S ! ; 0! - / # ! ,( & ! B C 1 - ! 0! $ !

) 2

4

E

/

! B / !( &% " ) - & / ! - " ) 0! # ! /

& Q" R !

. , / $ ; & & " ! 1 / $ ,(E) / ! - ) 0 ( N / O

(E . - ! A "( - < ( ,(E) 5 ! "( ( F , (E) (! 1 ! ! 4 , 4 & ( / & $/

&. ! 4 <-

% (( E F ! (

( ! ) I , B

) 2

C 1 ) $ E (( E (( E ! - - / & - / 2& )! ! - < 1 B <E !! 4( ( 0 ( , ,(E) 0 ( -

) I

) 0 ( N 1 - , ! 4O ) E( ! ! 4 & # ! 2& / & ! 1(

" - - / # / / $! ) I ! , & 0 ! 1 ( " 1 / N"1/O - < ! 0! #

) 2

"

F - 0! 0 "

- ! A ! 0! 1 0 ! ! ! ! ) ) ! ( A ,( , " 1 / ! " - 0 " ; - , A 0 -

&. ( ) ! ( / ! ! ( & (E ,

! ( / " , (

( < ! , " ( "( - "1/ < ! ( ,(E) ! !

" 1 / - ( ! # / () ,(E) / () " ,(E) - ,( ! )

#

) 2

& ) ! , " ; ! , ! . / / $! ! <) A) ! ) N , " O

-! - ) 3

- ! ( ! (E )! " ( B & ! N! " K>6 :8LO # A " & ! ( 4 ! ! ) ( ) $ C( - ! ( ! I ( / - 4 K8DL 1 & & 1 / !( B - / / / / " 0

K99L )! ! $ ! ! 5( N < O K97L

) 2

0 ! / E ; !

5 ! ! !

- ) I ! / B ) 1 / () (E ) I ! -

. ; (! ! ) A - ( ( ! B ) /) ( #

(

( ; ; <

!

" #

$# % &

! ' ( !

&

( <

; 0 I; * O+; *O; P0; ##( B ( ( < ( @ 6; =#>; ,+3 ###( ( < ( <

##(

; 0 I"( B & ;

( ; ; ! ! "#< ) & ( < ! * ; 0 I#( B & ; ##( ( ; $ % ; & !' ( ! < + (

M < ,

'

!

; 0 #I( 0 6 2 -- ; ##( ( ! < ! ( B 5 ; =>; ##4( 4( ( & < * . ( < ) *+ =? 3 >< / 0 1 ( % & ; "4"( ( , ; % ; % % ' % % < 0 +

%( < + ,- !

!

; 0 "I#( B & ; ##( "( '- . / ; & 0 # "< - . ( <

!,- !

; 0 "I"4#( 0 6 2 % -- ; ##( #( ( +; $ , )' 1+ % < 2 -. 3 * ( 5 $ 01%51%##%#; 2 1 ; ##( ( ! ( -
+

! /

( B & ; ##( ( < 8 + $& ( P 2; <I; ""( ( % ); % & ,2) < + 9 ( < ,* 6 . ! * ; 0 "I ; * O+; *O; P0; ##( B ( ( )( ) *) *+; + $ 3+ ' < !

. *

M

; ###(

( Q 2 1 6 ; 4=><#I

( $ < & $# ( < ! , :

; 0 I"; * O+; *O; P0; ##( B ( 4( $) + +< ! # ( &3 B ; <4I; "4( ( $ ; -

! ' < 0 + ; < < ! / ; 0 "I#4( B & ; ##( "( $ ". ! < = . $# ( < <

! /

; 0 "I"4( B & ; ##( #( $ , ! <

. ( < 6 ! / ; 0 I( B & ; ##( ( $ ! +; $ + ; ' + $ .. < - ( 5 & %?

; ) 2 ; ##( ( $4 < + &

( <

!

; 0 "I#( B & ; ##( ( 4; %) 1 < !

(

06 ; =><#I4; ##( ( 5 $ ' 6 6' , < - . - ( Q 2 &3 ; <I; "4"( ( 4) < + ( * +; <"I4; ""(

M

( ) 1 1 <

+

/% $#3 ! /

9 +

( < ; ##(

4( ) ; 1 1 * ' < + ( < ,* 6 .

!

*

; 0 #I; * O+; *O; P0; ##(

B ( ( ) ; 1 1 * ' < * 2

( < ,* ! * ; 0 I; * O+; *O; P0; ##( B ( "( ) * <

. + , . !,- ! * $# / 6 ! /

!,- !

( <

; 0 #I#4; * O+; *O; P0; ##( B ( #( ) < ( <

; 0 #I; * O+; *O; P0; ##( B ( ( ) ; & < ( < ; 0 4#I 4#"( 0 6 2 -- ; ##( ( 0 ) #; $ % & !(< * + ) 9 ( <

+ ! * 3 3 > - . , , ! / $ + 2 . ,* ! *

; 0 #I( B & ; ##( ( 0 < ( < ; 0 #I; ##( ( 0 7 < ( < I#; * O+; *O; P0; ##( B (

; 0 %

M

4

( 0 ; $ % ; )< 3#

( < ; 0 4I( B & ; ##( ( 0 ; $ % ; )< 3#

( !3 B-; =><I4; ##( 4( 0 ; $ % )< , ( < ! * ; 0 I4( B & ; ###( ( 0 ; )< ! ( <

!

; 0 I#( B & ; ##( "( 0 )<

&

( <

; 0 I( B & ; ##( #( 0 * ; & ; $ < " . 9 & ( < / < 6 ! / ; 0 #I( B & ; ##( ( / ; 0 ; ' ( # <

- ( < ? ,-/ -*!; ##( ( < ! $ , # " ( ; <4I#; "4( ( ( ,+; + ' ( " < . ( < , @

!,- !

; 0 4I4( 0 6 2 -- ; ##(

M

( % ; & '( * ' < - . & ( < / @ '

! /

; 0 I4( B & ; ##( ( .. ! + " . < 3# . ( < ,-#!! ((

> > >

( 4( ( "( #( ( (

(

; 0 % 44I( B & ; """( !< - . * ( ; <4I; "4( + + < $ & ,

1 / 1 ; <
2

( < * $+ 8 +9 =? % 3 >< 2 $ 0 C !&( *%?

; "4( < * ! "

( 5 1 ; <I#; "4( < /+

, . ) 9 ? P% 8R ; "4( ) ; * * ) < " , - ! ( < , 6 < -/// , , ; 0 I"; . ; !B; P0; ##( B- 0 6( & ) 1 )< 3 + . $# & 6 !

( <

; $ 1 ; 0 "I#( 0- ; ##( ( 1 1 < ( 5 ( B-( 0(; #=%><"I#; ##( ( $ ( < * ) ! . E ( < , 6 < -/// , ,

4( (

"( #( (

; 0 "I#; . ; !B; P0; ##( B- 0 6( 3+< - . ( < ( ; * * % 1( =? % 3 ><

> - !& ( .(.(*; ""( ; 35$ - < * ". + /% ( < @ ! ? / 5/((7; 0 "I#( B & ; """( * + 3 < # *( 5 - ; ""( * '$ ; * + " ' + < ! *( ,'2 P 6 & ; ""( * * ! < ( <

+

. -. .

. .

; 0 I4( 2 9

; """( ( * ! ; . " ' .< 1 . 2

#

M ( <

.

!

B (

; 0 I; * O+; *O; P0; ##(

( *5 1 1 < * +

+

/

( ( ( 4( ( "( 4#( 4( 4(

( < ; 0 4"I( 2 % 9

; ##( * +< ! ( < ( ; * * % 1( =? % 3 ><

> - !& ( .(.(*; ""( 1 < /9 # ( < ) , ; $ ; 0 I"; "#( 1 1< , ( M * B- 0 ; <I; """( 1 1< 3

( < A ! /

; 0 I( B & ; ###( 1 1< 3 E

( < $ % ; - =? 3 >< ( 5 & ; ##( 1 1 < ( < ! * ; 0 "I#( B & ; """( 1 1 <

$# ( < ! / ; 0 I( B & ; ###( 1 1 < * 9 %

E ( 3 ; ##( 1 1 < /+ % 9 ( 3 ; ##(

M 4( % $ <

( <

> >

! *

& ; ##(

; 0 4"I4( B

4( %) $+<

- . . / /%

( !+% 3 ; ! - 2 B- 2 0 ; P 6 2 & 6 ; ##( 4( %) $+ .. < - $ & &#. ! ( < ! , < * - C

! ,

; 0 I( B- 0 6; ##( 4( %) $+ + 7 < - . * ( <

,. ) -

* -. . -

; 0 4I( & L 5 5 & ; ###( 44( % ; 0 $+ %) < ! % ! , :

( <

P0; ##( B (

; 0 "4I#; * O+; *O;

4( *+; *+ !4 (

& < F G 0 '(; =><I; ##( 4"( ) -) ! < 3 #

< 53#<7? " @HH@; ""( #( < ! ( < ' ! / ; 0 #I( B & ; ##( ( ). * +; ) %) ' *+ <

( 0 ; =><I4; ""( ( < ! ( !+ 3 ; O

P 6; ##(

M

( ! <

<I; ##(

( 9

;

( ! < 33 -.

2 , /+ .

( 9

; <I; ##( ( ( *)<

( Q 2 % 5 6; #<4I4; "4( ( .. $+ %) < D

. < ! / , & !

( <

; 0 4I44( B & ; ##( 4( .. $+ %) < ( <

; 0 I"4( B & ; ##( ( .. ; $+ %) * 6< ( < ! ,-#!! &

. &

B & ; ##(

; 0 #I4(

"( ! ! + < # *( 5 $ M0%B! %##%#"; B! ; M 0 2 ; ##( "#( , +< / !

2 ( < ? D + 1& / ; Q 6 ""( "( , ) " < > > . , * ( 5 Q 2 @ ; <I 4; "( "( , , ); $ ) + <"I; ##4( "( / ; ; - - - < . & 9

##4(

( .

* +; =><4""I;

)

C3 3 ; ; #; ; 6; & 2 6 +- 3 :; D- 3 : 6 ; " -- %@+; # --' ; ; "; 4; 4;

; 4"; #; ; ; ; "; # +; D3 ; ; %; 4; 0

%; 4

+ 6%; ; + 6%; ; "; "; "# 06 ; #;

$ +; ; ; ; ; ; $&; $ % 6% &+

$ % 6%&+

; #; ; ; $ %& '; # $ % ; ; 4; ; ; 4#; 4 $6 ; ; B % %&% 2 ; # B + %D ; ; !A+ % ; ; ; ; !6 & ; 4

0

E ; ; ; "; 4; ; ; ; ; ; 4#; 4; 44; "; #; ; ; 4 + R + ; ; # 2+

; ; 4; ; #; "; # :3 + ; 3; 32+; ; 4; #; 4; #; 3 + ; "

-- 13% ; -- % 13 ; # ? +; 4 -

; I

1 :; ; 4; ; ; 4# D ?: ; 4 D ; ; # D- 3 : %; ; 4; "; 4; ; 4"; ; #; #; ; @ 2 ; #; ; ; #; ; 4 ; $ %; ; D+ %; ; 3 &+

%; ; ; ; " D-

':; ; " 8N ; "4 * +%; 3 ; D+- ; ; 4 3- ; 4 D 2+; #; 3- ; ; "" D 3

; " ,1S%0- ; " ,1%0- ; " M&%1 ' ; ,1L,1%0- ; " & 6

- 3 ; &; ##

,1%0- ; " +% /

; ; ;

; ; #; "; ; "; 4; $ 6 ; ; ; 4; 4 ; ; "I"; #; ; 4; "; ; ; 4; ; B%3 ; 4; # ' -; ; ; ' - * %; " + 6%B + % ; "; 3 % ; ; ; ; "; 44; ; * %; ; ; ; "; #

0 ; ; #; ; ; ; 4 * %

;

*&%?: ; "; 4; 4 *&%

:+ ; #; 44; ; 4 * 2+; # 7 ; ; "; 4; ; 4; 4# ,- -3

; ,1S% 3- ; 3- ,1% 3- ; 3- & %,- :; E & ; # &2 +% ; # & 3A +; "" & 2 6; 1 ; 1 :; ; ; #; #; ; ; ; #; "; ; ; 1 ; # 1 ' ; 1+ :; 1; # ; #4 ; #4 %; 4 1%5 3

; ; 4; "

4

0 %& %; ; ; ; ; ; "; ; ; ; ; "; ; 1%& 6; #" 0%?-; ; 4 / &2 ; #" 0 - 6 B- % ; 0

% 3 ; 0 ; ; ; #;

$ %; 4

-2

; ; # 2 /

; *

; 4 0 13 ; 4; ; 4; "; ; 4#; 44; ; ; ; ; 4

; 0

: ; 4 56-; 4 + 6%+; + . 0 & +; 4 . ; ,1% 3- ; 3- ) ; ) 2+; ; 4; #; ; ) 3

;