An Empirical Study on Computing Equilibria\\ in Polymatrix Games
\alignauthor Argyrios Deligkas
\affaddr{University of Liverpool
UK
The Nash equilibrium is an important benchmark for behaviour in systems of strategic autonomous agents. Polymatrix games are a succinct and expressive representation of multiplayer games that model pairwise interactions between players. The empirical performance of algorithms to solve these games has received little attention, despite their wide-ranging applications. In this paper we carry out a comprehensive empirical study of two prominent algorithms for computing a sample equilibrium in these games, Lemke's algorithm that computes an exact equilibrium, and a gradient descent method that computes an approximate equilibrium. Our study covers games arising from a number of interesting applications. We find that Lemke's algorithm can compute exact equilibria in relatively large games in a reasonable amount of time. If we are willing to accept (high-quality) approximate equilibria, then we can deal with much larger games using the descent method. We also report on which games are most challenging for each of the algorithms.
note.tex
%\documentclass{aamas2016}
\documentclass{aamas2016_arxiv}

% multiple citations is ascending order
\usepackage{cite}

\usepackage{enumitem}
\setlist[itemize]{leftmargin=*}

\pdfpagewidth=8.5truein
\pdfpageheight=11truein

%\usepackage{tcolorbox}
\usepackage{amsmath}
\usepackage{amsfonts}
%\usepackage{amsthm}
\usepackage{verbatim}
%\usepackage{bbm}
\usepackage{hhline}
\usepackage{multirow}

%\usepackage[disable]{todonotes}
%\usepackage{todonotes}
\usepackage{pdfpages}
\usepackage{graphicx}
\usepackage{subcaption}
%\usepackage[notref,notcite]{showkeys}

\usepackage{xspace}

\newcommand{\nats}{\mathbb N}
\newcommand{\rats}{\mathbb Q}
\newcommand{\eps}{\ensuremath{\epsilon}\xspace}

\newcommand{\T}{\mathsf{T}}
%\newcommand{\x}{\mathbf{x}}
%\newcommand{\y}{\mathbf{y}}
\newcommand{\profx}{\ensuremath{\mathbf{x}}\xspace}
\newcommand{\profy}{\ensuremath{\mathbf{y}}\xspace}
\newcommand{\row}{\mathbf{r}}
\newcommand{\col}{\mathbf{c}}
\newcommand{\G}{\mathcal{G}}

\newcommand{\PPAD}{\texttt{PPAD}\xspace}
\newcommand{\NP}{\texttt{NP}\xspace}
\newcommand{\PLS}{\texttt{PLS}\xspace}
\newcommand{\PSPACE}{\texttt{PSPACE}\xspace}

%%%%%%%%%%%%%%%%%%%%%%%%% GAME MACROS %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%% ALGORITHM MACROS %%%%%%%%%%%%%%%%%%%%%%
\newcommand{\lemke}{\textsc{Lemke}\xspace}
\newcommand{\descent}{\textsc{Descent}\xspace}

\DeclareMathOperator{\supp}{Supp}
\DeclareMathOperator{\pr}{Pr}

\begin{document}



\title{An Empirical Study on Computing Equilibria\\ in Polymatrix Games}

\numberofauthors{4}

\author{
\alignauthor Argyrios Deligkas\\
    \affaddr{University of Liverpool, UK}
    %\affaddr{United Kingdom}
    %\email{a.deligkas@liverpool.ac.uk} 
\alignauthor John Fearnley\\
    \affaddr{University of Liverpool, UK}
    %\affaddr{United Kingdom}
    %\email{john.fearnley@liverpool.ac.uk} 
\and
\alignauthor Tobenna Peter Igwe\\
    \affaddr{University of Liverpool, UK}
    %\affaddr{United Kingdom}
    %\email{t.igwe@liverpool.ac.uk}
\alignauthor Rahul Savani\\
    \affaddr{University of Liverpool, UK}
    %\affaddr{United Kingdom}
    %\email{rahul.savani@liverpool.ac.uk}
}


\maketitle

\begin{abstract}
The Nash equilibrium is an important benchmark for behaviour in systems of strategic autonomous agents.  Polymatrix games are a succinct and expressive representation of multiplayer games that model pairwise interactions between players.  The empirical performance of algorithms to solve these games has received little attention, despite their wide-ranging applications.  In this paper we carry out a comprehensive empirical study of two prominent algorithms for computing a sample equilibrium in these games, Lemke's algorithm that computes an exact equilibrium, and a gradient descent method that computes an approximate equilibrium.  Our study covers games arising from a number of interesting applications.  We find that Lemke's algorithm can compute exact equilibria in relatively large games in a reasonable amount of time.  If we are willing to accept (high-quality) approximate equilibria, then we can deal with much larger games using the descent method.  We also report on which games are most challenging for each of the algorithms.
\end{abstract}

% Note that the category section should be completed after reference to the ACM Computing Classification Scheme available at
% http://www.acm.org/about/class/1998/.

%\category{J.4}{Social and Behavioral Sciences} {Economics}

%A category including the fourth, optional field follows...
%\category{D.2.8}{Software Engineering}{Metrics}[complexity measures, performance measures]

%General terms should be selected from the following 16 terms: Algorithms, Management, Measurement, Documentation, Performance, Design, Economics, Reliability, Experimentation, Security, Human Factors, Standardization, Languages, Theory, Legal Aspects, Verification.

\terms{Algorithms, Economics}

%Keywords are your own choice of terms you would like the paper to be indexed by.

\keywords{%
Game Theory;
Nash Equilibrium;
Approximate Equilibria;
Polymatrix Games; 
Auctions;
Bayesian Two-Player Games;
Lemke's Algorithm; 
Gradient Descent}

\section{Introduction}

In multiagent systems it is often the case that autonomous agents interact with
each other, but do not necessarily have the same objectives or goals. This
situation can be described as a game played between the agents, and the tools
from game theory can be used to analyse the possible outcomes. In particular,
the concept of a Nash equilibrium~\cite{N} describes a stable situation in which
no agent can increase its reward by changing its behaviour. Therefore, to
gain insight into the possible behaviours that a system of rational agents will
produce, one can compute the Nash equilibria of the game that is played between
the agents.

Games are often represented in \emph{strategic-form}, where for each possible
combination of strategy choices, a numerical payoff is specified
for each of the players. However, the size of this representation grows
\emph{exponentially} in the number of players. For example, for a game with $n$
players who can each choose between $2$ strategies, $n \cdot 2^n$ payoffs must
be specified. Hence, the strategic-form is typically unsuitable for the types of
games that arise from multiagent systems.

Many realistic scenarios do not need the flexibility that strategic-form
games provide. In particular, it is often the case that only the \emph{pairwise}
interactions between players are important. In this paper we study
\emph{polymatrix games} which model this. In these games the
interaction between the players is specified as a graph. Each player plays
an independent two-player game against each other player that he is connected
to, and the same strategy must be played in all of his
games. A player's payoff is then the sum of the payoffs from each of the
games. Crucially, the representations of these games grow \emph{quadratically}
in the number of players, which makes them more suitable for representing the large
multiagent systems that arise from real-world scenarios.

While there has been a large amount of theoretical work on polymatrix
games~\cite{DGP,CDT,EY10,FT-C10,CPY13,GW04}, the practical aspects of computing
equilibria in polymatrix games have yet to be studied. In this paper, we
provide an empirical study of two prominent methods for computing equilibria in
these games. Firstly, we study \emph{Lemke's algorithm}. The Lemke-Howson 
algorithm is a
famous algorithm for finding Nash equilibria in bimatrix
games~\cite{lemke64}, and Lemke's algorithm is a more general
technique for solving
\emph{linear complementarity problems} (LCPs). Miller and Zucker \cite{miller91}
have shown that the problem of finding a Nash equilibrium in a polymatrix game
can be reduced to the problem of solving an LCP that can then be tackled by
Lemke's algorithm.

%Apart from brute force
%support enumeration (which is exponential for polymatrix games even for finding
%pure Nash equilibria), Lemke's algorithm is the only known method for finding an
%Nash equilibrium in a polymatrix game.

Secondly, we study a method for finding \emph{approximate} equilibria in
polymatrix games. In contrast to a Nash equilibrium, where no player has an
incentive to deviate, an approximate equilibrium allows the players to have a
positive, but small, incentive to deviate from their current strategies.
Approximate equilibria have received a large amount of interest in theoretical
work~\cite{BBM10,BGR08,DFSS,DMP,HRS08,TS}, because the problem of finding an
exact Nash equilibrium in a polymatrix game, even for only two players, is known
to be \PPAD-complete (which implies that there is unlikely to be a
polynomial-time algorithm for this problem). From a practical point of view, it
is reasonable to use sufficiently accurate approximate equilibria to study
real-world systems, because often there is a non-negative cost to changing
strategy, which could deter an agent from deviating even if doing so would lead
to a small increase in payoff. Also, if the game is derived from real data, then
any uncertainty in the actual payoffs of the underlying situation means that
agents may be perfectly happy in the real world, even if the game model says
that they can gain a small amount through deviation.

We study a recently proposed gradient descent-like algorithm for finding
approximate equilibria in polymatrix games~\cite{DFSS}, which is the only known
approximation technique for (general) polymatrix games. It generalizes
the algorithm of Tsaknakis and Spirakis (TS) for bimatrix games\cite{TS}.
A recent
study found that the TS algorithm typically finds high-quality approximate
equilibria in practice~\cite{FIS15}, much better that its
theoretical worst-case performance.

%The vast majority of multiagent systems have an equivalent game representation 
%and usually many game theoretic approaches are adopted in order to analyze the 
%properties of that model~\cite{SLB}. It is often the case that the analysis 
%focuses on situations where all the agents adopt a specific way to interact with 
%the other agents and no agent is willing to unilaterally change the adopted 
%strategy. The situation described above is a \emph{Nash equilibrium} for the 
%system.

%Although the existence of Nash equilibria (NE) in games was established in
%1950~\cite{N}, only recently the problem of computing one was answered. More
%specifically, it was shown that the problem of finding a Nash equilibrium is
%\PPAD-complete~\cite{DGP, CDT}. This implies that it is unlikely to exist a
%polynomial time algorithm for the problem, hence a line of work that studies
%approximate notions of Nash equilibria has
%arisen~\cite{BBM10,BGR08,DFSS,DMP,HRS08,TS}. 

%The most widely studied notion is of an \emph{$\epsilon$-approximate Nash
%equilibrium} ($\epsilon$-Nash), which requires that all players have an expected
%payoff that is within~$\epsilon$ of a best response. 
%%
%This is an \emph{additive} notion of approximate equilibrium; the problem of
%computing approximate equilibria of bimatrix games using a relative notion of
%approximation is known to be \PPAD-hard even for constant
%approximations~\cite{Das13}.

%\todo[inline]{Introduce the Bayesian auctions setup with item bidding, say how 
%much attention it got for proving PoA and PoS bounds and that recently we are
%interested in computation of NE for this class of games.}
%Auctions is another popular class of games where agents interact to each other.

%\todo[inline]{Now expand on abstract}

%\vskip -\baselineskip
%\paragraph{\textbf{Our contribution}}
\medskip

\noindent \textbf{Our contribution.}
We provide a thorough empirical study of finding exact and
approximate Nash equilibria in polymatrix games. We develop an extensive library
of game classes that cover a number of applications of polymatrix games
including cooperation games, strictly competitive games, and
group-wise zero-sum games. We also study \emph{Bayesian two-player games}, 
which can be modelled as
polymatrix games. In particular, we focus on various forms of \emph{Bayesian
auctions} (e.g., item bidding combinatorial auctions) and Bayesian variants of
Colonel Blotto games, which have applications to task allocation and resource
allocation problems between agents~\cite{SL08}.
All of our algorithm implementations and
game generators are open source and publicly
available\footnote{\texttt{http://polymatrix-games.github.io/}}, so that any new
algorithms developed for polymatrix games can be tested against our test suite.

We study Lemke's algorithm and the descent method on all of the
problems that we consider. In total we applied Lemke's algorithm to 188,000
instances using 26 months of CPU time, while we applied descent to
213,000 instances using 2.7 months of CPU time.  We found that Lemke's algorithm
can compute exact equilibria in relatively large games in a reasonable amount of
time, though the descent method is much more scalable and can be used to compute
approximate equilibria for instances that are an order of magnitude bigger.
Moreover, in contrast to its
theoretical worst-case performance guarantee, the descent method typically finds
very high quality approximate equilibria.

%The contributions of this paper can be be divided into three main categories:
%implementation of the algorithms, construction and implementation of game 
%generators, experimental results. To our knowledge, this is the first 
%implementation of the \descent algorithm, and since it is not known whether the 
%analysis of the approximation guarantee is tight, our results give lower bounds 
%for the algorithm. 

%The second contribution of our project is the construction and the implementation
%of generators for two bidder Bayesian auctions, Bayesian blotto, and several 
%classes of polymatrix games with known and unknown complexity. Our plan is to 
%make the generators (and the algorithms' code) public to the community, 
%so they can
%can be used in the future as a test suite for other algorithms for polymatrix 
%and two player Bayesian games. Furthermore, the games generators we constructed 
%are rather general and easy to adapt in order to produce many different games. 
%To our knowledge these are the first generators only for polymatrix games. 
%GAMUT produces polymatrix games and then converts them into general n-player 
%games without giving the option to the end user to output a polymatrix game.  

%The last contribution is the experiments. Since the majority of the studies for
%the games we consider are theoretical, our experiments are an important first 
%step to understand better the average complexity for the known to be hard problems
%and to get some intuition for the games whose complexity remains unknown. 

%\vskip -\baselineskip
%\paragraph{\textbf{Related work}}
\medskip
\noindent \textbf{Related work.}
The problem of equilibrium computation has received much attention from the 
theoretical point of view. Firstly, it was proven that computing an exact Nash 
equilibrium is \PPAD-complete~\cite{DGP,CDT}, even for games with only 
two players. 
While the class \NP captures 
decision problems, the complexity class \PPAD captures problems where it is 
\emph{known} that a solution exists. It is assumed that it is unlikely that
there exists a polynomial time algorithm for \PPAD-complete problems.
For this reason a line of work that studies approximate 
notions of Nash equilibria has arisen~\cite{BBM10,BGR08,DMP,HRS08,TS}. 
Specifically for polymatrix games, there is the recent descent procedure 
studied in this paper~\cite{DFSS}, and a recent QPTAS for polymatrix games 
on trees~\cite{BLP15}.
%
%Polymatrix games have played a central role in the reductions that have 
%been used to show \PPAD-hardness of games and other equilibrium 
%problems~\cite{DGP,CDT,EY10,FT-C10,CPY13}. 


There are empirical studies on equilibrium computation both for exact 
equilibria~\cite{SGC05,ARSvS,ABH,PNS,FIS15} and approximate equilibria~\cite{FIS15}, 
but none of them focused on polymatrix games. Instead, these studies mainly 
focused on games created by GAMUT~\cite{GAMUT}, the most famous suite of game generators.
GAMUT has a generator for some simple polymatrix games, but it converts them to strategic-form
games which blows up the representation exponentially.

Polymatrix games have received a lot of attention recently.
Computing a Nash equilibrium in a polymatrix game is \PPAD-hard even when all
the bimatrix games are either zero-sum or coordination games~\cite{CD11}.
Recently, it was proven that there is a constant $\eps>0$ such that it is
\PPAD-hard to compute an \eps-Nash equilibrium of a polymatrix
game~\cite{Rub15}.
Govindan and Wilson proposed a 
(non-polynomial-time) algorithm for computing equilibria of an $n$-player 
strategic-form game, by approximating the game with a sequence of polymatrix games~\cite{GW04}.  
Later, they presented a (non-polynomial) reduction that reduces $n$-player games
to polymatrix games while preserving approximate Nash equilibria \cite{GW10}.
%Their reduction introduces a central coordinator player, who interacts
%bilaterally with every player.

Many papers have derived bounds on the Price of Anarchy~\cite{BR11,R12,FHGL} in
item bidding auctions~\cite{CKS08}.
Only recently Cai and Papadimitriou~\cite{CP14} and Dobzinski, Fu and
Kleinberg~\cite{DFK} studied the question of the complexity of the equilibrium
computation problem in this setting. Blotto games are a basic model of resource
allocation, and have therefore been studied in the agents
community~\cite{PTW14,AHLMS16}. There have also been several papers that
study Blotto games with incomplete information as well, see for
example~\cite{AM09,KR11}.

Polymatrix games are examples of \emph{graphical games}, which are succinct
representations of games where interactions between players are encoded in a graph.
A related succinct representation is that of Action Graph Games (AGGs); 
introduced by Bhat and Leyton-Brown, AGGs capture local dependencies as
in graphical games, and partial indifference to other agents' identities as in
anonymous games~\cite{JLB11,BL04,DSVV09}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminaries}
\label{sec:pre}
%\paragraph{\textbf{Bimatrix Games}}
\noindent \textbf{Bimatrix games.}
A bimatrix game is a pair $(R,C)$ of two $n \times n$ matrices: $R$ gives
payoffs for the \emph{row} player, and $C$ gives the payoffs for the
\emph{column} player. Each player has $n$ \emph{pure} strategies. To play the
game, both players simultaneously select a pure strategy: the row player selects
a row $i$, and the column player selects a column $j$. The row player then
receives $R_{i,j}$, and the column player $C_{i,j}$.

A \emph{mixed strategy} is a probability distribution over $[n]$. We denote a
row player mixed strategy as a vector $\profx$ of length $n$, such that
$\profx_i$ is the probability assigned to row $i$. Mixed strategies of the
column player are defined symmetrically. If $\profx$ and $\profy$ are mixed
strategies for the row and the column player, respectively, then the expected
payoff for the row player under the strategy profile $(\profx, \profy)$ is given
by $\profx^T R \profy$ and for the column player by $\profx^T C \profy$.

%\vskip -\baselineskip
%\paragraph{\textbf{Polymatrix Games}}
\medskip
\noindent \textbf{Polymatrix games.}
An $n$-player polymatrix game is defined by an $n$-vertex graph. Each 
vertex represents a player. 
Each edge $e$ corresponds to a bimatrix game that will be
played by the players that $e$ connects. Hence, a player with degree $d$ plays
$d$ bimatrix games. More precisely, each player picks a strategy
$x_i$ and plays that strategy in \emph{all} of the bimatrix games that he is
involved in. His expected payoff is given by the sum of the expected payoffs that
he obtains over all the bimatrix games that he participates in. We use $\profx = (x_1,
\ldots, x_n)$ to denote a strategy profile of an $n$-player game, where $x_i$
denotes the mixed strategy of player $i \in [n]$.

%\vskip -\baselineskip
%\paragraph{\textbf{Solution concepts}}
\medskip
\noindent \textbf{Solution concepts.}
The standard solution concept for strategic-form games is the \emph{Nash equilibrium} 
(NE). A relaxed version of this concept is the approximate NE, or \eps-NE. 
Intuitively, a strategy profile is an \eps-NE in an $n$-player game, if no player 
can increase his utility more than \eps by unilaterally changing his strategy. 
To put it formally, let \profx denote a strategy profile for the players and let
$u_i(z, \profx_{-i})$ denote the utility of player $i$ when he plays the 
strategy $z$ and the rest of the players play according to $\profx$. We say that
\profx is an \eps-NE if for every player $i$ it holds that
%\begin{align*}
$u_i(x_i, \profx_{-i}) \geq u_i(z, \profx_{-i}) - \eps$ for all possible $z$.
%\end{align*}
If $\eps = 0$, we have an exact Nash equilibrium.
%The same notion of approximation can be applied for Bayesian Nash equilibria 
%(\eps-BNE). The reduction presented in~\cite{DFSS} is approximation preserving,
%that is every $\eps$-NE in the polymatrix game constructed form a Bayesian game 
%$B$, is an $\eps$-BNE in $B$ too.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Algorithms}
%In this section, we describe the two algorithms that we study in this paper. 

%The first algorithm 
%computes exact Nash equilibria in polymatrix games albeit in exponential time in 
%in the input size in the worst case, whereas \descent computes in polynomial
%time, in the input size, approximate equilibria with constant approximation 
%guarantee.
%with theoretical approximation guarantee at least 0.5-NE.

%\vskip -\baselineskip
%\paragraph{\textbf{Lemke}}
\medskip
\textbf{Lemke's algorithm} is a complementary pivoting algorithm 
for the Linear
Complementarity Problem (LCP)~\cite{lemke65}. 
%An LCP is given by an $n \times n$
%matrix $M$ and a vector $q$ of size $n$. The problem is to find $w, z$ such
%that:
%\begin{align*}
 %w = q + Mz, \qquad w \ge \mathbf{0}, \qquad z \ge \mathbf{0}, \qquad z^\mathtt{T} w = 0.
%\end{align*}
Miller and Zucker have shown that finding a Nash equilibrium in
a polymatrix game can be reduced in polynomial time to a Lemke-solvable 
LCP~\cite{miller91}. 
So, we first turn the polymatrix game into an LCP, and then apply Lemke's
algorithm.  We shall refer to this algorithm as \lemke.

One drawback is that the reduction assumes a complete
interaction graph even if the actual interaction graph is not complete (by
padding with all-zero payoff bimatrix games).  Hence, for sparse polymatrix games the
reduction introduces a significant blowup, which affects the
performance of the algorithm.  To make this blowup clear, in our results we
report the number of payoffs in the original polymatrix game and the number of
matrix entries in the resulting LCP.

%Lemke's algorithm starts by introducing and pivoting an artificial variable 
%$z_0$ into the basis.
%As long as this variable is in the basis, there will always exist a pair 
%$z_i, w_i$ that could enter the basis. The complementary pivoting rule used 
%pivots in the complement of the variable which just left the basis. The algorithm
%continues pivoting until the variable $z_0$ leaves the basis. In order to resolve
%degeneracies, the implementation which we used performs a lexicographic minimum
%ratio to find the leaving variable. 


%In this reduction, an $n$-player polymatrix game with $m$ actions per player
%is represented as a matrix

%\[
%R = 
%\left(
%\begin{array}{ccc}
%r_{11} & \dots & r_{1n} \\
%\vdots & \ddots & \vdots \\
%r_{n1} & \dots & r_{nn}
%\end{array}
%\right)
%\]

%where $r_{ij}$ represents the payoff matrix of player $i$ against player $j$, and $R < 0$.
%Also, let the matrix $A$ be the $n \times mn$ matrix

%\[
%A = \left(
%\begin{array}{ccccccc}
%-1 & \dots & -1 & \dots & 0 & \dots & 0 \\
%\vdots & & & \ddots & & & \vdots\\
%0 & \dots & 0 & \dots & -1 & \dots & -1\\
%\end{array}
%\right)
%\]

%Using the above matrices, the polymatrix game can then be represented as a
%copositive-plus LCP where

%\[
%M = \left(
%\begin{array}{cc}
%-R & A^T \\
%-A & 0
%\end{array}
%\right)
%\]

%Due to the nature of this reduction, the generated LCP could contain a lot of constant entries, most
%especially on games represented on sparse graphs.
%The Lemke-Howson algorithm is known to be the \lemke algorithm with a special
%covering vector to determine the missing label\cite{Sav06}.

%\vskip -\baselineskip
%\paragraph{\textbf{Descent}}
\medskip
\textbf{Descent} is a gradient descent-like algorithm proposed in~\cite{DFSS}.
It tries to minimize the \emph{regret} that a player suffers, which
is the difference between the best-response utility
and the actual utility he gets. 
%For a given strategy profile, each player will have a different regret,
%and the algorithm aims to reduce the regret of the player with the maximum
%regret.
%
The algorithm starts from an arbitrary strategy profile~\profx and in each
iteration it computes a new profile in which the maximum regret (over the
players) has been reduced.
%
%$\profx'$ which specifies the direction in which the
%maximum regret decreases with the highest rate. Then it produces a new
%strategy profile which is obtained by moving in this direction.
%
The algorithm takes a parameter $\delta$ that controls how accurate the
resulting approximate Nash equilibrium is. The theoretical results state that
the algorithm finds a $(0.5+\delta)$-NE after $O(\delta^{-2})$ iterations (for a fixed 
size game).
We test the cases where $\delta$ is either $0.1$ or
$0.001$, and we provide full results for both cases. We shall refer to
this algorithm as \descent in our results.

For the strategy profile
$\profx$, the algorithm first computes a direction vector $(\profx' - \profx)$,
and then moves a certain distance in that direction. In other words, the
algorithm moves to a new strategy profile $\profx + \alpha(\profx' - \profx)$,
where $\alpha$ is some constant in the range $(0, 1]$. The theoretical analysis
in~\cite{DFSS} uses $\alpha = \frac{\delta}{\delta + 2}$ in the proof of 
polynomial-time convergence. In practice we found that using
larger step sizes greatly improves the running time.
%
Hence, we adopt a \emph{line search} technique, which we adapt from the
two-player setting~\cite{TSK08}. It checks a number of equally
spaced values for $\alpha$ in $[0,1]$, and selects the best
improvement that is found. We also 
include $\alpha = \frac{\delta}{\delta + 2}$ as an extra value in this check, so
that the theoretical worst-case running time is unchanged. In
our results, we check 201 different points for $\alpha$ in each iteration.  For
a justification of the reasonableness of this choice, see
Appendix~A in the full version of this paper~\cite{DFIS16}.
%In the full version of the paper we present results that show how the number of
%points checked impacts the overall running time of the algorithm.

%One final implementation issue is how to move from one strategy profile to the
%next. The theoretical work states that we should take a fixed step of size
%$\frac{\delta}{\delta+2}$ in the direction 
%$(\profx'-\profx)$, however empirical work on gradient descent for bimatrix
%games~\cite{FIS15} has found that a line-search procedure, where several points
%in the direction $(\profx'-\profx)$ are checked and the best is chosen, tends to
%outperform the fixed step-size approach. As our results will show,
%we found that line-search also helps greatly in the polymatrix game setting, so
%we use the line-search variant of the algorithm throughout.

%with a predefined stepsize. Formally,
%$\profx'':= \profx + \alpha (\profx'-\profx)$ where $\alpha = \frac{\delta}{\delta+2}$
%is the stepsize and $\delta \in (0,0.5]$. The $\delta$ is a parameter of the algorithm that 
%determines the stepsize and the approximation guarantee. Then the next iteration
%starts and a new strategy profile is computed. The algorithm computes a 
%$0.5+\delta$-NE after $O(\frac{1}{\delta^2})$ iterations.

%Notice that the original \descent algorithm uses a fixed stepsize in every 
%iteration. This was sufficient in order to prove the time complexity of algorithm. 
%In our experiments though, we modified the algorithm and we used a varying 
%stepsize in every iteration. We perform a line search over different possible 
%values for the stepsize and we choose the one that achieves the minimum regret. 
%%More specifically we represent the regret function
%%of the game as a piecewise polynomial function, which we evaluate different values of
%%$\alpha$ within the range $(0, 1]$ with a spacing of $0.005$.
%Although this procedure adds some extra computation time in each iteration, 
%overall it boosts the running time of \descent. It should also be noted that 
%\descent also suffers slightly from a similar issue as \lemke, with the linear 
%program having a lot of zero entries on sparse graphs. However, it is not as 
%pronounced due to only a subset of the full set of rows needed to solve the game.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Game classes}
\label{sec:classes}

%The main structural difference between these categories
%is the underlying graph. In the Bayesian two player games is a complete bipartite
%graph, whereas for the latter can be any arbitrary graph. 

%\subsection*{Bayesian two player games}

\subsection*{Bayesian Auctions}

%\vskip -\baselineskip
%\paragraph{\textbf{Combinatorial auctions}} 
\noindent \textbf{Combinatorial auctions.} 
In a combinatorial auction, $m$ items are auctioned to $n$ bidders. Each bidder 
has a valuation function that assigns a non-negative real number to every subset 
of the items. 
%
Notice that in this setting, in general, the size required to represent the 
valuation function is exponential in $m$.
%
In combinatorial auctions with \emph{item bidding}, each player bids for every
item separately and all the items are auctioned simultaneously. A bidder wins an
item if he submitted the highest bid for that item. The bidders pay
according to a predefined payment rule. We study three popular
payment rules.
In a \emph{first price} auction the winner of an item has to pay his bid for that item,
in a \emph{second price} auction the winner of an item has to pay the second highest
bid submitted for the item, 
and in an \emph{all pay} auction every bidder has to pay his bid 
\emph{irrespective} of whether he won the item or not.
If more than one bidder has the highest bid
for some item, we resolve this tie according to a predefined publicly known
rule. We study two tie-breaking rules: either we always favor one
of the players, or we choose the winner for each item independently uniformly at
random.

We say that a combinatorial auction allows \emph{overbidding} if a bidder is 
allowed to make a bid for a item greater than his value for it. 
A common assumption in the literature is that overbidding is not allowed, since
allowing overbidding leads to the existence of trivial equilibria. 
Therefore, in our experiments we do not allow overbidding. 


In a \emph{Bayesian}  combinatorial auction the valuation
function for every player is chosen according to a commonly known joint probability
distribution, which in this paper is always discrete. 
The different valuation functions that may be drawn for a player are 
known as his~\emph{types}. 
%In this paper we study Bayesian combinatorial auctions with two
%bidders. 

\medskip

%\vskip -\baselineskip
%\paragraph{\textbf{Item bidding auctions}} 

\noindent \textbf{Item bidding auctions.} 
We create two-bidder Bayesian item bidding combinatorial auctions with 
2 to 4 items for sale and 2 to 5 different types per player.
Each player's type (valuation function) is chosen uniformly at random. 
We study several well known valuation functions:
\begin{itemize}
\itemsep0em
\item \emph{Additive}: the value of each bundle of items is the sum of the 
values of the items contained in the bundle.
\item \emph{Budget additive}: the value of each bundle is the minimum of a
	budget parameter and the sum of the values of the items contained in the
	bundle.
\item \emph{Single minded}: each bidder has positive value for a specific bundle 
of items (and the same value for any other bundle of items containing that
bundle) and zero otherwise.
\item \emph{Unit demand}: the value of each bundle is the maximum value the bidder
has for any single item contained in the bundle.
\item \emph{AND-OR}: the first bidder has positive value only for the grand bundle
of items and zero otherwise, while the second one has a unit demand valuation.
\end{itemize}
%
%Since we study Bayesian auctions with item bidding, a pure strategy for a bidders 
%when $n$ items are auctioned is defined as $(b_1, \ldots, b_n)$ where $b_i$ 
%represents the bid the player made for item $i$. We allow bid increments of one
%unit for every $b_i$. In all the created games we do 
%not allow overbidding; as mentioned earlier too, there are trivial equilibria if
%overbidding is allowed. A player overbids for a subset of items if the sum of 
%his bids for the items in this subset is greater than his valuation for the 
%subset. 
To create the valuations, we set a maximum value~$M\in \nats$ that a player 
can have for any item, and a minimum value $m \in \nats$ such that in every valuation
there must be an item with a value of at least $m$. Bids are restricted to $\nats$, so 
$M$ and $m$ define the number of pure strategies a player has, and
consequently the size of the game. For a player with a single-minded
valuation function, we choose a random subset of items and a random value for
that subset in the range $[m, M]$. For additive and unit demand valuations, we
randomly select a value for each item from the set of allowed valuations. The
same procedure is extended for budget additive bidders: first we draw values for
items as for additive bidders; then we draw the budget as a random integer
in $[M,N]$ where~$N$ is the sum of the values for the items.

%\vskip -\baselineskip
%\paragraph{\textbf{Multi-unit auctions}}

\medskip

\noindent \textbf{Multi-unit auctions.}
In these auctions all the items being sold are 
identical. When there are $n$ items for sale, a valuation is 
given by an $n$-tuple $(v_{1}, \ldots, v_{n})$, where $v_{j}$ represents the 
player's marginal value for receiving a $j$-th copy of the item. Hence, the 
valuation for a bidder when he wins~$k$ items is the sum of the values $v_1$ up 
to $v_k$. 
%
%A pure strategy for a player is an $n$-tuple of bids in non-increasing order. 

Again we study the three most common payment rules: the first price rule, a.k.a.\
the \emph{discriminatory auction}, where a player that won $k$ items has to pay the
sum of his $k$ highest bids; the second price rule, a.k.a.\ the \emph{uniform-price
auction}, where the price for every item is the market-clearing price, i.e., the
highest losing bid; and the all-pay rule, where a player has to pay the sum of
his bids. 

We consider two well known valuation functions:
additive, where $v_j = v_1$ for all $j > 1$, and submodular, where $v_{j} \ge
v_{j+1}$ for all $j \in [n-1]$. We create games with 2 to 4 items
and 2 to 5 different types per player. The sampling of non-additive 
sub-modular valuation functions is not described here; we refer the reader to
the source code for further details\footnote{\texttt{http://polymatrix-games.github.io/}}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Other Bayesian Two-player Games}
%\vskip -\baselineskip
%\paragraph{\textbf{Two-Player Bayesian Games}}
A two-player Bayesian game is played between a row player and a column player. 
Each player has a set of possible types, and at the start of the game, each 
player is assigned a type according to a publicly known joint probability 
distribution. Each player learns his type, but not the type of the other player.
Rosenthal and Howson showed that the problem of finding an exact equilibrium in
a two-player Bayesian game can be reduced to finding an exact equilibrium in a
polymatrix game~\cite{HR74}, and this was extended to 
approximate equilibria in~\cite{DFSS}.
The underlying graph in the resulting polymatrix game is a complete 
bipartite graph where the vertices of each side represent the types of a player.
%
More specifically, if the row player has $n$ types and the column player has $m$
types, the corresponding polymatrix game has $n+m$ vertices and the payoff matrix
for edge $(uv)$ corresponds to the payoff matrix of the Bayesian game where the
row player has type $u$ and the column player has type $v$. We study the
following Bayesian two-player games.

\medskip

%\vskip -\baselineskip
%\paragraph{\textbf{Colonel Blotto games}}

\noindent \textbf{Colonel Blotto games.}
In Colonel Blotto games, each player has a number of soldiers $m_1$, $m_2$ that are 
simultaneously assigned to $n$ hills. 
Each player has a value for each hill that he receives if he 
assigns strictly more soldiers to the hill than his opponent and any ties are 
resolved by choosing a winner uniformly at random. The value that a player has 
for a hill is generated independently uniformly at random and the 
payoff a player 
gets under a strategy profile is given by the sum of the value of the hills 
won by that player. We consider games with 3 and 4 hills and 3 to 15
soldiers per player. We study two different Bayesian parameters: the valuations 
of the players over the hills and the number of soldiers that each player has. 
In the game we looked at, only one of these two parameters was used (i.e., for the 
other there was complete information).
For both cases we study games with 2 to 4 types per player.
When the types correspond to different valuations for hills, for every type, 
the valuations for each hill were drawn from independent uniform distributions on $[0, 1]$.
When the types correspond to the number of soldiers, we drew independently from
$\{3,\ldots,15\}$ for each player and each type.

\medskip

%\vskip -\baselineskip
%\paragraph{\textbf{Adjusted Winner games}}

\noindent \textbf{Adjusted Winner games.}
The adjusted winner procedure fractionally allocates a set of $n$ divisible items
to two players~\cite{AW}.  Under the procedure, $n-1$ items stay whole and
at most one is split between the players.  Each player has a
non-negative value for each item, and these values sum to 1.
Both players have additive valuations over bundles of items.  For a split item that 
a player has value $v$ for,
if the player receives $w \in [0, 1]$ of the item, he gets gets $w \cdot v$ value
from this part of the item.

The players simultaneously assign $m$ points to the items. Suppose player 1
assigns $\alpha_i$ points for the items $i=1,\ldots,n$ with $\sum_i \alpha_i =
m$, and similarly player 2's assignment is $(\beta_1, \dots,
\beta_n)$. The procedure starts with an initial allocation in which each item
goes to one of the players that assigned most points to it.  If the players get
equal utilities it stops. Otherwise it next determines which player gets higher
utility under this allocation, say player 1.  Next it finds the item~$i$ that is
currently allocated to player 1 and has the smallest ratio $\alpha_i / \beta_i$.
If possible it splits this item in a such a way as to equalize the total utilities of
the two players, or, if not, completely reallocates this item to player 2, and
repeats this step until the utilities of the two players are equalized.
Thus, at most one item is actually split.

We create Bayesian games where the players' types are different
valuations for the items.
We study the cases of 2 to 4 items and between 3 and 15 points for the players
to assign.  Independently for every type, the valuations for each item were drawn from independent
uniform distributions on $[0, 1]$, and then normalized to sum up to 1. 

\subsection*{Multi-player Polymatrix Games}
We study several types of game. For each, we study 
a range of underlying graphs: complete graphs, cycles, stars, and grid graphs.
In each case the entries of the payoff
matrices are drawn from independent uniform distributions on~$[0,1]$.
%
%\begin{description}
%\itemsep0em
%\item[Net coordination games.]
%\vskip -\baselineskip
%\paragraph{\textbf{Net coordination games}}

\medskip
\noindent \textbf{Net coordination games.}
In these games, every edge~$e$ corresponds to a coordination bimatrix game 
$(A_e, A_e)$. These games posses a pure NE, 
which is \PLS-complete to compute. The complexity of finding a (possibly non-pure)
exact equilibrium is in 
$\PLS \cap \PPAD$~\cite{CD11}.

%\item[Coordination/zero-sum games.]
%\vskip -\baselineskip
%\paragraph{\textbf{Coordination/zero-sum games}}

\medskip
\noindent \textbf{Coordination/zero-sum games.}
Here each edge is either a coordination or zero-sum game, i.e., on edge $e$ the
bimatrix game is $(A_e, A_e)$, or $(A_e, -A_e)$. These games are
\PPAD-complete~\cite{CD11} to solve.
%
We create games having a proportion $p$ of coordination games for $p \in \{0,
0.25, 0.5, 0.75, 1\} $. We study how $p$ affects the running time of
the algorithms. 

%\item[Group-wise zero-sum games.]
%\vskip -\baselineskip
%\paragraph{\textbf{Group-wise zero-sum games}}

\medskip
\noindent \textbf{Group-wise zero-sum games.}
The players are partitioned into groups so that the edges going between groups
are zero-sum while those within the same group are coordination games. In other
words, players inside a group are ``friends'' who want to coordinate their
actions, while players in different groups are competitors. These games are
\PPAD-complete~\cite{CD11} to solve even with 3 groups. 
We create games with 2 and 5 groups, all played on complete
graphs. In every case, each group is approximately the same size, 
and each player is assigned to a group at random. 

%\todo[inline]{
%The partition that a player belongs to is 
%chosen in the following way: we order the players and then we put each one of them to the
%group with number equal to his order modulo number of partitions. }

%\item[Strictly competitive games.]
%\vskip -\baselineskip
%\paragraph{\textbf{Strictly competitive games}}

\medskip
\noindent \textbf{Strictly competitive games.}
A bimatrix game is strictly competitive if for every pair of mixed strategy profiles $s$
and~$s'$ we have that: if the payoff of one player is better in $s$ than in $s'$, then the 
payoff of the other player is worse in $s$ than in $s'$. 
%These games were known 
%to be solvable via linear programming~\cite{aumann87}, and recent work has shown
%that they are merely affine transformations of zero-sum games~\cite{AdlerDP09}. 
%That is, if $(R,C)$ is a strictly competitive game, there exists a zero-sum game 
%$(R',C')$ and constants $c_1, c_2 > 0$ and $d_1, d_2$ such that $R = c_1R'+d_1I$
%and $C = c_2C'+d_2I$, where $I$ is the all-ones matrix. 
We study polymatrix games with strictly competitive games on the edges, which are
\PPAD-complete~\cite{CD11}.

\medskip

%\item[Weighted cooperation games.]
%\vskip -\baselineskip
%\paragraph{\textbf{Weighted cooperation games}}

\noindent \textbf{Weighted cooperation games.}
The unweighted version of these games was introduced in~\cite{ARSS15}. 
Each player chooses a colour from a set of available colours. The payoff of a
player is the number of neighbours who choose the same colour. These games have
a pure NE that can be computed in polynomial time. We study the more general
case where each edge has a positive weight. The complexity for the weighted case
is unknown~\cite{DP11}. We create games where all players have the same number
of available colors $k$, where $k$ is in $\{15,\ldots,45\}$.
For every player, his available colors are chosen uniformly at random
from all $k$-sized subsets from a universe of colors of size either~$2k$ or~$5k$.

%\todo[inline]{Will we include transduction games??}
%\item \textbf{Transduction games.}
%Graph transduction is a popular class of semi-supervised learning techniques which
%aims to estimate a classification function defined over a graph of labeled and 
%unlabeled data points. In~\cite{ErdemP12} the transduction problem is formulated 
%in terms of a polymatrix game where NE correspond to consistent labelings of the 
%data. The payoff matrix between players $i$ and $j$ is of the form 
%$A_{ij}=w_{ij}*I$ where $I$ is the identity matrix.

%\item \textbf{Ranking}
%
%\item \textbf{Security Games}
%In the security game which we studied, the defender is a security agent who wants to secure $k$
%houses, but can only patrol $d$ houses while the theif seeks to break into a house and steal it's
%valuables. If a theif chooses to rob a house which the security guard is not patrolling, then he is
%successful, otherwise, if he robs the $j$-th house in the patrol order, he is caught with
%probability $p_j$, such that for all $j$, $p_{j} \ge p_{j+1}$. If the theif successfully breaks in
%to a house, then he gains his valuation and the security guard loses theirs. In the event that the
%theif gets caught, he then pays a fine for getting caught and the guard gains a value for catching
%the theif.

%\end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experimental setup}

%\vskip -\baselineskip
%\paragraph{\textbf{Implementation}}
%\noindent \textbf{Implementation.}
The algorithms and game generators were implemented in~C. The
CPLEX library was used for solving LPs in the implementation of \descent. 
Our implementation of \lemke uses integer pivoting
in exact arithmetic using the GMP library; we were unable to produce a
numerically stable floating point implementation
(generally our attempts would start to fail on LCP instances of dimension $60$).
%Due to floating point inaccuracies, we were unable
%to produce a stable implementation of the \lemke algorithm which worked on LCP's
%of size greater than $60 \times 60$ (an issue which plagues several libraries
%with an implementation of \lemke's algorithm). This usually lead to incorrect
%pivots being made within the impementation causing it to eventually ray
%terminate.
%
%\todo[inline]{Argy's comment: I believe that this explanation is not convincing 
%enough. What exactly are the inaccuracies and HOW they affect the algo? In the 
%way it is written someone can argue that we favoured \descent.}
%As a result, for \lemke's algorithm, we
%used an implementation which performs integer pivoting in exact arithmetic using the GMP library.
%
%For our runtime results, we only measure the amount of time which is spent
%running the algorithm.
%\todo[inline]{What does the above mean - we don't count the reduction to an
%LCP for Lemke? Anything else?}
All experiments had a time-out of 10 minutes. In our results, the average
runtime of the algorithms, as well as the approximation guarantee found,
include the instances which timed out. 
The experiments used a cluster of
8 machines with Intel Core i7-2600 CPU's clocked at 3.40GHz and 16GB of memory, running
Scientific Linux 6.6 with kernel version 2.6.32.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Results}

\begin{table*}[htp]{
\centering
\input{tables/auc_joint.tex}
\caption{Results for item bidding and multi-unit auctions with 3 items and 3
types per player. Ties are broken by
favouring the second player for item bidding, and by allocating the item uniformly at
random in the multi-unit case. For \lemke, we report the average running time, the percentage of instances
that exceeded our timeout of 10 minutes, and the percentage of instances for
which the algorithm finds a pure equilibrium. For \descent, we report the
average running time and the approximation quality of the approximate equilibrium that was found.}
\label{tbl:auction}
}
\end{table*}
%
\begin{table*}[htp]{
\centering
{\small
\input{tables/blotto/joint.tex}
}
\caption{Results for Adjusted Winner and Blotto games. 
%The table shows the
%number of types and points for adjusted winner games, and the number of hills
%and troops for Blotto games. 
The two rows for Adjusted Winner show similar running
times but actually correspond to very different input sizes, with the second row 
corresponding to much larger games. The underlying reason is that the number of players 
in the polymatrix game (i.e., number of types) affects the running time
much more that the number of actions (i.e., number of items/troops). Also see
Appendix~B in the full version of this paper~\cite{DFIS16}.
}
\label{tbl:bayesian} 
} 
\end{table*}

% The next two tables are small and each fit in one column
%\begin{table*}[htp]
%\begin{subtable}{0.5\textwidth}{
%\centering
%\input{tables/auc_small/tables2.tex}
%\subcaption{Results for \lemke on first price (FP), second price (SP) and all-pay
%(AP) auctions with budget additive valuations, 3 items and 5 types per player.
%In the first two columns, all tied items are given to player 1,
%while in the last two, tied items are given uniformly at random
%}
%\label{tbl:ties}
%}
%\end{subtable}%
%\begin{subtable}{0.5\textwidth}{
%\centering
%\input{tables/auc_small/tables.tex}
%}
%\subcaption{Results for first price (FP), second price (SP),
%and all-pay (AP) auctions for additive bidders, with \lemke timing out on 13\% and 44.5\% of
%FP and AP auctions respectively, while \descent without line search times out on
%61.5\%, 56 \% and 94\% of instances on the respective auctions.}
%\label{tbl:ls}
%\end{subtable}
%\end{table*}

\begin{table*}[htp]{
\centering
\input{tables/auc_small/tables2.tex}
\caption{Results for \lemke showing the impact of the tie-breaking rule. We
report on first price (FP), second price (SP) and all-pay
(AP) auctions with budget additive valuations, 3 items, and 5 types per
player. In the first two columns, all tied items are allocated to player 1,
while in the last two, tied items are allocated uniformly at random.
}
\label{tbl:ties}
}
\end{table*}

\begin{table*}[htp]{ 
\centering
\input{tables/auc_small/tables.tex}
\caption{Results showing the impact of line search for \descent. We report
results for first price (FP), second price (SP),
and all-pay (AP) auctions for additive bidders. \lemke timed out on 13\% and 44.5\% of
FP and AP auctions respectively, while \descent without line search times out on
61.5\%, 56 \% and 94\% of instances on the respective auctions.}
\label{tbl:ls}
}
\end{table*}


\begin{table*}[t]{
\centering
\input{tables/large.tex}
%\input{tables/coord_joint.tex}
\caption{Results for multi-player (non-Bayesian) polymatrix games.
The underlying graphs are complete graphs, cycles,
grids and star graphs. $\% T$ is the proportion of the timed out instances.
On Cooperation-Zerosum games, the value of $p$ represents the proportion of
games which are coordination games, for group zero-sum games, it represents the number of groups,
and for weighted cooperation games, it represents the multiplier dictating the total number of
colours available, i.e. if there are $k$ colours per player, then there are 
$k \cdot p$ total colours
available. }
\label{tbl:polymatrix}
}
\end{table*}

We ran both \lemke and \descent on all of our input instances.
Table~\ref{tbl:auction}
shows the results for auctions, Table~\ref{tbl:bayesian} shows the results for
other Bayesian two-player games, and Table~\ref{tbl:polymatrix} shows the results for
multi-player polymatrix games. While we tested games of many different sizes,
for the purposes of exposition, the tables 
display the largest instances that \lemke can solve without
timing out.

\begin{figure*}[h]
\centering
\includegraphics[page=1,width=\linewidth]{plots/multi.pdf}
\caption{
%Plots showing the performance \lemke and \descent with $\delta = 0.001$ on multi unit auctions on first price, second price
%and all-pay payment methods
Plots showing the performance of the algorithms on multi-unit auctions with
first price, second price, and all-pay payment rules. The left plot
shows the performance of \lemke's algorithm. It can clearly be seen that
the allocation rule impacts the performance of the algorithm. The right chart
right shows the performance of \descent with $\delta = 0.001$. The
$y$-axis scales on the two charts are not equal: \descent is much
faster than \lemke.
}
\label{fig:comparison}
\end{figure*}

One general feature of our results is that \descent is much
faster than \lemke. To illustrate this, Figure~\ref{fig:comparison} shows the
performance of the two algorithms on the three types of additive item-bidding
auctions included in the study. It can be seen that on the hard instances (first
price and all pay), \lemke starts to struggle when there are around 5 million
payoffs in the game, whereas even the slower and more accurate of the two
\descent variants ($\delta=0.001$) can handle games with 30 million payoffs in
under a minute.
%
Indeed, a runtime regression for Bayesian Blotto games
found that \lemke has roughly quadratic running time (with an
$R^2$ of $0.75$ for the regression), while \descent has roughly linear running time 
% 0.999 for delta 0.1 and 0.83 for delta 0.001
(with $R^2$s of $0.88$ and $0.96$ 
for the $\delta$ values of $0.1$ and $0.001$
respectively).

However, good runtime performance for \descent would be
of limited value if it only found poor quality approximate equilibria. Fortunately, our
results show that this is not the case. In almost all experiments \descent found
high quality approximate equilibria. The variant with $\delta = 0.1$
typically found an $\epsilon$-NE with $\epsilon \le 0.05$, while
the variant with $\delta = 0.001$ typically found an $\epsilon$-NE
with $\epsilon \le 0.002$.

\begin{figure*}[htp]
\centering
\includegraphics[page=1,width=\textwidth]{plots/boxplots.pdf}
\caption{Box and whisker plots showing the approximation quality of the
	approximate equilibria found by \descent with $\delta = 0.001$. The results
	show that \descent almost always finds a high quality approximate
	equilibrium. It can be seen that on many classes of games, even the worst
	approximation quality over all test cases is very good.} 
	\label{fig:box}
\end{figure*}

Figure~\ref{fig:box} shows a box and whisker plot for the quality of approximate
equilibrium found by accurate \descent variant.  It can be seen
that even the worst performance of the algorithm is relatively good for several
classes of game. The overall worst approximate equilibrium was a $0.1065$-NE that was found on a
weighted cooperation game. While this is far larger than the average
performance, it is still much better than best-known theoretical upper bound of~$0.5$.


We now make more detailed observations about the specific classes of games that
we tested. For auctions, one interesting observation is that on certain classes
of auctions \lemke will often find a pure Nash equilibrium. This is shown in the
``\% Pure column'' of Table~\ref{tbl:auction}. This phenomenon is particularly
prevalent for second-price auctions, where in some cases we found that \lemke
always finds a pure, and in these cases it does so in a very small amount of
time.

%\begin{figure*}
%\centering
%\begin{subfigure}{.4\textwidth}
%\includegraphics[page=1,width=\linewidth]{plots/item_ties.pdf}
%\end{subfigure}
%\begin{subfigure}{.4\textwidth}
%\includegraphics[page=2,width=\linewidth]{plots/item_ties.pdf}
%\end{subfigure}
%\caption{Plots showing the performance on \lemke on item bidding auctions on first price, second
%price and all-pay payment methods, on the three different tie resolution methods.}
%\end{figure*}

We also found that the tie-breaking rule used
in the auction can have a huge impact on the time that \lemke takes to find an
exact equilibrium. Table~\ref{tbl:ties} shows the performance of the algorithm
on otherwise identical auctions with different tie-breaking rules. It can be
seen that resolving ties deterministically makes the game much easier to solve
than resolving ties randomly.

Finally, we discuss the results in Table~\ref{tbl:ls} for  \descent
with and without line search. It
can be seen that, without line search, the \descent algorithm with $\delta=0.001$ 
is often slower than \lemke, and that using line search greatly
speeds it up (and so in our other results we always used line search). 
Interestingly, the line-search variant of
the algorithm also finds better quality approximate equilibria;
it would be interesting to understand why.

%\paragraph{\textbf{Input complexity}}
%Throughout the experiments we used two natural ways to define the input size of 
%a game, with regards to \lemke algorithm. The first one is to use the size of 
%the corresponding LCP, while the second is to count the number of payoff entries 
%of the game. The definition of the input size it is crucial for the running time 
%of the algorithms, especially for \lemke.

%A general remark from our experiments is that if we take as input size the size 
%of the LCP, then the \lemke algorithm tends to perform really well on polymatrix 
%games represented by sparse graphs compared to polymatrix games on dense graphs 
%with the same set off players and actions per player.  Note that in both cases 
%the size of the LCP of these games is the same. However, if we use the total 
%number of payoff entries as the input size, then by increasing the number of 
%actions per player the size of the LCP drastically increases and makes \lemke 
%incapable of handling these games. For example, \lemke times out on most
%games with size greater than 20480 payoff entries. On the other hand, \descent algorithm is 
%really fast even for very large games, especially with $\delta = 0.1$, which was capable of solving
%instances with upto 32 million payoff entries in under 150 seconds, and it produces approximate 
%equilibria with good accuracy (worst case = 0.2037-NE, 0.0224-NE on avg). Despite timing out on
%some instances, using $\delta = 0.001$ was capable of producing a better approximation (worst case = 
%0.1065-NE, 0.0029-NE on avg). It should be noted that in all of our experiments the \descent computes \eps-NE 
%with $\eps < 0.1065-NE$ which is far away from the theoretical approximation which is far away from 
%the theoretical approximation guarantee of the algorithm.

%\paragraph{Auction}


%In the majority of the experiments on auction games, the \lemke algorithm was
%considerably faster than the \descent (with $\delta = 0.001$) when the line 
%search procedure it is not used. However, adding the line search to the 
%\descent algorithm increased significantly its efficiency, both in the running 
%time and the approximation guarantee. 


%More specifically, in all of the experiments, less than 0.001\% of instances
%timed out for \descent when line search was used. For that reason, in the rest 
%of the experiments, we always ran the \descent algorithm using the line search
%procedure. Furthermore, for the same reason, we do not include any information 
%on the timeout of \descent for the experiments on the auction setting.

%Due to disallowing overbidding in the auctions, it was difficult to control the exact sizes of the
%games being generated, which resulted in different sizes between the different valuation functions.
%Despite this we were still able to make some observations, which in general apply to the different
%settings which we used but we would be presenting the results on 3 types and 3 items. 

%In general, the setting where players have budget additive valuation functions 
%is harder than the one with additive additive valuation functions.
%Furthermore, for these two classes of valuation functions, the all pay payment
%rule tends to be harder than first price one which in turn is harder than 
%the second price. On the other hand, when bidders have unit demand or single 
%minded valuation functions, the difficulty over the payment rule varies.

%\begin{table*}[t]{
%\centering
%\input{tables/auc_table/joint.tex}
%\caption{Results for Bayesian combinatorial auctions with two bidders. FP stands 
%for first price payment rule, SP for second price and AP for all pay payment 
%rule. All the games have close to BLAH payoff entries.}
%}
%\end{table*}

%The choice of tie resolution had very little impact on the hardness of these 
%auctions on \descent, however on \lemke, it had a significant impact. When 
%\lemke was run, regardless of which player it is, favouring a single player 
%yielded similar results. For all valuation functions, given that the payment 
%mechanism is not the easiest to solve under that valuation function, we found 
%that breaking ties uniformly at random increased the difficulty of the game. 
%Games with the And-Or valuation setup were the exception to this observation, as 
%they seemed to be easier when the ties are broken at random in comparison to 
%being allocated to a predetermined player.

%In most of the instances, this difference in the tie resolution rule, leads to 
%the games having different equilibrium, with second price auctions being the 
%exception. On games with additive or And-Or valuations, the equilibrium remained 
%the same regardless of changes in the player being favoured, whereas in games 
%where the bidders have single minded or budget additive valuations, 56.6\% and 
%4.1\% respectively of solved instances had the same equilibrium when a single 
%player was favoured. With regards to resolution of ties uniformly at random, 
%under second price auctions with And-Or valuation, 43\% of the solved instances 
%had the same equilibria with predefined allocations. Also, for single minded and
%additive valuations under the second price payment rule, 16\% and 1\% of 
%instances respectively had similar valuations to predefined allocations. It 
%should also be noted, that in these cases, for all three tie resolution rules, 
%\lemke found the exact same equilibria.




%In the multiunit setting, we found that additive valuations were harder than submodular valuations
%only on the all-pay auction setting, which was the hardest payment mechanism for both valuation
%functions, with uniform price being the easiest. Unlike item-bidding, in this auction setting, the
%tie resolution didn't make much of a difference in the computation time or the approximation
%guarantee of the algorithms. The most noticable difference which it made was in the number of pure
%equilibria found by \lemke's algorithm. In all-pay auctions, regardless of the tie resolution, none
%of the equilibria found was a pure nash equilibrium. In uniform price auctions, all the
%equilibria found on instances with additive valuation had a pure nash equilibrium, and with
%submodular valuations, \lemke found a pure nash equilibrium in 89\% of instances when either
%favouring the first player or breaking uniformly at random, and 83\% of instances when favouring the
%second player. However, in discriminatory auctions, \lemke found a pure equilibrium in 30\% of
%instances when favouring a predetermined player, which increased to 67\% of instances when breaking
%ties uniformly at random.

%\begin{table*}[t]{
%\centering
%\input{tables/auc_joint.tex}
%\begin{tabular}{cccc}
%\input{tables/multi/games.tex} & \input{tables/multi/lemke.tex} &
%\input{tables/multi/ts1ls.tex} & \input{tables/multi/ts001ls.tex}
%\end{tabular}
%\caption{Showing results of multiunit auctions with 3 types and 3 items with discriminatory (D),
%uniform price (U) and all-pay (AP) auction formats with tie breaks resolved uniformly at random}
%}
%\end{table*}

%\paragraph{Blotto}

%With regards to Blotto and Adjusted Winner games, we performed our experiments 
%on games of size $[12800, 5.32 \times 10^6]$ payoff entries which is equivalent 
%to LCPs of size [166, 3268]. Despite the various parameters involved in both 
%games, we were unable to find a combination which proved to be harder for \lemke 
%to solve than the other. Ultimately, it is the size of the games which matters.
%We performed a regression using the number of payoff entries against the running 
%time, ignoring the instances which timed out. \lemke was found to run roughly 
%proportional to polynomial of degree 2 with an $r^2 = 0.75$, while \descent ran
%polynomial of degree $0.999$ with $r^2 = 0.88$ and $0.83$ with $r^2 = 0.96$ for 
%$\delta$ of $0.1$ and $0.001$ respectively.

%In comparison to Blotto games, Adjusted Winner games turned out to be a lot 
%easier. Due to the nature of the allocation rule, these games are zero-sum games, 
%with \lemke finding a pure Nash equilibrium in about 97\% of instances which were solved within the
%time limit. 


%\paragraph{Polymatrix}
%\todo[inline]{do we want to keep that?}
%For games which were of a non-Bayesian nature, we performed our experiments on complete, cycles,
%square grids and star graphs. We noticed that with the exception of games on star graphs, games on
%sparse graphs tend to be harder than games on dense graphs with approximately the same number of
%payoff entries. This is mainly due to the representation used by both algorithms which introduces
%zero entries whenever there is no edge between two players. Also, games which have a large number 
%of players with very few actions per player are considerably harder than games with few players 
%who have a lot of actions.

%\paragraph{Coordination Zerosum}

%For \lemke algorithm a determining factor for hard instances is the proportion 
%$p$ between coordination and zero-sum games.  Although the value of $p$ that 
%creates the hardest instances depends on the graph structure, we discovered a 
%common property. The function that maps $p$ to average runtime seems to be 
%single peaked. For games on sparse graphs, where we tried to match the size of 
%the LCPs to those of dense graphs, we noticed that for $p = 0.75$ the function 
%is maximized. However, increasing the
%size of the games so as to approximately match the number of payoff entries, we 
%noticed that the peak shifted to $p=1$.

%With regards to the performance of \descent on this class of games, there was 
%very little difference between the different instances of the game based on the 
%value of $p$. The most noticable difference occurred when all the games on the 
%graph were coordination games, which were easier to solve. Furthermore, \descent 
%computed \eps-Nash equilibria with better approximation guarantee, both on the 
%worst and average case, compared to other classes of games.  For complete graphs, 
%we were able to go up to games with 250 players and 5 actions per player 
%(approximately 1.6 million payoff entries) with an average running time of 551.3 
%seconds with the worst approximation found  being $1.7e^{-3}$, when run with 
%$\delta = 0.001$. When $25\%$ of the bimatrix games were coordination games, 
%then \descent with $\delta = 0.001$ timed out in $20\%$ of those instances which
%was the worst case for this class. 



%\paragraph{Group Zerosum}

%For this class we studied games played on complete graphs. Our main observation 
%is that the games get harder as the number of groups that the players form is 
%increasing. On \descent, there was very little difference between the different 
%number of partitions in the game. We were capable of running up to games with 
%250 players and five actions per player. For these games the average running 
%time was 538 seconds and timed out on about 12\% of instances when 
%$\delta = 0.001$. When $\delta = 0.1$ improved the runtime to an average of 52 
%seconds, however the approximation guarantee found worsened from an
%average of $1.076e^{-3}$-NE to an average of $1.398e^{-2}$.

%\begin{table*}{
%\centering
%\input{tables/gzero_joint.tex}
%\caption{Results for Group Zerosum games played on Complete graphs, where
%$p$ is the number of groups the players form in the game.}
%}
%\end{table*}


%\paragraph{Strictly Competitive}

%\begin{table*}{
%\centering
%\input{tables/strict_joint.tex}
%\caption{Results for strictly competitive games. The number of payoff entries 
%in each game are close to 20250.}
%}
%\end{table*}

%We studied games played on complete graphs with of up to 250 players and five 
%actions per player. For \descent algorithm $17\%$ of the instances timed out for 
%$\delta =0.001$ and in the worst case, \descent algorithm computed a 
%$1.729e^{-3}$-NE (over all timed out and non timed out instances). For games with 
%300 players and five actions per player 97\% of instances timed out, but despite 
%this, \descent still computed a $5.4e^{-3}$-NE in the worst case. This is better 
%than the $1.3e^{-2}$-Nash found on average by \descent in about 100 seconds when
%$\delta = 0.1$. 

%For $\delta = 0.001$, grid graphs provided the worst approximate Nash equilibrium,
%an 0.021-NE. However for $\delta = 0.1$, the worst instance was produced by cycle
%graphs and more specifically it was a 0.127-NE.  Star graphs were relatively 
%easy to solve, as someone could expect. Games with 400 players and five
%strategies per player solved on average within 1.6 seconds with an 
%approximation guarantee of $2.49e^{-3}$ in the worst case, for $\delta = 0.001$.

%\paragraph{Weighted Cooperation}

%This class of games seems to be the easiest over all underlying graph structures;
%\lemke algorithm always finds really fast a \emph{pure} Nash equilibrium. This
%allowed us to test \lemke on games with much larger size compared to games form
%other classes. The first setting involved 10 players with 105 colours per player,
%which yielded games of approximately 992000 payoff entries (equivalent to LCPs 
%of 1020 rows). The second setting involved 200 players with 5 colours per player, 
%which gave games with 995000 payoff entries (equivalent to LCPs of 1200 rows). 
%In both settings we created games where the total number of colours available
%were 2, 3, and 5 times the number of colours available to each player. 

%The setting with fewer colours per player increased in difficulty as the total 
%number of available colours increased. On complete graphs, when there were 10 
%available colours, the
%corresponding games were solved on average within 194.2 seconds and \lemke timed
%out on 8\% of the instances, while on instances with 25 available colours, the 
%average runtime was 552.6 seconds with \lemke timing out on 81\% of all tested 
%instances. In contrast, the setting with fewer players but more colours per 
%player, got easier as the number of available colours increased, with the hardest 
%having an average running time of $3.1$ seconds.

%With the exception of complete graphs and stars in the setting with a large 
%number of players, \lemke was able to out perform \descent with $\delta = 0.001$. 
%The greatest difference occurred in the setting of 200 players and 5 actions and 
%10 available colours, where \descent took on average 208 seconds to solve the 
%problem, where as \lemke was capable of solving these instances in 19.6 seconds 
%on average.

%With the exception of grid graphs, \descent tend to get harder to solve as the 
%number of available colours increase, however, the approximation found by 
%\descent got better. On grid graphs with 15 available colours seemed to be 
%the hardest set of instances to solve. For $\delta = 0.001$, we were able to 
%solve games with 5 actions per player, 350 players on complete graphs and cycles, 
%and $18 \times 18$ grid graphs. The hardest cases had 10 available colours for 
%complete graphs and cycles, and 15 available colours for grid graphs. \descent
%timed out on 50\%, 73\% and 62\% of these instances. The easiest case had 25 
%available colours for complete graphs and cycles, and 10 available colours for
%grid graphs and only 3\% of instances on cycles and 1\% of instances on grid 
%graphs timed out. With regards to the approximation guarantee, including 
%instances that timed out, in the worst case \descent computed $1.826e^{-3}$-NE, 
%$0.1065$-NE, and $0.0848$-NE for complete, cycle and grid graphs respectively.
%Note that the $0.1065$-NE is the worst case approximation guarantee we created.

%For the same games with $\delta = 0.1$, there is a significant reduction on 
%runtime with complete graphs being solved on average within 71 seconds, cycles 
%averaged around 0.22 seconds and grid graphs in about 1.096 seconds. This 
%reduction in runtime comes at the cost of an increase in the approximation 
%guarantee found not only in the worst case, but also the average case, with 
%cycles and grid graphs increasing to $0.1446$-NE and $0.149$-NE in the worst 
%case and $0.1429$-NE and $0.1385$-NE in the average case respectively. 
%%
%However, for stars, we get both a reduction in runtime as well as in the 
%approximation guarantee. On these graphs, as the number of players involved got 
%larger, the approximate Nash equilibria found increased, to the point where for 
%games having equal to 200 players or larger, (with 10 and 15 available colours) 
%or 600 players (with 25 available colours), \descent with $\delta = 0.1$ was 
%always able to find an exact Nash equilibrium.

%\begin{table*}{
%\centering
%\input{tables/weight_joint.tex}
%\caption{Results for weighted cooperation games with 5 colours per player, where $p$ is the 
%multiplier dictating the total number of colours available, i.e. if each player has $k$ 
%colours, then there are a total of $pk$ colours available. On Complete graphs, there were 200
%players (995000 payoff entries), Cycles had 350 players (17500 payoff entries), grids had
%dimensions $17 \times 17$ (27200 payoff entries) while trees had 500 players (24950 payoff entries)}
%}
%\end{table*}


\section{Conclusions}

In this paper we extensively studied the performance of two algorithms
for computing a sample equilibria of polymatrix games.
Both algorithms produce
good results for most of the test instances, even though many were drawn from
theoretically hard classes. More specifically, we saw that
combinatorial auctions with two bidders are relatively easy to solve. This
raises the natural question whether we can derive efficient algorithms for
auctions with two, or a constant number of players. Furthermore, we saw that 
tie resolution significantly affects the difficulty of the auctions (see~\cite{CP14} 
for a discussion of this issue in a theoretical context).

In all of our experiments \descent produced \eps-NE far better than the
(best-known) 0.5 theoretical worst-case guarantee, which is not known to be tight.  
So it would be interesting to understand if
this good performance is due to the nature of the games we studied or if there is a better
theoretical analysis. 
%
In~\cite{FIS15}, a genetic algorithm was used to construct a bimatrix 
game for which 
the Tsaknakis and Spirakis (TS) algorithm computes an 0.3393-NE, which shows the 
analysis of the TS algorithm is essentially tight.  
Since bimatrix games are a
special case of polymatrix games, this gives a lower bound of 0.03393 for the 
best-possible approximation guarantee for \descent in polymatrix games. 
Can a better lower bound, closer to the 0.5 upper bound, be found? We believe that it
should be easier to construct a bad game for the \descent algorithm compared to
the TS algorithm,  because \descent computes a single strategy profile,
whereas TS computes three profiles (one by descent, and then two further
profiles are derived from that one) and then chooses the best one.

\smallskip

\noindent \textbf{Acknowledgements.} The last author is supported by EPSRC grant EP/L011018/1.

% For AAMAS-2016, as references are unlimited but appendices must fit within
% 8 pages, the References section must come after the appendices (if any)
%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
\clearpage
%\bibliographystyle{abbrv}
%\bibliography{references}  % sigproc.bib is the name of the Bibliography in this case

\begin{thebibliography}{10}

\bibitem{AM09}
T.~Adamo and A.~Matros.
\newblock A {B}lotto game with incomplete information.
\newblock {\em Economics Letters}, 105(1):100 -- 102, 2009.

\bibitem{AHLMS16}
A.~Ahmadi, M.~Hajiaghayi, B.~Lucier, H.~Mahini, and S.~Seddighin.
\newblock From duels to battlefields: Computing equilibria of {B}lotto and
  other games.
\newblock In {\em Proc.\ of AAAI}, 2016.

\bibitem{ARSS15}
K.~R. Apt, M.~Rahn, G.~Sch{\"{a}}fer, and S.~Simon.
\newblock Coordination games on graphs.
\newblock {\em CoRR}, abs/1501.07388, 2015.

\bibitem{ABH}
C.~Audet, S.~Belhaiza, and P.~Hansen.
\newblock Enumeration of all the extreme equilibria in game theory: Bimatrix
  and polymatrix games.
\newblock {\em Journal of Optimization Theory and Applications},
  129(3):349--372, 2006.

\bibitem{ARSvS}
D.~Avis, G.~Rosenberg, R.~Savani, and B.~von Stengel.
\newblock Enumeration of {N}ash equilibria for two-player games.
\newblock {\em Economic Theory}, 42(1):9--37, 2010.

\bibitem{BLP15}
S.~Barman, K.~Ligett, and G.~Piliouras.
\newblock Approximating nash equilibria in tree polymatrix games.
\newblock In {\em Proc.\ of SAGT}, pages 285--296, 2015.

\bibitem{BL04}
N.~A.~R. Bhat and K.~Leyton{-}Brown.
\newblock Computing {N}ash equilibria of action-graph games.
\newblock In {\em Proc.\ of {UAI}}, pages 35--42, 2004.

\bibitem{BR11}
K.~Bhawalkar and T.~Roughgarden.
\newblock Welfare guarantees for combinatorial auctions with item bidding.
\newblock In {\em Proc.\ of SODA}, pages 700--709, 2011.

\bibitem{BBM10}
H.~Bosse, J.~Byrka, and E.~Markakis.
\newblock New algorithms for approximate {N}ash equilibria in bimatrix games.
\newblock {\em Theoretical Computer Science}, 411(1):164--173, 2010.

\bibitem{AW}
S.~J. Brams.
\newblock Fair division.
\newblock In {\em Computational Complexity}, pages 1073--1080. Springer, 2012.

\bibitem{BGR08}
P.~Briest, P.~W. Goldberg, and H.~R{\"{o}}glin.
\newblock Approximate equilibria in games with few players.
\newblock {\em CoRR}, abs/0804.4524, 2008.

\bibitem{CD11}
Y.~Cai and C.~Daskalakis.
\newblock On minmax theorems for multiplayer games.
\newblock In {\em Proc.\ of SODA}, pages 217--234, 2011.

\bibitem{CP14}
Y.~Cai and C.~H. Papadimitriou.
\newblock Simultaneous bayesian auctions and computational complexity.
\newblock In {\em Proc.\ of {EC}}, pages 895--910, 2014.

\bibitem{CDT}
X.~Chen, X.~Deng, and S.-H. Teng.
\newblock Settling the complexity of computing two-player {N}ash equilibria.
\newblock {\em Journal of the ACM}, 56(3):14:1--14:57, 2009.

\bibitem{CPY13}
X.~Chen, D.~Paparas, and M.~Yannakakis.
\newblock The complexity of non-monotone markets.
\newblock In {\em Proc.\ of {STOC}}, pages 181--190, 2013.

\bibitem{CKS08}
G.~Christodoulou, A.~Kov{\'{a}}cs, and M.~Schapira.
\newblock Bayesian combinatorial auctions.
\newblock In {\em Proc.\ of {ICALP}}, pages 820--832, 2008.

\bibitem{DGP}
C.~Daskalakis, P.~W. Goldberg, and C.~H. Papadimitriou.
\newblock The complexity of computing a {N}ash equilibrium.
\newblock {\em SIAM Journal on Computing}, 39(1):195--259, 2009.

\bibitem{DMP}
C.~Daskalakis, A.~Mehta, and C.~H. Papadimitriou.
\newblock A note on approximate {N}ash equilibria.
\newblock {\em Theoretical Computer Science}, 410(17):1581--1588, 2009.

\bibitem{DP11}
C.~Daskalakis and C.~H. Papadimitriou.
\newblock Continuous local search.
\newblock In {\em Proc.\ of {SODA}}, pages 790--804, 2011.

\bibitem{DSVV09}
C.~Daskalakis, G.~Schoenebeck, G.~Valiant, and P.~Valiant.
\newblock On the complexity of {N}ash equilibria of action-graph games.
\newblock In {\em Proc.\ of {SODA}}, pages 710--719, 2009.

\bibitem{DFIS16}
A.~{Deligkas}, J.~{Fearnley}, T.~P. {Igwe}, and R.~{Savani}.
\newblock {An Empirical Study on Computing Equilibria in Polymatrix Games}.
\newblock {\em CoRR}, abs/1602.06865, 2016.

\bibitem{DFSS}
A.~Deligkas, J.~Fearnley, R.~Savani, and P.~Spirakis.
\newblock Computing approximate {N}ash equilibria in polymatrix games.
\newblock {\em Algorithmica}, pages 1--28, 2015.

\bibitem{DFK}
S.~Dobzinski, H.~Fu, and R.~D. Kleinberg.
\newblock On the complexity of computing an equilibrium in combinatorial
  auctions.
\newblock In {\em Proc.\ of {SODA}}, pages 110--122, 2015.

\bibitem{EY10}
K.~Etessami and M.~Yannakakis.
\newblock On the complexity of {N}ash equilibria and other fixed points.
\newblock {\em SIAM J. Comput.}, 39(6):2531--2597, 2010.

\bibitem{FIS15}
J.~Fearnley, T.~P. Igwe, and R.~Savani.
\newblock An empirical study of finding approximate equilibria in bimatrix
  games.
\newblock In {\em Proc.\ of {SEA}}, pages 339--351, 2015.

\bibitem{FT-C10}
U.~Feige and I.~Talgam{-}Cohen.
\newblock A direct reduction from \emph{k}-player to 2-player approximate
  {N}ash equilibrium.
\newblock In {\em Proc.\ of {SAGT}}, pages 138--149, 2010.

\bibitem{FHGL}
M.~Feldman, H.~Fu, N.~Gravin, and B.~Lucier.
\newblock Simultaneous auctions are (almost) efficient.
\newblock In {\em Proc.\ of {STOC}}, pages 201--210, 2013.

\bibitem{GW04}
S.~Govindan and R.~Wilson.
\newblock Computing {N}ash equilibria by iterated polymatrix approximation.
\newblock {\em Journal of Economic Dynamics and Control}, 28(7):1229--1241,
  2004.

\bibitem{GW10}
S.~Govindan and R.~Wilson.
\newblock A decomposition algorithm for n-player games.
\newblock {\em Economic Theory}, 42(1):97--117, 2010.

\bibitem{HRS08}
S.~H{\'{e}}mon and M.~Santha.
\newblock Approximate {N}ash equilibria for multi-player games.
\newblock In {\em Proc.\ of {SAGT}}, pages 267--278, 2008.

\bibitem{HR74}
J.~Howson, Joseph~T. and R.~W. Rosenthal.
\newblock {B}ayesian equilibria of finite two-person games with incomplete
  information.
\newblock {\em Management Science}, 21(3):pp. 313--315, 1974.

\bibitem{JLB11}
A.~X. Jiang, K.~Leyton{-}Brown, and N.~A.~R. Bhat.
\newblock Action-graph games.
\newblock {\em Games and Economic Behavior}, 71(1):141--173, 2011.

\bibitem{KR11}
D.~Kovenock and B.~Roberson.
\newblock A {B}lotto game with multi-dimensional incomplete information.
\newblock {\em Economics Letters}, 113(3):273 -- 275, 2011.

\bibitem{lemke65}
C.~E. Lemke.
\newblock Bimatrix equilibrium points and mathematical programming.
\newblock {\em Management Science}, 11(7):pp. 681--689, 1965.

\bibitem{lemke64}
C.~E. Lemke and J.~Howson, J.~T.
\newblock Equilibrium points of bimatrix games.
\newblock {\em Journal of the Society for Industrial and Applied Mathematics},
  12(2):pp. 413--423, 1964.

\bibitem{miller91}
D.~A. Miller and S.~W. Zucker.
\newblock Copositive-plus lemke algorithm solves polymatrix games.
\newblock {\em Operations Research Letters}, 10(5):285 -- 290, 1991.

\bibitem{N}
J.~Nash.
\newblock Non-cooperative games.
\newblock {\em The Annals of Mathematics}, 54(2):286--295, 1951.

\bibitem{GAMUT}
E.~Nudelman, J.~Wortman, Y.~Shoham, and K.~Leyton-Brown.
\newblock Run the gamut: A comprehensive approach to evaluating game-theoretic
  algorithms.
\newblock In {\em Proc.\ of {AAMAS}}, pages 880--887, 2004.

\bibitem{PTW14}
G.~Polevoy, S.~Trajanovski, and M.~de~Weerdt.
\newblock {N}ash equilibria in shared effort games.
\newblock In {\em Proc.\ of {AAMAS}}, pages 861--868, 2014.

\bibitem{PNS}
R.~Porter, E.~Nudelman, and Y.~Shoham.
\newblock Simple search methods for finding a {N}ash equilibrium.
\newblock In {\em Proc.\ of {AAAI}}, pages 664--669, 2004.

\bibitem{R12}
T.~Roughgarden.
\newblock The price of anarchy in games of incomplete information.
\newblock In {\em Proc.\ of {EC}}, pages 862--879, 2012.

\bibitem{Rub15}
A.~Rubinstein.
\newblock Inapproximability of {N}ash equilibrium.
\newblock In {\em Proc.\ of {STOC}}, pages 409--418, 2015.

\bibitem{SGC05}
T.~Sandholm, A.~Gilpin, and V.~Conitzer.
\newblock Mixed-integer programming methods for finding {N}ash equilibria.
\newblock In {\em Proc.\ of {AAAI}}, pages 495--501, 2005.

\vfill\eject

\bibitem{SL08}
Y.~Shoham and K.~Leyton-Brown.
\newblock Protocols for multiagent resource allocation: Auctions.
\newblock In {\em Multiagent Systems}, pages 315--366. Cambridge University
  Press, 2008.
\newblock Cambridge Books Online.

\bibitem{TS}
H.~Tsaknakis and P.~G. Spirakis.
\newblock An optimization approach for approximate {N}ash equilibria.
\newblock {\em Internet Mathematics}, 5(4):365--382, 2008.

\bibitem{TSK08}
H.~Tsaknakis, P.~G. Spirakis, and D.~Kanoulas.
\newblock Performance evaluation of a descent algorithm for bi-matrix games.
\newblock In {\em Proc.\ of {WINE}}, pages 222--230, 2008.

\end{thebibliography}




\newpage
\appendix
\section{Line Search}
\label{app:linesearch}

%This procedure is
%done by representing the $\epsilon$-NE of the new point in the \descent method
%$x + \alpha(x' - x)$ as a piecewise function in terms of $\alpha$, which is then
%evaluated for different values of $\alpha \in (0, 1]$, with the aim of finding
%an $\alpha$ which minimizes the $\epsilon$-NE. Prior to performing the search,
%$\alpha = \frac{\delta}{\delta + 2}$ which has been proven to get a new point
%with a better approximation value than $x$, the current point. 

As noted in the main text, the line search procedure for \descent greatly
affects the running time of the running time of the algorithm. In this section,
we give some results that describe this impact.

Recall that the line search procedure selects a number of equally spaced points
for $\alpha$ between $0$ and $1$, and the key decision is how many points to
check. In order to study the effects of the number of points on line search has
on the algorithm, we took the average over 100 random instances on
Coordination/Zero-sum games on cycles and grids as well as Weighted Zero-sum
games on Cycles.

Figure~\ref{fig:linesearch} shows the results. The red lines show how the
overall running time of the algorithm varies depending on the number of point
checked in each iteration, while the green lines show how the number of
iterations change. As one might expect, the number of iterations tends to
decrease as we increase the number of points checked in each iteration. In other
words, checking more points increases the amount of progress that each iteration
makes. However, checking more points in each iteration also adds more
computational cost, and eventually the overall running time begins to rise,
which indicates that the cost of checking more points is too high relative to
the extra progress that is made.

%, the number of points on the line
%search affects the performance of the algorithm. Larger search spaces tend to
%result in a reduction in the number of iterations, however there is a trade-off
%as this gets more expensive to perform the search and this ends up slowing down
%the algorithm. This point tends to differ based on the size of the game, with
%more points needed for larger games.

\begin{figure*}[th]
\centering
\begin{tabular}{cc}
\includegraphics[page=1,width=.4\linewidth]{plots/descent_iter.pdf} &

\includegraphics[page=3,width=.4\linewidth]{plots/descent_iter.pdf}\\

\includegraphics[page=5,width=.4\linewidth]{plots/descent_iter.pdf} &

\includegraphics[page=7,width=.4\linewidth]{plots/descent_iter.pdf}\\
\end{tabular}
\caption{Plots showing the effect of varying the number of points used in line search on the number of
iterations and computation time of \descent.}
\label{fig:linesearch}
\end{figure*}

\section{Game size: Players vs Actions}
\label{app:playersvactions}

The size of a polymatrix game increases with more players and with more actions.
In general, we found that the number of players had a much greater effect on the
running time of the algorithms that the number of actions. Table~\ref{tab:playersactiontradeoff} 
illustrates this point.

\begin{table*}[htp]{
\centering
\input{tables/joint_pva.tex}
\caption{Table showing Weighted Cooperation games on Complete graphs relatively 
close in size, comparing the case of a large number of players and few actions 
with the case of a few players with larger action sets. $\% T$ is the proportion of the timed 
out instances.}
\label{tab:playersactiontradeoff}
}
\end{table*}
%
% ACM needs 'a single self-contained file'!
%\balancecolumns % GM June 2007
% That's all folks!
\end{document}

large.tex

\begin{tabular}{|c|c|c|c|c||c|c||c|c||c|c|c|}
\multicolumn{5}{|c||}{Games} & \multicolumn{2}{c||}{\lemke} & \multicolumn{2}{c||}{\descent 0.1 LS} &
\multicolumn{3}{c|}{\descent 0.001 LS} \\\hline
Game & Graph & \# Payoff & LCP & $p$ & Time & \% T & Time & \eps & Time & \eps & \% T\\
\hhline{|~|=|=|=|=||=|=||=|=||=|=|=|}
\multirow{20}{*}{\rotatebox[origin=c]{90}{Coord-Zero}}& \multirow{5}{*}{Complete} &
\multirow{5}{*}{26010} & \multirow{5}{*}{32400} & 0 & 1.270 & 0.0 & 0.034 & 2.103e-02 & 0.760 & 9.951e-04 & 0.0 \\\cline{5-12}
 & & & & 0.25 & 63.407 & 4.0 & 0.033 & 2.115e-02 & 0.748 & 1.026e-03 & 0.0 \\\cline{5-12}
 & & & & 0.5 & 337.443 & 45.0 & 0.034 & 1.859e-02 & 0.750 & 1.070e-03 & 0.0 \\\cline{5-12}
 & & & & 0.75 & 522.207 & 74.0 & 0.033 & 1.604e-02 & 0.725 & 1.076e-03 & 0.0 \\\cline{5-12}
 & & & & 1 & 116.354 & 0.0 & 0.034 & 4.844e-03 & 0.598 & 5.087e-04 & 0.0 \\
\hhline{|~|=|=|=|=||=|=||=|=||=|=|=|}
 & \multirow{5}{*}{Cycle} & \multirow{5}{*}{25920} & \multirow{5}{*}{136900} & 0 & 18.430 & 2.0 & 0.103 & 3.352e-02 & 3.612 & 1.093e-03 & 0.0 \\\cline{5-12}
 & & & & 0.25 & 184.451 & 21.0 & 0.103 & 3.157e-02 & 3.534 & 1.167e-03 & 0.0 \\\cline{5-12}
 & & & & 0.5 & 412.947 & 55.0 & 0.105 & 2.859e-02 & 3.430 & 1.136e-03 & 0.0 \\\cline{5-12}
 & & & & 0.75 & 593.414 & 96.0 & 0.103 & 2.626e-02 & 3.206 & 1.121e-03 & 0.0 \\\cline{5-12}
 & & & & 1 & 600.097 & 100.0 & 0.107 & 1.906e-02 & 2.712 & 6.557e-04 & 0.0 \\
\hhline{|~|=|=|=|=||=|=||=|=||=|=|=|}
 & \multirow{5}{*}{Grid} & \multirow{5}{*}{26136} & \multirow{5}{*}{93636} & 0 & 35.447 & 3.0 & 0.072 & 3.143e-02 & 2.257 & 1.023e-03 & 0.0 \\\cline{5-12}
 & & & & 0.25 & 260.455 & 35.0 & 0.069 & 3.239e-02 & 2.233 & 1.137e-03 & 0.0 \\\cline{5-12}
 & & & & 0.5 & 451.699 & 61.0 & 0.072 & 2.955e-02 & 2.254 & 1.170e-03 & 0.0 \\\cline{5-12}
 & & & & 0.75 & 552.286 & 82.0 & 0.072 & 2.786e-02 & 2.106 & 1.186e-03 & 0.0 \\\cline{5-12}
 & & & & 1 & 599.349 & 99.0 & 0.070 & 2.159e-02 & 1.802 & 6.489e-04 & 0.0 \\
\hhline{|~|=|=|=|=||=|=||=|=||=|=|=|}
 & \multirow{5}{*}{Tree} & \multirow{5}{*}{25992} & \multirow{5}{*}{152100} & 0 & 0.276 & 0.0 & 0.060 & 1.012e-02 & 0.818 & 1.175e-03 & 0.0 \\\cline{5-12}
 & & & & 0.25 & 0.542 & 0.0 & 0.062 & 1.997e-02 & 0.806 & 1.220e-03 & 0.0 \\\cline{5-12}
 & & & & 0.5 & 73.443 & 5.0 & 0.062 & 2.139e-02 & 0.814 & 1.246e-03 & 0.0 \\\cline{5-12}
 & & & & 0.75 & 165.418 & 4.0 & 0.061 & 2.150e-02 & 0.796 & 1.084e-03 & 0.0 \\\cline{5-12}
 & & & & 1 & 162.420 & 0.0 & 0.063 & 1.469e-03 & 0.778 & 7.686e-04 & 0.0 \\
\hhline{|=|=|=|=|=||=|=||=|=||=|=|=|}

 \multirow{9}{*}{\rotatebox[origin=c]{90}{Group Zero}}& \multirow{9}{*}{Complete} &
\multirow{3}{*}{20250} & \multirow{3}{*}{25600} & 2 & 368.032 & 36.0 & 0.025 & 1.976e-02 & 0.564 & 1.093e-03 & 0.0 \\\cline{5-12}
 & & & & 3 & 495.919 & 66.0 & 0.025 & 1.762e-02 & 0.550 & 1.129e-03 & 0.0 \\\cline{5-12}
 & & & & 5 & 435.207 & 29.0 & 0.025 & 1.308e-02 & 0.525 & 9.926e-04 & 0.0 \\\cline{3-12}
 & & \multirow{3}{*}{26010} & \multirow{3}{*}{32400} & 2 & 438.650 & 59.0 & 0.034 & 1.855e-02 & 0.760 & 1.068e-03 & 0.0 \\\cline{5-12}
 & & & & 3 & 576.439 & 91.0 & 0.034 & 1.583e-02 & 0.731 & 1.120e-03 & 0.0 \\\cline{5-12}
 & & & & 5 & 582.924 & 88.0 & 0.033 & 1.186e-02 & 0.677 & 9.738e-04 & 0.0 \\\cline{3-12}
 & & \multirow{3}{*}{36000} & \multirow{3}{*}{44100} & 2 & 545.997 & 84.0 & 0.052 & 1.564e-02 & 1.073 & 1.049e-03 & 0.0 \\\cline{5-12}
 & & & & 3 & 598.616 & 99.0 & 0.051 & 1.396e-02 & 1.037 & 1.110e-03 & 0.0 \\\cline{5-12}
 & & & & 5 & 600.088 & 100.0 & 0.051 & 1.101e-02 & 0.969 & 9.721e-04 & 0.0 \\
\hhline{|=|=|=|=|=||=|=||=|=||=|=|=|}

\multirow{4}{*}{\rotatebox[origin=c]{90}{Strict}}& Complete & 20250 & 25600& 5 & 356.009 & 17.0 & 0.024 & 1.878e-02 & 0.552 & 1.054e-03 & 0.0 \\\cline{2-12}
 & Cycle & 20480 & 108900 & 5 & 580.891 & 85.0 & 0.087 & 1.729e-02 & 2.102 & 1.068e-03 & 0.0 \\\cline{2-12}
 & Grid & 20184 & 72900 & 5 & 551.795 & 77.0 & 0.066 & 1.612e-02 & 1.428 & 1.108e-03 & 0.0 \\\cline{2-12}
 & Tree & 20808 & 122500 & 5 & 79.560 & 0.0 & 0.048 & 2.571e-03 & 0.664 & 8.111e-04 & 0.0 \\
\hhline{|=|=|=|=|=||=|=||=|=||=|=|=|}

 \multirow{12}{*}{\rotatebox[origin=c]{90}{Weighted Cooperation}}& \multirow{3}{*}{Complete} &
\multirow{3}{*}{995000} & \multirow{3}{*}{1440000} & 2 & 194.233 & 8.0 & 8.455 & 1.446e-02 & 86.116 & 9.603e-04 & 0.0 \\\cline{5-12}
 & & & & 3 & 410.118 & 38.0 & 6.551 & 1.909e-02 & 73.485 & 1.047e-03 & 0.0 \\\cline{5-12}
 & & & & 5 & 552.583 & 81.0 & 4.957 & 2.585e-02 & 64.676 & 1.130e-03 & 0.0 \\
\hhline{|~|=|=|=|=||=|=||=|=||=|=|=|}
 & \multirow{3}{*}{Cycle} & \multirow{3}{*}{17500} & \multirow{3}{*}{4410000} & 2 & 103.403 & 0.0 & 0.227 & 1.334e-01 & 577.984 & 3.094e-02 & 73.0 \\\cline{5-12}
 & & & & 3 & 90.062 & 0.0 & 0.172 & 1.412e-01 & 529.581 & 4.199e-02 & 48.0 \\\cline{5-12}
 & & & & 5 & 78.883 & 0.0 & 0.156 & 1.427e-01 & 438.707 & 3.950e-02 & 28.0 \\
\hhline{|~|=|=|=|=||=|=||=|=||=|=|=|}
 & \multirow{3}{*}{Grid} & \multirow{3}{*}{27200} & \multirow{3}{*}{3006756} & 2 & 116.157 & 0.0 & 0.864 & 8.298e-02 & 275.839 & 5.461e-03 & 1.0 \\\cline{5-12}
 & & & & 3 & 81.933 & 0.0 & 0.464 & 1.110e-01 & 480.608 & 1.368e-02 & 15.0 \\\cline{5-12}
 & & & & 5 & 58.054 & 0.0 & 0.131 & 1.384e-01 & 358.662 & 3.028e-02 & 2.0 \\
\hhline{|~|=|=|=|=||=|=||=|=||=|=|=|}
 & \multirow{3}{*}{Tree} & \multirow{3}{*}{24950} & \multirow{3}{*}{9000000} & 2 & 240.215 & 0.0 & 0.750 & 0.000e+00 & 2.768 & 3.253e-04 & 0.0 \\\cline{5-12}
 & & & & 3 & 220.510 & 0.0 & 0.709 & 0.000e+00 & 2.533 & 1.194e-04 & 0.0 \\\cline{5-12}
 & & & & 5 & 204.919 & 0.0 & 0.653 & 0.000e+00 & 2.345 & 8.947e-05 & 0.0 \\\hline\end{tabular}

games_gzero.tex

\begin{tabular}{|l|c|c|}
\multicolumn{2}{c}{Games}\\\hline
\# Payoff& p \\\hline
20250.0 & 2\\\hline
20250.0 & 3\\\hline
20250.0 & 5\\\hhline{|=|=|}
26010.0 & 2\\\hline
26010.0 & 3\\\hline
26010.0 & 5\\\hhline{|=|=|}
36000.0 & 2\\\hline
36000.0 & 3\\\hline
36000.0 & 5\\\hline
\end{tabular}

ts1ls_strict.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.1}\\\hline

Time & Avg Eps\\\hline
0.024 & 1.878e-02\\
\hhline{|=|=|}
0.088 & 1.729e-02\\
\hhline{|=|=|}
0.066 & 1.612e-02\\
\hhline{|=|=|}
0.047 & 2.571e-03\\
\hhline{|=|=|}
\end{tabular}

lemke_coord.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Lemke}\\\hline
Time & \% Timeout \\\hline
1.270 & 0.0\\\hline
63.407 & 4.0\\\hline
337.443 & 45.0\\\hline
522.207 & 74.0\\\hline
116.354 & 0.0\\\hhline{|=|=|}
18.430 & 2.0\\\hline
184.451 & 21.0\\\hline
412.947 & 55.0\\\hline
593.414 & 96.0\\\hline
600.097 & 100.0\\\hhline{|=|=|}
35.447 & 3.0\\\hline
260.455 & 35.0\\\hline
451.699 & 61.0\\\hline
552.286 & 82.0\\\hline
599.349 & 99.0\\\hhline{|=|=|}
0.276 & 0.0\\\hline
0.542 & 0.0\\\hline
73.443 & 5.0\\\hline
165.418 & 4.0\\\hline
162.420 & 0.0\\\hline
\end{tabular}

tables.tex
\documentclass{article}
\usepackage{geometry}
 \geometry{
 a4paper,
 total={170mm,257mm},
 left=20mm,
 top=20mm,
 }
\pdfpagewidth=8.5truein
\pdfpageheight=11truein

\usepackage{amsmath}
\usepackage{amsfonts}
%\usepackage{amsthm}
\usepackage{verbatim}
\usepackage{bbm}
\usepackage{hhline}

\usepackage{pdflscape}

\begin{document}
\begin{table}{
\begin{tabular}{cccc}
\input{games_coord.tex} & \input{lemke_coord.tex} & \input{ts1ls_coord.tex} & \input{ts001ls_coord.tex}
\end{tabular}
\caption{Shows the results of Coordination-Zero sum games which were performed on Complete, Cycles,
Grids and Tree graphs, where $p$ is the proportion of edges which were Cooperation games. These
results are for games which were constructed to have close to 26000 payoff entries.}
}
\end{table}

\begin{table}{
\begin{tabular}{cccc}
\input{games_gzero.tex} & \input{lemke_gzero.tex} & \input{ts1ls_gzero.tex} & \input{ts001ls_gzero.tex}
\end{tabular}
\caption{Shows the results of experiments carried on Group Zero sum games on Complete graphs, where
the first column shows the number of payoff entries, and $p$ represents the number of groups in the
game.}
}
\end{table}

\begin{table}{
\begin{tabular}{cccc}
\input{games_strict.tex} & \input{lemke_strict.tex} & \input{ts1ls_strict.tex} & \input{ts001ls_strict.tex}
\end{tabular}
\caption{Shows the results of strictly competitive games constructed such that the number of payoff
entries are close to 20250.}
}
\end{table}

\begin{table}{
\begin{tabular}{cccc}
\input{games_weight.tex} & \input{lemke_weight.tex} & \input{ts1ls_weight.tex} & \input{ts001ls_weight.tex}
\end{tabular}
\caption{Shows the results of Weighted cooperation games where $p$ is the multiplier dictating the
total number of colours available (i.e. if each player has $k$ colours, then there are a total of
$pk$ colours).}
}
\end{table}
\end{document}

lemke_gzero.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Lemke}\\\hline
Time & \% Timeout \\\hline
368.032 & 36.0\\\hline
495.919 & 66.0\\\hline
435.207 & 29.0\\\hhline{|=|=|}
438.650 & 59.0\\\hline
576.439 & 91.0\\\hline
582.924 & 88.0\\\hhline{|=|=|}
545.997 & 84.0\\\hline
598.616 & 99.0\\\hline
600.088 & 100.0\\\hline
\end{tabular}

tables.tex
\documentclass{article}
\usepackage{rotating}
\usepackage{hhline}
\usepackage[a3paper, top=1cm, bottom=1cm, left=1cm, right=1cm]{geometry}

\begin{document}
\begin{table}{
\begin{tabular}{cccc}
\input{games.tex} & \input{lemke.tex} & \input{ts1ls.tex} & \input{ts001ls.tex}
\end{tabular}
}
\end{table}
\end{document}

ts001.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent 0.001}\\\hline

Time & Iterations & Eps & \% Timeout \\\hline
0.519 & 2.0 & 1.396e-02 & 0.0\\\hline
0.565 & 1.3 & 1.578e-02 & 0.0\\\hline
0.600 & 1.4 & 5.963e-03 & 0.0\\\hline
0.391 & 2.0 & 1.350e-02 & 0.0\\\hline
0.407 & 1.3 & 2.462e-02 & 0.0\\\hline
0.451 & 2.0 & 1.129e-02 & 0.0\\\hline
\end{tabular}

games.tex

\begin{tabular}{|l|c|c|}
\multicolumn{3}{c}{Games}\\\hline
Valuation & Auc & Avg. Size\\\hline
Additive & D & \multirow{3}{*}{836465}\\\hline
Additive & U & \\\hline
Additive & AP & \\\hline
SubModular & D & \multirow{3}{*}{878491}\\\hline
SubModular & U & \\\hline
SubModular & AP & \\\hline
\end{tabular}

ts001ls.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.001}\\\hline

Time & Eps \\\hline
1.338 & 1.513e-03\\\hline
1.486 & 4.055e-04\\\hline
1.589 & 2.328e-04\\\hline
1.442 & 6.161e-04\\\hline
1.483 & 8.924e-04\\\hline
1.677 & 2.536e-04\\\hline
\end{tabular}

ts1ls.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent 0.1}\\\hline

Time & Eps \\\hline
0.319 & 1.807e-02\\\hline
0.345 & 1.700e-02\\\hline
0.468 & 3.456e-03\\\hline
0.272 & 1.442e-02\\\hline
0.282 & 2.471e-02\\\hline
0.321 & 1.094e-02\\\hline
\end{tabular}

lemke.tex

\begin{tabular}{|c|c|c|}
\multicolumn{3}{c}{Lemke}\\\hline

Time & \% Timeout & \% Pure \\\hline
6.255 & 0.0 & 67.0 \\\hline
0.958 & 0.0 & 100.0 \\\hline
473.103 & 53.0 & 0.0 \\\hline
21.172 & 0.0 & 18.0 \\\hline
6.402 & 0.0 & 89.0 \\\hline
220.444 & 18.0 & 0.0 \\\hline
\end{tabular}

joint.tex

\begin{tabular}{|l|c|c|c||c|c||c|c||c|c|}
\multicolumn{4}{|c||}{Games} & \multicolumn{2}{c||}{\lemke} & \multicolumn{2}{c||}{\descent 0.1 LS} &
\multicolumn{2}{c|}{\descent 0.001 LS} \\\hline
Valuation & Auc & Avg. Size & Time & \% Timeout & Time & Eps & Time & Eps \\
\hhline{|=|=|=||=|=||=|=||=|=|}
Additive & D & 3 & 3 & 9.504 & 0.0 & 30.0 & 0.295 & 1.452e-02 & 1.481 & 4.411e-04\\\hline
Additive & U & 3 & 3 & 0.954 & 0.0 & 100.0 & 0.380 & 1.321e-02 & 1.870 & 3.579e-04\\\hline
Additive & AP & 3 & 3 & 512.564 & 64.0 & 0.0 &  0.417 & 4.080e-03 & 2.182 & 3.170e-04\\\hhline{|=|=|=||=|=||=|=||=|=|}
SubModular & D & 3 & 3 & 29.054 & 0.0 & 5.0 & 0.270 & 1.326e-02 & 1.954 & 3.209e-04\\\hline
SubModular & U & 3 & 3 & 5.818 & 0.0 & 83.0 & 0.272 & 2.636e-02 & 1.741 & 8.645e-04\\\hline
SubModular & AP & 3 & 3 & 210.290 & 12.0 & 0.0 & 0.323 & 1.115e-02 & 2.192 & 3.273e-04\\\hline\end{tabular}

weight_joint.tex

\begin{tabular}{|c|c||c|c||c|c||c|c|c|}
\multicolumn{2}{|c||}{Games} & \multicolumn{2}{c||}{\lemke} & \multicolumn{2}{c||}{\descent 0.1 LS} &
\multicolumn{3}{c|}{\descent 0.001 LS} \\\hline
Graph & $p$ & Time & \% Timeout & Time & Eps & Time & Eps & \% Timeout \\
\hhline{|=|=||=|=||=|=||=|=|=|}
Complete & 2 & 194.233 & 8.0 & 8.455 & 1.446e-02 & 86.116 & 9.603e-04 & 0.0 \\\hline
Complete & 3 & 410.118 & 38.0 & 6.551 & 1.909e-02 & 73.485 & 1.047e-03 & 0.0 \\\hline
Complete & 5 & 552.583 & 81.0 & 4.957 & 2.585e-02 & 64.676 & 1.130e-03 & 0.0
\\\hhline{|=|=||=|=||=|=||=|=|=|}
Cycle & 2 & 103.403 & 0.0 & 0.227 & 1.334e-01 & 577.984 & 3.094e-02 & 73.0 \\\hline
Cycle & 3 & 90.062 & 0.0 & 0.172 & 1.412e-01 & 529.581 & 4.199e-02 & 48.0 \\\hline
Cycle & 5 & 78.883 & 0.0 & 0.156 & 1.427e-01 & 438.707 & 3.950e-02 & 28.0
\\\hhline{|=|=||=|=||=|=||=|=|=|}
Grid & 2 & 116.157 & 0.0 & 0.864 & 8.298e-02 & 275.839 & 5.461e-03 & 1.0 \\\hline
Grid & 3 & 81.933 & 0.0 & 0.464 & 1.110e-01 & 480.608 & 1.368e-02 & 15.0 \\\hline
Grid & 5 & 58.054 & 0.0 & 0.131 & 1.384e-01 & 358.662 & 3.028e-02 & 2.0
\\\hhline{|=|=||=|=||=|=||=|=|=|}
Tree & 2 & 240.215 & 0.0 & 0.750 & 0.000e+00 & 2.768 & 3.253e-04 & 0.0\\\hline
Tree & 3 & 220.510 & 0.0 & 0.709 & 0.000e+00 & 2.533 & 1.194e-04 & 0.0\\\hline
Tree & 5 & 204.919 & 0.0 & 0.653 & 0.000e+00 & 2.345 & 8.947e-05 & 0.0\\\hline\end{tabular}

joint_pva.tex
\begin{tabular}{|c|c|c|c|c||c|c||c|c||c|c|c|}
\multicolumn{5}{|c||}{Games} & \multicolumn{2}{c||}{\lemke} & \multicolumn{2}{c||}{\descent 0.1 LS} &
\multicolumn{3}{c|}{\descent 0.001 LS} \\\hline
Players & Actions& \# Payoff & LCP & $p$ & Time & \% T & Time & \eps & Time & \eps & \% T\\
\hhline{|=|=|=|=|=||=|=||=|=||=|=|=|}
 & & 992250 & 1060 & 2 & 3.113 & 0.0 & 0.301 & 7.152e-04 & 12.586 & 8.502e-04 & 0.0 \\\cline{3-12}
10 & 105 & 992250 & 1060 & 3 & 1.933 & 0.0 & 0.262 & 5.853e-04 & 13.704 & 8.381e-04 & 0.0 \\\cline{3-12}
 & & 992250 & 1060 & 5 & 1.430 & 0.0 & 0.198 & 6.931e-04 & 15.256 & 7.425e-04 & 0.0 \\\cline{3-12}
\hhline{|=|=|=|=|=||=|=||=|=||=|=|=|}
 & & 995000 & 1200 & 2 & 194.233 & 8.0 & 8.455 & 1.446e-02 & 86.116 & 9.603e-04 & 0.0 \\\cline{3-12}
200 & 5 & 995000 & 1200 & 3 & 410.118 & 38.0 & 6.551 & 1.909e-02 & 73.485 & 1.047e-03 & 0.0 \\\cline{3-12}
 & & 995000 & 1200 & 5 & 552.583 & 81.0 & 4.957 & 2.585e-02 & 64.676 & 1.130e-03 & 0.0 \\\hline\end{tabular}

ts1ls_weight.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.1}\\\hline

Time & Avg Eps\\\hline
0.017 & 5.522e-03\\
\hline
0.013 & 6.601e-03\\
\hhline{|=|=|}
0.022 & 5.625e-03\\
\hline
0.015 & 4.546e-03\\
\hhline{|=|=|}
0.020 & 4.753e-03\\
\hline
0.013 & 4.620e-03\\
\hhline{|=|=|}
0.020 & 2.821e-04\\
\hline
0.016 & 7.897e-03\\
\hline
\end{tabular}

lemke_strict.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Lemke}\\\hline
Time & \% Timeout \\\hline
356.009 & 17.0\\\hhline{|=|=|}
580.891 & 85.0\\\hhline{|=|=|}
551.795 & 77.0\\\hhline{|=|=|}
79.560 & 0.0\\\hhline{|=|=|}
\end{tabular}

ts001ls_strict.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.001}\\\hline

Time & Avg Eps\\\hline
0.565 & 1.054e-03\\
\hhline{|=|=|}
2.121 & 1.068e-03\\
\hhline{|=|=|}
1.444 & 1.108e-03\\
\hhline{|=|=|}
0.673 & 8.111e-04\\
\hhline{|=|=|}
\end{tabular}

games_weight.tex

\begin{tabular}{|l|c|c|}
\multicolumn{2}{c}{Games}\\\hline
Graph & p \\\hline
Complete & 2\\\hline
Complete & 5\\\hhline{|=|=|}
Cycle & 2\\\hline
Cycle & 5\\\hhline{|=|=|}
Grid & 2\\\hline
Grid & 5\\\hhline{|=|=|}
Tree & 2\\\hline
Tree & 5\\\hline
\end{tabular}

games_strict.tex

\begin{tabular}{|l|c|c|}
\multicolumn{2}{c}{Games}\\\hline
Graph & p \\\hline
Complete & 5\\\hhline{|=|=|}
Cycle & 5\\\hhline{|=|=|}
Grid & 5\\\hhline{|=|=|}
Tree & 5\\\hline
\end{tabular}

gzero_joint.tex

\begin{tabular}{|c|c||c|c||c|c||c|c|}
\multicolumn{2}{|c||}{Games} & \multicolumn{2}{c||}{\lemke} & \multicolumn{2}{c||}{\descent 0.1 LS} &
\multicolumn{2}{c|}{\descent 0.001 LS} \\\hline
Graph & $p$ & Time & \% Timeout & Time & Eps & Time & Eps \\
\hhline{|=|=||=|=||=|=||=|=|}
\multirow{3}{*}{20250} & 2 & 368.032 & 36.0 & 0.025 & 1.976e-02 & 0.577 & 1.093e-03\\\cline{2-8}
 & 3 & 495.919 & 66.0 & 0.026 & 1.762e-02 & 0.571 & 1.131e-03\\\cline{2-8}
 & 5 & 435.207 & 29.0 & 0.025 & 1.308e-02 & 0.531 & 9.926e-04\\\hhline{|=|=||=|=||=|=||=|=|}
\multirow{3}{*}{26010.0} & 2 & 438.650 & 59.0 & 0.035 & 1.855e-02 & 0.775 & 1.068e-03\\\cline{2-8}
 & 3 & 576.439 & 91.0 & 0.035 & 1.583e-02 & 0.756 & 1.120e-03\\\cline{2-8}
 & 5 & 582.924 & 88.0 & 0.034 & 1.186e-02 & 0.686 & 9.738e-04\\\hhline{|=|=||=|=||=|=||=|=|}
\multirow{3}{*}{36000.0} & 2 & 545.997 & 84.0 & 0.053 & 1.564e-02 & 1.092 & 1.049e-03\\\cline{2-8}
& 3 & 598.616 & 99.0 & 0.053 & 1.396e-02 & 1.074 & 1.110e-03\\\cline{2-8}
& 5 & 600.088 & 100.0 & 0.052 & 1.101e-02 & 0.982 & 9.721e-04\\\hline\end{tabular}

strict_joint.tex

\begin{tabular}{|c|c||c|c||c|c||c|c|}
\multicolumn{2}{|c||}{Games} & \multicolumn{2}{c||}{\lemke} & \multicolumn{2}{c||}{\descent 0.1 LS} &
\multicolumn{2}{c|}{\descent 0.001 LS} \\\hline
Graph & $p$ & Time & \% Timeout & Time & Eps & Time & Eps \\
\hhline{|=|=||=|=||=|=||=|=|}
Complete & 5 & 356.009 & 17.0 & 0.024 & 1.878e-02 & 0.552 & 1.054e-03\\\hhline{|=|=||=|=||=|=||=|=|}
Cycle & 5 & 580.891 & 85.0 & 0.087 & 1.729e-02 & 2.102 & 1.068e-03\\\hhline{|=|=||=|=||=|=||=|=|}
Grid & 5 & 551.795 & 77.0 & 0.066 & 1.612e-02 & 1.428 & 1.108e-03\\\hhline{|=|=||=|=||=|=||=|=|}
Tree & 5 & 79.560 & 0.0 & 0.048 & 2.571e-03 & 0.664 & 8.111e-04\\\hline\end{tabular}

lemke_weight.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Lemke}\\\hline
Time & \% Timeout \\\hline
0.113 & 0.0\\\hline
0.050 & 0.0\\\hhline{|=|=|}
0.168 & 0.0\\\hline
0.129 & 0.0\\\hhline{|=|=|}
0.122 & 0.0\\\hline
0.089 & 0.0\\\hhline{|=|=|}
0.177 & 0.0\\\hline
0.144 & 0.0\\\hline
\end{tabular}

ts1ls_gzero.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.1}\\\hline

Time & Avg Eps\\\hline
0.025 & 1.976e-02\\
\hline
0.026 & 1.762e-02\\
\hline
0.025 & 1.308e-02\\
\hhline{|=|=|}
0.035 & 1.855e-02\\
\hline
0.035 & 1.583e-02\\
\hline
0.034 & 1.186e-02\\
\hhline{|=|=|}
0.053 & 1.564e-02\\
\hline
0.053 & 1.396e-02\\
\hline
0.052 & 1.101e-02\\
\hline
\end{tabular}

ts1ls_coord.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.1}\\\hline

Time & Avg Eps\\\hline
0.033 & 2.103e-02\\
\hline
0.034 & 2.115e-02\\
\hline
0.034 & 1.859e-02\\
\hline
0.034 & 1.604e-02\\
\hline
0.035 & 4.844e-03\\
\hhline{|=|=|}
0.104 & 3.352e-02\\
\hline
0.104 & 3.157e-02\\
\hline
0.106 & 2.859e-02\\
\hline
0.104 & 2.626e-02\\
\hline
0.108 & 1.906e-02\\
\hhline{|=|=|}
0.073 & 3.143e-02\\
\hline
0.070 & 3.239e-02\\
\hline
0.073 & 2.955e-02\\
\hline
0.073 & 2.786e-02\\
\hline
0.070 & 2.159e-02\\
\hhline{|=|=|}
0.060 & 1.012e-02\\
\hline
0.062 & 1.997e-02\\
\hline
0.062 & 2.139e-02\\
\hline
0.061 & 2.150e-02\\
\hline
0.063 & 1.469e-03\\
\hline
\end{tabular}

ts001ls_gzero.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.001}\\\hline

Time & Avg Eps\\\hline
0.577 & 1.093e-03\\
\hline
0.571 & 1.131e-03\\
\hline
0.531 & 9.926e-04\\
\hhline{|=|=|}
0.775 & 1.068e-03\\
\hline
0.756 & 1.120e-03\\
\hline
0.686 & 9.738e-04\\
\hhline{|=|=|}
1.092 & 1.049e-03\\
\hline
1.074 & 1.110e-03\\
\hline
0.982 & 9.721e-04\\
\hline
\end{tabular}

coord_joint.tex

\begin{tabular}{|c|c||c|c||c|c||c|c|}
\multicolumn{2}{|c||}{Games} & \multicolumn{2}{c||}{\lemke} & \multicolumn{2}{c||}{\descent 0.1 LS} &
\multicolumn{2}{c|}{\descent 0.001 LS} \\\hline
Graph & $p$ & Time & \% Timeout & Time & Eps & Time & Eps \\
\hhline{|=|=||=|=||=|=||=|=|}
Complete & 0 & 1.270 & 0.0 & 0.034 & 2.103e-02 & 0.760 & 9.951e-04\\\hline
Complete & 0.25 & 63.407 & 4.0 & 0.033 & 2.115e-02 & 0.748 & 1.026e-03\\\hline
Complete & 0.5 & 337.443 & 45.0 & 0.034 & 1.859e-02 & 0.750 & 1.070e-03\\\hline
Complete & 0.75 & 522.207 & 74.0 & 0.033 & 1.604e-02 & 0.725 & 1.076e-03\\\hline
Complete & 1 & 116.354 & 0.0 & 0.034 & 4.844e-03 & 0.598 & 5.087e-04\\\hhline{|=|=||=|=||=|=||=|=|}
Cycle & 0 & 18.430 & 2.0 & 0.103 & 3.352e-02 & 3.612 & 1.093e-03\\\hline
Cycle & 0.25 & 184.451 & 21.0 & 0.103 & 3.157e-02 & 3.534 & 1.167e-03\\\hline
Cycle & 0.5 & 412.947 & 55.0 & 0.105 & 2.859e-02 & 3.430 & 1.136e-03\\\hline
Cycle & 0.75 & 593.414 & 96.0 & 0.103 & 2.626e-02 & 3.206 & 1.121e-03\\\hline
Cycle & 1 & 600.097 & 100.0 & 0.107 & 1.906e-02 & 2.712 & 6.557e-04\\\hhline{|=|=||=|=||=|=||=|=|}
Grid & 0 & 35.447 & 3.0 & 0.072 & 3.143e-02 & 2.257 & 1.023e-03\\\hline
Grid & 0.25 & 260.455 & 35.0 & 0.069 & 3.239e-02 & 2.233 & 1.137e-03\\\hline
Grid & 0.5 & 451.699 & 61.0 & 0.072 & 2.955e-02 & 2.254 & 1.170e-03\\\hline
Grid & 0.75 & 552.286 & 82.0 & 0.072 & 2.786e-02 & 2.106 & 1.186e-03\\\hline
Grid & 1 & 599.349 & 99.0 & 0.070 & 2.159e-02 & 1.802 & 6.489e-04\\\hhline{|=|=||=|=||=|=||=|=|}
Tree & 0 & 0.276 & 0.0 & 0.060 & 1.012e-02 & 0.818 & 1.175e-03\\\hline
Tree & 0.25 & 0.542 & 0.0 & 0.062 & 1.997e-02 & 0.806 & 1.220e-03\\\hline
Tree & 0.5 & 73.443 & 5.0 & 0.062 & 2.139e-02 & 0.814 & 1.246e-03\\\hline
Tree & 0.75 & 165.418 & 4.0 & 0.061 & 2.150e-02 & 0.796 & 1.084e-03\\\hline
Tree & 1 & 162.420 & 0.0 & 0.063 & 1.469e-03 & 0.778 & 7.686e-04\\\hline\end{tabular}

ts001ls_weight.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.001}\\\hline

Time & Avg Eps\\\hline
0.593 & 7.370e-04\\
\hline
0.863 & 7.156e-04\\
\hhline{|=|=|}
4.190 & 7.782e-04\\
\hline
3.463 & 6.098e-04\\
\hhline{|=|=|}
2.458 & 6.149e-04\\
\hline
2.056 & 7.221e-04\\
\hhline{|=|=|}
1.568 & 7.612e-04\\
\hline
0.977 & 7.646e-04\\
\hline
\end{tabular}

tables.tex
\begin{tabular}{|c||c||c|c||c|c|}
\hline
& \lemke & \multicolumn{2}{c|}{\descent 0.001} & \multicolumn{2}{|c|}{\descent LS 0.001}\\\hline
& Time & Time & \eps & Time & \eps \\\hline
FP & 229.4 & 508.0 & 5.4e-03 & 4.894 & 6.768e-04\\\hline
SP & 1.6 & 470.8 & 3.7e-03 & 0.491 & 1.013e-05\\\hline
AP & 547.3 & 496.0 & 6.5e-03 & 5.551 & 3.283e-04\\\hline
\end{tabular}

ts001.tex

\begin{tabular}{|c|c|c|}
\multicolumn{3}{c}{Descent 0.001}\\\hline

Time & \eps & \% Timeout \\\hline
508.037 & 5.400e-03 & 61.5\\\hline
470.797 & 3.724e-03 & 56.0\\\hline
541.041 & 2.670e-02 & 94.0\\\hline
\end{tabular}

games.tex

\begin{tabular}{|l|c|c|c|}
\multicolumn{4}{c}{Games}\\\hline
Valuation & Auc & Types & Items\\\hline
Additive & 0 & 3 & 2\\\hline
Additive & 1 & 3 & 2\\\hline
Unit & 2 & 3 & 2\\\hline
\end{tabular}

ts001ls.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.001}\\\hline

Time & \eps\\\hline
4.894 & 6.768e-04\\\hline
0.491 & 1.013e-05\\\hline
13.164 & 5.759e-03\\\hline
\end{tabular}

lemke.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Lemke}\\\hline

Time & \% Timeout \\\hline
229.442 & 13.0\\\hline
1.666 & 0.0\\\hline
427.573 & 44.5\\\hline
\end{tabular}

tables2.tex
\begin{tabular}{|c||c|c||c|c|}
\hline
Auc & \multicolumn{2}{c||}{Player 1} & \multicolumn{2}{c|}{Random}\\\hline
 & Time & \% Timeout & Time & \% Timeout \\
\hhline{|=||=|=||=|=|}
FP & 63.411 & 0.0 & 408.223 & 43.0 \\\hline
SP & 3.663 & 0.0 & 39.727 & 3.0 \\\hline
AP & 100.949 & 4.0 & 248.665 & 19.0 \\\hline
\end{tabular}

tables.tex
\documentclass{article}
\usepackage{rotating}
\usepackage{hhline}
\usepackage[a3paper, top=1cm, bottom=1cm, left=1cm, right=1cm]{geometry}
\newcommand{\lemke}{LEMKE}
\newcommand{\descent}{DESCENT}

\begin{document}
\begin{table}{
\begin{tabular}{cccc}
\input{games.tex} & \input{lemke.tex} & \input{ts1ls.tex} & \input{ts001ls.tex}
\end{tabular}
}
\end{table}

\begin{table}
\input{joint.tex}
\end{table}
\end{document}

ts001.tex

\begin{tabular}{c|c|c|c}
\multicolumn{4}{c}{Descent LS 0.1}\\\hline

Time & Iterations & Eps & \% Timeout \\\hline

games.tex

\begin{tabular}{|l|c|c|c|}
\multicolumn{4}{c}{Games}\\\hline
Valuation & Auc & Types & Items\\\hline
\hhline{|=|=|=|}
Additive & FP & 3 & 3\\\hline
Additive & SP & 3 & 3\\\hline
Additive & AP & 3 & 3\\\hline
\hhline{|=|=|=|}
Unit-b2 & FP & 3 & 3\\\hline
Unit-b2 & SP & 3 & 3\\\hline
Unit-b2 & AP & 3 & 3\\\hline
\hhline{|=|=|=|}
AndOr-b2 & FP & 3 & 3\\\hline
AndOr-b2 & SP & 3 & 3\\\hline
AndOr-b2 & AP & 3 & 3\\\hline
\hhline{|=|=|=|}
Budget-b3 & FP & 3 & 3\\\hline
Budget-b3 & SP & 3 & 3\\\hline
Budget-b3 & AP & 3 & 3\\\hline
\hhline{|=|=|=|}
SingleMinded & FP & 3 & 3\\\hline
SingleMinded & SP & 3 & 3\\\hline
SingleMinded & AP & 3 & 3\\\hline
\end{tabular}

ts001ls.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.001}\\\hline

Time & Eps &\\\hline
\hhline{|=|=|}
1.287 & 2.630e-04\\\hline
0.232 & 2.312e-05\\\hline
1.610 & 1.943e-04\\\hline
\hhline{|=|=|}
3.336 & 3.063e-02\\\hline
1.831 & 2.647e-04\\\hline
2.757 & 1.113e-02\\\hline
\hhline{|=|=|}
1.732 & 1.594e-04\\\hline
0.595 & 1.019e-04\\\hline
1.328 & 2.842e-04\\\hline
\hhline{|=|=|}
2.003 & 4.064e-03\\\hline
0.915 & 2.186e-04\\\hline
2.199 & 2.233e-03\\\hline
\hhline{|=|=|}
1.551 & 1.822e-03\\\hline
1.359 & 1.669e-04\\\hline
1.544 & 1.038e-03\\\hline
\end{tabular}

ts1ls.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.1}\\\hline

Time & Eps &\\\hline
\hhline{|=|=|}
0.200 & 1.133e-02\\\hline
0.233 & 7.103e-03\\\hline
0.289 & 6.163e-03\\\hline
\hhline{|=|=|}
0.199 & 6.249e-02\\\hline
0.459 & 1.442e-02\\\hline
0.168 & 4.182e-02\\\hline
\hhline{|=|=|}
0.194 & 1.927e-02\\\hline
0.279 & 7.026e-03\\\hline
0.171 & 8.662e-03\\\hline
\hhline{|=|=|}
0.206 & 3.055e-02\\\hline
0.348 & 2.543e-02\\\hline
0.271 & 1.990e-02\\\hline
\hhline{|=|=|}
0.139 & 2.775e-02\\\hline
0.475 & 1.045e-02\\\hline
0.162 & 1.856e-02\\\hline
\end{tabular}

lemke.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Lemke}\\\hline

Time & \% Timeout \\\hline
\hhline{|=|=|}
35.005 & 0.0\\\hline
0.764 & 0.0\\\hline
214.049 & 12.0\\\hline
\hhline{|=|=|}
46.351 & 0.0\\\hline
203.107 & 19.0\\\hline
14.709 & 0.0\\\hline
\hhline{|=|=|}
280.322 & 23.0\\\hline
1.269 & 0.0\\\hline
166.011 & 9.1\\\hline
\hhline{|=|=|}
100.444 & 5.0\\\hline
9.438 & 1.0\\\hline
248.739 & 24.0\\\hline
\hhline{|=|=|}
82.166 & 5.0\\\hline
110.341 & 17.0\\\hline
59.942 & 3.0\\\hline
\end{tabular}

joint.tex

\begin{tabular}{|l|c|c||c|c|c||c|c||c|c|}
\multicolumn{3}{|c||}{Games} & \multicolumn{3}{c||}{\lemke} & \multicolumn{2}{c||}{\descent 0.1 LS} &
\multicolumn{2}{c|}{\descent 0.001 LS} \\\hline
Valuation & Auc & Avg. Size & Time & \% Timeout & \% Pure & Time & Eps & Time & Eps \\
\hhline{|=|=|=||=|=|=||=|=||=|=|}
Additive & FP & \multirow{3}{*}{623990} & 35.005 & 0.0 & 0.0 & 0.200 & 1.133e-02 & 1.287 & 2.630e-04\\\hline
Additive & SP &  & 0.764 & 0.0 & 100.0 & 0.233 & 7.103e-03 & 0.232 & 2.312e-05\\\hline
Additive & AP &  & 214.049 & 12.0 & 0.0 & 0.289 & 6.163e-03 & 1.610 & 1.943e-04\\
\hhline{|=|=|=||=|=|=||=|=||=|=|}
Unit-b2 & FP & \multirow{3}{*}{650417} & 46.351 & 0.0 & 34.0 & 0.199 & 6.249e-02 & 3.336 & 3.063e-02\\\hline
Unit-b2 & SP &  & 203.107 & 19.0 & 58.0 & 0.459 & 1.442e-02 & 1.831 & 2.647e-04\\\hline
Unit-b2 & AP &  & 14.709 & 0.0 & 21.0 & 0.168 & 4.182e-02 & 2.757 & 1.113e-02\\
\hhline{|=|=|=||=|=|=||=|=||=|=|}
AndOr-b2 & FP & \multirow{3}{*}{519055} & 280.322 & 23.0 & 0.0 & 0.194 & 1.927e-02 & 1.732 & 1.594e-04\\\hline
AndOr-b2 & SP &  & 1.269 & 0.0 & 100.0 & 0.279 & 7.026e-03 & 0.595 & 1.019e-04\\\hline
AndOr-b2 & AP &  & 166.011 & 9.1 & 0.0 & 0.171 & 8.662e-03 & 1.328 & 2.842e-04\\
\hhline{|=|=|=||=|=|=||=|=||=|=|}
Budget-b3 & FP & \multirow{3}{*}{647583} & 100.444 & 5.0 & 3.16 & 0.206 & 3.055e-02 & 2.003 & 4.064e-03\\\hline
Budget-b3 & SP &  & 9.438 & 1.0 & 84.85 & 0.348 & 2.543e-02 & 0.915 & 2.186e-04\\\hline
Budget-b3 & AP &  & 248.739 & 24.0 & 0.0 & 0.271 & 1.990e-02 & 2.199 & 2.233e-03\\
\hhline{|=|=|=||=|=|=||=|=||=|=|}
SingleMinded & FP & \multirow{3}{*}{606511} & 82.166 & 7.37 & 5.0 & 0.139 & 2.775e-02 & 1.551 & 1.822e-03\\\hline
SingleMinded & SP &  & 110.341 & 17.0 & 48.19 & 0.475 & 1.045e-02 & 1.359 & 1.669e-04\\\hline
SingleMinded & AP &  & 59.942 & 3.0 & 1.0 & 0.162 & 1.856e-02 & 1.544 & 1.038e-03\\\hline\end{tabular}

ts001ls_coord.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.001}\\\hline

Time & Avg Eps\\\hline
0.762 & 9.951e-04\\
\hline
0.760 & 1.026e-03\\
\hline
0.765 & 1.070e-03\\
\hline
0.737 & 1.076e-03\\
\hline
0.604 & 5.087e-04\\
\hhline{|=|=|}
3.660 & 1.093e-03\\
\hline
3.581 & 1.167e-03\\
\hline
3.478 & 1.136e-03\\
\hline
3.243 & 1.121e-03\\
\hline
2.739 & 6.557e-04\\
\hhline{|=|=|}
2.284 & 1.023e-03\\
\hline
2.270 & 1.137e-03\\
\hline
2.293 & 1.170e-03\\
\hline
2.138 & 1.186e-03\\
\hline
1.811 & 6.489e-04\\
\hhline{|=|=|}
0.807 & 1.175e-03\\
\hline
0.804 & 1.220e-03\\
\hline
0.822 & 1.246e-03\\
\hline
0.804 & 1.084e-03\\
\hline
0.781 & 7.686e-04\\
\hline
\end{tabular}

games_coord.tex

\begin{tabular}{|l|c|c|}
\multicolumn{2}{c}{Games}\\\hline
Graph & p \\\hline
Complete & 0\\\hline
Complete & 0.25\\\hline
Complete & 0.5\\\hline
Complete & 0.75\\\hline
Complete & 1\\\hhline{|=|=|}
Cycle & 0\\\hline
Cycle & 0.25\\\hline
Cycle & 0.5\\\hline
Cycle & 0.75\\\hline
Cycle & 1\\\hhline{|=|=|}
Grid & 0\\\hline
Grid & 0.25\\\hline
Grid & 0.5\\\hline
Grid & 0.75\\\hline
Grid & 1\\\hhline{|=|=|}
Tree & 0\\\hline
Tree & 0.25\\\hline
Tree & 0.5\\\hline
Tree & 0.75\\\hline
Tree & 1\\\hline
\end{tabular}

games.tex

\begin{tabular}{|l|c|c|c|}
\multicolumn{4}{c}{Games}\\\hline
Game & Hills & Types & Troops\\\hline
AdjWinner & 3 & 3 & 8\\\hline
AdjWinner & 3 & 3 & 10\\\hline
AdjWinner & 3 & 3 & 12\\\hline
AdjWinner & 3 & 4 & 8\\\hline
AdjWinner & 3 & 4 & 9\\\hline
AdjWinner & 3 & 4 & 10\\\hline
BlottoPayoff & 3 & 3 & 8\\\hline
BlottoPayoff & 3 & 3 & 10\\\hline
BlottoPayoff & 3 & 3 & 12\\\hline
BlottoPayoff & 4 & 3 & 4\\\hline
BlottoPayoff & 4 & 3 & 5\\\hline
BlottoPayoff & 4 & 3 & 6\\\hline
\end{tabular}

ts1.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.1}\\\hline

Time & Avg Eps \\\hline
0.028 & 2.237e-02\\\hline
0.048 & 2.229e-02\\\hline
0.079 & 2.558e-02\\\hline
0.047 & 2.474e-02\\\hline
0.063 & 2.693e-02\\\hline
0.084 & 2.752e-02\\\hline
0.059 & 1.417e-02\\\hline
0.151 & 1.684e-02\\\hline
0.263 & 1.547e-02\\\hline
0.018 & 9.091e-03\\\hline
0.036 & 7.473e-03\\\hline
0.075 & 5.867e-03\\\hline
\end{tabular}

ts001ls.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Descent LS 0.001}\\\hline

Time & Avg Eps \\\hline
0.188 & 1.654e-03\\\hline
0.342 & 2.002e-03\\\hline
0.569 & 1.864e-03\\\hline
0.344 & 2.273e-03\\\hline
0.456 & 2.155e-03\\\hline
0.604 & 2.254e-03\\\hline
0.477 & 5.281e-04\\\hline
0.843 & 5.408e-04\\\hline
1.405 & 6.268e-04\\\hline
0.292 & 4.980e-04\\\hline
0.583 & 4.913e-04\\\hline
1.106 & 5.088e-04\\\hline
\end{tabular}

lemke.tex

\begin{tabular}{|c|c|}
\multicolumn{2}{c}{Lemke}\\\hline

Time & \% Timeout \\\hline
0.248 & 0.0\\\hline
0.493 & 0.0\\\hline
12.725 & 2.0\\\hline
0.527 & 0.0\\\hline
0.726 & 0.0\\\hline
0.870 & 0.0\\\hline
71.814 & 0.0\\\hline
382.497 & 23.0\\\hline
573.663 & 91.0\\\hline
12.114 & 0.0\\\hline
87.155 & 0.0\\\hline
499.651 & 49.0\\\hline
\end{tabular}

joint.tex

\begin{tabular}{|l|c|c||c|c||c|c||c|c|c|}
\multicolumn{3}{|c||}{Games} & \multicolumn{2}{c||}{\lemke} & \multicolumn{2}{c||}{\descent 0.1 LS} &
\multicolumn{3}{c|}{\descent 0.001 LS} \\\hline
Game & \# Types & \# Points/Troops& Time & \% Timeout & Time & \eps & Time & \eps & \% Timeout\\
\hhline{|=|=|=||=|=||=|=||=|=|=|}
AdjWinner & 30 & 5 & 281.407 & 21.0 & 0.939 & 4.450e-02 & 3.065 & 7.469e-03 & 0.0 \\\hline
AdjWinner & 3 & 60 & 233.963 & 10.0 & 138.584 & 2.683e-02 & 220.254 & 1.827e-03 & 10.0 \\
\hhline{|=|=|=||=|=||=|=||=|=|=|}
Blotto & 3 & 8 & 71.814 & 0.0 & 0.032 & 9.181e-03 & 0.480 & 5.281e-04 & 0.0 \\\hline
Blotto & 3 & 10 & 382.497 & 23.0 & 0.063 & 8.859e-03 & 0.845 & 5.408e-04 & 0.0 \\\hline
Blotto & 3 & 12 & 573.663 & 91.0 & 0.118 & 8.590e-03 & 1.392 & 6.268e-04 & 0.0 \\\hline
\end{tabular}

auc_joint.tex

\begin{tabular}{|l|c|c|c||c|c|c||c|c||c|c|}
\multicolumn{4}{|c||}{Games} & \multicolumn{3}{c||}{\lemke} & \multicolumn{2}{c||}{\descent 0.1 LS} &
\multicolumn{2}{c|}{\descent 0.001 LS} \\\hline
& Valuation & Avg. Size & Auc & Time & \% Timeout & \% Pure & Time & \eps & Time & \eps \\
\hhline{|=|=|=|=||=|=|=||=|=||=|=|}
\multirow{15}{*}{\rotatebox[origin=c]{90}{Itembidding}}& \multirow{3}{*}{Additive} & \multirow{3}{*}{623990} & FP & 35.005 & 0.0 & 0.0 & 0.200 & 1.133e-02 & 1.287 & 2.630e-04\\\cline{4-11}
& & & SP & 0.764 & 0.0 & 100.0 & 0.233 & 7.103e-03 & 0.232 & 2.312e-05\\\cline{4-11}
& & & AP & 214.049 & 12.0 & 0.0 & 0.289 & 6.163e-03 & 1.610 & 1.943e-04\\
\hhline{|~|=|=|=||=|=|=||=|=||=|=|}
& & \multirow{3}{*}{650417} & FP & 46.351 & 0.0 & 34.0 & 0.199 & 6.249e-02 & 3.336 & 3.063e-02\\\cline{4-11}
& Unit &  & SP & 203.107 & 19.0 & 58.0 & 0.459 & 1.442e-02 & 1.831 & 2.647e-04\\\cline{4-11}
& &  & AP & 14.709 & 0.0 & 21.0 & 0.168 & 4.182e-02 & 2.757 & 1.113e-02\\
\hhline{|~|=|=|=||=|=|=||=|=||=|=|}
& & \multirow{3}{*}{519055} & FP & 280.322 & 23.0 & 0.0 & 0.194 & 1.927e-02 & 1.732 & 1.594e-04\\\cline{4-11}
& AndOr &  & SP & 1.269 & 0.0 & 100.0 & 0.279 & 7.026e-03 & 0.595 & 1.019e-04\\\cline{4-11}
& &  & AP & 166.011 & 9.1 & 0.0 & 0.171 & 8.662e-03 & 1.328 & 2.842e-04\\
\hhline{|~|=|=|=||=|=|=||=|=||=|=|}
& & \multirow{3}{*}{647583} & FP & 100.444 & 5.0 & 3.16 & 0.206 & 3.055e-02 & 2.003 & 4.064e-03\\\cline{4-11}
& Budget &  & SP & 9.438 & 1.0 & 84.85 & 0.348 & 2.543e-02 & 0.915 & 2.186e-04\\\cline{4-11}
& &  & AP & 248.739 & 24.0 & 0.0 & 0.271 & 1.990e-02 & 2.199 & 2.233e-03\\
\hhline{|~|=|=|=||=|=|=||=|=||=|=|}
& & \multirow{3}{*}{606511} & FP & 82.166 & 7.37 & 5.0 & 0.139 & 2.775e-02 & 1.551 & 1.822e-03\\\cline{4-11}
& SingleMinded &  & SP & 110.341 & 17.0 & 48.19 & 0.475 & 1.045e-02 & 1.359 & 1.669e-04\\\cline{4-11}
& &  & AP & 59.942 & 3.0 & 1.0 & 0.162 & 1.856e-02 & 1.544 & 1.038e-03\\
\hhline{|=|=|=|=||=|=|=||=|=||=|=|}
\multirow{6}{*}{\rotatebox[origin=c]{90}{Multiunit}}& \multirow{3}{*}{Additive} & \multirow{3}{*}{836465} & D 
& 9.504 & 0.0 & 30.0 & 0.295 & 1.452e-02 & 1.481 & 4.411e-04\\\cline{4-11}
& & & U & 0.954 & 0.0 & 100.0 & 0.380 & 1.321e-02 & 1.870 & 3.579e-04\\\cline{4-11}
& & & AP & 512.564 & 64.0 & 0.0 &  0.417 & 4.080e-03 & 2.182 & 3.170e-04\\
\hhline{|~|=|=|=||=|=|=||=|=||=|=|}
& \multirow{3}{*}{SubModular} & \multirow{3}{*}{878491}& D 
& 29.054 & 0.0 & 5.0 & 0.270 & 1.326e-02 & 1.954 & 3.209e-04\\\cline{4-11}
& & & U & 5.818 & 0.0 & 83.0 & 0.272 & 2.636e-02 & 1.741 & 8.645e-04\\\cline{4-11}
& & & AP & 210.290 & 12.0 & 0.0 & 0.323 & 1.115e-02 & 2.192 & 3.273e-04\\\hline\end{tabular}

note.bbl
\begin{thebibliography}{10}

\bibitem{AM09}
T.~Adamo and A.~Matros.
\newblock A {B}lotto game with incomplete information.
\newblock {\em Economics Letters}, 105(1):100 -- 102, 2009.

\bibitem{AHLMS16}
A.~Ahmadi, M.~Hajiaghayi, B.~Lucier, H.~Mahini, and S.~Seddighin.
\newblock From duels to battlefields: Computing equilibria of {B}lotto and
  other games.
\newblock In {\em Proc.\ of AAAI}, 2016.

\bibitem{ARSS15}
K.~R. Apt, M.~Rahn, G.~Sch{\"{a}}fer, and S.~Simon.
\newblock Coordination games on graphs.
\newblock {\em CoRR}, abs/1501.07388, 2015.

\bibitem{ABH}
C.~Audet, S.~Belhaiza, and P.~Hansen.
\newblock Enumeration of all the extreme equilibria in game theory: Bimatrix
  and polymatrix games.
\newblock {\em Journal of Optimization Theory and Applications},
  129(3):349--372, 2006.

\bibitem{ARSvS}
D.~Avis, G.~Rosenberg, R.~Savani, and B.~von Stengel.
\newblock Enumeration of {N}ash equilibria for two-player games.
\newblock {\em Economic Theory}, 42(1):9--37, 2010.

\bibitem{BLP15}
S.~Barman, K.~Ligett, and G.~Piliouras.
\newblock Approximating nash equilibria in tree polymatrix games.
\newblock In {\em Proc.\ of SAGT}, pages 285--296, 2015.

\bibitem{BL04}
N.~A.~R. Bhat and K.~Leyton{-}Brown.
\newblock Computing {N}ash equilibria of action-graph games.
\newblock In {\em Proc.\ of {UAI}}, pages 35--42, 2004.

\bibitem{BR11}
K.~Bhawalkar and T.~Roughgarden.
\newblock Welfare guarantees for combinatorial auctions with item bidding.
\newblock In {\em Proc.\ of SODA}, pages 700--709, 2011.

\bibitem{BBM10}
H.~Bosse, J.~Byrka, and E.~Markakis.
\newblock New algorithms for approximate {N}ash equilibria in bimatrix games.
\newblock {\em Theoretical Computer Science}, 411(1):164--173, 2010.

\bibitem{AW}
S.~J. Brams.
\newblock Fair division.
\newblock In {\em Computational Complexity}, pages 1073--1080. Springer, 2012.

\bibitem{BGR08}
P.~Briest, P.~W. Goldberg, and H.~R{\"{o}}glin.
\newblock Approximate equilibria in games with few players.
\newblock {\em CoRR}, abs/0804.4524, 2008.

\bibitem{CD11}
Y.~Cai and C.~Daskalakis.
\newblock On minmax theorems for multiplayer games.
\newblock In {\em Proc.\ of SODA}, pages 217--234, 2011.

\bibitem{CP14}
Y.~Cai and C.~H. Papadimitriou.
\newblock Simultaneous bayesian auctions and computational complexity.
\newblock In {\em Proc.\ of {EC}}, pages 895--910, 2014.

\bibitem{CDT}
X.~Chen, X.~Deng, and S.-H. Teng.
\newblock Settling the complexity of computing two-player {N}ash equilibria.
\newblock {\em Journal of the ACM}, 56(3):14:1--14:57, 2009.

\bibitem{CPY13}
X.~Chen, D.~Paparas, and M.~Yannakakis.
\newblock The complexity of non-monotone markets.
\newblock In {\em Proc.\ of {STOC}}, pages 181--190, 2013.

\bibitem{CKS08}
G.~Christodoulou, A.~Kov{\'{a}}cs, and M.~Schapira.
\newblock Bayesian combinatorial auctions.
\newblock In {\em Proc.\ of {ICALP}}, pages 820--832, 2008.

\bibitem{DGP}
C.~Daskalakis, P.~W. Goldberg, and C.~H. Papadimitriou.
\newblock The complexity of computing a {N}ash equilibrium.
\newblock {\em SIAM Journal on Computing}, 39(1):195--259, 2009.

\bibitem{DMP}
C.~Daskalakis, A.~Mehta, and C.~H. Papadimitriou.
\newblock A note on approximate {N}ash equilibria.
\newblock {\em Theoretical Computer Science}, 410(17):1581--1588, 2009.

\bibitem{DP11}
C.~Daskalakis and C.~H. Papadimitriou.
\newblock Continuous local search.
\newblock In {\em Proc.\ of {SODA}}, pages 790--804, 2011.

\bibitem{DSVV09}
C.~Daskalakis, G.~Schoenebeck, G.~Valiant, and P.~Valiant.
\newblock On the complexity of {N}ash equilibria of action-graph games.
\newblock In {\em Proc.\ of {SODA}}, pages 710--719, 2009.

\bibitem{DFIS16}
A.~{Deligkas}, J.~{Fearnley}, T.~P. {Igwe}, and R.~{Savani}.
\newblock {An Empirical Study on Computing Equilibria in Polymatrix Games}.
\newblock {\em CoRR}, abs/1602.06865, 2016.

\bibitem{DFSS}
A.~Deligkas, J.~Fearnley, R.~Savani, and P.~Spirakis.
\newblock Computing approximate {N}ash equilibria in polymatrix games.
\newblock {\em Algorithmica}, pages 1--28, 2015.

\bibitem{DFK}
S.~Dobzinski, H.~Fu, and R.~D. Kleinberg.
\newblock On the complexity of computing an equilibrium in combinatorial
  auctions.
\newblock In {\em Proc.\ of {SODA}}, pages 110--122, 2015.

\bibitem{EY10}
K.~Etessami and M.~Yannakakis.
\newblock On the complexity of {N}ash equilibria and other fixed points.
\newblock {\em SIAM J. Comput.}, 39(6):2531--2597, 2010.

\bibitem{FIS15}
J.~Fearnley, T.~P. Igwe, and R.~Savani.
\newblock An empirical study of finding approximate equilibria in bimatrix
  games.
\newblock In {\em Proc.\ of {SEA}}, pages 339--351, 2015.

\bibitem{FT-C10}
U.~Feige and I.~Talgam{-}Cohen.
\newblock A direct reduction from \emph{k}-player to 2-player approximate
  {N}ash equilibrium.
\newblock In {\em Proc.\ of {SAGT}}, pages 138--149, 2010.

\bibitem{FHGL}
M.~Feldman, H.~Fu, N.~Gravin, and B.~Lucier.
\newblock Simultaneous auctions are (almost) efficient.
\newblock In {\em Proc.\ of {STOC}}, pages 201--210, 2013.

\bibitem{GW04}
S.~Govindan and R.~Wilson.
\newblock Computing {N}ash equilibria by iterated polymatrix approximation.
\newblock {\em Journal of Economic Dynamics and Control}, 28(7):1229--1241,
  2004.

\bibitem{GW10}
S.~Govindan and R.~Wilson.
\newblock A decomposition algorithm for n-player games.
\newblock {\em Economic Theory}, 42(1):97--117, 2010.

\bibitem{HRS08}
S.~H{\'{e}}mon and M.~Santha.
\newblock Approximate {N}ash equilibria for multi-player games.
\newblock In {\em Proc.\ of {SAGT}}, pages 267--278, 2008.

\bibitem{HR74}
J.~Howson, Joseph~T. and R.~W. Rosenthal.
\newblock {B}ayesian equilibria of finite two-person games with incomplete
  information.
\newblock {\em Management Science}, 21(3):pp. 313--315, 1974.

\bibitem{JLB11}
A.~X. Jiang, K.~Leyton{-}Brown, and N.~A.~R. Bhat.
\newblock Action-graph games.
\newblock {\em Games and Economic Behavior}, 71(1):141--173, 2011.

\bibitem{KR11}
D.~Kovenock and B.~Roberson.
\newblock A {B}lotto game with multi-dimensional incomplete information.
\newblock {\em Economics Letters}, 113(3):273 -- 275, 2011.

\bibitem{lemke65}
C.~E. Lemke.
\newblock Bimatrix equilibrium points and mathematical programming.
\newblock {\em Management Science}, 11(7):pp. 681--689, 1965.

\bibitem{lemke64}
C.~E. Lemke and J.~Howson, J.~T.
\newblock Equilibrium points of bimatrix games.
\newblock {\em Journal of the Society for Industrial and Applied Mathematics},
  12(2):pp. 413--423, 1964.

\bibitem{miller91}
D.~A. Miller and S.~W. Zucker.
\newblock Copositive-plus lemke algorithm solves polymatrix games.
\newblock {\em Operations Research Letters}, 10(5):285 -- 290, 1991.

\bibitem{N}
J.~Nash.
\newblock Non-cooperative games.
\newblock {\em The Annals of Mathematics}, 54(2):286--295, 1951.

\bibitem{GAMUT}
E.~Nudelman, J.~Wortman, Y.~Shoham, and K.~Leyton-Brown.
\newblock Run the gamut: A comprehensive approach to evaluating game-theoretic
  algorithms.
\newblock In {\em Proc.\ of {AAMAS}}, pages 880--887, 2004.

\bibitem{PTW14}
G.~Polevoy, S.~Trajanovski, and M.~de~Weerdt.
\newblock {N}ash equilibria in shared effort games.
\newblock In {\em Proc.\ of {AAMAS}}, pages 861--868, 2014.

\bibitem{PNS}
R.~Porter, E.~Nudelman, and Y.~Shoham.
\newblock Simple search methods for finding a {N}ash equilibrium.
\newblock In {\em Proc.\ of {AAAI}}, pages 664--669, 2004.

\bibitem{R12}
T.~Roughgarden.
\newblock The price of anarchy in games of incomplete information.
\newblock In {\em Proc.\ of {EC}}, pages 862--879, 2012.

\bibitem{Rub15}
A.~Rubinstein.
\newblock Inapproximability of {N}ash equilibrium.
\newblock In {\em Proc.\ of {STOC}}, pages 409--418, 2015.

\bibitem{SGC05}
T.~Sandholm, A.~Gilpin, and V.~Conitzer.
\newblock Mixed-integer programming methods for finding {N}ash equilibria.
\newblock In {\em Proc.\ of {AAAI}}, pages 495--501, 2005.

\bibitem{SL08}
Y.~Shoham and K.~Leyton-Brown.
\newblock Protocols for multiagent resource allocation: Auctions.
\newblock In {\em Multiagent Systems}, pages 315--366. Cambridge University
  Press, 2008.
\newblock Cambridge Books Online.

\bibitem{TS}
H.~Tsaknakis and P.~G. Spirakis.
\newblock An optimization approach for approximate {N}ash equilibria.
\newblock {\em Internet Mathematics}, 5(4):365--382, 2008.

\bibitem{TSK08}
H.~Tsaknakis, P.~G. Spirakis, and D.~Kanoulas.
\newblock Performance evaluation of a descent algorithm for bi-matrix games.
\newblock In {\em Proc.\ of {WINE}}, pages 222--230, 2008.

\end{thebibliography}
