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
she 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 non-cooperative 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; in contrast, 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 {\`E}(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 is at most a (universal for the class) constant times its expectation.
Then, the Diffuse Price of Anarchy is at most that same
constant, which is just 2 when each demand is distributed symmetrically
around its expectation.
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: Consider a network vulnerable to viral infection, where the security software can guarantee safety only to a limited part of it. 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. We are interested in the associated Nash equilibria, where no network entity can unilaterally improve its local objective. We obtain the following results: for certain families of graphs, mixed Nash equilibria can be computed in polynomially time. These families include, among others, regular graphs, graphs with perfect matchings and trees. The corresponding price of anarchy for any mixed Nash equilibria of the game is upper and lower bounded by a linear function of the number of vertices of the graph. (We define the price of anarchy to reflect the utility of the protector). Finally, we introduce a generalised version of the game. We show that the existence problem of pure Nash equilibria here is NP complete.
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 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 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: This work is an attempt to present and describe the design and implementation of a system for the cooperative multiplayer control of gaming and entertainment-related software, based on the use of mobile devices with wireless networking capabilities. We are currently using wireless sensor networking devices as the enabling platform, and our prototype application is based on Google Earth�s integrated flight simulator.
Abstract: In large scale networks users often behave selfishly trying to minimize their routing cost. Modelling this as a noncooperative game, may yield a Nash equilibrium with unboundedly poor network performance. To measure this inefficacy, the Coordination Ratio or Price of Anarchy (PoA) was introduced. It equals the ratio of the cost induced by the worst Nash equilibrium, to the corresponding one induced by the overall optimum assignment of the jobs to the network. On improving the PoA of a given network, a series of papers model this selfish behavior as a Stackelberg or Leader-Followers game.
We consider random tuples of machines, with either linear or M/M/1 latency functions, and PoA at least a tuning parameter c. We validate a variant (NLS) of the Largest Latency First (LLF) Leaderrsquos strategy on tuples with PoA ge c. NLS experimentally improves on LLF for systems with inherently high PoA, where the Leader is constrained to control low portion agr of jobs. This suggests even better performance for systems with arbitrary PoA. Also, we bounded experimentally the least Leaderrsquos portion agr0 needed to induce optimum cost. Unexpectedly, as parameter c increases the corresponding agr0 decreases, for M/M/1 latency functions. All these are implemented in an extensive Matlab toolbox.
Abstract: We study the problem of fair resource allocation in a simple cooperative multi-agent setting where we have k agents and a set of n objects to be allocated to those agents. Each object is associated with a weight represented by a positive integer or real number. We would like to allocate all objects to the agents so that each object is allocated to only one agent and the weight is distributed fairly. We adopt the fairness index popularized by the networking community as our measure of fairness, and study centralized algorithms for fair resource allocation. Based on the relationship between our problem and number partitioning, we devise a greedy algorithm for fair resource allocation that runs in polynomial time but is not guaranteed to find the optimal solution, and a complete anytime algorithm that finds the optimal solution but runs in exponential time. Then we study the phase transition behavior of the complete algorithm. Finally, we demonstrate that the greedy algorithm actually performs very well and returns almost perfectly fair allocations.
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: Consider an information network with harmful procedures called attackers (e.g., viruses); each attacker uses a probability distribution to choose a node of the network to damage. Opponent to the attackers is the system protector scanning and cleaning from attackers some part of the network (e.g., an edge or a path), which it chooses independently using another probability distribution. Each attacker wishes to maximize the probability of escaping its cleaning by the system protector; towards a conflicting objective, the system protector aims at maximizing the expected number of cleaned attackers.
We model this network scenario as a non-cooperative strategic game on graphs. We focus on the special case where the protector chooses a single edge. We are interested in the associated Nash equilibria, where no network entity can unilaterally improve its local objective. We obtain the following results:
{\^a}{\"i}¿½{\"i}¿½ No instance of the game possesses a pure Nash equilibrium.
{\^a}{\"i}¿½{\"i}¿½Every mixed Nash equilibrium enjoys a graph-theoretic structure, which enables a (typically exponential) algorithm to compute it.
{\^a}{\"i}¿½{\"i}¿½ We coin a natural subclass of mixed Nash equilibria, which we call matching Nash equilibria, for this game on graphs. Matching Nash equilibria are defined using structural parameters of graphs, such as independent sets and matchings.
{\^a}{\"i}¿½{\"i}¿½We derive a characterization of graphs possessing matching Nash equilibria. The characterization enables a linear time algorithm to compute a matching Nash equilibrium on any such graph with a given independent set and vertex cover.
{\^a}{\"i}¿½{\"i}¿½ Bipartite graphs are shown to satisfy the characterization. So, using a polynomial-time algorithm to compute a perfect matching in a bipartite graph, we obtain, as our main result, an efficient graph-theoretic algorithm to compute a matching Nash equilibrium on any instance of the game with a bipartite graph.
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: 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: 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: We address several recent developments in non-cooperative as well as
evolutionary game theory, that give a new viewpoint to Complex Systems understanding.
In particular, we discuss notions like the anarchy cost, equilibria formation,
social costs and evolutionary stability. We indicate how such notions help
in understanding Complex Systems behaviour when the system includes selfish,
antagonistic entities of varying degrees of rationality. Our main motivation is the
Internet, perhaps the most complex artifact to date, as well as large-scale systems
such as the high-level P2P systems, where where the interaction is among
humans, programmes and machines and centralized approaches cannot apply.
Abstract: We consider a security problem on a distributed network.
We assume a network whose nodes are vulnerable to infection
by threats (e.g. viruses), the attackers. A system security
software, the defender, is available in the system. However,
due to the network¢s size, economic and performance reasons,
it is capable to provide safety, i.e. clean nodes from
the possible presence of attackers, only to a limited part of
it. The objective of the defender is to place itself in such a
way as to maximize the number of attackers caught, while
each attacker aims not to be caught.
In [7], a basic case of this problem was modeled as a
non-cooperative game, called the Edge model. There, the
defender could protect a single link of the network. Here,
we consider a more general case of the problem where the
defender is able to scan and protect a set of k links of the
network, which we call the Tuple model. It is natural to expect
that this increased power of the defender should result
in a better quality of protection for the network. Ideally,
this would be achieved at little expense on the existence and
complexity of Nash equilibria (profiles where no entity can
improve its local objective unilaterally by switching placements
on the network).
In this paper we study pure and mixed Nash equilibria
in the model. In particular, we propose algorithms for computing
such equilibria in polynomial time and we provide a
polynomial-time transformation of a special class of Nash
equilibria, called matching equilibria, between the Edge
model and the Tuple model, and vice versa. Finally, we
establish that the increased power of the defender results in
higher-quality protection of the network.
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: In cooperative multiagent systems an alternative that maximizes the social welfare—the sum of utilities—can only be selected if each agent reports its full utility function. This may be infeasible in environments where communication is restricted. Employing a voting rule to choose an alternative greatly reduces the communication burden, but leads to a possible gap between the social welfare of the optimal alternative and the social welfare of the one that is ultimately elected. Procaccia and Rosenschein (2006) have introduced the concept of distortion to quantify this gap. In this paper, we present the notion of embeddings into voting rules: functions that receive an agent¢s utility function and return the agent¢s vote. We establish that very low distortion can be obtained using randomized embeddings, especially when the number of agents is large compared to the number of alternatives. We investigate our ideas in the context of three prominent voting rules with low communication costs: Plurality, Approval, and Veto. Our results arguably provide a compelling reason for employing voting in cooperative multiagent systems.
Abstract: In cooperative multiagent systems an alternative that maximizes the social welfare—the sum of utilities—can only be selected if each agent reports its full utility function. This may be infeasible in environments where communication is restricted. Employing a voting rule to choose an alternative
greatly reduces the communication burden, but leads to a possible gap between the social welfare of the optimal alternative and the social welfare of the one that is ultimately elected. Procaccia and Rosenschein (2006) have introduced the concept of distortion to quantify this gap.
In this paper, we present the notion of embeddings into voting rules: functions that receive an agent¢s utility function and return the agent¢s vote. We establish that very low distortion can be obtained using randomized embeddings, especially when the number of agents is large compared to the number of alternatives. We investigate our ideas in the context
of three prominent voting rules with low communication costs: Plurality, Approval, and Veto. Our results arguably provide a compelling reason for employing voting in cooperative multiagent systems.
