
Low rank matrix approximation is an important tool in machine learning. Given
a data matrix, low rank approximation helps to find factors, patterns and
provides concise representations for the data. Research on low rank
approximation usually focus on real matrices. However, in many applications
data are binary (categorical) rather than continuous. This leads to the problem
of low rank approximation of binary matrix. Here we are given a $d \times n$
binary matrix $A$ and a small integer $k$. The goal is to find two binary
matrices $U$ and $V$ of sizes $d \times k$ and $k \times n$ respectively, so
that the Frobenius norm of $A  U V$ is minimized. There are two models of this
problem, depending on the definition of the dot product of binary vectors: The
$\mathrm{GF}(2)$ model and the Boolean semiring model. Unlike low rank
approximation of real matrix which can be efficiently solved by Singular Value
Decomposition, approximation of binary matrix is $NP$hard even for $k=1$.
In this paper, we consider the problem of Column Subset Selection (CSS), in
which one low rank matrix must be formed by $k$ columns of the data matrix. We
characterize the approximation ratio of CSS for binary matrices. For $GF(2)$
model, we show the approximation ratio of CSS is bounded by
$\frac{k}{2}+1+\frac{k}{2(2^k1)}$ and this bound is asymptotically tight. For
Boolean model, it turns out that CSS is no longer sufficient to obtain a bound.
We then develop a Generalized CSS (GCSS) procedure in which the columns of one
low rank matrix are generated from Boolean formulas operating bitwise on
columns of the data matrix. We show the approximation ratio of GCSS is bounded
by $2^{k1}+1$, and the exponential dependency on $k$ is inherent.

We study the truthful facility assignment problem, where a set of agents with
private mostpreferred points on a metric space are assigned to facilities that
lie on the metric space, under capacity constraints on the facilities. The goal
is to produce such an assignment that minimizes the social cost, i.e., the
total distance between the mostpreferred points of the agents and their
corresponding facilities in the assignment, under the constraint of
truthfulness, which ensures that agents do not misreport their mostpreferred
points.
We propose a resource augmentation framework, where a truthful mechanism is
evaluated by its worstcase performance on an instance with enhanced facility
capacities against the optimal mechanism on the same instance with the original
capacities. We study a very wellknown mechanism, Serial Dictatorship, and
provide an exact analysis of its performance. Although Serial Dictatorship is a
purely combinatorial mechanism, our analysis uses linear programming; a linear
program expresses its greedy nature as well as the structure of the input, and
finds the input instance that enforces the mechanism have its worstcase
performance. Bounding the objective of the linear program using duality
arguments allows us to compute tight bounds on the approximation ratio. Among
other results, we prove that Serial Dictatorship has approximation ratio
$g/(g2)$ when the capacities are multiplied by any integer $g \geq 3$. Our
results suggest that even a limited augmentation of the resources can have
wondrous effects on the performance of the mechanism and in particular, the
approximation ratio goes to 1 as the augmentation factor becomes large. We
complement our results with bounds on the approximation ratio of Random Serial
Dictatorship, the randomized version of Serial Dictatorship, when there is no
resource augmentation.

The Stackelberg equilibrium solution concept describes optimal strategies to
commit to: Player 1 (termed the leader) publicly commits to a strategy and
Player 2 (termed the follower) plays a best response to this strategy (ties are
broken in favor of the leader). We study Stackelberg equilibria in finite
sequential games (or extensiveform games) and provide new exact algorithms,
approximate algorithms, and hardness results for several classes of these
sequential games.

In this paper we study how to play (stochastic) games optimally using little
space. We focus on repeated games with absorbing states, a type of twoplayer,
zerosum concurrent meanpayoff games. The prototypical example of these games
is the well known Big Match of Gillete (1957). These games may not allow
optimal strategies but they always have {\epsilon}optimal strategies. In this
paper we design {\epsilon}optimal strategies for Player 1 in these games that
use only O(log log T ) space. Furthermore, we construct strategies for Player 1
that use space s(T), for an arbitrary small unbounded nondecreasing function
s, and which guarantee an {\epsilon}optimal value for Player 1 in the limit
superior sense. The previously known strategies use space {\Omega}(logT) and it
was known that no strategy can use constant space if it is {\epsilon}optimal
even in the limit superior sense. We also give a complementary lower bound.
Furthermore, we also show that no Markov strategy, even extended with finite
memory, can ensure value greater than 0 in the Big Match, answering a question
posed by Abraham Neyman.

We consider finitestate concurrent stochastic games, played by k>=2 players
for an infinite number of rounds, where in every round, each player
simultaneously and independently of the other players chooses an action,
whereafter the successor state is determined by a probability distribution
given by the current state and the chosen actions. We consider reachability
objectives that given a target set of states require that some state in the
target is visited, and the dual safety objectives that given a target set
require that only states in the target set are visited. We are interested in
the complexity of stationary strategies measured by their patience, which is
defined as the inverse of the smallest nonzero probability employed. Our main
results are as follows: We show that in twoplayer zerosum concurrent
stochastic games (with reachability objective for one player and the
complementary safety objective for the other player): (i) the optimal bound on
the patience of optimal and epsilonoptimal strategies, for both players is
doubly exponential; and (ii) even in games with a single nonabsorbing state
exponential (in the number of actions) patience is necessary. In general we
study the class of nonzerosum games admitting stationary epsilonNash
equilibria. We show that if there is at least one player with reachability
objective, then doublyexponential patience may be needed for epsilonNash
equilibrium strategies, whereas in contrast if all players have safety
objectives, the optimal bound on patience for epsilonNash equilibrium
strategies is only exponential.

We consider the task of computing an approximation of a trembling hand
perfect equilibrium for an nplayer game in strategic form, n >= 3. We show
that this task is complete for the complexity class FIXP_a. In particular, the
task is polynomial time equivalent to the task of computing an approximation of
a Nash equilibrium in strategic form games with three (or more) players.

For matrix games we study how small nonzero probability must be used in
optimal strategies. We show that for nxn winlosedraw games (i.e. (1,0,1)
matrix games) nonzero probabilities smaller than n^{O(n)} are never needed. We
also construct an explicit nxn winlose game such that the unique optimal
strategy uses a nonzero probability as small as n^{Omega(n)}. This is done by
constructing an explicit (1,1) nonsingular nxn matrix, for which the inverse
has only nonnegative entries and where some of the entries are of value
n^{Omega(n)}.

Two standard algorithms for approximately solving twoplayer zerosum
concurrent reachability games are value iteration and strategy iteration. We
prove upper and lower bounds of 2^(m^(Theta(N))) on the worst case number of
iterations needed by both of these algorithms for providing nontrivial
approximations to the value of a game with N nonterminal positions and m
actions for each player in each position. In particular, both algorithms have
doublyexponential complexity. Even when the game given as input has only one
nonterminal position, we prove an exponential lower bound on the worst case
number of iterations needed to provide nontrivial approximations.

Shapley's discounted stochastic games, Everett's recursive games and
Gillette's undiscounted stochastic games are classical models of game theory
describing twoplayer zerosum games of potentially infinite duration. We
describe algorithms for exactly solving these games.

We consider approximating the minmax value of a multiplayer game in
strategic form. Tightening recent bounds by Borgs et al., we observe that
approximating the value with a precision of epsilon log n digits (for any
constant epsilon>0 is NPhard, where n is the size of the game. On the other
hand, approximating the value with a precision of c log log n digits (for any
constant c >= 1) can be done in quasipolynomial time. We consider the
parameterized complexity of the problem, with the parameter being the number of
pure strategies k of the player for which the minmax value is computed. We show
that if there are three players, k=2 and there are only two possible rational
payoffs, the minmax value is a rational number and can be computed exactly in
linear time. In the general case, we show that the value can be approximated
with any polynomial number of digits of accuracy in time n^(O(k)). On the other
hand, we show that minmax value approximation is W[1]hard and hence not likely
to be fixed parameter tractable. Concretely, we show that if kCLIQUE requires
time n^(Omega(k)) then so does minmax value computation.

We define the class of "simple recursive games". A simple recursive game is
defined as a simple stochastic game (a notion due to Anne Condon), except that
we allow arbitrary real payoffs but disallow moves of chance. We study the
complexity of solving simple recursive games and obtain an almostlinear time
comparisonbased algorithm for computing an equilibrium of such a game. The
existence of a linear time comparisonbased algorithm remains an open problem.