AI802: Algoritmisk Spilteori

Ingen

De studerende, der tager kurset, forventes at have:

• Matematisk modenhed: At være fortrolige med strenge beviser (induktion, modstridsbeviser, grundlæggende diskret matematik) (f.eks. fra DM549).
• Algoritmer og kompleksitet: Et grundkursus i algoritmer (Big‑O, grafalgoritmer) og basal viden om NP‑komplethed (f.eks. fra DM553).
• Sandsynlighed: Forståelse for forventningsværdi, betinget sandsynlighed, uafhængighed og almindelige diskrete fordelinger (f.eks. fra AI501).
• Lineær algebra og calculus: Vektorer/matricer samt grundlæggende afledninger/optimering (f.eks. fra AI503 og AI511).
• Programmering: Evne til at implementere simple algoritmer og udføre eksperimenter (f.eks. i Python) (f.eks. fra DM574).

Algoritmisk spilteori undersøger strategisk beslutningstagning gennem et stringent matematisk og computationelt perspektiv, med fokus på hvordan egeninteresserede aktører opfører sig i komplekse systemer. Dette kursus introducerer de centrale begreber i spilteori og deres algoritmiske modstykker, herunder løsningsbegreber, ligevægte, mekanismer og læring i spil. Vi lægger vægt på både det teoretiske fundament (definitioner, sætninger og beviser) og betydningen af disse for design og analyse af moderne digitale og computationelle systemer.

Undervejs fremhæver vi forbindelser til AI/ML, såsom den spilteoretiske struktur i Generative Adversarial Networks (GANs) samt forklaringsmetoder i maskinlæring.

Ved kursets afslutning skal de studerende være i stand til at modellere strategiske interaktioner, ræsonnere om ligevægtsadfærd og effektivitet samt anvende algoritmiske spilteoretiske værktøjer på problemer inden for datalogi og kunstig intelligens.

Læringsmålet for kurset er, at den studerende demonstrerer evnen til at:

• Forstå og anvende centrale begreber fra spilteori (strategisk interaktion, ligevægt og effektivitet) på en præcis og matematisk måde.
• Formulere relevante virkelighedsnære scenarier som spil, identificere de relevante aktører, strategier og gevinster samt ræsonnere om sandsynlige udfald.
• Analysere ligevægte ved hjælp af stringente argumenter, herunder kunne bevise, hvornår ligevægte eksisterer, og vurdere hvor “gode” eller “dårlige” de er for deltagerne eller for samfundet.
• Genkende og ræsonnere om algoritmiske aspekter af spil, f.eks. hvornår ligevægte er lette eller svære at beregne, og hvordan dette påvirker systemdesign.
• Fortolke og evaluere mekanismer og protokoller (f.eks. auktioner, matching‑metoder eller ruteringsregler) ud fra både incitaments‑ og effektivitetsperspektiver.
• Koble spilteoretiske modeller til anvendelser inden for datalogi og kunstig intelligens, og formidle deres analyser klart i skriftligt arbejde og diskussioner.

Vi vil gennemgå et udvalg af centrale emner inden for algoritmisk spilteori, herunder auktioner og mekanismedesign, egoistisk routing og netværksspil, ligevægtsbegreber (deres matematiske formulering og beregningsmæssige kompleksitet) samt algoritmer til læring og tilpasning i spil. Gennem hele kurset vil vi fremhæve forbindelser og anvendelser inden for AI og maskinlæring, såsom den spilteoretiske forståelse af Generative Adversarial Networks, idéer fra forklarlig AI og træning af agenter til konkurrenceprægede miljøer som Go og poker.

• Læsning af lærebøger og relevant literatur.
• Gå i dybden med materiale samt opfølgning på forelæsninger og opgavetimer gennem selv-studie.
• Bruge de lærte koncepter i relevante anvendelser.