AU kursuskatalog arkiv

Computational Game Theory (Q2) (Honours) ( 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: 25033

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 og praktisk erfaring med at generalisere kendte teknikker for løsning af spil til nye problemstillinger. Kursets arbejdsform vil også træne deltagernes evne til at søge information på egen hånd og til at læse og forstå videnskabelige artikler.

Obligatorisk program

Tre obligatoriske opgaver af teoretisk karakter samt en selvstændig opgave af forskningsforberedende 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 kendte algoritmer til at beregne løsningerne.
• reflektere over brugen af algoritmer til løsning af 2-spiller 0-sums spil.
• generalisere brugen af algoritmiske løsninger af spil til nye problemstillinger.

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