hide
Free keywords:
-
Abstract:
We study algorithmic questions concerning a basic
microeconomic congestion game in which there is a single provider
that offers a service to a set of potential customers. Each
customer has a particular demand of service and the behavior of
the customers is determined by utility functions that are
non-increasing in the congestion. Customers decide whether to join
or leave the service based on the experienced congestion and the
offered prices. Following standard game theory, we
assume each customer behaves in the most rational way. If the
prices of service are fixed, then such a customer behavior leads
to a pure, not necessarily unique Nash equilibrium among the
customers. In order to evaluate marketing strategies, the service
provider is interested in estimating its revenue under the best and
worst customer equilibria. We study the complexity of this problem
under different models of information available to the provider.
%
\begin{itemize}
\item We first consider the classical model in which the provider
has perfect knowledge of the behavior of all customers. We present
a complete characterization of the \emph{complexity of computing
optimal pricing strategies} and of \emph{computing best and worst
equilibria}. Basically, we show that most of these problems are
inapproximable in the worst case but admit an
``average-case FPAS.'' Our average case analysis covers general
distributions for customer demands and utility thresholds.
We generalize our analysis to robust equilibria
in which players change their strategies only when this promises
a significant utility improvement.
%
\item We extend our analysis to a more realistic model in which
the provider has \emph{incomplete information}. Following the game
theoretic framework of Bayesian games introduced by Harsanyi, we
assume that the provider is aware of probability distributions
describing the behavior of the customers and aims at estimating
its expected revenue under best and worst equilibria. Somewhat
counterintuitive, we obtain an FPRAS for the equilibria problem
in the model with imperfect information although the problem with
perfect information is inapproximable under the worst case measures.
In particular, the worst case complexity of the considered
stochastic equilibria problems increases with the precision of the
available knowledge.
\end{itemize}
