We give a simple and computationally efficient algorithm that, for any constant ε> 0, obtains ε
T-swap regret within only T=(n) rounds; this is an exponential improvement compared to the …

We introduce a new approach for computing optimal equilibria via learning in games. It
applies to extensive-form settings with any number of players, including mechanism design …

For a constant ϵ, we prove a (N) lower bound on the (randomized) communication
complexity of ϵ-Nash equilibrium in two-player N x N games. For n-player binary-action …

We consider (i) the problem of finding a (possibly mixed) Nash equilibrium in congestion
games, and (ii) the problem of finding an (exponential precision) fixed point of the gradient …

Separations: We introduce a monotone variant of Xor-Sat and show it has exponential
monotone circuit complexity. Since Xor-Sat is in NC^ 2, this improves qualitatively on the …

In the envy-free cake-cutting problem we are given a resource, usually called a cake and
represented as the 0,1 interval, and a set of n agents with heterogeneous preferences over …

We show that deterministic communication complexity can be superlogarithmic in the
partition number of the associated communication matrix. We also obtain near-optimal …

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria Page 1 Copyright
© by SIAM. Unauthorized reproduction of this article is prohibited. SIAM J. COMPUT. © 2021 …

We study classic cake-cutting problems, but in discrete models rather than using infinite-
precision real values, specifically, focusing on their communication complexity. Using …

Nowadays, there are lots of disks from various disk models in datacenter. It is a challenge to
make failure prediction for all disk models with high precision and high coverage. One-for …