We consider the problem of minimizing social cost in atomic congestion games and show, perhaps surprisingly, that efficiently computed taxation mechanisms yield the same performance achievable by the best polynomial time algorithm, even when the latter has full control over the players' actions. It follows that no other tractable approach geared at incentivizing desirable system behavior can improve upon this result, regardless of whether it is based on taxations, coordination mechanisms, information provision, or any other principle. Three technical contributions underpin this conclusion. First, we show that computing the minimum social cost is NP-hard to approximate within a given factor depending solely on the admissible resource costs. Second, we design a tractable taxation mechanism whose efficiency (price of anarchy) matches this hardness factor, and thus is optimal. As these results extend to coarse correlated equilibria, any no-regret algorithm inherits the same performances, allowing us to devise polynomial time algorithms with optimal approximation.

We study the existence of approximate pure Nash equilibria (α-PNE) in weighted atomic congestion games with polynomial cost functions of maximum degree d. Previously it was known that d-approximate equilibria always exist, while nonexistence was established only for small constants, namely for 1.153-PNE. We improve significantly upon this gap, proving that such games in general do not have Θ̃(√d)-approximate PNE, which provides the first super-constant lower bound. Furthermore, we provide a black-box gap-introducing method of combining such nonexistence results with a specific circuit gadget, in order to derive NP-completeness of the decision version of the problem. In particular, deploying this technique we are able to show that deciding whether a weighted congestion game has an Õ(√d)-PNE is NP-complete. Previous hardness results were known only for the special case of exact equilibria and arbitrary cost functions. The circuit gadget is of independent interest and it allows us to also prove hardness for a variety of problems related to the complexity of PNE in congestion games. For example, we demonstrate that the question of existence of α-PNE in which a certain set of players plays a specific strategy profile is NP-hard for any α < 3^(d/2), even for unweighted congestion games. Finally, we study the existence of approximate equilibria in weighted congestion games with general (nondecreasing) costs, as a function of the number of players n. We show that n-PNE always exist, matched by an almost tight nonexistence bound of Θ̃(n) which we can again transform into an NP-completeness proof for the decision problem.

The field of Human Activity Recognition (HAR) focuses on obtaining and analysing data captured from monitoring devices (e.g. sensors). There is a wide range of applications within the field; for instance, assisted living, security surveillance, and intelligent transportation. In HAR, the development of Activity Recognition models is dependent upon the data captured by these devices and the methods used to analyse them, which directly affect performance metrics. In this work, we address the issue of accurately recognising human activities using different Machine Learning (ML) techniques. We propose a new feature representation based on consecutive occurring observations and compare it against previously used feature representations using a wide range of classification methods. Experimental results demonstrate that techniques based on the proposed representation outperform the baselines and a better accuracy was achieved for both highly and less frequent actions. We also investigate how the addition of further features and their pre-processing techniques affect performance results leading to state-of-the-art accuracy on a Human Activity Recognition dataset.

We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial cost functions. In particular, for any positive integer $d$ we construct rather simple games with cost functions of degree at most $d$ which have a PoS of at least $\varOmega(\Phi_d)^{d+1}$, where $\Phi_d\sim d/\ln d$ is the unique positive root of the equation $x^{d+1}=(x+1)^d$. This almost closes the huge gap between $\varTheta(d)$ and $\Phi_d^{d+1}$. Our bound extends also to network congestion games. We further show that the PoS remains exponential even for singleton games. More generally, we provide a lower bound of $\varOmega((1+1/\alpha)^d/d)$ on the PoS of $\alpha$-approximate Nash equilibria for singleton games. All our lower bounds hold for mixed and correlated equilibria as well. On the positive side, we give a general upper bound on the PoS of $\alpha$-approximate Nash equilibria, which is sensitive to the range $W$ of the player weights and the approximation parameter $\alpha$. We do this by explicitly constructing a novel approximate potential function, based on Faulhaber's formula, that generalizes Rosenthal's potential in a continuous, analytic way. From the general theorem, we deduce two interesting corollaries. First, we derive the existence of an approximate pure Nash equilibrium with PoS at most $(d+3)/2$; the equilibrium's approximation parameter ranges from $\varTheta(1)$ to $d+1$ in a smooth way with respect to $W$. Second, we show that for unweighted congestion games, the PoS of $\alpha$-approximate Nash equilibria is at most $(d+1)/\alpha$.

In this paper, we study the problem of deciding the winner of reachability switching games. We study zero-, one-, and two-player variants of these games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case is PSPACE-hard and in EXPTIME. For the zero-player case, we also show P-hardness for a succinctly-represented model that maintains the upper bound of NP n coNP. For the one- and two-player cases, our results hold in both the natural, explicit model and succinctly-represented model. We also study the structure of winning strategies in these games, and in particular we show that exponential memory is required in both the one- and two-player settings.

In this paper, we study contention resolution protocols from a game-theoretic perspective. We focus on acknowledgment-based protocols, where a user gets feedback from the channel only when she attempts transmission. In this case she will learn whether her transmission was successful or not. Users that do not transmit will not receive any feedback. We are interested in equilibrium protocols, where no player has an incentive to deviate. The limited feedback makes the design of equilibrium protocols a hard task as best response policies usually have to be modeled as Partially Observable Markov Decision Processes, which are hard to analyze. Nevertheless, we show how to circumvent this for the case of two players and present an equilibrium protocol. For many players, we give impossibility results for a large class of acknowledgment-based protocols, namely age-based and backoff protocols with finite expected finishing time. Finally, we provide an age-based equilibrium protocol, which has infinite expected finishing time, but every player finishes in linear time with high probability.

A recent body of experimental literature has studied empirical game-theoretical analysis, in which we have partial knowledge of a game, consisting of observations of a subset of the pure-strategy profiles and their associated payoffs to players. The aim is to find an exact or approximate Nash equilibrium of the game, based on these observations. It is usually assumed that the strategy profiles may be chosen in an on-line manner by the algorithm. We study a corresponding computational learning model, and the query complexity of learning equilibria for various classes of games. We give basic results for bimatrix and graphical games. Our focus is on symmetric network congestion games. For directed acyclic networks, we can learn the cost functions (and hence compute an equilibrium) while querying just a small fraction of pure-strategy profiles. For the special case of parallel links, we have the stronger result that an equilibrium can be identified while only learning a small fraction of the cost values.

We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a randomized algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm, surprisingly, closely approximates the idealized process (where the tokens are divisible) on important network topologies. On $d$-dimensional torus graphs with $n$ nodes it deviates from the idealized process only by an additive constant. In contrast, the randomized rounding approach of Friedrich and Sauerwald [Proceedings of the \textup41st Annual ACM Symposium on Theory of Computing, 2009, pp. 121--130] can deviate up to $\Omega(\operatorname{polylog}(n))$, and the deterministic algorithm of Rabani, Sinclair, and Wanka [Proceedings of the \textup39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 694--705] has a deviation of $\Omega(n^{1/d})$. This makes our quasirandom algorithm the first known algorithm for this setting, which is optimal both in time and achieved smoothness. We further show that on the hypercube as well, our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.

We show exact values for the worst-case price of anarchy in weighted and unweighted (atomic unsplittable) congestion games, provided that all cost functions are bounded-degree polynomials with nonnegative coefficients. The given values also hold for weighted and unweighted network congestion games.

In this work we study weighted network congestion games with player-specific latency functions where selfish players wish to route their traffic through a shared network. We consider both the case of splittable and unsplittable traffic. Our main findings are as follows. For routing games on parallel links with linear latency functions, we introduce two new potential functions for unsplittable and for splittable traffic, respectively. We use these functions to derive results on the convergence to pure Nash equilibria and the computation of equilibria. For several generalizations of these routing games, we show that such potential functions do not exist. We prove tight upper and lower bounds on the price of anarchy for games with polynomial latency functions. All our results on the price of anarchy translate to general congestion games.

We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a random algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm approximates the idealized process (where the tokens are divisible) on important network topologies surprisingly closely. On d-dimensional torus graphs with n nodes it deviates from the idealized process only by an additive constant. In contrast to that, the randomized rounding approach of Friedrich and Sauerwald [8] can deviate up to Ω(polylog n) and the deterministic algorithm of Rabani, Sinclair and Wanka [23] has a deviation of Ω(n1/d). This makes our quasirandom algorithm the first known algorithm for this setting which is optimal both in time and achieved smoothness. We further show that also on the hypercube our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.

In his seminal work Harsanyi [13] introduced an elegant approach to study non-cooperative games with incomplete information where the players are uncertain about some parameters. To model such games he introduced the Harsanyi transformation, which converts a game with incomplete information to a strategic game where players may have different types. In the resulting Bayesian game players' uncertainty about each others types is described by a probability distribution over all possible type profiles.In this work, we introduce a particular selfish routing game with incomplete information that we call Bayesian routing game. Here, n selfish users wish to assign their traffic to one of m links. Users do not know each others traffic. Following Harsanyi's approach, we introduce for each user a set of possible types.This paper presents a comprehensive collection of results for the Bayesian routing game.We prove, with help of a potential function, that every Bayesian routing game possesses a pure Bayesian Nash equilibrium. For the model of identical links and independent type distribution we give a polynomial time algorithm to compute a pure Bayesian Nash equilibrium.We study structural properties of fully mixed Bayesian Nash equilibria for the model of identical links and show that they maximize individual cost. In general there exists more than one fully mixed Bayesian Nash equilibrium. We characterize the class of fully mixed Bayesian Nash equilibria in the case of independent type distribution.We conclude with results on coordination ratio for the model of identical links for three social cost measures, that is, social cost as expected maximum congestion, sum of individual costs and maximum individual cost. For the latter two we are able to give (asymptotic) tight bounds using our results on fully mixed Bayesian Nash equilibria.To the best of our knowledge this is the first time that mixed Bayesian Nash equilibria have been studied in conjunction with social cost.

We consider the problem of routing n users on m parallel links, under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. Thus, the problem is equivalent to the correspondingly restricted problem of assigning n jobs to m parallel machines. In a pure Nash equilibrium, no user may improve its own individual cost (delay) by unilaterally switching to another link from its set of allowed links. As our main result, we introduce a polynomial time algorithm to compute from any given assignment a pure Nash equilibrium with non-increased makespan. The algorithm gradually changes a given assignment by pushing unsplittable user traffics through a network that is defined by the users and the links. Here, we use ideas from blocking flows. Furthermore, we use similar techniques as in the generic Preflow-Push algorithm to approximate a schedule with minimum makespan, gaining an improved approximation factor of 2 - 1/w1 for identical links, where w1 is the largest user traffic. We extend this result to related links, gaining an approximation factor of 2. Our approximation algorithms run in polynomial time. We close with tight upper bounds on the coordination ratio for pure Nash equilibria.