Algoritmická složitost řešení ve vybraných třídách nekooperativních her

Abstract

Název práce: Algoritmická složitost řešení ve vybraných třídách nekooperativních her Autor: Adam Wichera Katedra (ústav): Katedra logiky Vedoucí bakalářské práce: RNDr. Ondřej Majer, CSc. e-mail vedoucího: majer@ u.cas.cz Abstrakt V předložené práci studujeme přirozené algoritmické problémy vyvstávající z pojmu Nashova equilibria. Problém jeho existence je triviální, protože plyne z Nashova důkazu úplnosti. Ani příslušný vyhledávací problém se tedy nezdá být NP-úplný a to právě proto, že existence ře- šení je zaručena. Zajímavé ale je, že jakékoli přirozené rozšíření tohoto problému už se zdá být NP-úplné. U mnohých už byla NP-úplnost pro konečné nekooperativní hry s obecným součtem dávno dokázána, většinou redukcí problému SAT, Klikového problému, nebo množinového pro- blému hledajícího podpokrytí. Ovšem zda se k ostatním řadí i problém existence asymetrického equilibria pro symetrické hry, byl otevřený problém. Zde ukážeme, jak zobecnit důkaz z [? ] tak, aby dokázal postihnout i problém asymetrických Equilibrií a dokážeme tak jeho NP-kompletnost. Klíčová slova: Nashovo equilibrium, Algoritmická složitost, Nekooperativní hry, Teorie her, Asymetrické equilibrium, 1

Title: Algorithmic complexity of solution concepts in selected classes of non-cooperative games Author: Adam Wichera Department: Department of Logic Supervisor: RNDr. Ondřej Majer, CSc. Supervisor's e-mail address: majer@ u.cas.cz Abstract In the presented work we study natural algorthmic problems rising from the concept of Nash Equilibrium. The problem of it's existence is trivial, because it follows from Nash The- orem of completeness of Nash Equilibria. Even related search problem doesn't seem to belong to NP-complete class, the reason being the very fact, that existence of Nash Equilibria is certain. Interesting observation is that every natural extension of this problem seems to be NP-complete. Many of such problems have been proven to be NP-complete through reduction of SAT problem, Klike problem or problem of searching subcover of certain size. The question, wheather the pro- blem of existence of assymmetric Nash equilibria of symmeric game ts with the others, in being NP-complete, has been an open problem. Here we show how to alternate the proof from [? ] and apply the construction to problem of existence of assymetric equilibria and therefore prove its NP-completness. Keywords: Nash equilibrium, Algorithmic complexity, Non-cooperative games, Game Theory, Assymetric equilibria, 1