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 Nashequilibrium exists for all
possible choices of the demands. Further on, the fully mixed Nashequilibrium is the unique Nashequilibrium 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 give an efficient local search
algorithm that computes a good vertex coloring of a graph $G$. In
order to better illustrate this local search method, we view local
moves as selfish moves in a suitably defined game. In particular,
given a graph $G=(V,E)$ of $n$ vertices and $m$ edges, we define
the \emph{graph coloring game} $\Gamma(G)$ as a strategic game
where the set of players is the set of vertices and the players
share the same action set, which is a set of $n$ colors. The
payoff that a vertex $v$ receives, given the actions chosen by all
vertices, equals the total number of vertices that have chosen the
same color as $v$, unless a neighbor of $v$ has also chosen the
same color, in which case the payoff of $v$ is 0. We show:
\begin{itemize}
\item The game $\Gamma(G)$ has always pure Nash equilibria. Each
pure equilibrium is a proper coloring of $G$. Furthermore, there
exists a pure equilibrium that corresponds to an optimum coloring.
\item We give a polynomial time algorithm $\mathcal{A}$ which
computes a pure Nashequilibrium of $\Gamma(G)$. \item The total
number, $k$, of colors used in \emph{any} pure Nashequilibrium
(and thus achieved by $\mathcal{A}$) is $k\leq\min\{\Delta_2+1,
\frac{n+\omega}{2}, \frac{1+\sqrt{1+8m}}{2}, n-\alpha+1\}$, where
$\omega, \alpha$ are the clique number and the independence number
of $G$ and $\Delta_2$ is the maximum degree that a vertex can have
subject to the condition that it is adjacent to at least one
vertex of equal or greater degree. ($\Delta_2$ is no more than the
maximum degree $\Delta$ of $G$.) \item Thus, in fact, we propose
here a \emph{new}, \emph{efficient} coloring method that achieves
a number of colors \emph{satisfying (together) the known general
upper bounds on the chromatic number $\chi$}. Our method is also
an alternative general way of \emph{proving},
\emph{constructively}, all these bounds. \item Finally, we show
how to strengthen our method (staying in polynomial time) so that
it avoids ``bad'' pure Nash equilibria (i.e. those admitting a
number of colors $k$ far away from $\chi$). In particular, we show
that our enhanced method colors \emph{optimally} dense random
$q$-partite graphs (of fixed $q$) with high probability.
\end{itemize}
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 Nashequilibrium is NP-complete for the Path model.
This opposed to that, no instance of the Edge model possesses a pure Nashequilibrium,
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: 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 Nashequilibrium for random bimatrix games, in the sense that it is, with high probability, an {\aa}-well-supported Nashequilibrium 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 NashEquilibrium. 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 NashEquilibrium, 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 NashEquilibrium. 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 Nashequilibrium exists for all possible choices of the demands. Further
on, the fully mixed Nashequilibrium is the unique Nashequilibrium 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 Nashequilibrium 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 Nashequilibrium 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 Nashequilibrium 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 Nashequilibrium or there is another equilibrium of
total cost at least 6/5 times the optimal cost.
Abstract: We exploit the game-theoretic ideas presented in [12] to
study the vertex coloring problem in a distributed setting. The vertices
of the graph are seen as players in a suitably defined strategic game,
where each player has to choose some color, and the payoff of a vertex is
the total number of players that have chosen the same color as its own.
We extend here the results of [12] by showing that, if any subset of nonneighboring
vertices perform a selfish step (i.e., change their colors in order
to increase their payoffs) in parallel, then a (Nashequilibrium) proper
coloring, using a number of colors within several known upper bounds
on the chromatic number, can still be reached in polynomial time. We
also present an implementation of the distributed algorithm in wireless
networks of tiny devices and evaluate the performance in simulated and
experimental environments. The performance analysis indicates that it
is the first practically implementable distributed algorithm.
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: Intuitively, Braess's paradox states that destroying a part
of a network may improve the common latency of sel sh
ows at Nashequilibrium. Such a paradox is a pervasive phenomenon in real-world
networks. Any administrator, who wants to improve equilibrium delays
in sel sh networks, is facing some basic questions: (i) Is the network
paradox-ridden? (ii) How can we delete some edges to optimize equilibrium
ow delays? (iii) How can we modify edge latencies to optimize
equilibrium
ow delays?
Unfortunately, such questions lead to NP-hard problems in general. In
this work, we impose some natural restrictions on our networks, e.g.
we assume strictly increasing linear latencies. Our target is to formulate
ecient algorithms for the three questions above.We manage to provide:
{ A polynomial-time algorithm that decides if a network is paradoxridden,
when latencies are linear and strictly increasing.
{ A reduction of the problem of deciding if a network with arbitrary
linear latencies is paradox-ridden to the problem of generating all
optimal basic feasible solutions of a Linear Program that describes
the optimal trac allocations to the edges with constant latency.
{ An algorithm for nding a subnetwork that is almost optimal wrt
equilibrium latency. Our algorithm is subexponential when the number
of paths is polynomial and each path is of polylogarithmic length.
{ A polynomial-time algorithm for the problem of nding the best
subnetwork, which outperforms any known approximation algorithm
for the case of strictly increasing linear latencies.
{ A polynomial-time method that turns the optimal
ow into a Nash
ow by deleting the edges not used by the optimal
ow, and performing
minimal modi cations to the latencies of the remaining ones.
Our results provide a deeper understanding of the computational complexity
of recognizing the Braess's paradox most severe manifestations,
and our techniques show novel ways of using the probabilistic method
and of exploiting convex separable quadratic programs.
Abstract: Intuitively, Braess’s paradox states that destroying a part of a network may improve the common latency of selfish flows at Nashequilibrium. Such a paradox is a pervasive phenomenon in real-world networks. Any administrator who wants to improve equilibrium delays in selfish networks, is facing some basic questions:
– Is the network paradox-ridden?
– How can we delete some edges to optimize equilibrium flow delays?
– How can we modify edge latencies to optimize equilibrium flow delays?
Unfortunately, such questions lead to View the MathML sourceNP-hard problems in general. In this work, we impose some natural restrictions on our networks, e.g. we assume strictly increasing linear latencies. Our target is to formulate efficient algorithms for the three questions above. We manage to provide:
– A polynomial-time algorithm that decides if a network is paradox-ridden, when latencies are linear and strictly increasing.
– A reduction of the problem of deciding if a network with (arbitrary) linear latencies is paradox-ridden to the problem of generating all optimal basic feasible solutions of a Linear Program that describes the optimal traffic allocations to the edges with constant latency.
– An algorithm for finding a subnetwork that is almost optimal wrt equilibrium latency. Our algorithm is subexponential when the number of paths is polynomial and each path is of polylogarithmic length.
– A polynomial-time algorithm for the problem of finding the best subnetwork which outperforms any known approximation for the case of strictly increasing linear latencies.
– A polynomial-time method that turns the optimal flow into a Nash flow by deleting the edges not used by the optimal flow, and performing minimal modifications on the latencies of the remaining ones.
Our results provide a deeper understanding of the computational complexity of recognizing the most severe manifestations of Braess’s paradox, and our techniques show novel ways of using the probabilistic method and of exploiting convex separable quadratic programs.
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 Nashequilibrium 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: 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 Nash equilibria and global guarantees of convergence to equilibrium, are widely studied in the literature. In this paper we discuss some computational aspects of the theory, which we prefer to view more as Game Theoretic Aspects of Evolution than 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.
Abstract: In large scale networks users often behave selfishly trying to minimize their routing cost. Modelling this as a noncooperative game, may yield a Nashequilibrium 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 Nashequilibrium, 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 fundamental problem of computing an arbitrary Nashequilibrium 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 Nashequilibrium, 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 Nashequilibrium.
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 (Nashequilibrium 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: We study the combinatorial structure and computational complexity of extreme Nash equilibria, ones that maximize or minimize a certain objective function, in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel links, to control the routing of its own assigned traffic. In a Nashequilibrium, each user routes its traffic on links that minimize its expected latency cost.
Our structural results provide substantial evidence for the Fully Mixed NashEquilibrium Conjecture, which states that the worst Nashequilibrium is the fully mixed Nashequilibrium, where each user chooses each link with positive probability. Specifically, we prove that the Fully Mixed NashEquilibrium Conjecture is valid for pure Nash equilibria and that under a certain condition, the social cost of any Nashequilibrium is within a factor of 6 + epsi, of that of the fully mixed Nashequilibrium, assuming that link capacities are identical.
Our complexity results include hardness, approximability and inapproximability ones. Here we show, that for identical link capacities and under a certain condition, there is a randomized, polynomial-time algorithm to approximate the worst social cost within a factor arbitrarily close to 6 + epsi. Furthermore, we prove that for any arbitrary integer k > 0, it is -hard to decide whether or not any given allocation of users to links can be transformed into a pure Nashequilibrium using at most k selfish steps. Assuming identical link capacities, we give a polynomial-time approximation scheme (PTAS) to approximate the best social cost over all pure Nash equilibria. Finally we prove, that it is -hard to approximate the worst social cost within a multiplicative factor . The quantity is the tight upper bound on the ratio of the worst social cost and the optimal cost in the model of identical capacities.
Abstract: Let n atomic players be routing their unsplitable flow on mresources.
When each player has the option to drop her current resource and select a better
one, and this option is exercised sequentially and unilaterally, then a NashEquilibrium
(NE) will be eventually reached. Acting sequentially, however, is unrealistic
in large systems. But, allowing concurrency, with an arbitrary number of
players updating their resources at each time point, leads to an oscillation away
from NE, due to big groups of players moving simultaneously and due to nonsmooth
resource cost functions. In this work, we validate experimentally simple
concurrent protocols that are realistic, distributed and myopic yet are scalable, require
only information local at each resource and, still, are experimentally shown
to quickly reach a NE for a range of arbitrary cost functions.
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 Nashequilibrium.
{\^a}{\"i}¿½{\"i}¿½Every mixed Nashequilibrium 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 Nashequilibrium 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 Nashequilibrium on any instance of the game with a bipartite graph.
Abstract: We study the fundamental problem 2NASH of computing a Nashequilibrium (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 focus on the problem of computing an epsilon (Porson)-Nashequilibrium of a bimatrix game, when epsilon (Porson) is an absolute constant. We present a simple algorithm for computing a View the MathML source-Nashequilibrium for any bimatrix game in strongly polynomial time and we next show how to extend this algorithm so as to obtain a (potentially stronger) parameterized approximation. Namely, we present an algorithm that computes a View the MathML source-Nashequilibrium, where {\"e} is the minimum, among all Nash equilibria, expected payoff of either player. The suggested algorithm runs in time polynomial in the number of strategies available to the players.
Abstract: We focus on the problem of computing an -Nashequilibrium
of a bimatrix game, when is an absolute constant. We present a simple
algorithm for computing a 3 -Nashequilibrium for any bimatrix game in
4
strongly polynomial time and we next show how to extend this algorithm
so as to obtain a (potentially stronger) parameterized approximation.
Namely, we present an algorithm that computes a 2+{\"e} -Nashequilibrium,
4
where {\"e} is the minimum, among all Nash equilibria, expected payoff of
either player. The suggested algorithm runs in time polynomial in the
number of strategies available to the players.
Abstract: We focus on the problem of computing an ²-Nashequilibrium
of a bimatrix game, when ² is an absolute constant. We present a simple
algorithm for computing a 3
4 -Nashequilibrium for any bimatrix game in
strongly polynomial time and we next show how to extend this algorithm
so as to obtain a (potentially stronger) parameterized approximation.
Namely, we present an algorithm that computes a 2+¸
4 -Nashequilibrium,
where ¸ is the minimum, among all Nash equilibria, expected payoff of
either player. The suggested algorithm runs in time polynomial in the
number of strategies available to the players.
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 -Nashequilibrium and a TeX -well supported Nashequilibrium, where n is the number of pure strategies available to each player. This asserts that the completely mixed, uniform strategy profile is an almost Nashequilibrium for random bimatrix games, since it is, with high probability, an ϵ-well-supported Nashequilibrium where ϵ tends to zero as n tends to infinity.
Abstract: Braess’s paradox states that removing a part of a network may im-
prove the players’ latency at equilibrium. In this work, we study the approxima-
bility of the best subnetwork problem for the class of random
G
n;p
instances
proven prone to Braess’s paradox by (Roughgarden and Valiant, RSA 2010) and
(Chung and Young, WINE 2010). Our main contribution is a polynomial-time
approximation-preserving reduction of the best subnetwork problem for such in-
stances to the corresponding problem in a simplified network where all neighbors
of
s
and
t
are directly connected by
0
latency edges. Building on this, we obtain
an approximation scheme that for any constant
" >
0
and with high probabil-
ity, computes a subnetwork and an
"
-Nash flow with maximum latency at most
(1+
"
)
L
+
"
, where
L
is the equilibrium latency of the best subnetwork. Our ap-
proximation scheme runs in polynomial time if the random network has average
degree
O
(poly(ln
n
))
and the traffic rate is
O
(poly(lnln
n
))
, and in quasipoly-
nomial time for average degrees up to
o
(
n
)
and traffic rates of
O
(poly(ln
n
))
.
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 Nashequilibrium.
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 NashEquilibrium. 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 extreme Nash equilibria in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel identical links, to control the routing of its own assigned traffic. In a Nashequilibrium, each user selfishly routes its traffic on those links that minimize its expected latency cost. The social cost of a Nashequilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link.
We provide substantial evidence for the Fully Mixed NashEquilibrium Conjecture, which states that the worst Nashequilibrium is the fully mixed Nashequilibrium, where each user chooses each link with positive probability. Specifically, we prove that the Fully Mixed NashEquilibrium Conjecture is valid for pure Nash equilibria. Furthermore, we show, that under a certain condition, the social cost of any Nashequilibrium is within a factor of 2h(1+ɛ) of that of the fully mixed Nashequilibrium, where h is the factor by which the largest user traffic deviates from the average user traffic.
Considering pure Nash equilibria, we provide a PTAS to approximate the best social cost, we give an upper bound on the worst social cost and we show that it is View the MathML source-hard to approximate the worst social cost within a multiplicative factor better than 2-2/(m+1).
Abstract: We study extreme Nash equilibria in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel identical links, to control the routing of its own assigned traffic. In a Nashequilibrium, each user selfishly routes its traffic on those links that minimize its expected latency cost. The social cost of a Nashequilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link.We provide substantial evidence for the Fully Mixed NashEquilibrium Conjecture, which states that the worst Nashequilibrium is the fully mixed Nashequilibrium, where each user chooses each link with positive probability. Specifically, we prove that the Fully Mixed NashEquilibrium Conjecture is valid for pure Nash equilibria. Furthermore, we show, that under a certain condition, the social cost of any Nashequilibrium is within a factor of 2h(1 + {\aa}) of that of the fully mixed Nashequilibrium, where h is the factor by which the largest user traffic deviates from the average user traffic.Considering pure Nash equilibria, we provide a PTAS to approximate the best social cost, we give an upper bound on the worst social cost and we show that it is N P-hard to approximate the worst social cost within a multiplicative factor better than 2 - 2/(m + 1).
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 Nashequilibrium
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 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: We consider a strategic game with two classes of confronting
randomized players on a graph G(V,E): {\'i} attackers, each choosing vertices
and wishing to minimize the probability of being caught, and a
defender, who chooses edges and gains the expected number of attackers
it catches. The Price of Defense is the worst-case ratio, over all Nash
equilibria, of the optimal gain of the defender over its gain at a Nashequilibrium.
We provide a comprehensive collection of trade-offs between the
Price of Defense and the computational efficiency of Nash equilibria.
– Through reduction to a Two-Players, Constant-Sum Game, we prove
that a Nashequilibrium can be computed in polynomial time. The
reduction does not provide any apparent guarantees on the Price of
Defense.
– To obtain such, we analyze several structured Nash equilibria:
• In a Matching Nashequilibrium, the support of the defender is
an Edge Cover. We prove that they can be computed in polynomial
time, and they incur a Price of Defense of {\'a}(G), the
Independence Number of G.
• In a Perfect Matching Nashequilibrium, the support of the defender
is a Perfect Matching. We prove that they can be computed
in polynomial time, and they incur a Price of Defense of
|V |
2 .
• In a Defender Uniform Nashequilibrium, the defender chooses
uniformly each edge in its support. We prove that they incur a
Price of Defense falling between those for Matching and Perfect
Matching Nash Equilibria; however, it is NP-complete to decide
their existence.
• In an Attacker Symmetric and Uniform Nashequilibrium, all
attackers have a common support on which each uses a uniform
distribution. We prove that they can be computed in polynomial
time and incur a Price of Defense of either
|V |
2 or {\'a}(G).
Abstract: Consider a network vulnerable to security attacks and equipped with defense mechanisms. How much is the loss in the provided security guarantees due to the selfish nature of attacks and defenses? The Price of Defense was recently introduced in [7] as a worst-case measure, over all associated Nash equilibria, of this loss. In the particular strategic game considered in [7], there are two classes of confronting randomized players on a graph G(V,E): v attackers, each choosing vertices and wishing to minimize the probability of being caught, and a single defender, who chooses edges and gains the expected number of attackers it catches. In this work, we continue the study of the Price of Defense. We obtain the following results: - The Price of Defense is at least |V| 2; this implies that the Perfect Matching Nash equilibria considered in [7] are optimal with respect to the Price of Defense, so that the lower bound is tight. - We define Defense-Optimal graphs as those admitting a Nashequilibrium that attains the (tight) lower bound of |V| 2. We obtain: › A graph is Defense-Optimal if and only if it has a Fractional Perfect Matching. Since graphs with a Fractional Perfect Matching are recognizable in polynomial time, the same holds for Defense-Optimal graphs. › We identify a very simple graph that is Defense-Optimal but has no Perfect Matching Nashequilibrium. - Inspired by the established connection between Nash equilibria and Fractional Perfect Matchings, we transfer a known bivaluedness result about Fractional Matchings to a certain class of Nash equilibria. So, the connection to Fractional Graph Theory may be the key to revealing the combinatorial structure of Nash equilibria for our network security game.
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 Nashequilibrium 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 problem of routing traffic through a congested network. We focus on the simplest case of a network consisting of m parallel links. We assume a collection of n network users; each user employs a mixed strategy, which is a probability distribution over links, to control the shipping of its own assigned traffic. Given a capacity for each link specifying the rate at which the link processes traffic, the objective is to route traffic so that the maximum (over all links) latency is minimized. We consider both uniform and arbitrary link capacities. How much decrease in global performace is necessary due to the absence of some central authority to regulate network traffic and implement an optimal assignment of traffic to links? We investigate this fundamental question in the context of Nash equilibria for such a system, where each network user selfishly routes its traffic only on those links available to it that minimize its expected latency cost, given the network congestion caused by the other users. We use the Coordination Ratio, originally defined by Koutsoupias and Papadimitriou, as a measure of the cost of lack of coordination among the users; roughly speaking, the Coordination Ratio is the ratio of the expectation of the maximum (over all links) latency in the worst possible Nashequilibrium, over the least possible maximum latency had global regulation been available. Our chief instrument is a set of combinatorial Minimum Expected Latency Cost Equations, one per user, that characterize the Nash equilibria of this system. These are linear equations in the minimum expected latency costs, involving the user traffics, the link capacities, and the routing pattern determined by the mixed strategies. In turn, we solve these equations in the case of fully mixed strategies, where each user assigns its traffic with a strictly positive probability to every link, to derive the first existence and uniqueness results for fully mixed Nash equilibria in this setting. Through a thorough analysis and characterization of fully mixed Nash equilibria, we obtain tight upper bounds of no worse than O(ln n/ln ln n) on the Coordination Ratio for (i) the case of uniform capacities and arbitrary traffics and (ii) the case of arbitrary capacities and identical traffics.
Abstract: In this work, we study the combinatorial structure and the
computational complexity of Nash equilibria for a certain game that
models selfish routing over a network consisting of m parallel links. We
assume a collection of n users, each employing a mixed strategy, which
is a probability distribution over links, to control the routing of its own
assigned traffic. In a Nashequilibrium, each user selfishly routes its traffic
on those links that minimize its expected latency cost, given the network
congestion caused by the other users. The social cost of a Nashequilibrium
is the expectation, over all random choices of the users, of the
maximum, over all links, latency through a link.
We embark on a systematic study of several algorithmic problems related
to the computation of Nash equilibria for the selfish routing game we consider.
In a nutshell, these problems relate to deciding the existence of a
Nashequilibrium, constructing a Nashequilibrium with given support
characteristics, constructing the worst Nashequilibrium (the one with
maximum social cost), constructing the best Nashequilibrium (the one
with minimum social cost), or computing the social cost of a (given) Nashequilibrium. Our work provides a comprehensive collection of efficient algorithms,
hardness results (both as NP-hardness and #P-completeness
results), and structural results for these algorithmic problems. Our results
span and contrast a wide range of assumptions on the syntax of the
Nash equilibria and on the parameters of the system.
Abstract: A Nashequilibrium of a routing network represents a stable state of the network where no user finds it beneficial to unilaterally deviate from its routing strategy. In this work, we investigate the structure of such equilibria within the context of a certain game that models selfish routing for a set of n users each shipping its traffic over a network consisting of m parallel links. In particular, we are interested in identifying the worst-case Nashequilibrium – the one that maximizes social cost. Worst-case Nash equilibria were first introduced and studied in the pioneering work of Koutsoupias and Papadimitriou [9].
More specifically, we continue the study of the Conjecture of the Fully Mixed NashEquilibrium, henceforth abbreviated as FMNE Conjecture, which asserts that the fully mixed Nashequilibrium, when existing, is the worst-case Nashequilibrium. (In the fully mixed Nashequilibrium, the mixed strategy of each user assigns (strictly) positive probability to every link.) We report substantial progress towards identifying the validity, methodologies to establish, and limitations of, the FMNE Conjecture.
