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: Goto entry point

 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:

 (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},