Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Beier, Rene
Krysta, Piotr
Czumaj, Artur
Vöcking, Berthold

dblp
dblp
dblp
dblp

Not MPG Author(s):

Krysta, Piotr
Czumaj, Artur
Vöcking, Berthold

Editor(s):





BibTeX cite key*:

Beier2004b

Title, Booktitle

Title*:

Computing Equilibria for Congestion Games with (Im)perfect Information

Booktitle*:

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04)

Event, URLs

URL of the conference:

http://www.siam.org/meetings/da04/

URL for downloading the paper:

http://www.mpi-sb.mpg.de/%7Erbeier/soda04_2.ps.gz

Event Address*:

New Orleans, USA

Language:

English

Event Date*
(no longer used):

January, 11-13

Organization:

Association of Computing Machinery (ACM)

Event Start Date:

11 January 2004

Event End Date:

16 January 2004

Publisher

Name*:

ACM

URL:


Address*:

New York, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

739-748

Year*:

2004

VG Wort Pages:

33

ISBN/ISSN:

0-89871-558-X

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) 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}



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Beier2004b,
AUTHOR = {Beier, Rene and Krysta, Piotr and Czumaj, Artur and V{\"o}cking, Berthold},
TITLE = {Computing Equilibria for Congestion Games with (Im)perfect Information},
BOOKTITLE = {Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04)},
PUBLISHER = {ACM},
YEAR = {2004},
ORGANIZATION = {Association of Computing Machinery (ACM)},
PAGES = {739--748},
ADDRESS = {New Orleans, USA},
ISBN = {0-89871-558-X},
}


Entry last modified by Christine Kiesel, 05/23/2005
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Rene Beier
Created
01/16/2004 03:34:34 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Christine Kiesel
Ulrich Meyer
Sabine Krott
Christine Kiesel
Christine Kiesel
Edit Dates
23.05.2005 14:15:14
04/21/2005 11:27:05 AM
02.02.2005 12:07:33
09.06.2004 16:43:31
01/16/2004 03:36:52 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section