English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Computing Equilibria for a Service Provider Game with (Im)perfect Information

Beier, R., Czumaj, A., Krysta, P., & Vöcking, B. (2006). Computing Equilibria for a Service Provider Game with (Im)perfect Information. ACM Transactions on Algorithms, 2, 679-706.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-225D-C Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-225E-A
Genre: Journal Article

Files

show Files
hide Files
:
Beier2006c.pdf (Publisher version), 198KB
 
File Permalink:
-
Name:
Beier2006c.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Beier, René1, Author           
Czumaj, Artur1, Author           
Krysta, Piotr1, Author           
Vöcking, Berthold1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: We study fundamental algorithmic questions concerning the complexity of market equilibria under perfect and imperfect information by means of a basic microeconomic game. Suppose a provider offers a service to a set of potential customers. Each customer has a particular demand of service and her behavior is determined by a utility function that is nonincreasing in the sum of demands that are served by the provider. Classical game theory assumes complete information: the provider has full knowledge of the behavior of all customers. We present a complete characterization of the complexity of computing optimal pricing strategies and of computing best/worst equilibria in this model. Basically, we show that most of these problems are inapproximable in theworst case but admit an FPASin the average case. Our average case analysis covers large classes of distributions for customer utilities. We generalize our analysis to robust equilibria in which players change their strategies only when this promises a significant utility improvement.

Details

show
hide
Language(s): eng - English
 Dates: 2007-02-052006
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 314454
Other: Local-ID: C1256428004B93B8-26C30D10F87C8A88C125726B004C1CF9-Beier2006c
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: ACM Transactions on Algorithms
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2 Sequence Number: - Start / End Page: 679 - 706 Identifier: ISSN: 1549-6325