[{"abstract":[{"lang":"eng","text":"In this paper we consider a strategic variant of the online facility location problem. Given is a graph in which each node serves two roles: it is a strategic client stating requests as well as a potential location for a facility. In each time step one client states a request which induces private costs equal to the distance to the closest facility. Before serving, the clients may collectively decide to open new facilities, sharing the corresponding price. Instead of optimizing the global costs, each client acts selfishly. The prices of new facilities vary between nodes and also change over time, but are always bounded by some fixed value α. Both the requests as well as the facility prices are given by an online sequence and are not known in advance.We characterize the optimal strategies of the clients and analyze their overall performance in comparison to a centralized offline solution. If all players optimize their own competitiveness, the global performance of the system is O(√α⋅α) times worse than the offline optimum. A restriction to a natural subclass of strategies improves this result to O(α). We also show that for fixed facility costs, we can find strategies such that this bound further improves to O(√α)."}],"file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2018-03-21T12:55:43Z","creator":"florida","date_created":"2018-03-21T12:55:43Z","file_size":236253,"file_name":"149-chp_3A10.1007_2F978-3-319-48749-6_43.pdf","file_id":"1553","access_level":"closed"}],"status":"public","type":"conference","publication":"Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)","ddc":["040"],"language":[{"iso":"eng"}],"file_date_updated":"2018-03-21T12:55:43Z","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"name":"SFB 901 - Subproject A3","_id":"7"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"149","user_id":"477","series_title":"LNCS","department":[{"_id":"63"},{"_id":"541"}],"year":"2016","citation":{"bibtex":"@inproceedings{Drees_Feldkord_Skopalik_2016, series={LNCS}, title={Strategic Online Facility Location}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">10.1007/978-3-319-48749-6_43</a>}, booktitle={Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}, author={Drees, Maximilian and Feldkord, Björn and Skopalik, Alexander}, year={2016}, pages={593--607}, collection={LNCS} }","short":"M. Drees, B. Feldkord, A. Skopalik, in: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 593--607.","mla":"Drees, Maximilian, et al. “Strategic Online Facility Location.” <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2016, pp. 593--607, doi:<a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">10.1007/978-3-319-48749-6_43</a>.","apa":"Drees, M., Feldkord, B., &#38; Skopalik, A. (2016). Strategic Online Facility Location. In <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i> (pp. 593--607). <a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">https://doi.org/10.1007/978-3-319-48749-6_43</a>","ama":"Drees M, Feldkord B, Skopalik A. Strategic Online Facility Location. In: <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>. LNCS. ; 2016:593--607. doi:<a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">10.1007/978-3-319-48749-6_43</a>","ieee":"M. Drees, B. Feldkord, and A. Skopalik, “Strategic Online Facility Location,” in <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2016, pp. 593--607.","chicago":"Drees, Maximilian, Björn Feldkord, and Alexander Skopalik. “Strategic Online Facility Location.” In <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 593--607. LNCS, 2016. <a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">https://doi.org/10.1007/978-3-319-48749-6_43</a>."},"page":"593--607","has_accepted_license":"1","title":"Strategic Online Facility Location","doi":"10.1007/978-3-319-48749-6_43","date_updated":"2022-01-06T06:52:10Z","author":[{"last_name":"Drees","full_name":"Drees, Maximilian","first_name":"Maximilian"},{"first_name":"Björn","last_name":"Feldkord","full_name":"Feldkord, Björn","id":"22704"},{"first_name":"Alexander","last_name":"Skopalik","full_name":"Skopalik, Alexander","id":"40384"}],"date_created":"2017-10-17T12:41:21Z"},{"abstract":[{"lang":"eng","text":"Following the direction pioneered by Fiat and Papadimitriou in their 2010 paper [12], we study the complexity of deciding the existence of mixed equilibria for minimization games where players use valuations other than expectation to evaluate their costs. We consider risk-averse players seeking to minimize the sum V=E+R of expectationE and a risk valuationR of their costs; R is non-negative and vanishes exactly when the cost incurred to a player is constant over all choices of strategies by the other players. In a V-equilibrium, no player could unilaterally reduce her cost.Say that V has the Weak-Equilibrium-for-Expectation property if all strategies supported in a player's best-response mixed strategy incur the same conditional expectation of her cost. We introduce E-strict concavity and observe that every E-strictly concave valuation has the Weak-Equilibrium-for-Expectation property. We focus on a broad class of valuations shown to have the Weak-Equilibrium-for-Expectation property, which we exploit to prove two main complexity results, the first of their kind, for the two simplest cases of the problem:• Two strategies: Deciding the existence of a V-equilibrium is strongly NP-hard for the restricted class of player-specific scheduling games on two ordered links [22], when choosing R as (1)Var (variance), or (2)SD (standard deviation), or (3) a concave linear sum of even moments of small order.• Two players: Deciding the existence of a V-equilibrium is strongly NP-hard when choosing R as (1)γ⋅Var, or (2)γ⋅SD, where γ>0 is the risk-coefficient, or choosing V as (3) a convex combination of E+γ⋅Var and the concave ν-valuationν−1(E(ν(⋅))), where ν(x)=xr, with r≥2. This is a concrete consequence of a general strong NP-hardness result that only needs the Weak-Equilibrium-for-Expectation property and a few additional properties for V; its proof involves a reduction with a single parameter, which can be chosen efficiently so that each valuation satisfies the additional properties."}],"file":[{"relation":"main_file","success":1,"content_type":"application/pdf","file_name":"144-Monien_Mavronicolas-TCS2016_01.pdf","file_id":"1557","access_level":"closed","file_size":633599,"creator":"florida","date_created":"2018-03-21T12:58:42Z","date_updated":"2018-03-21T12:58:42Z"}],"status":"public","type":"journal_article","publication":"Theoretical Computer Science","ddc":["040"],"file_date_updated":"2018-03-21T12:58:42Z","language":[{"iso":"eng"}],"project":[{"name":"SFB 901","_id":"1"},{"_id":"7","name":"SFB 901 - Subprojekt A3"},{"name":"SFB 901 - Project Area A","_id":"2"}],"_id":"144","user_id":"42447","year":"2016","citation":{"short":"B. Monien, M. Mavronicolas, Theoretical Computer Science 634 (2016) 67–96.","bibtex":"@article{Monien_Mavronicolas_2016, title={The complexity of equilibria for risk-modeling valuations}, volume={634}, DOI={<a href=\"https://doi.org/10.1016/j.tcs.2016.04.013\">10.1016/j.tcs.2016.04.013</a>}, journal={Theoretical Computer Science}, publisher={Elsevier}, author={Monien, Burkhard and Mavronicolas, Marios}, year={2016}, pages={67–96} }","mla":"Monien, Burkhard, and Marios Mavronicolas. “The Complexity of Equilibria for Risk-Modeling Valuations.” <i>Theoretical Computer Science</i>, vol. 634, Elsevier, 2016, pp. 67–96, doi:<a href=\"https://doi.org/10.1016/j.tcs.2016.04.013\">10.1016/j.tcs.2016.04.013</a>.","apa":"Monien, B., &#38; Mavronicolas, M. (2016). The complexity of equilibria for risk-modeling valuations. <i>Theoretical Computer Science</i>, <i>634</i>, 67–96. <a href=\"https://doi.org/10.1016/j.tcs.2016.04.013\">https://doi.org/10.1016/j.tcs.2016.04.013</a>","chicago":"Monien, Burkhard, and Marios Mavronicolas. “The Complexity of Equilibria for Risk-Modeling Valuations.” <i>Theoretical Computer Science</i> 634 (2016): 67–96. <a href=\"https://doi.org/10.1016/j.tcs.2016.04.013\">https://doi.org/10.1016/j.tcs.2016.04.013</a>.","ieee":"B. Monien and M. Mavronicolas, “The complexity of equilibria for risk-modeling valuations,” <i>Theoretical Computer Science</i>, vol. 634, pp. 67–96, 2016.","ama":"Monien B, Mavronicolas M. The complexity of equilibria for risk-modeling valuations. <i>Theoretical Computer Science</i>. 2016;634:67-96. doi:<a href=\"https://doi.org/10.1016/j.tcs.2016.04.013\">10.1016/j.tcs.2016.04.013</a>"},"intvolume":"       634","page":"67-96","has_accepted_license":"1","title":"The complexity of equilibria for risk-modeling valuations","doi":"10.1016/j.tcs.2016.04.013","date_updated":"2022-01-06T06:51:59Z","publisher":"Elsevier","author":[{"first_name":"Burkhard","last_name":"Monien","full_name":"Monien, Burkhard"},{"first_name":"Marios","full_name":"Mavronicolas, Marios","last_name":"Mavronicolas"}],"date_created":"2017-10-17T12:41:20Z","volume":634},{"citation":{"apa":"N, N. (2016). <i>Renegotiable vs. Non-Renegotiable Agreements - Theory and Applications</i>. Universität Paderborn.","bibtex":"@book{N_2016, title={Renegotiable vs. Non-Renegotiable Agreements - Theory and Applications}, publisher={Universität Paderborn}, author={N, N}, year={2016} }","short":"N. N, Renegotiable vs. Non-Renegotiable Agreements - Theory and Applications, Universität Paderborn, 2016.","mla":"N, N. <i>Renegotiable vs. Non-Renegotiable Agreements - Theory and Applications</i>. Universität Paderborn, 2016.","ama":"N N. <i>Renegotiable vs. Non-Renegotiable Agreements - Theory and Applications</i>. Universität Paderborn; 2016.","chicago":"N, N. <i>Renegotiable vs. Non-Renegotiable Agreements - Theory and Applications</i>. Universität Paderborn, 2016.","ieee":"N. N, <i>Renegotiable vs. Non-Renegotiable Agreements - Theory and Applications</i>. Universität Paderborn, 2016."},"year":"2016","date_created":"2018-11-28T10:27:23Z","supervisor":[{"full_name":"Haake, Claus-Jochen","id":"20801","last_name":"Haake","first_name":"Claus-Jochen"}],"author":[{"full_name":"N, N","last_name":"N","first_name":"N"}],"publisher":"Universität Paderborn","date_updated":"2022-11-30T14:17:14Z","title":"Renegotiable vs. Non-Renegotiable Agreements - Theory and Applications","type":"mastersthesis","status":"public","department":[{"_id":"205"}],"user_id":"477","_id":"5934","project":[{"name":"SFB 901","_id":"1"},{"_id":"7","name":"SFB 901 - Subproject A3"},{"_id":"2","name":"SFB 901 - Project Area A"}],"language":[{"iso":"eng"}]},{"status":"public","type":"bachelorsthesis","language":[{"iso":"eng"}],"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Project Area A","_id":"2"},{"name":"SFB 901 - Subproject A3","_id":"7"}],"_id":"5932","user_id":"477","department":[{"_id":"205"}],"year":"2016","citation":{"ama":"N N. <i>Wie Wertvoll Ist Der Einzelne Für Das Team? - Performancemessung Der Bundesligaspieler Anhand Der Kooperativen Spieltheorie Der Saison 2014/2015</i>. Universität Paderborn; 2016.","chicago":"N, N. <i>Wie Wertvoll Ist Der Einzelne Für Das Team? - Performancemessung Der Bundesligaspieler Anhand Der Kooperativen Spieltheorie Der Saison 2014/2015</i>. Universität Paderborn, 2016.","ieee":"N. N, <i>Wie wertvoll ist der Einzelne für das Team? - Performancemessung der Bundesligaspieler anhand der kooperativen Spieltheorie der Saison 2014/2015</i>. Universität Paderborn, 2016.","apa":"N, N. (2016). <i>Wie wertvoll ist der Einzelne für das Team? - Performancemessung der Bundesligaspieler anhand der kooperativen Spieltheorie der Saison 2014/2015</i>. Universität Paderborn.","mla":"N, N. <i>Wie Wertvoll Ist Der Einzelne Für Das Team? - Performancemessung Der Bundesligaspieler Anhand Der Kooperativen Spieltheorie Der Saison 2014/2015</i>. Universität Paderborn, 2016.","short":"N. N, Wie Wertvoll Ist Der Einzelne Für Das Team? - Performancemessung Der Bundesligaspieler Anhand Der Kooperativen Spieltheorie Der Saison 2014/2015, Universität Paderborn, 2016.","bibtex":"@book{N_2016, title={Wie wertvoll ist der Einzelne für das Team? - Performancemessung der Bundesligaspieler anhand der kooperativen Spieltheorie der Saison 2014/2015}, publisher={Universität Paderborn}, author={N, N}, year={2016} }"},"title":"Wie wertvoll ist der Einzelne für das Team? - Performancemessung der Bundesligaspieler anhand der kooperativen Spieltheorie der Saison 2014/2015","publisher":"Universität Paderborn","date_updated":"2022-11-30T14:25:52Z","date_created":"2018-11-28T10:23:06Z","author":[{"first_name":"N","last_name":"N","full_name":"N, N"}],"supervisor":[{"id":"20801","full_name":"Haake, Claus-Jochen","last_name":"Haake","first_name":"Claus-Jochen"}]},{"department":[{"_id":"205"}],"user_id":"477","_id":"5940","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area A","_id":"2"},{"name":"SFB 901 - Subproject A3","_id":"7"}],"language":[{"iso":"eng"}],"type":"bachelorsthesis","status":"public","author":[{"first_name":"N","last_name":"N","full_name":"N, N"}],"supervisor":[{"id":"20801","full_name":"Haake, Claus-Jochen","last_name":"Haake","first_name":"Claus-Jochen"}],"date_created":"2018-11-28T10:39:15Z","date_updated":"2022-11-30T14:26:34Z","publisher":"Universität Paderborn","title":"Automatisiertes Matching von Angebot und Nachfrage in der Kunststoffindustrie Ein Fallbeispiel in Kooperation mit der PINPOOLS GmbH","citation":{"chicago":"N, N. <i>Automatisiertes Matching von Angebot Und Nachfrage in Der Kunststoffindustrie Ein Fallbeispiel in Kooperation Mit Der PINPOOLS GmbH</i>. Universität Paderborn, 2016.","ieee":"N. N, <i>Automatisiertes Matching von Angebot und Nachfrage in der Kunststoffindustrie Ein Fallbeispiel in Kooperation mit der PINPOOLS GmbH</i>. Universität Paderborn, 2016.","ama":"N N. <i>Automatisiertes Matching von Angebot Und Nachfrage in Der Kunststoffindustrie Ein Fallbeispiel in Kooperation Mit Der PINPOOLS GmbH</i>. Universität Paderborn; 2016.","bibtex":"@book{N_2016, title={Automatisiertes Matching von Angebot und Nachfrage in der Kunststoffindustrie Ein Fallbeispiel in Kooperation mit der PINPOOLS GmbH}, publisher={Universität Paderborn}, author={N, N}, year={2016} }","short":"N. N, Automatisiertes Matching von Angebot Und Nachfrage in Der Kunststoffindustrie Ein Fallbeispiel in Kooperation Mit Der PINPOOLS GmbH, Universität Paderborn, 2016.","mla":"N, N. <i>Automatisiertes Matching von Angebot Und Nachfrage in Der Kunststoffindustrie Ein Fallbeispiel in Kooperation Mit Der PINPOOLS GmbH</i>. Universität Paderborn, 2016.","apa":"N, N. (2016). <i>Automatisiertes Matching von Angebot und Nachfrage in der Kunststoffindustrie Ein Fallbeispiel in Kooperation mit der PINPOOLS GmbH</i>. Universität Paderborn."},"year":"2016"},{"language":[{"iso":"eng"}],"department":[{"_id":"205"}],"user_id":"477","_id":"5935","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area A","_id":"2"},{"name":"SFB 901 - Subproject A3","_id":"7"}],"status":"public","type":"bachelorsthesis","title":"Der Einfluss von Netzwerken auf Gleichgewichtspreise - eine spieltheoretische Analyse","supervisor":[{"first_name":"Claus-Jochen","id":"20801","full_name":"Haake, Claus-Jochen","last_name":"Haake"}],"date_created":"2018-11-28T10:29:57Z","author":[{"last_name":"N","full_name":"N, N","first_name":"N"}],"publisher":"Universität Paderborn","date_updated":"2022-11-30T14:25:23Z","citation":{"ama":"N N. <i>Der Einfluss von Netzwerken Auf Gleichgewichtspreise - Eine Spieltheoretische Analyse</i>. Universität Paderborn; 2016.","chicago":"N, N. <i>Der Einfluss von Netzwerken Auf Gleichgewichtspreise - Eine Spieltheoretische Analyse</i>. Universität Paderborn, 2016.","ieee":"N. N, <i>Der Einfluss von Netzwerken auf Gleichgewichtspreise - eine spieltheoretische Analyse</i>. Universität Paderborn, 2016.","mla":"N, N. <i>Der Einfluss von Netzwerken Auf Gleichgewichtspreise - Eine Spieltheoretische Analyse</i>. Universität Paderborn, 2016.","short":"N. N, Der Einfluss von Netzwerken Auf Gleichgewichtspreise - Eine Spieltheoretische Analyse, Universität Paderborn, 2016.","bibtex":"@book{N_2016, title={Der Einfluss von Netzwerken auf Gleichgewichtspreise - eine spieltheoretische Analyse}, publisher={Universität Paderborn}, author={N, N}, year={2016} }","apa":"N, N. (2016). <i>Der Einfluss von Netzwerken auf Gleichgewichtspreise - eine spieltheoretische Analyse</i>. Universität Paderborn."},"year":"2016"},{"year":"2016","citation":{"chicago":"N, N. <i>Hat Vertikale Integration Einen Einfluss Auf Die Allgemeine Wohlfahrt?</i> Universität Paderborn, 2016.","ieee":"N. N, <i>Hat vertikale Integration einen Einfluss auf die allgemeine Wohlfahrt?</i> Universität Paderborn, 2016.","ama":"N N. <i>Hat Vertikale Integration Einen Einfluss Auf Die Allgemeine Wohlfahrt?</i> Universität Paderborn; 2016.","short":"N. N, Hat Vertikale Integration Einen Einfluss Auf Die Allgemeine Wohlfahrt?, Universität Paderborn, 2016.","mla":"N, N. <i>Hat Vertikale Integration Einen Einfluss Auf Die Allgemeine Wohlfahrt?</i> Universität Paderborn, 2016.","bibtex":"@book{N_2016, title={Hat vertikale Integration einen Einfluss auf die allgemeine Wohlfahrt?}, publisher={Universität Paderborn}, author={N, N}, year={2016} }","apa":"N, N. (2016). <i>Hat vertikale Integration einen Einfluss auf die allgemeine Wohlfahrt?</i> Universität Paderborn."},"date_updated":"2022-11-30T14:26:07Z","publisher":"Universität Paderborn","supervisor":[{"last_name":"Haake","id":"20801","full_name":"Haake, Claus-Jochen","first_name":"Claus-Jochen"}],"date_created":"2018-11-28T10:14:40Z","author":[{"first_name":"N","last_name":"N","full_name":"N, N"}],"title":"Hat vertikale Integration einen Einfluss auf die allgemeine Wohlfahrt?","type":"bachelorsthesis","status":"public","project":[{"_id":"1","name":"SFB 901"},{"_id":"2","name":"SFB 901 - Project Area A"},{"_id":"7","name":"SFB 901 - Subproject A3"}],"_id":"5931","user_id":"477","department":[{"_id":"205"}],"language":[{"iso":"eng"}]},{"language":[{"iso":"eng"}],"project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"7","name":"SFB 901 - Subproject A3"}],"_id":"5941","user_id":"477","department":[{"_id":"205"}],"status":"public","type":"bachelorsthesis","title":"Stabile Supply-Chains - Basierend auf der Theorie der Matching-Märkte","date_updated":"2022-11-30T14:26:22Z","publisher":"Universität Paderborn","author":[{"full_name":"N, N","last_name":"N","first_name":"N"}],"date_created":"2018-11-28T10:42:02Z","supervisor":[{"first_name":"Claus-Jochen","last_name":"Haake","id":"20801","full_name":"Haake, Claus-Jochen"}],"year":"2016","citation":{"ama":"N N. <i>Stabile Supply-Chains - Basierend Auf Der Theorie Der Matching-Märkte</i>. Universität Paderborn; 2016.","chicago":"N, N. <i>Stabile Supply-Chains - Basierend Auf Der Theorie Der Matching-Märkte</i>. Universität Paderborn, 2016.","ieee":"N. N, <i>Stabile Supply-Chains - Basierend auf der Theorie der Matching-Märkte</i>. Universität Paderborn, 2016.","apa":"N, N. (2016). <i>Stabile Supply-Chains - Basierend auf der Theorie der Matching-Märkte</i>. Universität Paderborn.","mla":"N, N. <i>Stabile Supply-Chains - Basierend Auf Der Theorie Der Matching-Märkte</i>. Universität Paderborn, 2016.","short":"N. N, Stabile Supply-Chains - Basierend Auf Der Theorie Der Matching-Märkte, Universität Paderborn, 2016.","bibtex":"@book{N_2016, title={Stabile Supply-Chains - Basierend auf der Theorie der Matching-Märkte}, publisher={Universität Paderborn}, author={N, N}, year={2016} }"}},{"title":"Die Berechnung von Machtindizes - ein Vergleich verschiedener Verfahren","date_updated":"2022-11-30T14:25:37Z","publisher":"Universität Paderborn","date_created":"2018-11-28T10:25:05Z","supervisor":[{"first_name":"Claus-Jochen","last_name":"Haake","full_name":"Haake, Claus-Jochen","id":"20801"}],"author":[{"first_name":"N","last_name":"N","full_name":"N, N"}],"year":"2016","citation":{"mla":"N, N. <i>Die Berechnung von Machtindizes - Ein Vergleich Verschiedener Verfahren</i>. Universität Paderborn, 2016.","bibtex":"@book{N_2016, title={Die Berechnung von Machtindizes - ein Vergleich verschiedener Verfahren}, publisher={Universität Paderborn}, author={N, N}, year={2016} }","short":"N. N, Die Berechnung von Machtindizes - Ein Vergleich Verschiedener Verfahren, Universität Paderborn, 2016.","ama":"N N. <i>Die Berechnung von Machtindizes - Ein Vergleich Verschiedener Verfahren</i>. Universität Paderborn; 2016.","apa":"N, N. (2016). <i>Die Berechnung von Machtindizes - ein Vergleich verschiedener Verfahren</i>. Universität Paderborn.","chicago":"N, N. <i>Die Berechnung von Machtindizes - Ein Vergleich Verschiedener Verfahren</i>. Universität Paderborn, 2016.","ieee":"N. N, <i>Die Berechnung von Machtindizes - ein Vergleich verschiedener Verfahren</i>. Universität Paderborn, 2016."},"language":[{"iso":"eng"}],"project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"7","name":"SFB 901 - Subproject A3"}],"_id":"5933","user_id":"477","department":[{"_id":"205"}],"status":"public","type":"bachelorsthesis"},{"citation":{"bibtex":"@book{N_2016, title={Intermediaries in Buyer Seller Networks}, publisher={Universität Paderborn}, author={N, N}, year={2016} }","short":"N. N, Intermediaries in Buyer Seller Networks, Universität Paderborn, 2016.","mla":"N, N. <i>Intermediaries in Buyer Seller Networks</i>. Universität Paderborn, 2016.","apa":"N, N. (2016). <i>Intermediaries in Buyer Seller Networks</i>. Universität Paderborn.","ama":"N N. <i>Intermediaries in Buyer Seller Networks</i>. Universität Paderborn; 2016.","chicago":"N, N. <i>Intermediaries in Buyer Seller Networks</i>. Universität Paderborn, 2016.","ieee":"N. N, <i>Intermediaries in Buyer Seller Networks</i>. Universität Paderborn, 2016."},"year":"2016","title":"Intermediaries in Buyer Seller Networks","date_created":"2018-11-28T10:36:09Z","author":[{"first_name":"N","last_name":"N","full_name":"N, N"}],"supervisor":[{"last_name":"Haake","id":"20801","full_name":"Haake, Claus-Jochen","first_name":"Claus-Jochen"}],"publisher":"Universität Paderborn","date_updated":"2022-11-30T14:26:49Z","status":"public","type":"bachelorsthesis","language":[{"iso":"eng"}],"user_id":"477","department":[{"_id":"205"}],"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"7","name":"SFB 901 - Subproject A3"}],"_id":"5939"},{"type":"bachelorsthesis","status":"public","department":[{"_id":"205"}],"user_id":"477","_id":"5937","project":[{"name":"SFB 901","_id":"1"},{"_id":"2","name":"SFB 901 - Project Area A"},{"_id":"7","name":"SFB 901 - Subproject A3"}],"language":[{"iso":"eng"}],"citation":{"ama":"N N. <i>Staatliche Regulierung in Vertikal Verbundenen Industrien - Eine Spieltheoretische Analyse</i>. Universität Paderborn; 2016.","chicago":"N, N. <i>Staatliche Regulierung in Vertikal Verbundenen Industrien - Eine Spieltheoretische Analyse</i>. Universität Paderborn, 2016.","ieee":"N. N, <i>Staatliche Regulierung in vertikal verbundenen Industrien - eine spieltheoretische Analyse</i>. Universität Paderborn, 2016.","apa":"N, N. (2016). <i>Staatliche Regulierung in vertikal verbundenen Industrien - eine spieltheoretische Analyse</i>. Universität Paderborn.","short":"N. N, Staatliche Regulierung in Vertikal Verbundenen Industrien - Eine Spieltheoretische Analyse, Universität Paderborn, 2016.","bibtex":"@book{N_2016, title={Staatliche Regulierung in vertikal verbundenen Industrien - eine spieltheoretische Analyse}, publisher={Universität Paderborn}, author={N, N}, year={2016} }","mla":"N, N. <i>Staatliche Regulierung in Vertikal Verbundenen Industrien - Eine Spieltheoretische Analyse</i>. Universität Paderborn, 2016."},"year":"2016","date_created":"2018-11-28T10:32:44Z","author":[{"last_name":"N","full_name":"N, N","first_name":"N"}],"supervisor":[{"last_name":"Haake","id":"20801","full_name":"Haake, Claus-Jochen","first_name":"Claus-Jochen"}],"publisher":"Universität Paderborn","date_updated":"2022-11-30T14:27:16Z","title":"Staatliche Regulierung in vertikal verbundenen Industrien - eine spieltheoretische Analyse"},{"date_updated":"2022-11-30T14:27:02Z","publisher":"Universität Paderborn","supervisor":[{"first_name":"Claus-Jochen","last_name":"Haake","id":"20801","full_name":"Haake, Claus-Jochen"}],"author":[{"first_name":"N","last_name":"N","full_name":"N, N"}],"date_created":"2018-11-28T10:34:03Z","title":"Pricing and Revenue Sharing of Bundles Using Game Theoretical Concepts","year":"2016","citation":{"ama":"N N. <i>Pricing and Revenue Sharing of Bundles Using Game Theoretical Concepts</i>. Universität Paderborn; 2016.","ieee":"N. N, <i>Pricing and Revenue Sharing of Bundles Using Game Theoretical Concepts</i>. Universität Paderborn, 2016.","chicago":"N, N. <i>Pricing and Revenue Sharing of Bundles Using Game Theoretical Concepts</i>. Universität Paderborn, 2016.","apa":"N, N. (2016). <i>Pricing and Revenue Sharing of Bundles Using Game Theoretical Concepts</i>. Universität Paderborn.","mla":"N, N. <i>Pricing and Revenue Sharing of Bundles Using Game Theoretical Concepts</i>. Universität Paderborn, 2016.","short":"N. N, Pricing and Revenue Sharing of Bundles Using Game Theoretical Concepts, Universität Paderborn, 2016.","bibtex":"@book{N_2016, title={Pricing and Revenue Sharing of Bundles Using Game Theoretical Concepts}, publisher={Universität Paderborn}, author={N, N}, year={2016} }"},"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Project Area A","_id":"2"},{"name":"SFB 901 - Subproject A3","_id":"7"}],"_id":"5938","user_id":"477","department":[{"_id":"205"}],"language":[{"iso":"eng"}],"type":"bachelorsthesis","status":"public"},{"ddc":["040"],"language":[{"iso":"eng"}],"abstract":[{"text":"We analyze the stability of networks when two intermediaries strategically form costly links to customers. We interpret these links as customer relationships that enable trade to sell a product. Equilibrium prices and equilibrium quantities on the output as well as on the input market are determined endogenously for a given network of customer relationships. We investigate in how far the substitutability of the intermediaries' products and the costs of link formation influence the intermediaries' equilibrium profits and thus have an impact on the incentives to strategically form relationships to customers. For networks with three customers we characterize locally stable networks, in particular existence is guaranteed for any degree of substitutability. Moreover for the special cases of perfect complements, independent products and perfect substitutes, local stability coincides with the stronger concept of Nash stability. Additionally, for networks with n customers we analyze stability regions for selected networks and determine their limits when n goes to infinity. It turns out that the shape of the stability regions for those networks does not significantly change compared to a setting with a small number of customers. ","lang":"eng"}],"file":[{"relation":"main_file","content_type":"application/pdf","title":"Strategic Formation of Customer Relationship Networks","file_size":908865,"file_name":"WP - Strategic Formation of Customer Relationship Networks.pdf","file_id":"3865","access_level":"closed","date_updated":"2018-08-09T09:13:36Z","creator":"cjhaake","date_created":"2018-08-09T09:10:34Z"}],"publisher":"Universität Paderborn","date_created":"2017-10-17T12:41:40Z","title":"Strategic Formation of Customer Relationship Networks","year":"2015","project":[{"_id":"1","name":"SFB 901"},{"_id":"7","name":"SFB 901 - Subprojekt A3"},{"name":"SFB 901 - Project Area A","_id":"2"}],"_id":"249","series_title":"Working Papers CIE","user_id":"65453","department":[{"_id":"205"},{"_id":"475"}],"file_date_updated":"2018-08-09T09:13:36Z","type":"working_paper","urn":"2499","status":"public","date_updated":"2022-01-06T06:56:40Z","author":[{"last_name":"Brangewitz","full_name":"Brangewitz, Sonja","first_name":"Sonja"},{"last_name":"Haake","id":"20801","full_name":"Haake, Claus-Jochen","first_name":"Claus-Jochen"},{"last_name":"Möhlmeier","full_name":"Möhlmeier, Philipp","first_name":"Philipp"}],"volume":91,"has_accepted_license":"1","citation":{"ama":"Brangewitz S, Haake C-J, Möhlmeier P. <i>Strategic Formation of Customer Relationship Networks</i>. Vol 91. Universität Paderborn; 2015.","ieee":"S. Brangewitz, C.-J. Haake, and P. Möhlmeier, <i>Strategic Formation of Customer Relationship Networks</i>, vol. 91. Universität Paderborn, 2015.","chicago":"Brangewitz, Sonja, Claus-Jochen Haake, and Philipp Möhlmeier. <i>Strategic Formation of Customer Relationship Networks</i>. Vol. 91. Working Papers CIE. Universität Paderborn, 2015.","mla":"Brangewitz, Sonja, et al. <i>Strategic Formation of Customer Relationship Networks</i>. Vol. 91, Universität Paderborn, 2015.","bibtex":"@book{Brangewitz_Haake_Möhlmeier_2015, series={Working Papers CIE}, title={Strategic Formation of Customer Relationship Networks}, volume={91}, publisher={Universität Paderborn}, author={Brangewitz, Sonja and Haake, Claus-Jochen and Möhlmeier, Philipp}, year={2015}, collection={Working Papers CIE} }","short":"S. Brangewitz, C.-J. Haake, P. Möhlmeier, Strategic Formation of Customer Relationship Networks, Universität Paderborn, 2015.","apa":"Brangewitz, S., Haake, C.-J., &#38; Möhlmeier, P. (2015). <i>Strategic Formation of Customer Relationship Networks</i> (Vol. 91). Universität Paderborn."},"intvolume":"        91"},{"department":[{"_id":"63"},{"_id":"541"}],"user_id":"14052","_id":"251","project":[{"_id":"1","name":"SFB 901"},{"_id":"7","name":"SFB 901 - Subprojekt A3"},{"_id":"2","name":"SFB 901 - Project Area A"}],"type":"mastersthesis","status":"public","supervisor":[{"last_name":"Skopalik","id":"40384","full_name":"Skopalik, Alexander","first_name":"Alexander"}],"date_created":"2017-10-17T12:41:41Z","author":[{"first_name":"Karlson","last_name":"Pfannschmidt","full_name":"Pfannschmidt, Karlson"}],"date_updated":"2022-01-06T06:56:50Z","publisher":"Universität Paderborn","title":"Solving the aggregated bandits problem","citation":{"apa":"Pfannschmidt, K. (2015). <i>Solving the aggregated bandits problem</i>. Universität Paderborn.","bibtex":"@book{Pfannschmidt_2015, title={Solving the aggregated bandits problem}, publisher={Universität Paderborn}, author={Pfannschmidt, Karlson}, year={2015} }","mla":"Pfannschmidt, Karlson. <i>Solving the Aggregated Bandits Problem</i>. Universität Paderborn, 2015.","short":"K. Pfannschmidt, Solving the Aggregated Bandits Problem, Universität Paderborn, 2015.","ama":"Pfannschmidt K. <i>Solving the Aggregated Bandits Problem</i>. Universität Paderborn; 2015.","ieee":"K. Pfannschmidt, <i>Solving the aggregated bandits problem</i>. Universität Paderborn, 2015.","chicago":"Pfannschmidt, Karlson. <i>Solving the Aggregated Bandits Problem</i>. Universität Paderborn, 2015."},"year":"2015"},{"type":"bachelorsthesis","status":"public","user_id":"42447","department":[{"_id":"280"}],"project":[{"name":"SFB 901","_id":"1"},{"_id":"7","name":"SFB 901 - Subprojekt A3"},{"name":"SFB 901 - Project Area A","_id":"2"}],"_id":"256","language":[{"iso":"ger"}],"citation":{"short":"F. Zindler, Selektive Vertriebssysteme am Fallbeispiel der Adidas AG - eine wettbewerbspolitische Beurteilung, Universität Paderborn, 2015.","mla":"Zindler, Finn. <i>Selektive Vertriebssysteme am Fallbeispiel der Adidas AG - eine wettbewerbspolitische Beurteilung</i>. Universität Paderborn, 2015.","bibtex":"@book{Zindler_2015, title={Selektive Vertriebssysteme am Fallbeispiel der Adidas AG - eine wettbewerbspolitische Beurteilung}, publisher={Universität Paderborn}, author={Zindler, Finn}, year={2015} }","apa":"Zindler, F. (2015). <i>Selektive Vertriebssysteme am Fallbeispiel der Adidas AG - eine wettbewerbspolitische Beurteilung</i>. Universität Paderborn.","chicago":"Zindler, Finn. <i>Selektive Vertriebssysteme am Fallbeispiel der Adidas AG - eine wettbewerbspolitische Beurteilung</i>. Universität Paderborn, 2015.","ieee":"F. Zindler, <i>Selektive Vertriebssysteme am Fallbeispiel der Adidas AG - eine wettbewerbspolitische Beurteilung</i>. Universität Paderborn, 2015.","ama":"Zindler F. <i>Selektive Vertriebssysteme am Fallbeispiel der Adidas AG - eine wettbewerbspolitische Beurteilung</i>. Universität Paderborn; 2015."},"year":"2015","author":[{"first_name":"Finn","full_name":"Zindler, Finn","last_name":"Zindler"}],"supervisor":[{"last_name":"Hehenkamp","id":"37339","full_name":"Hehenkamp, Burkhard","first_name":"Burkhard"}],"date_created":"2017-10-17T12:41:42Z","date_updated":"2022-01-06T06:57:07Z","publisher":"Universität Paderborn","title":"Selektive Vertriebssysteme am Fallbeispiel der Adidas AG - eine wettbewerbspolitische Beurteilung"},{"language":[{"iso":"ger"}],"user_id":"42447","department":[{"_id":"280"}],"project":[{"name":"SFB 901","_id":"1"},{"_id":"7","name":"SFB 901 - Subprojekt A3"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"282","status":"public","type":"bachelorsthesis","title":"Koordinierter Patentschutz in einer globalisierten Welt - Effizienz- und Anreizwirkungen auf die Arzneimittelversorgung in Entwicklungsländern","author":[{"first_name":"Michelle","full_name":"Kirsch, Michelle","last_name":"Kirsch"}],"supervisor":[{"last_name":"Hehenkamp","full_name":"Hehenkamp, Burkhard","id":"37339","first_name":"Burkhard"}],"date_created":"2017-10-17T12:41:47Z","date_updated":"2022-01-06T06:57:53Z","publisher":"Universität Paderborn","citation":{"bibtex":"@book{Kirsch_2015, title={Koordinierter Patentschutz in einer globalisierten Welt - Effizienz- und Anreizwirkungen auf die Arzneimittelversorgung in Entwicklungsländern}, publisher={Universität Paderborn}, author={Kirsch, Michelle}, year={2015} }","mla":"Kirsch, Michelle. <i>Koordinierter Patentschutz in einer globalisierten Welt - Effizienz- und Anreizwirkungen auf die Arzneimittelversorgung in Entwicklungsländern</i>. Universität Paderborn, 2015.","short":"M. Kirsch, Koordinierter Patentschutz in einer globalisierten Welt - Effizienz- und Anreizwirkungen auf die Arzneimittelversorgung in Entwicklungsländern, Universität Paderborn, 2015.","apa":"Kirsch, M. (2015). <i>Koordinierter Patentschutz in einer globalisierten Welt - Effizienz- und Anreizwirkungen auf die Arzneimittelversorgung in Entwicklungsländern</i>. Universität Paderborn.","ama":"Kirsch M. <i>Koordinierter Patentschutz in einer globalisierten Welt - Effizienz- und Anreizwirkungen auf die Arzneimittelversorgung in Entwicklungsländern</i>. Universität Paderborn; 2015.","ieee":"M. Kirsch, <i>Koordinierter Patentschutz in einer globalisierten Welt - Effizienz- und Anreizwirkungen auf die Arzneimittelversorgung in Entwicklungsländern</i>. Universität Paderborn, 2015.","chicago":"Kirsch, Michelle. <i>Koordinierter Patentschutz in einer globalisierten Welt - Effizienz- und Anreizwirkungen auf die Arzneimittelversorgung in Entwicklungsländern</i>. Universität Paderborn, 2015."},"year":"2015"},{"ddc":["040"],"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We revisit the simple class of weighted congestion games on parallel links [10], where each player has a non-negative weight and her cost on the link she chooses is the sum of the weights of all players choosing the link. We extend this class to mix-weighted congestion games on parallel links, where weights may as well be negative. For the resulting simple class, we study the complexity of deciding the existence of a pure equilibrium, where no player could unilaterally improve her cost by switching to another link.We show that even for a singlenegative weight, this decision problem is strongly NP-complete when the number of links is part of the input; the problem is NP-complete already for two links. When the number of links is a fixed constant, we show, through a pseudopolynomial, dynamic programming algorithm, that the problem is not strongly NP-complete unless P = NP; the algorithm works for any number of negative weights."}],"file":[{"relation":"main_file","success":1,"content_type":"application/pdf","file_id":"1494","access_level":"closed","file_name":"244-Mavronic_Monien2015_01.pdf","file_size":239984,"date_created":"2018-03-21T09:48:16Z","creator":"florida","date_updated":"2018-03-21T09:48:16Z"}],"publication":"Information Processing Letters","title":"The complexity of pure equilibria in mix-weighted congestion games on parallel links","publisher":"Elsevier","date_created":"2017-10-17T12:41:39Z","year":"2015","issue":"12","file_date_updated":"2018-03-21T09:48:16Z","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A3","_id":"7"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"244","user_id":"42447","status":"public","type":"journal_article","main_file_link":[{"url":"http://www.sciencedirect.com/journal/information-processing-letters/vol/115/issue/12"}],"doi":"10.1016/j.ipl.2015.07.012","date_updated":"2022-01-06T06:56:20Z","author":[{"first_name":"Burkhard","last_name":"Monien","full_name":"Monien, Burkhard"},{"first_name":"Marios","last_name":"Mavronicolas","full_name":"Mavronicolas, Marios"}],"volume":115,"citation":{"ama":"Monien B, Mavronicolas M. The complexity of pure equilibria in mix-weighted congestion games on parallel links. <i>Information Processing Letters</i>. 2015;115(12):927-931. doi:<a href=\"https://doi.org/10.1016/j.ipl.2015.07.012\">10.1016/j.ipl.2015.07.012</a>","chicago":"Monien, Burkhard, and Marios Mavronicolas. “The Complexity of Pure Equilibria in Mix-Weighted Congestion Games on Parallel Links.” <i>Information Processing Letters</i> 115, no. 12 (2015): 927–31. <a href=\"https://doi.org/10.1016/j.ipl.2015.07.012\">https://doi.org/10.1016/j.ipl.2015.07.012</a>.","ieee":"B. Monien and M. Mavronicolas, “The complexity of pure equilibria in mix-weighted congestion games on parallel links,” <i>Information Processing Letters</i>, vol. 115, no. 12, pp. 927–931, 2015.","apa":"Monien, B., &#38; Mavronicolas, M. (2015). The complexity of pure equilibria in mix-weighted congestion games on parallel links. <i>Information Processing Letters</i>, <i>115</i>(12), 927–931. <a href=\"https://doi.org/10.1016/j.ipl.2015.07.012\">https://doi.org/10.1016/j.ipl.2015.07.012</a>","bibtex":"@article{Monien_Mavronicolas_2015, title={The complexity of pure equilibria in mix-weighted congestion games on parallel links}, volume={115}, DOI={<a href=\"https://doi.org/10.1016/j.ipl.2015.07.012\">10.1016/j.ipl.2015.07.012</a>}, number={12}, journal={Information Processing Letters}, publisher={Elsevier}, author={Monien, Burkhard and Mavronicolas, Marios}, year={2015}, pages={927–931} }","mla":"Monien, Burkhard, and Marios Mavronicolas. “The Complexity of Pure Equilibria in Mix-Weighted Congestion Games on Parallel Links.” <i>Information Processing Letters</i>, vol. 115, no. 12, Elsevier, 2015, pp. 927–31, doi:<a href=\"https://doi.org/10.1016/j.ipl.2015.07.012\">10.1016/j.ipl.2015.07.012</a>.","short":"B. Monien, M. Mavronicolas, Information Processing Letters 115 (2015) 927–931."},"intvolume":"       115","page":"927-931","has_accepted_license":"1"},{"intvolume":"         3","citation":{"bibtex":"@article{Caragiannis_Fanelli_Gravin_Skopalik_2015, title={Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure}, volume={3}, DOI={<a href=\"https://doi.org/10.1145/2614687\">10.1145/2614687</a>}, number={12}, journal={Transactions on Economics and Computation}, publisher={ACM}, author={Caragiannis, Ioannis and Fanelli, Angelo and Gravin, Nick and Skopalik, Alexander}, year={2015} }","short":"I. Caragiannis, A. Fanelli, N. Gravin, A. Skopalik, Transactions on Economics and Computation 3 (2015).","mla":"Caragiannis, Ioannis, et al. “Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure.” <i>Transactions on Economics and Computation</i>, vol. 3, no. 1, 2, ACM, 2015, doi:<a href=\"https://doi.org/10.1145/2614687\">10.1145/2614687</a>.","apa":"Caragiannis, I., Fanelli, A., Gravin, N., &#38; Skopalik, A. (2015). Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure. <i>Transactions on Economics and Computation</i>, <i>3</i>(1). <a href=\"https://doi.org/10.1145/2614687\">https://doi.org/10.1145/2614687</a>","ieee":"I. Caragiannis, A. Fanelli, N. Gravin, and A. Skopalik, “Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure,” <i>Transactions on Economics and Computation</i>, vol. 3, no. 1, 2015.","chicago":"Caragiannis, Ioannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik. “Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure.” <i>Transactions on Economics and Computation</i> 3, no. 1 (2015). <a href=\"https://doi.org/10.1145/2614687\">https://doi.org/10.1145/2614687</a>.","ama":"Caragiannis I, Fanelli A, Gravin N, Skopalik A. Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure. <i>Transactions on Economics and Computation</i>. 2015;3(1). doi:<a href=\"https://doi.org/10.1145/2614687\">10.1145/2614687</a>"},"has_accepted_license":"1","doi":"10.1145/2614687","date_updated":"2022-01-06T06:59:04Z","volume":3,"author":[{"first_name":"Ioannis","full_name":"Caragiannis, Ioannis","last_name":"Caragiannis"},{"first_name":"Angelo","full_name":"Fanelli, Angelo","last_name":"Fanelli"},{"full_name":"Gravin, Nick","last_name":"Gravin","first_name":"Nick"},{"last_name":"Skopalik","full_name":"Skopalik, Alexander","id":"40384","first_name":"Alexander"}],"status":"public","type":"journal_article","article_number":"2","file_date_updated":"2018-03-20T07:40:55Z","_id":"320","project":[{"_id":"1","name":"SFB 901"},{"_id":"7","name":"SFB 901 - Subprojekt A3"},{"name":"SFB 901 - Project Area A","_id":"2"}],"department":[{"_id":"63"},{"_id":"541"}],"user_id":"477","year":"2015","issue":"1","title":"Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure","publisher":"ACM","date_created":"2017-10-17T12:41:54Z","abstract":[{"lang":"eng","text":"We consider structural and algorithmic questions related to the Nash dynamics of weighted congestion games. In weighted congestion games with linear latency functions, the existence of pure Nash equilibria is guaranteed by a potential function argument. Unfortunately, this proof of existence is inefficient and computing pure Nash equilibria in such games is a PLS-hard problem even when all players have unit weights. The situation gets worse when superlinear (e.g., quadratic) latency functions come into play; in this case, the Nash dynamics of the game may contain cycles and pure Nash equilibria may not even exist. Given these obstacles, we consider approximate pure Nash equilibria as alternative solution concepts. A ρ--approximate pure Nash equilibrium is a state of a (weighted congestion) game from which no player has any incentive to deviate in order to improve her cost by a multiplicative factor higher than ρ. Do such equilibria exist for small values of ρ? And if so, can we compute them efficiently?We provide positive answers to both questions for weighted congestion games with polynomial latency functions by exploiting an “approximation” of such games by a new class of potential games that we call Ψ-games. This allows us to show that these games have d!-approximate pure Nash equilibria, where d is the maximum degree of the latency functions. Our main technical contribution is an efficient algorithm for computing O(1)-approximate pure Nash equilibria when d is a constant. For games with linear latency functions, the approximation guarantee is 3+√5/2 + Oγ for arbitrarily small γ > 0; for latency functions with maximum degree d≥ 2, it is d2d+o(d). The running time is polynomial in the number of bits in the representation of the game and 1/γ. As a byproduct of our techniques, we also show the following interesting structural statement for weighted congestion games with polynomial latency functions of maximum degree d ≥ 2: polynomially-long sequences of best-response moves from any initial state to a dO(d2)-approximate pure Nash equilibrium exist and can be efficiently identified in such games as long as d is a constant.To the best of our knowledge, these are the first positive algorithmic results for approximate pure Nash equilibria in weighted congestion games. Our techniques significantly extend our recent work on unweighted congestion games through the use of Ψ-games. The concept of approximating nonpotential games by potential ones is interesting in itself and might have further applications."}],"file":[{"success":1,"relation":"main_file","content_type":"application/pdf","file_size":260503,"file_name":"320-a2-caragiannis.pdf","access_level":"closed","file_id":"1433","date_updated":"2018-03-20T07:40:55Z","creator":"florida","date_created":"2018-03-20T07:40:55Z"}],"publication":"Transactions on Economics and Computation","ddc":["040"],"language":[{"iso":"eng"}]},{"language":[{"iso":"ger"}],"user_id":"477","department":[{"_id":"280"}],"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A3","_id":"7"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"292","status":"public","type":"mastersthesis","title":"Fusionen von gesetzlichen Krankenversicherungen zu den Effizienz- und Wechselwirkungen","date_created":"2017-10-17T12:41:49Z","supervisor":[{"first_name":"Burkhard","last_name":"Hehenkamp","full_name":"Hehenkamp, Burkhard","id":"37339"}],"author":[{"last_name":"Osburg","full_name":"Osburg, Christina","first_name":"Christina"}],"publisher":"Universität Paderborn","date_updated":"2022-01-06T06:58:47Z","citation":{"apa":"Osburg, C. (2015). <i>Fusionen von gesetzlichen Krankenversicherungen zu den Effizienz- und Wechselwirkungen</i>. Universität Paderborn.","bibtex":"@book{Osburg_2015, title={Fusionen von gesetzlichen Krankenversicherungen zu den Effizienz- und Wechselwirkungen}, publisher={Universität Paderborn}, author={Osburg, Christina}, year={2015} }","short":"C. Osburg, Fusionen von gesetzlichen Krankenversicherungen zu den Effizienz- und Wechselwirkungen, Universität Paderborn, 2015.","mla":"Osburg, Christina. <i>Fusionen von gesetzlichen Krankenversicherungen zu den Effizienz- und Wechselwirkungen</i>. Universität Paderborn, 2015.","ama":"Osburg C. <i>Fusionen von gesetzlichen Krankenversicherungen zu den Effizienz- und Wechselwirkungen</i>. Universität Paderborn; 2015.","chicago":"Osburg, Christina. <i>Fusionen von gesetzlichen Krankenversicherungen zu den Effizienz- und Wechselwirkungen</i>. Universität Paderborn, 2015.","ieee":"C. Osburg, <i>Fusionen von gesetzlichen Krankenversicherungen zu den Effizienz- und Wechselwirkungen</i>. Universität Paderborn, 2015."},"year":"2015"},{"_id":"294","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A3","_id":"7"},{"name":"SFB 901 - Project Area A","_id":"2"}],"department":[{"_id":"280"}],"user_id":"42447","language":[{"iso":"ger"}],"type":"bachelorsthesis","status":"public","publisher":"Universität Paderborn","date_updated":"2022-01-06T06:58:48Z","supervisor":[{"last_name":"Hehenkamp","full_name":"Hehenkamp, Burkhard","id":"37339","first_name":"Burkhard"}],"date_created":"2017-10-17T12:41:49Z","author":[{"first_name":"GinaJoanna","full_name":"Materna, GinaJoanna","last_name":"Materna"}],"title":"Fair Trade - Eine neue Perspektive in der internationalen Handelspolitik","year":"2015","citation":{"short":"G. Materna, Fair Trade - Eine neue Perspektive in der internationalen Handelspolitik, Universität Paderborn, 2015.","mla":"Materna, GinaJoanna. <i>Fair Trade - Eine neue Perspektive in der internationalen Handelspolitik</i>. Universität Paderborn, 2015.","bibtex":"@book{Materna_2015, title={Fair Trade - Eine neue Perspektive in der internationalen Handelspolitik}, publisher={Universität Paderborn}, author={Materna, GinaJoanna}, year={2015} }","apa":"Materna, G. (2015). <i>Fair Trade - Eine neue Perspektive in der internationalen Handelspolitik</i>. Universität Paderborn.","ama":"Materna G. <i>Fair Trade - Eine neue Perspektive in der internationalen Handelspolitik</i>. Universität Paderborn; 2015.","ieee":"G. Materna, <i>Fair Trade - Eine neue Perspektive in der internationalen Handelspolitik</i>. Universität Paderborn, 2015.","chicago":"Materna, GinaJoanna. <i>Fair Trade - Eine neue Perspektive in der internationalen Handelspolitik</i>. Universität Paderborn, 2015."}}]