{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:30:14Z","timestamp":1709829014559},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,10]]},"abstract":"<jats:p>\n            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\n            <jats:italic>complete information<\/jats:italic>\n            : the provider has full knowledge of the behavior of all customers. We present a complete characterization of the\n            <jats:italic>complexity of computing optimal pricing strategies<\/jats:italic>\n            and of\n            <jats:italic>computing best\/worst equilibria<\/jats:italic>\n            in this model. Basically, we show that most of these problems are inapproximable in the worst case but admit an FPAS in 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.A more realistic model considers providers with\n            <jats:italic>incomplete information<\/jats:italic>\n            . Following the game theoretic framework of Bayesian games introduced by Harsanyi, the provider is aware of probability distributions describing the behavior of the customers and aims at estimating its expected revenue under best\/worst equilibria. Somewhat counterintuitively, 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 problems increases with the precision of the available knowledge.\n          <\/jats:p>","DOI":"10.1145\/1198513.1198524","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"679-706","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Computing equilibria for a service provider game with (Im)perfect information"],"prefix":"10.1145","volume":"2","author":[{"given":"Rene","family":"Beier","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Artur","family":"Czumaj","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Krysta","sequence":"additional","affiliation":[{"name":"Dortmund University, Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Berthold","family":"V\u00f6cking","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Bierman H. S. and Fernandez L. 1998. Game Theory with Economic Applications. Addison-Wesley Reading MA.  Bierman H. S. and Fernandez L. 1998. Game Theory with Economic Applications. Addison-Wesley Reading MA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007445"},{"key":"e_1_2_1_3_1","volume-title":"In Proceedings of the 29th Annual International Colloquium on Automata, Languages and Programming. Springer-Verlag","author":"Fotakis D.","unstructured":"Fotakis , D. , Kontogiannis , S. , Koutsoupias , E. , Mavronicolas , M. , and Spirakis , P . 2002. The structure and complexity of Nash equilibria for a selfish routing game . In In Proceedings of the 29th Annual International Colloquium on Automata, Languages and Programming. Springer-Verlag , Berlin, Germany, 123--134. Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., and Spirakis, P. 2002. The structure and complexity of Nash equilibria for a selfish routing game. In In Proceedings of the 29th Annual International Colloquium on Automata, Languages and Programming. Springer-Verlag, Berlin, Germany, 123--134."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 30th Annual International Colloquium on Automata, Languages and Programming Springer-Verlag","author":"Feldmann R.","unstructured":"Feldmann , R. , Gairing , M. , L\u00fccking , T. , Monien , B. , and Rode , M . 2003. Nashification and the coordination ratio for a selfish routing game . Proceedings of the 30th Annual International Colloquium on Automata, Languages and Programming Springer-Verlag , Berlin, Germany, 514--526. Feldmann, R., Gairing, M., L\u00fccking, T., Monien, B., and Rode, M. 2003. Nashification and the coordination ratio for a selfish routing game. Proceedings of the 30th Annual International Colloquium on Automata, Languages and Programming Springer-Verlag, Berlin, Germany, 514--526."},{"key":"e_1_2_1_5_1","unstructured":"Garey M. R. and Johnson M. R. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman San Francisco CA.   Garey M. R. and Johnson M. R. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman San Francisco CA."},{"key":"e_1_2_1_6_1","first-page":"347","article-title":"A theory of monopoly pricing schemes with demand uncertainty","volume":"71","author":"Harris M.","year":"1981","unstructured":"Harris , M. , and Raviv , A. 1981 . A theory of monopoly pricing schemes with demand uncertainty . Amer. Econ. Rev. 71 , 3, 347 -- 365 . Harris, M., and Raviv, A. 1981. A theory of monopoly pricing schemes with demand uncertainty. Amer. Econ. Rev. 71, 3, 347--365.","journal-title":"Amer. Econ. Rev."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.14.3.159"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737554"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0592"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Kellerer H. Pferschy U. and Pisinger D. 2004. Knapsack Problems. Springer-Verlag Berlin Germany.  Kellerer H. Pferschy U. and Pisinger D. 2004. Knapsack Problems. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-3-540-24777-7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-6419.00083"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2307\/2297551"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/3003266"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/2555674"},{"key":"e_1_2_1_17_1","first-page":"195","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics, Algorithms and Combinatorics","author":"McDiarmid C.","unstructured":"McDiarmid , C. 1998. Concentration . In Probabilistic Methods for Algorithmic Discrete Mathematics, Algorithms and Combinatorics , M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, Eds. Springer-Verlag , Berlin, Germany , pp. 195 -- 247 . McDiarmid, C. 1998. Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, Algorithms and Combinatorics, M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, Eds. Springer-Verlag, Berlin, Germany, pp. 195--247."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0027"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001820050086"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/1881841"},{"key":"e_1_2_1_23_1","volume-title":"Game Theory","author":"Owen G.","unstructured":"Owen , G. 1995. Game Theory . Academic Press , New York . Owen, G. 1995. Game Theory. Academic Press, New York."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/501158.501160"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 43st IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Ronen A.","unstructured":"Ronen , A. , and Saberi , A . 2002. On the hardness of optimal auctions . In Proceedings of the 43st IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 396--405. Ronen, A., and Saberi, A. 2002. On the hardness of optimal auctions. In Proceedings of the 43st IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 396--405."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.2307\/3003566"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2307\/2555506"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2307\/2555984"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0729"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1198513.1198524","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T20:33:54Z","timestamp":1672259634000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1198513.1198524"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,10]]}},"alternative-id":["10.1145\/1198513.1198524"],"URL":"https:\/\/doi.org\/10.1145\/1198513.1198524","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10]]},"assertion":[{"value":"2006-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}