Wiskundige Speltheorie

Dit is een keuzevak voor wiskunde-studenten. Het vak kan ook interessant zijn voor informatica-studenten met een sterke wiskundige achtergrond.

Deze cursus introduceert de wiskunde die gebruikt wordt om speltheoretische problemen op te lossen. Speltheorie bestudeert situaties waarbij uitkomsten afhangen van de beslissingen van meerdere partijen. Omdat de verschillende partijen niet de acties van andere partijen kunnen kiezen is het vaak niet mogelijk om dit soort situaties te analyseren met behulp van optimalisatie-theorie; in plaats daarvan is het nodig om de dekpunten van bepaalde functies of correspondenties te bestuderen (een dekpunt van een functie f van X naar zichzelf is een element x in X met de eigenschap dat f(x)=x).  We zullen zien hoe dekpunten gebruikt kunnen worden om spelen te analyseren, waarom dit een heel ander soort inzichten oplevert dan die we kennen van optimalisatie-theorie, onder welke omstandigheden de relevante dekpunten bestaan en hoe we ze kunnen vinden, en wat verschillende gebieden binnen de wiskunde ons kunnen leren over dekpunten. Ook zullen we zien hoe spelen kunnen worden gebruikt als bewijstechniek, zowel binnen speltheorie als (ver) daarbuiten.

Zie voor meer informatie over de studiepaden de studentenwebsite.

Belangrijk: Dit is een tweedejaars wiskunde-vak. Om succesvol te kunnen deelnemen is het daarom nodig om ruime ervaring te hebben met abstract wiskundig redeneren en het bewijzen van wiskundige resultaten, zowel binnen de vereiste vakken (zie “Voorkennis” hieronder) als daarbuiten. Het hebben gevolgd van één of meerdere wiskunde-vakken bij de eigen (niet-wiskunde) opleiding is over het algemeen niet voldoende. Het vak “Logica voor informatica” is bijvoorbeeld geen substituut voor het vak “Bewijzen in de wiskunde” in dit geval.

Leerdoelen: 
De student:

• Verwerft inzicht in de soorten wiskundige modellen die worden gebruikt om situaties bestuderen waarbij sprake is van conflict en samenwerking en is bekend met de belangrijkste oplossingsconcepten.
• Begrijpt de basisbegrippen binnen de combinatoriële speltheorie (zoals de Nim value, game sums, equivalentie van spelen, mex regel), is in staat de optimale strategie in Nim af te leiden, en kan deze kennis gebruiken om andere impartiële spelen te analyseren.
• Is in staat nulsomspelen te analyseren met behulp van de minimax stelling, begrijpt de relatie tussen Nash evenwicht en optimale strategiën, begrijpt hoe de minimax-stelling volgt uit de “separating hyperplane” stelling in convexe analyse, en begrijpt het verband tussen de nulsomspeltheorie en dualiteit bij lineair programmeren.
• Is in staat de rationaliseerbare strategieën en de Nash evenwichten te bepalen van strategic-form games, zowel voor eindige als voor compact continue spelen.
• Is in staat de rationaliseerbare strategieën in eindige spelen te bepalen door de separating hyperplane stelling toe te passen.
• Begrijpt hoe de dekpuntenstellingen van Brouwer en Kakutani kunnen worden gebruikt om het bestaan van Nash evenwichten aan te tonen, en waarom Nash evenwichten niet hoeven te bestaan als niet aan de voorwaarden van de dekpuntenstellingen is voldaan.
• Begrijpt de relatie tussen extensive-form en strategic-form games en is in staat extensive-form games te analyseren met verschillende oplossingsconcepten zoals Nash evenwicht, sequential equilibrium, perfect Bayesian equilibrium.
• Begrijpt wat het betekent als een nulsomspel gedetermineerd is, kan aantonen dat eindige spelen gedetermineerd zijn (stelling van Zermelo), en begrijpt de betekenis van gedetermineerde spelen voor de logica en verzamelingenleer.
• Is in staat de gecorreleerde evenwichten van eindige strategic-form games bepalen, kan aantonen dat alle gecorreleerde evenwichten gevonden kunnen worden met behulp van de canonische informatiestructuur, en kan bewijzen dat de verzameling van gecorreleerde evenwichten van een spel een polytoop is.
• Begrijpt hoe kennis en verwachtingen in spelen gemodelleerd kunnen worden met behulp van epistemische logica.
• Is in staat spelen met onvolledige informatie te analyseren met behulp van Bayesiaans evenwicht.
• Is in staat veilingen te analyseren en is bekend met de belangrijkste wiskundige resultaten op dit gebied, met name de “revenue equivalence” stelling.
• Begrijpt hoe nulsomspelen kunnen worden gebruikt als bewijstechniek, m.n. in de context van rationaliseerbaarheid en gecorreleerde evenwichten.

Onderwijsvormen:
Twee ker per week een hoorcollege en twee keer per week een werkcollege.
 
Toetsing: 
Inleveropgaven (20% van eindcijfer) en tentamen (80% van eindcijfer). De weging voor studenten die het hertentamen doen is hetzelfde.

Herkansing en inspanningsverplichting:
Een student die een lager eindcijfer heeft dan een 4 mag alleen meedoen aan het hertentamen mits voldaan is aan de inspanningsverplichting van het vak, te weten:

1. de student heeft alle inleveropgaven gemaakt en heeft een gemiddelde van tenminste 5 voor de inleveropgaves;
2. de student heeft deelgenomen aan het tentamen en heeft tenminste een 2 gehaald voor het tentamen. 

Taal van het vak:
De voertaal in dit vak is Nederlands.
In het geval dat er Engelstalige uitwisselingsstudenten deelnemen aan de cursus kan de cursus in het Engels gegeven worden.