Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

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

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Beier, René
Czumaj, Artur
Krysta, Piotr
Vöcking, Berthold

dblp
dblp
dblp
dblp

Not MPG Author(s):

Czumaj, Artur
Krysta, Piotr
Vöcking, Berthold

BibTeX cite key*:

Beier2006c

Title

Title*:

Computing Equilibria for a Service Provider Game with (Im)perfect Information

Journal

Journal Title*:

ACM Transactions on Algorithms

Journal's URL:

http://www.acm.org/talg/

Download URL
for the article:

http://portal.acm.org/ft_gateway.cfm?id=1198524&type=pdf&coll=GUIDE&dl=GUIDE&CFID=12080441&CFTOKEN=81355769
http://delivery.acm.org/10.1145/1200000/1198524/p679-beier.pdf?key1=1198524&key2=5031960711&coll=&dl=GUIDE&CFID=15151515&CFTOKEN=6184618

Language:

English

Publisher

Publisher's
Name:

ACM

Publisher's URL:

http://acm.org/

Publisher's
Address:

New York, USA

ISSN:

1549-6325

Vol, No, pp, Date

Volume*:

2

Number:

4

Publishing Date:

October 2006

Pages*:

679-706

Number of
VG Pages:

40

Page Start:

679

Page End:

706

Sequence Number:


DOI:


Note, Abstract, ©

Note:


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

URL for the Abstract:


Categories,
Keywords:

Algorithms, Economics, Theory, Market Equilibria

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

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:

@ARTICLE{Beier2006c,
AUTHOR = {Beier, Ren{\'e} and Czumaj, Artur and Krysta, Piotr and V{\"o}cking, Berthold},
TITLE = {Computing Equilibria for a Service Provider Game with (Im)perfect Information},
JOURNAL = {ACM Transactions on Algorithms},
PUBLISHER = {ACM},
YEAR = {2006},
NUMBER = {4},
VOLUME = {2},
PAGES = {679--706},
ADDRESS = {New York, USA},
MONTH = {October},
ISBN = {1549-6325},
}


Entry last modified by Christine Kiesel, 02/05/2007
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)
René Beier
Created
01/22/2007 02:51:21 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
René Beier
René Beier
René Beier
Edit Dates
05.02.2007 17:08:35
05.02.2007 17:07:48
01/22/2007 03:12:37 PM
01/22/2007 03:02:19 PM
01/22/2007 02:51:21 PM