Algoritmische speltheorie

Algoritmische speltheorie (Vaak afgekort 'AGT' naar de Engelstalige naam Algorithmic Game Theory) is een studiegebied op het raakvlak van speltheorie en theoretische informatica, met als doel het begrijpen en ontwerpen van algoritmes in strategische omgevingen.

Bij AGT-problemen wordt de input voor een bepaald algoritme doorgaans verdeeld over veel speler. Deze spelers hebben een persoonlijk belang hebben bij de output. In dergelijke situaties rapporteren de agenten de input mogelijk niet naar waarheid vanwege hun eigen persoonlijke belangen. We kunnen de algoritmische speltheorie vanuit twee perspectieven bekijken:

• Analyse: gegeven de momenteel geïmplementeerde algoritmen, analyseer ze met behulp van resultaten uit de speltheorie. Voorbeelden hiervan zijn eigenschappen berekenen en bewijzen op basis van hun Nash-evenwichten, prijs van anarchie en beste-responsdynamiek.
• Ontwerp: ontwerp games die zowel goede speltheoretische als algoritmische eigenschappen hebben. Dit gebied wordt algoritmisch mechanismeontwerp genoemd.

Geschiedenis

Nisan-Ronen: een nieuw raamwerk voor het bestuderen van algoritmen

In 1999 vestigde het artikel van Nisan en Ronen de aandacht van de theoretische informatici op het ontwerpen van algoritmen voor egoïstische (strategische) gebruikers.

Dit artikel introduceerde het begrip algoritmisch mechanismeontwerp en werd door de Gödelprijscommissie van 2012 erkend als een van "drie artikelen die de basis leggen voor groei in de algoritmische speltheorie".

Prijs van anarchie

De andere twee artikels die in de Gödelprijs van 2012 werden geciteerd voor fundamentele bijdragen aan de algoritmische speltheorie, introduceerden en ontwikkelden het concept van de "Prijs van de anarchie". In hun artikel uit 1999, "Worst-case Equilibria", stelden Koutsoupias en Papadimitriou een nieuwe maatstaf voor voor de achteruitgang van de systeemefficiëntie als gevolg van het egoïstische gedrag van zijn agenten Ze definieerden deze maatstaf als de verhouding tussen de systeemefficiëntie bij een optimale configuratie en de efficiëntie ervan bij het slechtste Nash-evenwicht. (De term ‘Price of Anarchy’ verscheen pas een paar jaar later.)

Het internet als katalysator

Het internet creëerde een nieuwe economie – zowel als basis voor uitwisseling en handel, als op zichzelf. Het computationele karakter van internet maakte het gebruik van computationele hulpmiddelen in deze nieuwe opkomende economie mogelijk. Aan de andere kant is het internet zelf het resultaat van acties van velen agenten. Dit was nieuw voor de klassieke, 'top-down'-benadering van berekeningen die tot dan toe gold. Speltheorie is dus een natuurlijke manier om naar het internet en de interacties daarin te kijken, zowel menselijk als mechanisch.

Speltheorie bestudeert evenwichten (zoals het Nash-evenwicht). Een evenwicht wordt over het algemeen gedefinieerd als een toestand waarin geen enkele speler een prikkel heeft om zijn strategie te veranderen. De speltheorie biedt hulpmiddelen om evenwichten te analyseren, en een gebruikelijke aanpak is dan het 'vinden van het spel', dat wil zeggen het formaliseren van specifieke internetinteracties als een spel, en het afleiden van de daarmee samenhangende evenwichten.

Het herformuleren van problemen in termen van spellen maakt de analyse mogelijk van op internet gebaseerde interacties en de constructie van mechanismen om aan specifieke eisen te voldoen, vanuit het perspectief van de algoritmische speltheorie. Als er kan worden aangetoond dat er evenwichten bestaan, moet nog een vraag worden beantwoord: kan er een evenwicht worden gevonden, en wel binnen een redelijke termijn? Dit leidt tot de analyse van algoritmen voor het vinden van evenwichten. Van bijzonder belang is de complexiteitsklasse PPAD, die veel problemen in de algoritmische speltheorie omvat.