Algorithmic game theory and machine learning

Abstract

Tato práce popisuje dva nové modely kombinující teorii her a vícehráčové učení. Nejdříve popíšeme přímočaré rozšíření volného trhu, jehož cílem je upřednostnit féro- vost v distribuci nedostatkové komodity. Ve zjednodušených případech ukazujeme, že náš systém tohoto dosáhne, a empiricky demonstrujeme jeho obecnost. V druhé části práce popisujeme přístup metaučících algoritmů pro minimalizaci regretu. Náš model apliku- jeme v doméně her dvou hráčů s nulovým součtem a při aproximaci Nashovy rovnováhy v obecných hrách. V obou případech dosahujeme výsledků převyšujících stávající nejlepší algoritmy, a to na hrách, pro které byly tyto algoritmy navrženy.

In this thesis we study two frameworks which combine game theory and multi-agent learning. The first describes an extension of the free market, designed to promote fair allocation of scarce resources. We prove theoretically the system achieves the goal in restricted settings, and demonstrate its generality empirically. In the second part, we describe a meta-learning framework over regret minimization algorithms. We use our approach to accelerate convergence to equilibrium in two-player zero-sum games, and to approximate Nash equilibra in general-sum games. In both cases, we outperform state- of-the-art algorithms on the domains they were designed to excel at.