Abstract: .We present a new methodology for computing approximate
Nash equilibria for two-person non-cooperative games based upon certain
extensions and specializations of an existing optimization approach pre-
viously used for the derivation of xed approximations for this problem.
In particular, the general two-person problem is reduced to an inde -
nite quadratic programming problem of special structure involving the
n x n adjacency matrix of an induced simple graph speci ed by the in-
put data of the game, where n is the number of players' strategies.
Abstract: Consider a network vulnerable to viral infection. The system security software can guarantee
safety only to a limited part of the network. Such limitations result from economy costs or processing
costs. The problem raised is to which part of the network the security software should
be installed, so that to secure as much as possible the network. We model this practical network
scenario as a non-cooperative multi-player game on a graph, with two kinds of players, a set
of attackers and a protector player, representing the viruses and the system security software,
respectively. Each attacker player chooses a node of the graph (or a set of them, via a probability
distribution) to infect. The protector player chooses independently, in a basic case of the
problem, a simple path or an edge of the graph (or a set of them, via a probability distribution)
and cleans this part of the network from attackers. Each attacker wishes to maximize the probability
of escaping its cleaning by the protector. In contrast, the protector aims at maximizing
the expected number of cleaned attackers. We call the two games obtained from the two basic
cases considered, as the Path and the Edge model, respectively. For these two games, we are
interested in the associated Nash equilibria, where no network entity can unilaterally improve
its local objective. We obtain the following results:
• The problem of existence of a pure Nash equilibrium is NP-complete for the Path model.
This opposed to that, no instance of the Edge model possesses a pure Nash equilibrium,
proved in [7].
• In [7] a characterization of mixed Nash equilibria for the Edge model is provided. However,
that characterization only implies an exponential time algorithm for the general case.
Here, combining it with clever exploration of properties of various practical families of
graphs, we compute, in polynomial time, mixed Nash equilibria on corresponding graph
instances. These graph families include, regular graphs, graphs that can be decomposed, in
polynomially time, into vertex disjoint r-regular subgraphs, graphs with perfect matchings
and trees.
• We utilize the notion of social cost [6] for measuring system performance on such scenario;
here is defined to be the utility of the protector. We prove that the corresponding Price of
Anarchy in any mixed Nash equilibria of the game is upper and lower bounded by a linear
function of the number of vertices of the graph.
Abstract: Known general proofs of Nash Theorem (about the existence of Nash Equilibria (NEa) in finite strategic games) rely on the use of a fixed point theorem (e.g. Brouwer or Kakutani. While it seems that there is no general way of proving the existence of Nash equilibria without the use of a fixed point theorem, there do however exist some (not so common in the CS literature) proofs that seem to indicate alternative proof paths, for games of two players. This note discusses two such proofs.
Abstract: In this paper we present a platform for developing mobile, locative and collaborative distributed games comprised of small programmable object technologies (e.g., wireless sensor networks) and traditional networked processors.
The platform is implemented using a combination of JAVA
Standard and Mobile editions, targeting also mobile phones
that have some kind of sensors installed. We briefly present
the architecture of our platform and demonstrate its capabilities by reporting two pervasive multiplayer games. The key
characteristic of these games is that players interact with each
other and their surrounding environment by moving, running
and gesturing as a means to perform game related actions, using small programmable object technologies.
Abstract: We discuss some new algorithmic and complexity issues in
coalitional and dynamic/evolutionary games, related to the understand-
ing of modern sel¯sh and Complex networks.
In particular: (a) We examine the achievement of equilibria via natural
distributed and greedy approaches in networks. (b) We present a model
of a coalitional game in order to capture the anarchy cost and complexity
of constructing equilibria in such situations. (c) We propose a stochastic
approach to some kinds of local interactions in networks, that can be
viewed also as extensions of the classical evolutionary game theoretic
setting.
Abstract: In this paper we propose a new methodology for determining
approximate Nash equilibria of non-cooperative bimatrix games and,
based on that, we provide an efficient algorithm that computes 0.3393-
approximate equilibria, the best approximation till now. The methodology
is based on the formulation of an appropriate function of pairs of
mixed strategies reflecting the maximum deviation of the players¢ payoffs
from the best payoff each player could achieve given the strategy
chosen by the other. We then seek to minimize such a function using
descent procedures. As it is unlikely to be able to find global minima
in polynomial time, given the recently proven intractability of the problem,
we concentrate on the computation of stationary points and prove
that they can be approximated arbitrarily close in polynomial time and
that they have the above mentioned approximation property. Our result
provides the best till now for polynomially computable -approximate
Nash equilibria of bimatrix games. Furthermore, our methodology for
computing approximate Nash equilibria has not been used by others.
Abstract: We focus on the problem of computing approximate Nash equilibria and well-supported approximate Nash equilibria in random bimatrix games, where each player's payoffs are bounded and independent random variables, not necessarily identically distributed, but with common expectations. We show that the completely mixed uniform strategy profile, i.e. the combination of mixed strategies (one per player) where each player plays with equal probability each one of her available pure strategies, is an almost Nash equilibrium for random bimatrix games, in the sense that it is, with high probability, an {\aa}-well-supported Nash equilibrium where {\aa} tends to zero as n tends to infinity.
Abstract: We consider algorithmic questions concerning the existence,
tractability and quality of atomic congestion games, among users that
are considered to participate in (static) selfish coalitions. We carefully
define a coalitional congestion model among atomic players.
Our findings in this model are quite interesting, in the sense that we
demonstrate many similarities with the non–cooperative case. For example,
there exist potentials proving the existence of Pure Nash Equilibria
(PNE) in the (even unrelated) parallel links setting; the Finite Improvement
Property collapses as soon as we depart from linear delays, but
there is an exact potential (and thus PNE) for the case of linear delays,
in the network setting; the Price of Anarchy on identical parallel
links demonstrates a quite surprising threshold behavior: it persists on
being asymptotically equal to that in the case of the non–cooperative
KP–model, unless we enforce a sublogarithmic number of coalitions.
We also show crucial differences, mainly concerning the hardness of algorithmic
problems that are solved efficiently in the non–cooperative case.
Although we demonstrate convergence to robust PNE, we also prove the
hardness of computing them. On the other hand, we can easily construct
a generalized fully mixed Nash Equilibrium. Finally, we propose a new
improvement policy that converges to PNE that are robust against (even
dynamically forming) coalitions of small size, in pseudo–polynomial time.
Keywords. Game Theory, Atomic Congestion Games, Coalitions, Convergence
to Equilibria, Price of Anarchy.
Abstract: We consider algorithmic questions concerning the existence, tractability and quality of Nash equi-
libria, in atomic congestion games among users participating in sel sh coalitions.
We introduce a coalitional congestion model among atomic players and demonstrate many in-
teresting similarities with the non-cooperative case. For example, there exists a potential function
proving the existence of Pure Nash Equilibria (PNE) in the unrelated parallel links setting; in
the network setting, the Finite Improvement Property collapses as soon as we depart from linear
delays, but there is an exact potential (and thus PNE) for linear delays; the Price of Anarchy on
identical parallel links demonstrates a quite surprising threshold behavior: it persists on being
asymptotically equal to that in the case of the non-cooperative KP-model, unless the number of
coalitions is sublogarithmic.
We also show crucial di erences, mainly concerning the hardness of algorithmic problems that
are solved eciently in the non{cooperative case. Although we demonstrate convergence to robust
PNE, we also prove the hardness of computing them. On the other hand, we propose a generalized
fully mixed Nash Equilibrium, that can be eciently constructed in most cases. Finally, we
propose a natural improvement policy and prove its convergence in pseudo{polynomial time to
PNE which are robust against (even dynamically forming) coalitions of small size.
Abstract: We consider algorithmic questions concerning the existence,
tractability and quality of atomic congestion games, among users that
are considered to participate in (static) selfish coalitions. We carefully
define a coalitional congestion model among atomic players.
Our findings in this model are quite interesting, in the sense that we
demonstrate many similarities with the non–cooperative case. For example,
there exist potentials proving the existence of Pure Nash Equilibria
(PNE) in the (even unrelated) parallel links setting; the Finite Improvement
Property collapses as soon as we depart from linear delays, but
there is an exact potential (and thus PNE) for the case of linear delays,
in the network setting; the Price of Anarchy on identical parallel
links demonstrates a quite surprising threshold behavior: it persists on
being asymptotically equal to that in the case of the non–cooperative
KP–model, unless we enforce a sublogarithmic number of coalitions.
We also show crucial differences, mainly concerning the hardness of algorithmic
problems that are solved efficiently in the non–cooperative case.
Although we demonstrate convergence to robust PNE, we also prove the
hardness of computing them. On the other hand, we can easily construct
a generalized fully mixed Nash Equilibrium. Finally, we propose a new
improvement policy that converges to PNE that are robust against (even
dynamically forming) coalitions of small size, in pseudo–polynomial time.
Keywords. Game Theory, Atomic Congestion Games, Coalitions, Convergence
to Equilibria, Price of Anarchy.
Abstract: We study here the effect of concurrent greedy moves of players in atomic congestion games
where n selfish agents (players) wish to select a resource each (out of m resources) so that her selfish delay there is not much. Such games usually admit a global potential that decreases by sequential and selfishly improving moves. However, concurrent moves may not always lead to global convergence. On the other hand, concurrent play is desirable because it might essentially improve the system convergence time to some balanced state. The problem of ?maintaining? global progress while allowing concurrent play is
exactly what is examined and answered here. We examine two orthogonal settings : (i) A game where the players decide their moves without global information, each acting ?freely? by sampling resources randomly and locally deciding to migrate (if the new resource is better) via a random experiment. Here, the resources can have quite arbitrary latency that is load dependent. (ii) An ?organised? setting where the players are prepartitioned into selfish groups (coalitions) and where each coalition does an improving coalitional move.
Here the concurrency is among the members of the coalition. In this second setting, the resources have latency functions that are only linearly dependent on the load, since this is the only case so far where a global potential exists. In both cases (i), (ii) we show that the system converges to an ?approximate? equilibrium very fast (in logarithmic rounds where the logarithm is taken on the maximum value of the global potential). This is interesting, since two quite orthogonal settings lead to the same result. Our work considers concurrent selfish play for arbitrary latencies for the first time. Also, this is the first time where fast coalitional convergence
to an approximate equilibrium is shown. All our results refer to atomic games (ie players are finite and distinct).
Abstract: We study here the effect of concurrent greedy moves of players in atomic
congestion games where n selfish agents (players) wish to select a resource each (out
of m resources) so that her selfish delay there is not much. The problem of “maintaining”
global progress while allowing concurrent play is exactly what is examined
and answered here. We examine two orthogonal settings: (i) A game where the players
decide their moves without global information, each acting “freely” by sampling
resources randomly and locally deciding to migrate (if the new resource is better)
via a random experiment. Here, the resources can have quite arbitrary latency that is
load dependent. (ii) An “organised” setting where the players are pre-partitioned into
selfish groups (coalitions) and where each coalition does an improving coalitional
move. Our work considers concurrent selfish play for arbitrary latencies for the first
time. Also, this is the first time where fast coalitional convergence to an approximate
equilibrium is shown.
Abstract: We study here the effect of concurrent greedy moves of players in
atomic congestion games where n selfish agents (players) wish to select a re-
source each (out of m resources) so that her selfish delay there is not much. The
problem of maintaining global progress while allowing concurrent play is ex-
actly what is examined and answered here. We examine two orthogonal settings :
(i) A game where the players decide their moves without global information, each
acting freely by sampling resources randomly and locally deciding to migrate
(if the new resource is better) via a random experiment. Here, the resources can
have quite arbitrary latency that is load dependent. (ii) An organised setting
where the players are pre-partitioned into selfish groups (coalitions) and where
each coalition does an improving coalitional move. Our work considers concur-
rent selfish play for arbitrary latencies for the first time. Also, this is the first time
where fast coalitional convergence to an approximate equilibrium is shown.
Abstract: In this survey we present some recent advances in the literature
of atomic (mainly network) congestion games. The algorithmic
questions that we are interested in have to do with the existence of pure
Nash equilibria, the efficiency of their construction when they exist, as
well as the gap of the best/worst (mixed in general) Nash equilibria from
the social optima in such games, typically called the Price of Anarchy
and the Price of Stability respectively.
Abstract: We examine multi-player pervasive games that rely on the
use of ad-hoc mobile sensor networks. The unique feature in
such games is that players interact with each other and their
surrounding environment by using movement and presence
as a means of performing game-related actions, utilizing sen-
sor devices. We brie
y discuss the fundamental issues and
challenges related to these type of games and the scenar-
ios associated with them. We have also developed a frame-
work, called Fun in Numbers (FinN) that handles a number
of these issues, such as such as neighbors discovery, local-
ization, synchronization and delay-tolerant communication.
FinN is developed using Java and is based on a multilayer ar-
chitecture, which provides developers with a set of templates
and services for building and operating new games.
Abstract: This chapter is an introduction to the basic concepts and advances of a new field, that of Computational (or Algorithmic) Game Theory. We study the computational complexity of Nash equilibria and review the related algorithms proposed in the literature. Then, given the apparent difficulty of computing exact Nash equilibria, we study the efficient computation of approximate notions of Nash equilibria. Next we deal with several computational issues related to the class of congestion games, which model the selfish behavior of individuals when competing on the usage of a common set of resources. Finally, we study the price of anarchy (in the context of congestion games), which is defined as a measure of the performance degradation due to the the lack of coordination among the involved players.
Abstract: We propose a simple and intuitive cost mechanism which assigns costs for the competitive
usage of m resources by n selfish agents. Each agent has an individual demand; demands are
drawn according to some probability distribution. The cost paid by an agent for a resource
it chooses is the total demand put on the resource divided by the number of agents who
chose that same resource. So, resources charge costs in an equitable, fair way, while each
resource makes no profit out of the agents.
We call our model the Fair Pricing model. Its fair cost mechanism induces a noncooperative
game among the agents. To evaluate the Nash equilibria of this game, we
introduce the Diffuse Price of Anarchy, as an extension of the Price of Anarchy that takes
into account the probability distribution on the demands. We prove:
² Pure Nash equilibria may not exist, unless all chosen demands are identical.
² A fully mixed Nash equilibrium exists for all possible choices of the demands. Further
on, the fully mixed Nash equilibrium is the unique Nash equilibrium in case there are
only two agents.
² In the worst-case choice of demands, the Price of Anarchy is £(n); for the special case
of two agents, the Price of Anarchy is less than 2 ¡ 1
m .
² Assume now that demands are drawn from a bounded, independent probability distribution,
where all demands are identically distributed, and each demand may not exceed
some (universal for the class) constant times its expectation. It happens that the constant
is just 2 when each demand is distributed symmetrically around its expectation.
We prove that, for asymptotically large games where the number of agents tends to
infinity, the Diffuse Price of Anarchy is at most that universal constant. This implies
the first separation between Price of Anarchy and Diffuse Price of Anarchy.
Towards the end, we consider two closely related cost sharing models, namely the Average
Cost Pricing and the Serial Cost Sharing models, inspired by Economic Theory. In contrast
to the Fair Pricing model, we prove that pure Nash equilibria do exist for both these models.
Abstract: We investigate the existence of optimal tolls for atomic symmetric
network congestion games with unsplittable traffic and arbitrary non-negative and
non-decreasing latency functions.We focus on pure Nash equilibria and a natural
toll mechanism, which we call cost-balancing tolls. A set of cost-balancing tolls
turns every path with positive traffic on its edges into a minimum cost path. Hence
any given configuration is induced as a pure Nash equilibrium of the modified
game with the corresponding cost-balancing tolls. We show how to compute in
linear time a set of cost-balancing tolls for the optimal solution such that the total
amount of tolls paid by any player in any pure Nash equilibrium of the modified
game does not exceed the latency on the maximum latency path in the optimal
solution. Our main result is that for congestion games on series-parallel networks
with increasing latencies, the optimal solution is induced as the unique pure Nash
equilibrium of the game with the corresponding cost-balancing tolls. To the best
of our knowledge, only linear congestion games on parallel links were known to
admit optimal tolls prior to this work. To demonstrate the difficulty of computing
a better set of optimal tolls, we show that even for 2-player linear congestion
games on series-parallel networks, it is NP-hard to decide whether the optimal
solution is the unique pure Nash equilibrium or there is another equilibrium of
total cost at least 6/5 times the optimal cost.
Abstract: In this paper we study the notion of the Evolutionary Stable
Strategies (ESS) in evolutionary games and we demonstrate their qualitative
difference from the Nash Equilibria, by showing that a random
evolutionary game has on average exponentially less number of ESS than
the number of Nash Equilibria in the underlying symmetric 2-person
game with random payoffs.
Abstract: Pervasive games are a new type of digital games that combines game and physical reality within the gameplay. This novel game type raises unprecedented research and design challenges for developers and urges the exploration of new technologies and methods to create high quality game experiences and design novel and compelling forms of content for the players. This chapter follows a systematic approach to explore the landscape of pervasive gaming. First, the authors approach pervasive games from a theoretical point of view, defining the four axes of pervasive games design, introducing the concept of game world persistency, and describing aspects of spatially/temporally/socially expanded games. Then, they present ten pervasive game projects, classified in five genres based on their playing environment and features. Following that, the authors present a comparative view of those projects with respect to several design aspects: communication and localization, context and personal awareness aspects, information model, player equipment, and game space visualization. Last, the authors highlight current trends, design principles, and future directions for pervasive games development.
Abstract: In the recent years we have seen an increased popularity in game development using Smartphones, which has provided an increasingly ubiquitous platform for designing games. In this paper we wish to investigate the use of a modern Smartphone’s capabilities in game
development by implementing and evaluating a classic game on the iPhone platform. We identify the limitations and possibilities that this field offers to the different aspect of game design.
Abstract: We here present Fun in Numbers (FinN), a framework for developing pervasive applications and interactive installations for entertainment and educational purposes. Using ad hoc mobile wireless sensor network nodes as the enabling devices, FinN allows for the quick prototyping of applications that utilize input from multiple physical sources (sensors and other means of interfacing), by o ffering a set of programming templates and services, such as topology discovery, localization and synchronization, that hide the underlying complexity. We present the target application domains of FinN, along with a set of multiplayer games and interactive installations. We describe the overall architecture of our platform
and discuss some key implementation issues of the application domains. Finally, we present the experience gained by deploying the applications developed with our platform.
Abstract: In this work we study the tractability of well supported approximate
Nash Equilibria (SuppNE in short) in bimatrix games. In view
of the apparent intractability of constructing Nash Equilibria (NE in
short) in polynomial time, even for bimatrix games, understanding the
limitations of the approximability of the problem is of great importance.
We initially prove that SuppNE are immune to the addition of arbitrary
real vectors to the rows (columns) of the row (column) player¢s
payoff matrix. Consequently we propose a polynomial time algorithm
(based on linear programming) that constructs a 0.5−SuppNE for arbitrary
win lose games.
We then parameterize our technique for win lose games, in order to
apply it to arbitrary (normalized) bimatrix games. Indeed, this new technique
leads to a weaker {\"o}−SuppNE for win lose games, where {\"o} = √5−1
2
is the golden ratio. Nevertheless, this parameterized technique extends
nicely to a technique for arbitrary [0, 1]−bimatrix games, which assures
a 0.658−SuppNE in polynomial time.
To our knowledge, these are the first polynomial time algorithms providing
{\aa}−SuppNE of normalized or win lose bimatrix games, for some
nontrivial constant {\aa} ∈ [0, 1), bounded away from 1.
Abstract: In large-scale or evolving networks, such as the Internet,
there is no authority possible to enforce a centralized traffic management.
In such situations, Game Theory and the concepts of Nash equilibria
and Congestion Games [8] are a suitable framework for analyzing
the equilibrium effects of selfish routes selection to network delays.
We focus here on layered networks where selfish users select paths to
route their loads (represented by arbitrary integer weights). We assume
that individual link delays are equal to the total load of the link. We
focus on the algorithm suggested in [2], i.e. a potential-based method
for finding pure Nash equilibria (PNE) in such networks. A superficial
analysis of this algorithm gives an upper bound on its time which is
polynomial in n (the number of users) and the sum of their weights. This
bound can be exponential in n when some weights are superpolynomial.
We provide strong experimental evidence that this algorithm actually
converges to a PNE in strong polynomial time in n (independent of the
weights values). In addition we propose an initial allocation of users
to paths that dramatically accelerates this algorithm, compared to an
arbitrary initial allocation. A by-product of our research is the discovery
of a weighted potential function when link delays are exponential to their
loads. This asserts the existence of PNE for these delay functions and
extends the result of
Abstract: We describe the design and implementation of secure and robust protocol and system for a national electronic lottery. Electronic lotteries at a national level are a viable cost effective alternative to mechanical ones when there is a business need to support many types of rdquogames of chancerdquo and to allow increased drawing frequency. Electronic lotteries are, in fact, extremely high risk financial application: If one discovers a way to predict or otherwise claim the winning numbers (even once) the result is huge financial damages. Moreover, the e-lottery process is complex, which increases the possibility of fraud or costly accidental failures. In addition, a national lottery must adhere to auditability and (regulatory) fairness requirements regarding its drawings. Our mechanism, which we believe is the first one of its kind to be described in the literature, builds upon a number of cryptographic primitives that ensure the unpredictability of the winning numbers, the prevention of their premature leakages and prevention of fraud. We also provide measures for auditability, fairness, and trustworthiness of the process. Besides cryptography, we incorporate security mechanisms that eliminate various risks along the entire process. Our system which was commissioned by a national organization, was implemented in the field and has been operational and active for a while, now.
Abstract: The presentwork considers the following computational problem:
Given any finite game in normal form G and the corresponding
infinitely repeated game G∞, determine in polynomial time (wrt1 the representation
ofG) a profile of strategies for the players inG∞ that is an equilibrium
point wrt the limit-of-means payoff. The problem has been solved
for two players [10], based mainly on the implementability of the threats
for this case. Nevertheless, [4] demonstrated that the traditional notion of
threats is a computationally hard problem for games with at least 3 players
(see also [8]). Our results are the following: (i) We propose an alternative
notion of correlated threats, which is polynomial time computable
(and therefore credible). Our correlated threats are also more severe than
the traditional notion of threats, but not overwhelming for any individual
player. (ii) When for the underlying game G there is a correlated strategy
with payoff vector strictly larger than the correlated threats vector,
we efficiently compute a polynomial–size (wrt the description of G) equilibrium
point for G∞, for any constant number of players. (iii) Otherwise,
we demonstrate the construction of an equilibrium point for an arbitrary
number of players and up to 2 concurrently positive payoff coordinates in
any payoff vector of G. This completely resolves the cases of 3 players, and
provides a direction towards handling the cases of more than 3 players. It
is mentioned that our construction is not a Nash equilibrium point, because
the correlated threats we use are implemented via, not only full synchrony
(as in [10]), but also coordination of the other players¢ actions. But
this seems to be a fair trade-off between efficiency of the construction and
players¢ coordination, in particular because it only affects the punishments
(which are anticipated never to be used).
Abstract: Evolutionary Game Theory is the study of strategic interactions
among large populations of agents who base their decisions on simple,
myopic rules. A major goal of the theory is to determine broad classes
of decision procedures which both provide plausible descriptions of selfish
behaviour and include appealing forms of aggregate behaviour. For example,
properties such as the correlation between strategies¢ growth rates
and payoffs, the connection between stationary states and the well-known
game theoretic notion of Nash equilibria, as well as global guarantees of
convergence to equilibrium, are widely studied in the literature.
Our paper can be seen as a quick introduction to Evolutionary Game
Theory, together with a new research result and a discussion of many
algorithmic and complexity open problems in the area. In particular, we
discuss some algorithmic and complexity aspects of the theory, which
we prefer to view more as Game Theoretic Aspects of Evolution rather
than as Evolutionary Game Theory, since the term “evolution” actually
refers to strategic adaptation of individuals¢ behaviour through a
dynamic process and not the traditional evolution of populations. We
consider this dynamic process as a self-organization procedure which,
under certain conditions, leads to some kind of stability and assures robustness
against invasion. In particular, we concentrate on the notion of
the Evolutionary Stable Strategies (ESS). We demonstrate their qualitative
difference from Nash Equilibria by showing that symmetric 2-person
games with random payoffs have on average exponentially less ESS than
Nash Equilibria. We conclude this article with some interesting areas of
future research concerning the synergy of Evolutionary Game Theory
and Algorithms.
Abstract: We study the fundamental problem of computing an arbitrary Nash equilibrium in bimatrix games.
We start by proposing a novel characterization of the set of Nash equilibria, via a bijective map to the solution set of a (parameterized) quadratic program, whose feasible space is the (highly structured) set of correlated equilibria.
We then proceed by proposing new subclasses of bimatrix games for which either an exact polynomial-time construction, or at least a FPTAS, is possible. In particular, we introduce the notion of mutual (quasi-) concavity of a bimatrix game, which assures (quasi-) convexity of our quadratic program, for at least one value of the parameter. For mutually concave bimatrix games, we provide a polynomial-time computation of a Nash equilibrium, based on the polynomial tractability of convex quadratic programming. For the mutually quasiconcave games, we provide (to our knowledge) the first FPTAS for the construction of a Nash equilibrium.
Of course, for these new polynomially tractable subclasses of bimatrix games to be useful, polynomial-time certificates are also necessary that will allow us to efficiently identify them. Towards this direction, we provide various characterizations of mutual concavity, which allow us to construct such a certificate. Interestingly, these characterizations also shed light to some structural properties of the bimatrix games satisfying mutual concavity. This subclass entirely contains the most popular subclass of polynomial-time solvable bimatrix games, namely, all the constant-sum games (rank-0 games). It is though incomparable to the subclass of games with fixed rank [KT07]: Even rank-1 games may not be mutually concave (eg, Prisoner's dilemma), but on the other hand, there exist mutually concave games of arbitrary (even full) rank. Finally, we prove closeness of mutual concavity under (Nash equilibrium preserving) positive affine transformations of bimatrix games having the same scaling factor for both payoff matrices. For different scaling factors the property is not necessarily preserved.
Abstract: Fun in Numbers (FinN) is a platform for developing and playing mobile, locative and collaborative distributed games
using wireless sensors. Using FinN, a very large and diverse set of games can be enhanced, by maximizing the on-game
experience and collecting statistics for off-line, web-based view. At the same time the essence of such games remains the
same: fun in large numbers, in every place and at any time. FinN is implemented using a combination of JAVA Standard
and Mobile editions, while on the hardware part we use wireless sensor devices, called Sun SPOTs. In the future, mobile
phones that have some kind of sensors embedded, or other custom devices can be used for the same purpose. We report a
number of examples of games created with FinN and briefly present the architecture of our platform.
Abstract: We discuss two different ways of having fun with two different kinds of games: On the one hand, we present a framework for developing multiplayer pervasive games that rely on the use of mobile sensor networks. On the other hand, we show how to exploit game theoretic concepts in order to study the graph-theoretic problem of vertex coloring.
Abstract: Distributed algorithm designers often assume that system processes execute the same predefined software. Alternatively, when they do not assume that, designers turn to non-cooperative games and seek an outcome that corresponds to a rough consensus when no coordination is allowed. We argue that both assumptions are inapplicable in many real distributed systems, e.g., the Internet, and propose designing self-stabilizing and Byzantine fault-tolerant distributed game authorities. Once established, the game authority can secure the execution of any complete information game. As a result, we reduce costs that are due to the processes¢ freedom of choice. Namely, we reduce the price of malice.
Abstract: Green Awareness in Action (GAIA) is introducing game challenges to the school community, where real-world sensor data produced inside school buildings are used,
aiming to increase awareness and reduce energy consumption. An initial small-scale in-school evaluation trial of the games¢ deployment is reported here.
Abstract: In this work we discuss Fun in Numbers, a software platform for implementing multiplayer games and interactive installations, that are based on the use of ad hoc mobile sensing devices. We utilize a detailed log of a three-day long public showcase as a basis to discuss the implementation issues related to a set of games and installations, which are examples of this unique category of applications, utilizing a blend of technologies. We discuss their fundamental concepts and features, also arguing that they have many aspects and potential uses. The architecture of the platform and implementation details are highlighted in this work, along with detailed descriptions of the protocols used. Our experiments shed light on a number of key issues, such as network scaling and real-time performance, and we provide experiments regarding cross-layer software issues. We additionally provide data showing that such games and installations can be efficiently supported by our platform, with as many as 50 concurrent players in the same physical space. These results are backed up by a user evaluation study from a large sample of 136 visitors, which shows that such applications can be seriously fun.
Abstract: In load balancing games, there is a set of available servers and
a set of clients; each client wishes to run her job on some server. Clients
are sel¯sh and each of them selects a server that, given an assignment
of the other clients to servers, minimizes the latency she experiences
with no regard to the global optimum. In order to mitigate the e®ect of
sel¯shness on the e±ciency, we assign taxes to the servers. In this way,
we obtain a new game where each client aims to minimize the sum of
the latency she experiences and the tax she pays. Our objective is to
¯nd taxes so that the worst equilibrium of the new game is as e±cient
as possible. We present new results concerning the impact of taxes on
the e±ciency of equilibria, with respect to the total latency of all clients
and the maximum latency (makespan).
Abstract: The possibilities offered by utilizing sensors and pervasive computing technologies for creating large-scale multiplayer games are discussed in this chapter. Such game installations constitute a new social form of play taking place in public spaces. A main characteristic is the need to scale to a large number of users and engage players located simultaneously in dispersed areas, thus connected both on a local and Internet level. Fun in Numbers is a platform for developing and playing mobile, locative and collaborative distributed games and interactive installations, based on the participation of large numbers of people and their movement in the physical space. Players interact with each other using a wide range of hardware devices that are either generic (smartphones) or specific (sensor devices A set of related fundamental issues drawn upon the experience from several public events, where the FinN platform supported as many as 50 local users at the same time, is hereby presented.
Abstract: We present here, Fun in Numbers, a framework for developing multiplayer pervasive games that rely on the use of ad hoc mobile sensor networks. The unique feature in such games is that players interact with each other and their surrounding environment by using movement and presence as a means of performing game-related actions, utilizing sensor devices. We present the fundamental issues and challenges related to these type of games and the scenarios associated with them is provided. Our framework is developed using Java and is based on a multilayer architecture, which provides developers with a set of templates and services for building and operating new games. Our framework handles a number of challenging fundamental and practical issues, such as synchronization, network congestion, delay-tolerant communication and neighbors discovery. We also present our platform and identify issues that arise in pervasive games which utilize sensor network nodes. The implemented games show how to use non-conventional user interface methods to breathe new life into familiar concepts, like the multiplayer games played out in open space.
Abstract: In this work, we showcase a set of implemented multiplayer games and interactive installations based on Fun in Numbers (FINN). FinN allows the quick prototyping of applications that utilize input from multiple physical sources (sensors and other means of interfacing), by offering a set of programming templates and services, such as proximity, localization and synchronization, that hide the underlying complexity.
Abstract: We study network load games, a class of routing games in
networks which generalize sel{\^A}¯sh routing games on networks consisting
of parallel links. In these games, each user aims to route some tra{\^A}±c from
a source to a destination so that the maximum load she experiences in the
links of the network she occupies is minimum given the routing decisions
of other users. We present results related to the existence, complexity,
and price of anarchy of Pure Nash Equilibria for several network load
games. As corollaries, we present interesting new statements related to
the complexity of computing equilibria for sel{\^A}¯sh routing games in net-
works of restricted parallel links.
Abstract: We study the fundamental problem 2NASH of computing a Nash equilibrium (NE) point in bimatrix games. We start by proposing a novel characterization of the NE set, via a bijective map to the solution set of a parameterized quadratic program (NEQP), whose feasible space is the highly structured set of correlated equilibria (CE). This is, to our knowledge, the first characterization of the subset of CE points that are in “1–1” correspondence with the NE set of the game, and contributes to the quite lively discussion on the relation between the spaces of CE and NE points in a bimatrix game (e.g., [15], [26] and [33]).
We proceed with studying a property of bimatrix games, which we call mutually concavity (MC), that assures polynomial-time tractability of 2NASH, due to the convexity of a proper parameterized quadratic program (either NEQP, or a parameterized variant of the Mangasarian & Stone formulation [23]) for a particular value of the parameter. We prove various characterizations of the MC-games, which eventually lead us to the conclusion that this class is equivalent to the class of strategically zero-sum (SZS) games of Moulin & Vial [25]. This gives an alternative explanation of the polynomial-time tractability of 2NASH for these games, not depending on the solvability of zero-sum games. Moreover, the recognition of the MC-property for an arbitrary game is much faster than the recognition SZS-property. This, along with the comparable time-complexity of linear programs and convex quadratic programs, leads us to a much faster algorithm for 2NASH in MC-games.
We conclude our discussion with a comparison of MC-games (or, SZS-games) to kk-rank games, which are known to admit for 2NASH a FPTAS when kk is fixed [18], and a polynomial-time algorithm for k=1k=1 [2]. We finally explore some closeness properties under well-known NE set preserving transformations of bimatrix games.
Abstract: In sponsored search auctions, advertisers compete for a number
of available advertisement slots of different quality. The
auctioneer decides the allocation of advertisers to slots using
bids provided by them. Since the advertisers may act
strategically and submit their bids in order to maximize their
individual objectives, such an auction naturally defines a
strategic game among the advertisers. In order to quantify
the efficiency of outcomes in generalized second price auctions,
we study the corresponding games and present new
bounds on their price of anarchy, improving the recent results
of Paes Leme and Tardos [16] and Lucier and Paes
Leme [13]. For the full information setting, we prove a surprisingly
low upper bound of 1.282 on the price of anarchy
over pure Nash equilibria. Given the existing lower bounds,
this bound denotes that the number of advertisers has almost
no impact on the price of anarchy. The proof exploits
the equilibrium conditions developed in [16] and follows by
a detailed reasoning about the structure of equilibria and a
novel relation of the price of anarchy to the objective value
of a compact mathematical program. For more general equilibrium
classes (i.e., mixed Nash, correlated, and coarse correlated
equilibria), we present an upper bound of 2.310 on
the price of anarchy. We also consider the setting where
advertisers have incomplete information about their competitors
and prove a price of anarchy upper bound of 3.037
over Bayes-Nash equilibria. In order to obtain the last two
bounds, we adapt techniques of Lucier and Paes Leme [13]
and significantly extend them with new arguments
Abstract: In routing games, the network performance at equilibrium can be significantly improved if we remove some edges from the network. This counterintuitive fact, widely known as Braess's paradox, gives rise to the (selfish) network design problem, where we seek to recognize routing games suffering from the paradox, and to improve the equilibrium performance by edge removal. In this work, we investigate the computational complexity and the approximability of the network design problem for non-atomic bottleneck routing games, where the individual cost of each player is the bottleneck cost of her path, and the social cost is the bottleneck cost of the network. We first show that bottleneck routing games do not suffer from Braess's paradox either if the network is series-parallel, or if we consider only subpath-optimal Nash flows. On the negative side, we prove that even for games with strictly increasing linear latencies, it is NP-hard not only to recognize instances suffering from the paradox, but also to distinguish between instances for which the Price of Anarchy (PoA) can decrease to 1 and instances for which the PoA is as large as \Omega(n^{0.121}) and cannot improve by edge removal. Thus, the network design problem for such games is NP-hard to approximate within a factor of O(n^{0.121-\eps}), for any constant \eps > 0. On the positive side, we show how to compute an almost optimal subnetwork w.r.t. the bottleneck cost of its worst Nash flow, when the worst Nash flow in the best subnetwork routes a non-negligible amount of flow on all used edges. The running time is determined by the total number of paths, and is quasipolynomial when the number of paths is quasipolynomial.
Abstract: We study the performance of approximate Nash equilibria for congestion
games with polynomial latency functions. We consider how much the price of anarchy
worsens and how much the price of stability improves as a function of the
approximation factor . We give tight bounds for the price of anarchy of atomic and
non-atomic congestion games and for the price of stability of non-atomic congestion
games. For the price of stability of atomic congestion games we give non-tight
bounds for linear latencies. Our results not only encompass and generalize the existing
results of exact equilibria to -Nash equilibria, but they also provide a unified
approach which reveals the common threads of the atomic and non-atomic price of
anarchy results. By expanding the spectrum, we also cast the existing results in a new
light.
Abstract: We study network connection games where the nodes of a networ
k perform edge swaps
in order to improve their communication costs. For the model
proposed by [2], in which the selfish
cost of a node is the sum of all shortest path distances to the o
ther nodes, we use the probabilistic
method to provide a new, structural characterization of equ
ilibrium graphs. We show how to use this
characterization in order to prove upper bounds on the diame
ter of equilibrium graphs in terms of the
size of the largest
k
-vicinity (defined as the the set of vertices within distance
k
from a vertex), for
any
k
≥
1 and in terms of the number of edges, thus settling positivel
y a conjecture of [2] in the cases
of graphs of large
k
-vicinity size (including graphs of large maximum degree) a
nd of graphs which are
dense enough.
Next, we present a new swap-based network creation game, in w
hich selfish costs depend on the imme-
diate neighborhood of each node; in particular, the profit of
a node is defined as the sum of the degrees
of its neighbors. We prove that, in contrast to the previous m
odel, this network creation game admits
an exact potential, and also that any equilibrium graph cont
ains an induced star. The existence of the
potential function is exploited in order to show that an equi
librium can be reached in expected polyno-
mial time even in the case where nodes can only acquire limite
d knowledge concerning non-neighboring
nodes.
Abstract: In this paper we study the support sizes of evolutionary stable strategies (ESS) in random
evolutionary games. We prove that, when the elements of the payo matrix behave either as uniform,
or normally distributed random variables, almost all ESS have support sizes o(n), where n is the
number of possible types for a player. Our arguments are based exclusively on a stability property
that the payo submatrix indicated by the support of an ESS must satisfy.
We then combine this result with a recent result of McLennan and Berg (2005), concerning the
expected number of Nash Equilibria in normal{random bimatrix games, to show that the expected
number of ESS is signi cantly smaller than the expected number of symmetric Nash equilibria of the
underlying symmetric bimatrix game.
Abstract: In this paper we present an implementation and performance evaluation of a descent algorithm that was proposed in \cite{tsaspi} for the computation of approximate Nash equilibria of non-cooperative bi-matrix games. This algorithm, which achieves the best polynomially computable \epsilon-approximate equilibria till now, is applied here to several problem instances designed so as to avoid the existence of easy solutions. Its performance is analyzed in terms of quality of approximation and speed of convergence. The results demonstrate significantly better performance than the theoretical worst case bounds, both for the quality of approximation and for the speed of convergence. This motivates further investigation into the intrinsic characteristics of descent algorithms applied to bi-matrix games. We discuss these issues and provide some insights about possible variations and extensions of the algorithmic concept that could lead to further understanding of the complexity of computing equilibria. We also prove here a new significantly better bound on the number of loops required for convergence of the descent algorithm.
Abstract: Pervasive games represent a radically new game form that extends
gaming experiences out into the physical world, weaving ICTs
into the fabric of players’ real environment. This emerging type of
games is rather challenging for developers who are engaged in
exploring new technologies and methods to achieve high quality
interactive experience for players. This paper follows a systematic
approach to explore the landscape of pervasive gaming. First, we
present ten representative pervasive game projects, classified in
five genres based on their playing environment and features.
Then, we present a comparative view of those projects with
respect to several design aspects. Last, we shed light on current
trends, design principles and future directions for pervasive games
development.
Abstract: We consider applications of probabilistic techniques in the
framework of algorithmic game theory. We focus on three distinct case
studies: (i) The exploitation of the probabilistic method to demonstrate
the existence of approximate Nash equilibria of logarithmic support sizes
in bimatrix games; (ii) the analysis of the statistical conflict that mixed
strategies cause in network congestion games; (iii) the effect of coalitions
in the quality of congestion games on parallel links.
Abstract: We focus on the problem of computing approximate Nash equilibria and well-supported approximate Nash equilibria in random bimatrix games, where each player's payoffs are bounded and independent random variables, not necessarily identically distributed, but with almost common expectations. We show that the completely mixed uniform strategy profile, i.e., the combination of mixed strategies (one per player) where each player plays with equal probability each one of her available pure strategies, is with high probability a TeX -Nash equilibrium and a TeX -well supported Nash equilibrium, where n is the number of pure strategies available to each player. This asserts that the completely mixed, uniform strategy profile is an almost Nash equilibrium for random bimatrix games, since it is, with high probability, an ϵ-well-supported Nash equilibrium where ϵ tends to zero as n tends to infinity.
Abstract: A collection of pervasive street games is presented in this paper, that constitute a new social form of play taking place in public spaces, such as city parks, public spaces and streets. The main characteristic of these games is the ability to scale to a large number of players (in some cases involving more than 40 players) and can engage players located simultaneously in dispersed areas. Players interact with each other using a wide range of hardware devices that are either generic (such as smart phones) or specific (such as wireless sensor devices). We discuss a set of fundamental issues related to game design emphasizing on the one hand the interaction of the players with the ubiquitous computing environment and on the other hand the embedding of the game rules within the environment. The games are developed using open source technologies and evaluated in a series of events such as the Athens Plaython 2012 festival. The feedback received from the players indicates that this new form of gaming is indeed very promising.
Abstract: Distributed algorithm designers often assume that system processes execute the same predefined software. Alternatively, when they do not assume that, designers turn to non-cooperative games and seek an outcome that corresponds to a rough consensus when no coordination is allowed. We argue that both assumptions are inapplicable in many real distributed systems, e.g., the Internet, and propose designing self-stabilizing and Byzantine fault-tolerant distributed game authorities. Once established, the game authority can secure the execution of any complete information game. As a result, we reduce costs that are due to the processes¢ freedom of choice. Namely, we reduce the price of malice.
Abstract: What is the price of anarchy when unsplittable demands are routed
selfishly in general networks with load-dependent edge delays? Motivated by
this question we generalize the model of [14] to the case of weighted congestion
games.We show that varying demands of users crucially affect the nature of these
games, which are no longer isomorphic to exact potential games, even for very
simple instances. Indeed we construct examples where even a single-commodity
(weighted) network congestion game may have no pure Nash equilibrium.
On the other hand, we study a special family of networks (which we call the
-layered networks) and we prove that any weighted congestion game on such
a network with resource delays equal to the congestions, possesses a pure Nash
Equilibrium. We also show how to construct one in pseudo-polynomial time.
Finally, we give a surprising answer to the question above for such games: The
price of anarchy of any weighted -layered network congestion game with m
edges and edge delays equal to the loads, is {\`E} logm
log logm.
Abstract: We study computational and coordination efficiency issues of
Nash equilibria in symmetric network congestion games. We first propose
a simple and natural greedy method that computes a pure Nash equilibrium
with respect to traffic congestion in a network. In this algorithm
each user plays only once and allocates her traffic to a path selected via
a shortest path computation. We then show that this algorithm works
for series-parallel networks when users are identical or when users are of
varying demands but have the same best response strategy for any initial
network traffic. We also give constructions where the algorithm fails if
either the above condition is violated (even for series-parallel networks)
or the network is not series-parallel (even for identical users). Thus, we
essentially indicate the limits of the applicability of this greedy approach.
We also study the price of anarchy for the objective of maximum
latency. We prove that for any network of m uniformly related links and
for identical users, the price of anarchy is {\`E}( logm
log logm).
Abstract: We study congestion games where players aim to access a set of resources. Each player has a set of possible strategies and each resource has a function associating the latency it incurs to the players using it. Players are non–cooperative and each wishes to follow strategies that minimize her own latency with no regard to the global optimum. Previous work has studied the impact of this selfish behavior to system performance. In this paper, we study the question of how much the performance can be improved if players are forced to pay taxes for using resources. Our objective is to extend the original game so that selfish behavior does not deteriorate performance. We consider atomic congestion games with linear latency functions and present both negative and positive results. Our negative results show that optimal system performance cannot be achieved even in very simple games. On the positive side, we show that there are ways to assign taxes that can improve the performance of linear congestion games by forcing players to follow strategies where the total latency suffered is within a factor of 2 of the minimum possible; this result is shown to be tight. Furthermore, even in cases where in the absence of taxes the system behavior may be very poor, we show that the total disutility of players (latency plus taxes) is not much larger than the optimal total latency. Besides existential results, we show how to compute taxes in time polynomial in the size of the game by solving convex quadratic programs. Similar questions have been extensively studied in the model of non-atomic congestion games. To the best of our knowledge, this is the first study of the efficiency of taxes in atomic congestion games.
Abstract: In this work, we discuss multiplayer pervasive
games that rely on the use of ad hoc mobile sensor networks.
The unique feature in such games is that players interact
with each other and their surrounding environment by using
movement and presence as a means of performing game-related
actions, utilizing sensor devices. We discuss the fundamental
issues and challenges related to these type of games and the
scenarios associated with them. We also present and evaluate
an example of such a game, called the “Hot Potato”, developed
using the Sun SPOT hardware platform. We provide a set of
experimental results, so as to both evaluate our implementation
and also to identify issues that arise in pervasive games which
utilize sensor network nodes, which show that there is great
potential in this type of games.
Abstract: We consider non-cooperative unsplittable congestion games where players share resources, and each player's strategy is pure and consists of a subset of the resources on which it applies a fixed weight. Such games represent unsplittable routing flow games and also job allocation games. The congestion of a resource is the sum of the weights of the players that use it and the player's cost function is the sum of the utilities of the resources on its strategy. The social cost is the total weighted sum of the player's costs. The quality of Nash equilibria is determined by the price of anarchy (PoA) which expresses how much worse is the social outcome in the worst equilibrium versus the optimal coordinated solution. In the literature the predominant work has only been on games with polynomial utility costs, where it has been proven that the price of anarchy is bounded by the degree of the polynomial. However, no results exist on general bounds for non-polynomial utility functions.
Here, we consider general versions of these games in which the utility of each resource is an arbitrary non-decreasing function of the congestion. In particular, we consider a large family of superpolynomial utility functions which are asymptotically larger than any polynomial. We demonstrate that for every such function there exist games for which the price of anarchy is unbounded and increasing with the number of players (even if they have infinitesimal weights) while network resources remain fixed. We give tight lower and upper bounds which show this dependence on the number of players. Furthermore we provide an exact characterization of the PoA of all congestion games whose utility costs are bounded above by a polynomial function. Heretofore such results existed only for games with polynomial cost functions.
Abstract: Let M be a single s-t network of parallel links with load dependent latency functions shared by an infinite number of selfish users. This may yield a Nash equilibrium with unbounded Coordination Ratio [E. Koutsoupias, C. Papadimitriou, Worst-case equilibria, in: 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS, vol. 1563, 1999, pp. 404-413; T. Roughgarden, E. Tardos, How bad is selfish routing? in: 41st IEEE Annual Symposium of Foundations of Computer Science, FOCS, 2000, pp. 93-102]. A Leader can decrease the coordination ratio by assigning flow {\'a}r on M, and then all Followers assign selfishly the (1-{\'a})r remaining flow. This is a Stackelberg Scheduling Instance(M,r,{\'a}),0≤{\'a}≤1. It was shown [T. Roughgarden, Stackelberg scheduling strategies, in: 33rd Annual Symposium on Theory of Computing, STOC, 2001, pp. 104-113] that it is weakly NP-hard to compute the optimal Leader's strategy. For any such network M we efficiently compute the minimum portion @b"M of flow r>0 needed by a Leader to induce M's optimum cost, as well as her optimal strategy. This shows that the optimal Leader's strategy on instances (M,r,@a>=@b"M) is in P. Unfortunately, Stackelberg routing in more general nets can be arbitrarily hard. Roughgarden presented a modification of Braess's Paradox graph, such that no strategy controlling {\'a}r flow can induce ≤1/{\'a} times the optimum cost. However, we show that our main result also applies to any s-t net G. We take care of the Braess's graph explicitly, as a convincing example. Finally, we extend this result to k commodities. A conference version of this paper has appeared in [A. Kaporis, P. Spirakis, The price of optimum in stackelberg games on arbitrary single commodity networks and latency functions, in: 18th annual ACM symposium on Parallelism in Algorithms and Architectures, SPAA, 2006, pp. 19-28]. Some preliminary results have also appeared as technical report in [A.C. Kaporis, E. Politopoulou, P.G. Spirakis, The price of optimum in stackelberg games, in: Electronic Colloquium on Computational Complexity, ECCC, (056), 2005].
Abstract: We study the load balancing problem in the context of a set of clients each
wishing to run a job on a server selected among a subset of permissible servers for
the particular client. We consider two different scenarios. In selfish load balancing,
each client is selfish in the sense that it chooses, among its permissible servers, to
run its job on the server having the smallest latency given the assignments of the
jobs of other clients to servers. In online load balancing, clients appear online and,
when a client appears, it has to make an irrevocable decision and assign its job to
one of its permissible servers. Here, we assume that the clients aim to optimize some
global criterion but in an online fashion. A natural local optimization criterion that
can be used by each client when making its decision is to assign its job to that server that gives the minimum increase of the global objective. This gives rise to greedy
online solutions. The aim of this paper is to determine how much the quality of load
balancing is affected by selfishness and greediness.
We characterize almost completely the impact of selfishness and greediness in
load balancing by presenting new and improved, tight or almost tight bounds on the
price of anarchy of selfish load balancing as well as on the competitiveness of the
greedy algorithm for online load balancing when the objective is to minimize the
total latency of all clients on servers with linear latency functions. In addition, we
prove a tight upper bound on the price of stability of linear congestion games.
Abstract: In this work we present two mobile, locative and collaborative distributed games that are played using wireless sensor
devices. We briefly present the architecture of the two games
and demonstrate their capabilities. The key characteristic of
these games is that players interact with each other and their
surrounding environment by moving, running and gesturing as a mean to perform game related actions, using sensor devices. We demonstrate our system by implementing it using
a combination of JAVA Standard and Mobile editions.
Abstract: In view of the apparent intractability of constructing Nash Equilibria (NE
in short) in polynomial time, even for bimatrix games, understanding the limitations
of the approximability of the problem is an important challenge.
In this work we study the tractability of a notion of approximate equilibria in bimatrix
games, called well supported approximate Nash Equilibria (SuppNE in short).
Roughly speaking, while the typical notion of approximate NE demands that each
player gets a payoff at least an additive term less than the best possible payoff, in a
SuppNE each player is assumed to adopt with positive probability only approximate
pure best responses to the opponent¢s strategy.
As a first step, we demonstrate the existence of SuppNE with small supports and
at the same time good quality. This is a simple corollary of Alth{\"o}fer¢s Approximation
Lemma, and implies a subexponential time algorithm for constructing SuppNE of
arbitrary (constant) precision.
We then propose algorithms for constructing SuppNE in win lose and normalized
bimatrix games (i.e., whose payoff matrices take values from {0, 1} and [0, 1] respectively).
Our methodology for attacking the problem is based on the solvability of zero sum bimatrix games (via its connection to linear programming) and provides a
0.5-SuppNE for win lose games and a 0.667-SuppNE for normalized games.
To our knowledge, this paper provides the first polynomial time algorithms constructing
{\aa}-SuppNE for normalized or win lose bimatrix games, for any nontrivial
constant 0 ≤{\aa} <1, bounded away from 1.
Abstract: We study the existence and tractability of a notion of approximate
equilibria in bimatrix games, called well supported approximate
Nash Equilibria (SuppNE in short).We prove existence of "−SuppNE for
any constant " 2 (0, 1), with only logarithmic support sizes for both players.
Also we propose a polynomial–time construction of SuppNE, both
for win lose and for arbitrary (normalized) bimatrix games. The quality
of these SuppNE depends on the girth of the Nash Dynamics graph in
the win lose game, or a (rounded–off) win lose image of the original normalized
game. Our constructions are very successful in sparse win lose
games (ie, having a constant number of (0, 1)−elements in the bimatrix)
with large girth in the Nash Dynamics graph. The same holds also for
normalized games whose win lose image is sparse with large girth.
Finally we prove the simplicity of constructing SuppNE both in random
normalized games and in random win lose games. In the former case we
prove that the uniform full mix is an o(1)−SuppNE, while in the case
of win lose games, we show that (with high probability) there is either a
PNE or a 0.5-SuppNE with support sizes only 2.
