Application of multiplicative weights update method in algorithmic game theory

Abstract

In this thesis, we apply the Multiplicative Weights Update Method (MWUM) to the design of approximation algorithms for some optimization problems in game-theoretic settings. Lavi and Swamy {LS05,LS11} introduced a randomized mechanism for combinatorial auctions that uses an approximation algorithm for the underlying optimization problem, so-called social welfare maximization and converts the approximation algorithm to a randomized mechanism that is { truthful-in-expectation}, which means each player maximizes its expected utility by telling the truth. The mechanism is powerful (e.g., see {LS05,LS11,CEF10,HKV11} for applications), but unlikely to be efficient in practice, because it uses the Ellipsoid method. In chapter 2, we follow the general scheme suggested by Lavi and Swamy and replace the Ellipsoid method with MWUM. This results in a faster and simpler approximately truthful-in-expectation mechanism. We also extend their assumption regarding the existence of an exact solution for the LP-relaxation of social welfare maximization. We assume that there exists an approximation algorithm for the LP and establish a new randomized approximation mechanism. In chapter 3, we consider the problem of computing an approximate saddle point, or equivalently equilibrium, for a convex-concave functions $F: X\times Y\to \RR$, where $X$ and $Y$ are convex sets of arbitrary dimensions. Our main contribution is the design of a randomized algorithm for computing an $\eps$-approximation saddle point for $F$. Our algorithm is based on combining a technique developed by Grigoriadis and Khachiyan {GK95}, which is a randomized variant of Brown's fictitious play {B51}, with the recent results on random sampling from convex sets (see, e.g., {LV06,V05}). The algorithm finds an $\eps$-approximation saddle point in an expected number of $O\left(\frac{\rho^2(n+m)}{\eps^{2}}\ln\frac{R}{\eps}\right)$ iterations, where in each iteration two points are sampled from log-concave distributions over strategy sets. It is assumed that $X$ and $Y$ have inscribed balls of radius $1/R$ and circumscribing balls of radius $R$ and $\rho=\max_{x\in X, y\in Y} |F(x,y)|$. In particular, the algorithm requires $O^*\left(\frac{\rho^2(n+m)^6}{\eps^{2}}\ln{R}\right)$ calls to a membership oracle, where $O^*(\cdot)$ suppresses polylogarithmic factors that depend on $n$, $m$, and $\eps$.

In dieser Doktorarbeit verwenden wir die Multiplicative Weights Update Method (MWUM) für den Entwurf von Approximationsalgorithmen für bestimmte Optimierungsprobleme im spieltheoretischen Umfeld. Lavi und Swamy {LS05,LS11} präsentierten einen randomisierten Mechanismus für kombinatorische Auktionen. Sie verwenden dazu einen Approximationsalgorithmus für die Lösung des zugrundeliegenden Optimierungsproblem, das so genannte Social Welfare Maximization Problem, und wandeln diesen zu einem randomisierten Mechanismus um, der im Erwartungsfall anreizkompatibel ist. Dies bedeutet jeder Spieler erreicht den maximalen Gewinn, wenn er sich ehrlich verhält. Der Mechanismus ist sehr mächtig (siehe {LS05,LS11,CEF10,HKV11} für Anwendungen); trotzdem ist es unwahrscheinlich, dass er in der Praxis effizient ist, da hier die Ellipsoidmethode verwendet wird. In Kapitel 2 folgen wir dem von Lavi und Swamy vorgeschlagenem Schema und ersetzen die Ellipsoidmethode durch MWUM. Das Ergebnis ist ein schnellerer, einfacherer und im Erwartungsfall anreizkompatibler Approximationsmechanismus. Wir erweitern ihre Annahme zur Existenz einer exakten Lösung der LP-Relaxierung für das Social Welfare Maximization Problem. Wir nehmen an, dass ein Approximationsalgorithmus für das LP existiert und beschreiben darauf basierend einen neuen randomisierten Approximationsmechanismus. In Kapitel 3 betrachten wir das Problem für konvexe und konkave Funktionen $F:X\times Y\rightarrow\mathbb{R}$, wobei $X$ und $Y$ konvexe Mengen von beliebiger Dimension sind, einen Sattelpunkt zu approximieren (oder gleichbedeutend ein Equilibrium). Unser Hauptbeitrag ist der Entwurf eines randomisierten Algorithmus zur Berechnung einer $\epsilon$-Näherung eines Sattelpunktes von $F$. Unser Algorithmus beruht auf der Kombination einer Technik entwickelt durch Grigoriadis und Khachiyan {GK95}, welche eine zufallsbasierte Variation von Browns Fictitious Play {B51} ist, mit kürzlich erschienenen Resultaten im Bereich der zufälligen Stichprobennahme aus konvexen Mengen (siehe {LV06,V05}). Der Algorithmus findet eine $\epsilon$-Näherung eines Sattelpunktes im Erwartungsfall in $O(\frac{\rho^{2}(n+m)^{6}}{\epsilon^{2}}\log\frac{R}{\epsilon})$ Rechenschritten, wobei in jedem Rechenschritt zwei Punkte zufällig gemäß einer log-konkaven Verteilungen über Strategiemengen gezogen werden. Hier nehmen wir an, dass $X$ und $Y$ einbeschriebene Kugeln mit Radius $1/R$ und umschreibende Kugeln von Radius R besitzen und $\rho=\max_{x\in X,y\in Y}|F(x,y)|$. Der Algorithmus benötigt dabei $O^{*}(\frac{\rho^{2}(n+m)^{6}}{\epsilon^{2}}\log R)$ Aufrufe eines Zugehörigkeitsorakels, hier versteckt $O^{*}(\cdot)$ polylogarithmische Faktoren, die von $n,m$ und $\epsilon$ abhängen.