{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T17:02:19Z","timestamp":1649178139376},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,1,4]],"date-time":"2016-01-04T00:00:00Z","timestamp":1451865600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s00453-015-0108-5","type":"journal-article","created":{"date-parts":[[2016,1,4]],"date-time":"2016-01-04T20:42:41Z","timestamp":1451940161000},"page":"836-866","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Price of Optimum: Complexity and Approximation for a Matching Game"],"prefix":"10.1007","volume":"77","author":[{"given":"Bruno","family":"Escoffier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurent","family":"Gourv\u00e8s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00f4me","family":"Monnot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,4]]},"reference":[{"key":"108_CR1","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1145\/506147.506153","volume":"49","author":"T Roughgarden","year":"2002","unstructured":"Roughgarden, T., Tardos, \u00c9.: How bad is selfish routing? J. ACM 49, 236\u2013259 (2002)","journal-title":"J. ACM"},{"key":"108_CR2","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.cosrev.2009.04.003","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. Comput. Sci. Rev. 3, 65\u201369 (2009)","journal-title":"Comput. Sci. Rev."},{"key":"108_CR3","doi-asserted-by":"publisher","unstructured":"Papadimitriou, C.H.: Algorithms, games, and the internet. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, STOC \u201801, pp. 749\u2013753. ACM, New York, NY, USA (2001). doi: 10.1145\/380752.380883","DOI":"10.1145\/380752.380883"},{"key":"108_CR4","doi-asserted-by":"crossref","first-page":"3327","DOI":"10.1016\/j.tcs.2009.01.005","volume":"410","author":"G Christodoulou","year":"2009","unstructured":"Christodoulou, G., Koutsoupias, E., Nanavati, A.: Coordination mechanisms. Theory Comput. Sci. 410, 3327\u20133336 (2009)","journal-title":"Theory Comput. Sci."},{"key":"108_CR5","volume-title":"Encyclopedia of Algorithms","author":"AC Kaporis","year":"2008","unstructured":"Kaporis, A.C., Spirakis, P.G.: Stackelberg games: the price of optimum. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms. Springer, Berlin (2008)"},{"key":"108_CR6","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1109\/90.554730","volume":"5","author":"YA Korilis","year":"1997","unstructured":"Korilis, Y.A., Lazar, A.A., Orda, A.: Achieving network optima using stackelberg routing strategies. IEEE\/ACM Trans. Netw. 5, 161\u2013173 (1997)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"108_CR7","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1137\/S0097539701397059","volume":"33","author":"T Roughgarden","year":"2004","unstructured":"Roughgarden, T.: Stackelberg scheduling strategies. SIAM J. Comput. 33, 332\u2013350 (2004)","journal-title":"SIAM J. Comput."},{"key":"108_CR8","volume-title":"Lecture Notes in Computer Science","author":"VSA Kumar","year":"2002","unstructured":"Kumar, V.S.A., Marathe, M.V.: Improved results for stackelberg scheduling strategies. In: Widmayer, P., Ruiz, F.T., Bueno, R.M., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) Lecture Notes in Computer Science. Springer, Berlin (2002)"},{"key":"108_CR9","first-page":"1133","volume-title":"SODA","author":"C Swamy","year":"2007","unstructured":"Swamy, C.: The effectiveness of stackelberg strategies and tolls for network congestion games. In: Bansal, N., Pruhs, K., Stein, C. (eds.) SODA, pp. 1133\u20131142. SIAM, Philadelphia (2007)"},{"key":"108_CR10","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1007\/s00224-008-9152-8","volume":"47","author":"D Fotakis","year":"2010","unstructured":"Fotakis, D.: Stackelberg strategies for atomic congestion games. Theory Comput. Syst. 47, 218\u2013249 (2010)","journal-title":"Theory Comput. Syst."},{"key":"108_CR11","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/j.geb.2009.06.006","volume":"67","author":"Y Sharma","year":"2009","unstructured":"Sharma, Y., Williamson, D.P.: Stackelberg thresholds in network routing games or the value of altruism. Games Econ. Behav. 67, 174\u2013190 (2009)","journal-title":"Games Econ. Behav."},{"key":"108_CR12","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1287\/moor.1100.0442","volume":"35","author":"V Bonifaci","year":"2010","unstructured":"Bonifaci, V., Harks, T., Sch\u00e4fer, G.: Stackelberg routing in arbitrary networks. Math. Oper. Res. 35, 330\u2013346 (2010)","journal-title":"Math. Oper. Res."},{"key":"108_CR13","doi-asserted-by":"crossref","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J Nash","year":"1951","unstructured":"Nash, J.: Non-cooperative games. Ann. Math. 54, 286\u2013295 (1951)","journal-title":"Ann. Math."},{"key":"108_CR14","first-page":"287","volume":"4","author":"RJ Aumann","year":"1959","unstructured":"Aumann, R.J.: Acceptable points in general cooperative n-person games. Contrib. Theory Games 4, 287\u2013324 (1959)","journal-title":"Contrib. Theory Games"},{"key":"108_CR15","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.geb.2008.03.005","volume":"65","author":"N Andelman","year":"2009","unstructured":"Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. Games Econ. Behav. 65, 289\u2013317 (2009)","journal-title":"Games Econ. Behav."},{"key":"108_CR16","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0166-218X(94)00091-Q","volume":"56","author":"Y Manoussakis","year":"1995","unstructured":"Manoussakis, Y.: Alternating paths in edge-colored complete graphs. Discret. Appl. Math. 56, 297\u2013309 (1995)","journal-title":"Discret. Appl. Math."},{"key":"108_CR17","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"DS Hochbaum","year":"1996","unstructured":"Hochbaum, D.S.: Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston, MA (1996)"},{"key":"108_CR18","doi-asserted-by":"crossref","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162, 439\u2013485 (2005)","journal-title":"Ann. Math."},{"key":"108_CR19","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74, 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"108_CR20","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some apx-completeness results for cubic graphs. Theory Comput. Sci. 237, 123\u2013134 (2000)","journal-title":"Theory Comput. Sci."},{"key":"108_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H (1979)"},{"key":"108_CR22","doi-asserted-by":"crossref","first-page":"9","DOI":"10.2307\/2312726","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69, 9\u201315 (1962)","journal-title":"Am. Math. Mon."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0108-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0108-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0108-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0108-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:47:23Z","timestamp":1559087243000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0108-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,4]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["108"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0108-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,4]]}}}