AU kursuskatalog arkiv

Computational Game Theory (Q2) ( efterår 2010 - 5 ECTS )

Rammer for udbud

• Uddannelsessprog: engelsk
• Niveau: Kandidatkursus
• Semester/kvarter: Q2
• Timer per uge: Forelæsninger (2+2t/uge)
• Deltagerbegrænsning: Ingen
• Undervisningssted: Århus
• Hovedområde: Det Naturvidenskabelige Fakultet
• Udbud ID: 19028

Formål

Deltagerne vil efter kurset have indsigt i to-spiller nulssumsspil med endeligt strategirum i strategisk og ekstensiv form, i endeligt præsenterede to-spiller nulssumsspil af uendelig varighed og uendeligt strategirum, især Shapley's stokastiske spil og Everett's rekursive spil, i løsningsbegreber for sådanne spil, i algoritmer til at finde disse løsninger, og i normative anvendelser af sådanne algoritmer.

Obligatorisk program

Tre obligatoriske opgaver af teoretisk karakter

Indhold

Typer af spil: To-spiller nulssums spil i strategisk form. To-spiller nulssums spil i extensiv form, med og uden perfekt information. Deterministiske grafiske spil. Stokastiske og rekursive spil, diskonterede og udiskonterede. 1-spiller stokastiske spil (Markov beslutningsprocesser). Generalsumspil (til perspektivering af nulsumsspil). Løsningbegreber: Rene og blandede strategier, adfærdsstrategier, stationære strategier. Minmax begrebet. Dominans. Nashligevægtsbegrebet og raffinementer heraf. Algoritmer: Lineær programmering til løsning af spil i strategisk form Sekvensformsmetoden til løsning af spil i extensiv form, med varianter for raffinerede løsningsbegreber. Den randomiserede alpha-beta algoritme til løsning af perfekt informationsspil. Retrograde analyse algoritmen til løsning af deterministiske grafiske spil. Value iteration og strategi iteration algoritmerne til løsning af stokastiske og rekursive spil. Random facet algoritmen til løsning af stokastiske spil med perfekt information. Algoritmer for stokastiske spil baseret på ikke-lineær matematisk programmering og semi-algebraisk geometri.

Faglige forudsætninger

Optimering, Kombinatorisk Søgning

Underviser

Peter Bro Miltersen

Undervisnings- og arbejdsform

Forelæsninger og øvelser

Litteratur

Noter

Kursushjemmeside

http://www.cs.au.dk/~bromille/CGT10/

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:

• definere og beskrive basale elementer af spilteori; typer af spil og løsningsbegreber og deres egenskaber, med fokus på 2-spiller 0-sumstilfældet.
• beskrive og bevise basale matematiske egenskaber for løsningsbegreberne.
• beskrive og analysere kendte algoritmer til at beregne løsningerne.
• diskutere normative anvendelser af algoritmer til løsning af spil.

Eksamensterminer

2. kvarter, reeksamen efter aftale med underviser

Udbyder

Datalogisk Institut

Tilmelding til undervisning

https://mit.au.dk/

Særligt om dette kursus

Skema for dette kursus

Bedømmelse

Mundtlig eksamen (30 min) uden forberedelse
7-skala, intern censur