Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Computing Equilibria for Congestion Games with (Im)perfect Information

Beier, R., Krysta, P., Czumaj, A., & Vöcking, B. (2004). Computing Equilibria for Congestion Games with (Im)perfect Information. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04) (pp. 739-748). New York, USA: ACM.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2916-1 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2917-0
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Beier, Rene1, Autor           
Krysta, Piotr1, Autor           
Czumaj, Artur1, Autor           
Vöcking, Berthold1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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}

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2005-05-232004
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: New York, USA : ACM
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 231173
Anderer: Local-ID: C1256428004B93B8-7B14608AB22B64B7C1256E1D005011CA-Beier2004b
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: New Orleans, USA
Start-/Enddatum: 2004-01-11

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04)
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: New York, USA : ACM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 739 - 748 Identifikator: ISBN: 0-89871-558-X