---
_id: '451'
abstract:
- lang: eng
  text: We introduce the concept of budget games. Players choose a set of tasks and
    each task has a certain demand on every resource in the game. Each resource has
    a budget. If the budget is not enough to satisfy the sum of all demands, it has
    to be shared between the tasks. We study strategic budget games, where the budget
    is shared proportionally. We also consider a variant in which the order of the
    strategic decisions influences the distribution of the budgets. The complexity
    of the optimal solution as well as existence, complexity and quality of equilibria
    are analysed. Finally, we show that the time an ordered budget game needs to convergence
    towards an equilibrium may be exponential.
author:
- first_name: Maximilian
  full_name: Drees, Maximilian
  last_name: Drees
- first_name: Sören
  full_name: Riechers, Sören
  last_name: Riechers
- first_name: Alexander
  full_name: Skopalik, Alexander
  id: '40384'
  last_name: Skopalik
citation:
  ama: 'Drees M, Riechers S, Skopalik A. Budget-restricted utility games with ordered
    strategic decisions. In: Lavi R, ed. <i>Proceedings of the 7th International Symposium
    on Algorithmic Game Theory (SAGT)</i>. Lecture Notes in Computer Science. ; 2014:110-121.
    doi:<a href="https://doi.org/10.1007/978-3-662-44803-8_10">10.1007/978-3-662-44803-8_10</a>'
  apa: Drees, M., Riechers, S., &#38; Skopalik, A. (2014). Budget-restricted utility
    games with ordered strategic decisions. In R. Lavi (Ed.), <i>Proceedings of the
    7th International Symposium on Algorithmic Game Theory (SAGT)</i> (pp. 110–121).
    <a href="https://doi.org/10.1007/978-3-662-44803-8_10">https://doi.org/10.1007/978-3-662-44803-8_10</a>
  bibtex: '@inproceedings{Drees_Riechers_Skopalik_2014, series={Lecture Notes in Computer
    Science}, title={Budget-restricted utility games with ordered strategic decisions},
    DOI={<a href="https://doi.org/10.1007/978-3-662-44803-8_10">10.1007/978-3-662-44803-8_10</a>},
    booktitle={Proceedings of the 7th International Symposium on Algorithmic Game
    Theory (SAGT)}, author={Drees, Maximilian and Riechers, Sören and Skopalik, Alexander},
    editor={Lavi, RonEditor}, year={2014}, pages={110–121}, collection={Lecture Notes
    in Computer Science} }'
  chicago: Drees, Maximilian, Sören Riechers, and Alexander Skopalik. “Budget-Restricted
    Utility Games with Ordered Strategic Decisions.” In <i>Proceedings of the 7th
    International Symposium on Algorithmic Game Theory (SAGT)</i>, edited by Ron Lavi,
    110–21. Lecture Notes in Computer Science, 2014. <a href="https://doi.org/10.1007/978-3-662-44803-8_10">https://doi.org/10.1007/978-3-662-44803-8_10</a>.
  ieee: M. Drees, S. Riechers, and A. Skopalik, “Budget-restricted utility games with
    ordered strategic decisions,” in <i>Proceedings of the 7th International Symposium
    on Algorithmic Game Theory (SAGT)</i>, 2014, pp. 110–121.
  mla: Drees, Maximilian, et al. “Budget-Restricted Utility Games with Ordered Strategic
    Decisions.” <i>Proceedings of the 7th International Symposium on Algorithmic Game
    Theory (SAGT)</i>, edited by Ron Lavi, 2014, pp. 110–21, doi:<a href="https://doi.org/10.1007/978-3-662-44803-8_10">10.1007/978-3-662-44803-8_10</a>.
  short: 'M. Drees, S. Riechers, A. Skopalik, in: R. Lavi (Ed.), Proceedings of the
    7th International Symposium on Algorithmic Game Theory (SAGT), 2014, pp. 110–121.'
date_created: 2017-10-17T12:42:20Z
date_updated: 2022-01-06T07:01:07Z
ddc:
- '040'
department:
- _id: '63'
- _id: '541'
doi: 10.1007/978-3-662-44803-8_10
editor:
- first_name: Ron
  full_name: Lavi, Ron
  last_name: Lavi
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-16T11:25:10Z
  date_updated: 2018-03-16T11:25:10Z
  file_id: '1344'
  file_name: 451-DRS14.pdf
  file_size: 283266
  relation: main_file
  success: 1
file_date_updated: 2018-03-16T11:25:10Z
has_accepted_license: '1'
language:
- iso: eng
page: 110-121
project:
- _id: '1'
  name: SFB 901
- _id: '14'
  name: SFB 901 - Subproject C2
- _id: '16'
  name: SFB 901 - Subproject C4
- _id: '7'
  name: SFB 901 - Subproject A3
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '4'
  name: SFB 901 - Project Area C
publication: Proceedings of the 7th International Symposium on Algorithmic Game Theory
  (SAGT)
series_title: Lecture Notes in Computer Science
status: public
title: Budget-restricted utility games with ordered strategic decisions
type: conference
user_id: '477'
year: '2014'
...
---
_id: '452'
abstract:
- lang: eng
  text: Today's networks, like the Internet, do not consist of one but a mixture of
    several interconnected networks. Each has individual qualities and hence the performance
    of a network node results from the networks' interplay.We introduce a new game
    theoretic model capturing the interplay between a high-speed backbone network
    and a low-speed general purpose network. In our model, n nodes are connected by
    a static network and each node can decide individually to become a gateway node.
    A gateway node pays a fixed price for its connection to the high-speed network,
    but can utilize the high-speed network to gain communication distance 0 to all
    other gateways. Communication distances in the low-speed network are given by
    the hop distances. The effective communication distance between any two nodes
    then is given by the shortest path, which is possibly improved by using gateways
    as shortcuts.Every node v has the objective to minimize its communication costs,
    given by the sum (SUM-game) or maximum (MAX-game) of the effective communication
    distances from v to all other nodes plus a fixed price \alpha > 0, if it decides
    to be a gateway. For both games and different ranges of \alpha, we study the existence
    of equilibria, the price of anarchy, and convergence properties of best-response
    dynamics.
author:
- first_name: Sebastian
  full_name: Abshoff, Sebastian
  last_name: Abshoff
- first_name: Andreas
  full_name: Cord-Landwehr, Andreas
  last_name: Cord-Landwehr
- first_name: Daniel
  full_name: Jung, Daniel
  id: '37827'
  last_name: Jung
- first_name: Alexander
  full_name: Skopalik, Alexander
  id: '40384'
  last_name: Skopalik
citation:
  ama: 'Abshoff S, Cord-Landwehr A, Jung D, Skopalik A. Brief Announcement: A Model
    for Multilevel Network Games. In: Lavi R, ed. <i>Proceedings of the 7th International
    Symposium on Algorithmic Game Theory (SAGT)</i>. LNCS. ; 2014:294.'
  apa: 'Abshoff, S., Cord-Landwehr, A., Jung, D., &#38; Skopalik, A. (2014). Brief
    Announcement: A Model for Multilevel Network Games. In R. Lavi (Ed.), <i>Proceedings
    of the 7th International Symposium on Algorithmic Game Theory (SAGT)</i> (p. 294).'
  bibtex: '@inproceedings{Abshoff_Cord-Landwehr_Jung_Skopalik_2014, series={LNCS},
    title={Brief Announcement: A Model for Multilevel Network Games}, booktitle={Proceedings
    of the 7th International Symposium on Algorithmic Game Theory (SAGT)}, author={Abshoff,
    Sebastian and Cord-Landwehr, Andreas and Jung, Daniel and Skopalik, Alexander},
    editor={Lavi, RonEditor}, year={2014}, pages={294}, collection={LNCS} }'
  chicago: 'Abshoff, Sebastian, Andreas Cord-Landwehr, Daniel Jung, and Alexander
    Skopalik. “Brief Announcement: A Model for Multilevel Network Games.” In <i>Proceedings
    of the 7th International Symposium on Algorithmic Game Theory (SAGT)</i>, edited
    by Ron Lavi, 294. LNCS, 2014.'
  ieee: 'S. Abshoff, A. Cord-Landwehr, D. Jung, and A. Skopalik, “Brief Announcement:
    A Model for Multilevel Network Games,” in <i>Proceedings of the 7th International
    Symposium on Algorithmic Game Theory (SAGT)</i>, 2014, p. 294.'
  mla: 'Abshoff, Sebastian, et al. “Brief Announcement: A Model for Multilevel Network
    Games.” <i>Proceedings of the 7th International Symposium on Algorithmic Game
    Theory (SAGT)</i>, edited by Ron Lavi, 2014, p. 294.'
  short: 'S. Abshoff, A. Cord-Landwehr, D. Jung, A. Skopalik, in: R. Lavi (Ed.), Proceedings
    of the 7th International Symposium on Algorithmic Game Theory (SAGT), 2014, p.
    294.'
date_created: 2017-10-17T12:42:20Z
date_updated: 2022-01-06T07:01:08Z
ddc:
- '040'
department:
- _id: '63'
- _id: '541'
editor:
- first_name: Ron
  full_name: Lavi, Ron
  last_name: Lavi
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-16T11:24:40Z
  date_updated: 2018-03-16T11:24:40Z
  file_id: '1343'
  file_name: 452-title_multilevel-sagt.pdf
  file_size: 84783
  relation: main_file
  success: 1
file_date_updated: 2018-03-16T11:24:40Z
has_accepted_license: '1'
language:
- iso: eng
page: '294'
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subproject A1
- _id: '7'
  name: SFB 901 - Subproject A3
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 7th International Symposium on Algorithmic Game Theory
  (SAGT)
series_title: LNCS
status: public
title: 'Brief Announcement: A Model for Multilevel Network Games'
type: conference
user_id: '15415'
year: '2014'
...
---
_id: '453'
abstract:
- lang: eng
  text: In this paper we study the potential function in congestion games. We consider
    both games with non-decreasing cost functions as well as games with non-increasing
    utility functions. We show that the value of the potential function $\Phi(\sf
    s)$ of any outcome $\sf s$ of a congestion game approximates the optimum potential
    value $\Phi(\sf s^*)$ by a factor $\Psi_{\mathcal{F}}$ which only depends on the
    set of cost/utility functions $\mathcal{F}$, and an additive term which is bounded
    by the sum of the total possible improvements of the players in the outcome $\sf
    s$. The significance of this result is twofold. On the one hand it provides \emph{Price-of-Anarchy}-like
    results with respect to the potential function. On the other hand, we show that
    these approximations can be used to compute $(1+\varepsilon)\cdot\Psi_{\mathcal{F}}$-approximate
    pure Nash equilibria for congestion games with non-decreasing cost functions.
    For the special case of polynomial cost functions, this significantly improves
    the guarantees from Caragiannis et al. [FOCS 2011]. Moreover, our machinery provides
    the first guarantees for general latency functions.
author:
- first_name: Matthias
  full_name: Feldotto, Matthias
  id: '14052'
  last_name: Feldotto
  orcid: 0000-0003-1348-6516
- first_name: Martin
  full_name: Gairing, Martin
  last_name: Gairing
- first_name: Alexander
  full_name: Skopalik, Alexander
  id: '40384'
  last_name: Skopalik
citation:
  ama: 'Feldotto M, Gairing M, Skopalik A. Bounding the Potential Function in Congestion
    Games and Approximate Pure Nash Equilibria. In: <i>Proceedings of the 10th International
    Conference on Web and Internet Economics (WINE)</i>. LNCS. ; 2014:30-43. doi:<a
    href="https://doi.org/10.1007/978-3-319-13129-0_3">10.1007/978-3-319-13129-0_3</a>'
  apa: Feldotto, M., Gairing, M., &#38; Skopalik, A. (2014). Bounding the Potential
    Function in Congestion Games and Approximate Pure Nash Equilibria. In <i>Proceedings
    of the 10th International Conference on Web and Internet Economics (WINE)</i>
    (pp. 30–43). <a href="https://doi.org/10.1007/978-3-319-13129-0_3">https://doi.org/10.1007/978-3-319-13129-0_3</a>
  bibtex: '@inproceedings{Feldotto_Gairing_Skopalik_2014, series={LNCS}, title={Bounding
    the Potential Function in Congestion Games and Approximate Pure Nash Equilibria},
    DOI={<a href="https://doi.org/10.1007/978-3-319-13129-0_3">10.1007/978-3-319-13129-0_3</a>},
    booktitle={Proceedings of the 10th International Conference on Web and Internet
    Economics (WINE)}, author={Feldotto, Matthias and Gairing, Martin and Skopalik,
    Alexander}, year={2014}, pages={30–43}, collection={LNCS} }'
  chicago: Feldotto, Matthias, Martin Gairing, and Alexander Skopalik. “Bounding the
    Potential Function in Congestion Games and Approximate Pure Nash Equilibria.”
    In <i>Proceedings of the 10th International Conference on Web and Internet Economics
    (WINE)</i>, 30–43. LNCS, 2014. <a href="https://doi.org/10.1007/978-3-319-13129-0_3">https://doi.org/10.1007/978-3-319-13129-0_3</a>.
  ieee: M. Feldotto, M. Gairing, and A. Skopalik, “Bounding the Potential Function
    in Congestion Games and Approximate Pure Nash Equilibria,” in <i>Proceedings of
    the 10th International Conference on Web and Internet Economics (WINE)</i>, 2014,
    pp. 30–43.
  mla: Feldotto, Matthias, et al. “Bounding the Potential Function in Congestion Games
    and Approximate Pure Nash Equilibria.” <i>Proceedings of the 10th International
    Conference on Web and Internet Economics (WINE)</i>, 2014, pp. 30–43, doi:<a href="https://doi.org/10.1007/978-3-319-13129-0_3">10.1007/978-3-319-13129-0_3</a>.
  short: 'M. Feldotto, M. Gairing, A. Skopalik, in: Proceedings of the 10th International
    Conference on Web and Internet Economics (WINE), 2014, pp. 30–43.'
date_created: 2017-10-17T12:42:20Z
date_updated: 2022-01-06T07:01:09Z
ddc:
- '040'
department:
- _id: '63'
- _id: '541'
doi: 10.1007/978-3-319-13129-0_3
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-16T11:24:11Z
  date_updated: 2018-03-16T11:24:11Z
  file_id: '1342'
  file_name: 453-WINE14FGS.pdf
  file_size: 324307
  relation: main_file
  success: 1
file_date_updated: 2018-03-16T11:24:11Z
has_accepted_license: '1'
page: 30-43
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Teilprojekt A
- _id: '7'
  name: SFB 901 - Subprojekt A3
publication: Proceedings of the 10th International Conference on Web and Internet
  Economics (WINE)
series_title: LNCS
status: public
title: Bounding the Potential Function in Congestion Games and Approximate Pure Nash
  Equilibria
type: conference
user_id: '14052'
year: '2014'
...
---
_id: '455'
abstract:
- lang: eng
  text: We study the existence of approximate pure Nash equilibria in weighted congestion
    games and develop techniques to obtain approximate potential functions that prove
    the existence of alpha-approximate pure Nash equilibria and the convergence of
    alpha-improvement steps. Specifically, we show how to obtain upper bounds for
    approximation factor alpha for a given class of cost functions. For example for
    concave cost functions the factor is at most 3/2, for quadratic cost functions
    it is at most 4/3, and for polynomial cost functions of maximal degree d it is
    at at most d + 1. For games with two players we obtain tight bounds which are
    as small as for example 1.054 in the case of quadratic cost functions.
author:
- first_name: Christoph
  full_name: Hansknecht, Christoph
  last_name: Hansknecht
- first_name: Max
  full_name: Klimm, Max
  last_name: Klimm
- first_name: Alexander
  full_name: Skopalik, Alexander
  id: '40384'
  last_name: Skopalik
citation:
  ama: 'Hansknecht C, Klimm M, Skopalik A. Approximate pure Nash equilibria in weighted
    congestion games. In: <i>Proceedings of the 17th. International Workshop on Approximation
    Algorithms for Combinatorial Optimization Problems (APPROX)</i>. LIPIcs. ; 2014:242-257.
    doi:<a href="https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242">10.4230/LIPIcs.APPROX-RANDOM.2014.242</a>'
  apa: Hansknecht, C., Klimm, M., &#38; Skopalik, A. (2014). Approximate pure Nash
    equilibria in weighted congestion games. In <i>Proceedings of the 17th. International
    Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)</i>
    (pp. 242–257). <a href="https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242">https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242</a>
  bibtex: '@inproceedings{Hansknecht_Klimm_Skopalik_2014, series={LIPIcs}, title={Approximate
    pure Nash equilibria in weighted congestion games}, DOI={<a href="https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242">10.4230/LIPIcs.APPROX-RANDOM.2014.242</a>},
    booktitle={Proceedings of the 17th. International Workshop on Approximation Algorithms
    for Combinatorial Optimization Problems (APPROX)}, author={Hansknecht, Christoph
    and Klimm, Max and Skopalik, Alexander}, year={2014}, pages={242–257}, collection={LIPIcs}
    }'
  chicago: Hansknecht, Christoph, Max Klimm, and Alexander Skopalik. “Approximate
    Pure Nash Equilibria in Weighted Congestion Games.” In <i>Proceedings of the 17th.
    International Workshop on Approximation Algorithms for Combinatorial Optimization
    Problems (APPROX)</i>, 242–57. LIPIcs, 2014. <a href="https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242">https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242</a>.
  ieee: C. Hansknecht, M. Klimm, and A. Skopalik, “Approximate pure Nash equilibria
    in weighted congestion games,” in <i>Proceedings of the 17th. International Workshop
    on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)</i>,
    2014, pp. 242–257.
  mla: Hansknecht, Christoph, et al. “Approximate Pure Nash Equilibria in Weighted
    Congestion Games.” <i>Proceedings of the 17th. International Workshop on Approximation
    Algorithms for Combinatorial Optimization Problems (APPROX)</i>, 2014, pp. 242–57,
    doi:<a href="https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242">10.4230/LIPIcs.APPROX-RANDOM.2014.242</a>.
  short: 'C. Hansknecht, M. Klimm, A. Skopalik, in: Proceedings of the 17th. International
    Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX),
    2014, pp. 242–257.'
date_created: 2017-10-17T12:42:20Z
date_updated: 2022-01-06T07:01:09Z
ddc:
- '040'
department:
- _id: '541'
- _id: '63'
doi: 10.4230/LIPIcs.APPROX-RANDOM.2014.242
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-16T11:23:40Z
  date_updated: 2018-03-16T11:23:40Z
  file_id: '1341'
  file_name: 455-HKS14.pdf
  file_size: 512712
  relation: main_file
  success: 1
file_date_updated: 2018-03-16T11:23:40Z
has_accepted_license: '1'
language:
- iso: eng
page: 242 - 257
project:
- _id: '1'
  name: SFB 901
- _id: '7'
  name: SFB 901 - Subprojekt A3
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 17th. International Workshop on Approximation Algorithms
  for Combinatorial Optimization Problems (APPROX)
series_title: LIPIcs
status: public
title: Approximate pure Nash equilibria in weighted congestion games
type: conference
user_id: '477'
year: '2014'
...
---
_id: '456'
abstract:
- lang: eng
  text: We study the existence of approximate pure Nash equilibriain social context
    congestion games. For any given set of allowed costfunctions F, we provide a threshold
    value μ(F), and show that for theclass of social context congestion games with
    cost functions from F, α-Nash dynamics are guaranteed to converge to α-approximate
    pure Nashequilibrium if and only if α > μ(F).Interestingly, μ(F) is related and
    always upper bounded by Roughgarden’sanarchy value [19].
author:
- first_name: Martin
  full_name: Gairing, Martin
  last_name: Gairing
- first_name: Grammateia
  full_name: Kotsialou, Grammateia
  last_name: Kotsialou
- first_name: Alexander
  full_name: Skopalik, Alexander
  id: '40384'
  last_name: Skopalik
citation:
  ama: 'Gairing M, Kotsialou G, Skopalik A. Approximate pure Nash equilibria in Social
    Context Congestion Games. In: <i>Proceedings of the 10th International Conference
    on Web and Internet Economics (WINE)</i>. LNCS. ; 2014:480-485. doi:<a href="https://doi.org/10.1007/978-3-319-13129-0_43">10.1007/978-3-319-13129-0_43</a>'
  apa: Gairing, M., Kotsialou, G., &#38; Skopalik, A. (2014). Approximate pure Nash
    equilibria in Social Context Congestion Games. In <i>Proceedings of the 10th International
    Conference on Web and Internet Economics (WINE)</i> (pp. 480–485). <a href="https://doi.org/10.1007/978-3-319-13129-0_43">https://doi.org/10.1007/978-3-319-13129-0_43</a>
  bibtex: '@inproceedings{Gairing_Kotsialou_Skopalik_2014, series={LNCS}, title={Approximate
    pure Nash equilibria in Social Context Congestion Games}, DOI={<a href="https://doi.org/10.1007/978-3-319-13129-0_43">10.1007/978-3-319-13129-0_43</a>},
    booktitle={Proceedings of the 10th International Conference on Web and Internet
    Economics (WINE)}, author={Gairing, Martin and Kotsialou, Grammateia and Skopalik,
    Alexander}, year={2014}, pages={480–485}, collection={LNCS} }'
  chicago: Gairing, Martin, Grammateia Kotsialou, and Alexander Skopalik. “Approximate
    Pure Nash Equilibria in Social Context Congestion Games.” In <i>Proceedings of
    the 10th International Conference on Web and Internet Economics (WINE)</i>, 480–85.
    LNCS, 2014. <a href="https://doi.org/10.1007/978-3-319-13129-0_43">https://doi.org/10.1007/978-3-319-13129-0_43</a>.
  ieee: M. Gairing, G. Kotsialou, and A. Skopalik, “Approximate pure Nash equilibria
    in Social Context Congestion Games,” in <i>Proceedings of the 10th International
    Conference on Web and Internet Economics (WINE)</i>, 2014, pp. 480–485.
  mla: Gairing, Martin, et al. “Approximate Pure Nash Equilibria in Social Context
    Congestion Games.” <i>Proceedings of the 10th International Conference on Web
    and Internet Economics (WINE)</i>, 2014, pp. 480–85, doi:<a href="https://doi.org/10.1007/978-3-319-13129-0_43">10.1007/978-3-319-13129-0_43</a>.
  short: 'M. Gairing, G. Kotsialou, A. Skopalik, in: Proceedings of the 10th International
    Conference on Web and Internet Economics (WINE), 2014, pp. 480–485.'
date_created: 2017-10-17T12:42:21Z
date_updated: 2022-01-06T07:01:10Z
ddc:
- '040'
department:
- _id: '541'
- _id: '63'
doi: 10.1007/978-3-319-13129-0_43
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-16T11:22:57Z
  date_updated: 2018-03-16T11:22:57Z
  file_id: '1340'
  file_name: 456-WINE14final.pdf
  file_size: 377378
  relation: main_file
  success: 1
file_date_updated: 2018-03-16T11:22:57Z
has_accepted_license: '1'
language:
- iso: eng
page: 480 - 485
project:
- _id: '1'
  name: SFB 901
- _id: '7'
  name: SFB 901 - Subprojekt A3
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 10th International Conference on Web and Internet
  Economics (WINE)
series_title: LNCS
status: public
title: Approximate pure Nash equilibria in Social Context Congestion Games
type: conference
user_id: '477'
year: '2014'
...
---
_id: '462'
abstract:
- lang: eng
  text: We discuss a technique to analyze complex infinitely repeated games using
    techniques from the fields of game theory and simulations. Our research is motivated
    by the analysis of electronic markets with thousands of participants and possibly
    complex strategic behavior. We consider an example of a global market of composed
    IT services to demonstrate the use of our simulation technique. We present our
    current work in this area and we want to discuss further approaches for the future.
author:
- first_name: Matthias
  full_name: Feldotto, Matthias
  id: '14052'
  last_name: Feldotto
  orcid: 0000-0003-1348-6516
- first_name: Alexander
  full_name: Skopalik, Alexander
  id: '40384'
  last_name: Skopalik
citation:
  ama: 'Feldotto M, Skopalik A. A Simulation Framework for Analyzing Complex Infinitely
    Repeated Games. In: <i>Proceedings of the 4th International Conference on Simulation
    and Modeling Methodologies, Technologies and Applications (SIMULTECH 2014)</i>.
    ; 2014:625-630. doi:<a href="https://doi.org/10.5220/0005110406250630">10.5220/0005110406250630</a>'
  apa: Feldotto, M., &#38; Skopalik, A. (2014). A Simulation Framework for Analyzing
    Complex Infinitely Repeated Games. In <i>Proceedings of the 4th International
    Conference on Simulation and Modeling Methodologies, Technologies and Applications
    (SIMULTECH 2014)</i> (pp. 625–630). <a href="https://doi.org/10.5220/0005110406250630">https://doi.org/10.5220/0005110406250630</a>
  bibtex: '@inproceedings{Feldotto_Skopalik_2014, title={A Simulation Framework for
    Analyzing Complex Infinitely Repeated Games}, DOI={<a href="https://doi.org/10.5220/0005110406250630">10.5220/0005110406250630</a>},
    booktitle={Proceedings of the 4th International Conference on Simulation and Modeling
    Methodologies, Technologies and Applications (SIMULTECH 2014)}, author={Feldotto,
    Matthias and Skopalik, Alexander}, year={2014}, pages={625–630} }'
  chicago: Feldotto, Matthias, and Alexander Skopalik. “A Simulation Framework for
    Analyzing Complex Infinitely Repeated Games.” In <i>Proceedings of the 4th International
    Conference on Simulation and Modeling Methodologies, Technologies and Applications
    (SIMULTECH 2014)</i>, 625–30, 2014. <a href="https://doi.org/10.5220/0005110406250630">https://doi.org/10.5220/0005110406250630</a>.
  ieee: M. Feldotto and A. Skopalik, “A Simulation Framework for Analyzing Complex
    Infinitely Repeated Games,” in <i>Proceedings of the 4th International Conference
    on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH
    2014)</i>, 2014, pp. 625–630.
  mla: Feldotto, Matthias, and Alexander Skopalik. “A Simulation Framework for Analyzing
    Complex Infinitely Repeated Games.” <i>Proceedings of the 4th International Conference
    on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH
    2014)</i>, 2014, pp. 625–30, doi:<a href="https://doi.org/10.5220/0005110406250630">10.5220/0005110406250630</a>.
  short: 'M. Feldotto, A. Skopalik, in: Proceedings of the 4th International Conference
    on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH
    2014), 2014, pp. 625–630.'
date_created: 2017-10-17T12:42:22Z
date_updated: 2022-01-06T07:01:15Z
ddc:
- '040'
department:
- _id: '63'
- _id: '541'
doi: 10.5220/0005110406250630
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-16T11:21:24Z
  date_updated: 2018-03-16T11:21:24Z
  file_id: '1337'
  file_name: 462-FS2014SIMULTECH.pdf
  file_size: 993721
  relation: main_file
  success: 1
file_date_updated: 2018-03-16T11:21:24Z
has_accepted_license: '1'
page: 625-630
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Teilprojekt A
- _id: '7'
  name: SFB 901 - Subprojekt A3
publication: Proceedings of the 4th International Conference on Simulation and Modeling
  Methodologies, Technologies and Applications (SIMULTECH 2014)
status: public
title: A Simulation Framework for Analyzing Complex Infinitely Repeated Games
type: conference
user_id: '14052'
year: '2014'
...
---
_id: '395'
abstract:
- lang: eng
  text: We consider a multilevel network game, where nodes can improvetheir communication
    costs by connecting to a high-speed network.The n nodes are connected by a static
    network and each node can decideindividually to become a gateway to the high-speed
    network. The goalof a node v is to minimize its private costs, i.e., the sum (SUM-game)
    ormaximum (MAX-game) of communication distances from v to all othernodes plus
    a fixed price α > 0 if it decides to be a gateway. Between gatewaysthe communication
    distance is 0, and gateways also improve othernodes’ distances by behaving as
    shortcuts. For the SUM-game, we showthat for α ≤ n − 1, the price of anarchy is
    Θ (n/√α) and in this rangeequilibria always exist. In range α ∈ (n−1, n(n−1))
    the price of anarchyis Θ(√α), and for α ≥ n(n − 1) it is constant. For the MAX-game,
    weshow that the price of anarchy is either Θ (1 + n/√α), for α ≥ 1, orelse 1.
    Given a graph with girth of at least 4α, equilibria always exist.Concerning the
    dynamics, both games are not potential games. For theSUM-game, we even show that
    it is not weakly acyclic.
author:
- first_name: Sebastian
  full_name: Abshoff, Sebastian
  last_name: Abshoff
- first_name: Andreas
  full_name: Cord-Landwehr, Andreas
  last_name: Cord-Landwehr
- first_name: Daniel
  full_name: Jung, Daniel
  id: '37827'
  last_name: Jung
- first_name: Alexander
  full_name: Skopalik, Alexander
  id: '40384'
  last_name: Skopalik
citation:
  ama: 'Abshoff S, Cord-Landwehr A, Jung D, Skopalik A. Multilevel Network Games.
    In: <i>Proceedings of the 10th International Conference on Web and Internet Economics
    (WINE)</i>. LNCS. ; 2014:435-440. doi:<a href="https://doi.org/10.1007/978-3-319-13129-0_36">10.1007/978-3-319-13129-0_36</a>'
  apa: Abshoff, S., Cord-Landwehr, A., Jung, D., &#38; Skopalik, A. (2014). Multilevel
    Network Games. In <i>Proceedings of the 10th International Conference on Web and
    Internet Economics (WINE)</i> (pp. 435–440). <a href="https://doi.org/10.1007/978-3-319-13129-0_36">https://doi.org/10.1007/978-3-319-13129-0_36</a>
  bibtex: '@inproceedings{Abshoff_Cord-Landwehr_Jung_Skopalik_2014, series={LNCS},
    title={Multilevel Network Games}, DOI={<a href="https://doi.org/10.1007/978-3-319-13129-0_36">10.1007/978-3-319-13129-0_36</a>},
    booktitle={Proceedings of the 10th International Conference on Web and Internet
    Economics (WINE)}, author={Abshoff, Sebastian and Cord-Landwehr, Andreas and Jung,
    Daniel and Skopalik, Alexander}, year={2014}, pages={435–440}, collection={LNCS}
    }'
  chicago: Abshoff, Sebastian, Andreas Cord-Landwehr, Daniel Jung, and Alexander Skopalik.
    “Multilevel Network Games.” In <i>Proceedings of the 10th International Conference
    on Web and Internet Economics (WINE)</i>, 435–40. LNCS, 2014. <a href="https://doi.org/10.1007/978-3-319-13129-0_36">https://doi.org/10.1007/978-3-319-13129-0_36</a>.
  ieee: S. Abshoff, A. Cord-Landwehr, D. Jung, and A. Skopalik, “Multilevel Network
    Games,” in <i>Proceedings of the 10th International Conference on Web and Internet
    Economics (WINE)</i>, 2014, pp. 435–440.
  mla: Abshoff, Sebastian, et al. “Multilevel Network Games.” <i>Proceedings of the
    10th International Conference on Web and Internet Economics (WINE)</i>, 2014,
    pp. 435–40, doi:<a href="https://doi.org/10.1007/978-3-319-13129-0_36">10.1007/978-3-319-13129-0_36</a>.
  short: 'S. Abshoff, A. Cord-Landwehr, D. Jung, A. Skopalik, in: Proceedings of the
    10th International Conference on Web and Internet Economics (WINE), 2014, pp.
    435–440.'
date_created: 2017-10-17T12:42:09Z
date_updated: 2022-01-06T06:59:59Z
ddc:
- '040'
department:
- _id: '63'
- _id: '541'
doi: 10.1007/978-3-319-13129-0_36
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-20T06:59:20Z
  date_updated: 2018-03-20T06:59:20Z
  file_id: '1382'
  file_name: 395-WINE2014ACJS.pdf
  file_size: 161479
  relation: main_file
  success: 1
file_date_updated: 2018-03-20T06:59:20Z
has_accepted_license: '1'
language:
- iso: eng
page: 435-440
project:
- _id: '1'
  name: SFB 901
- _id: '7'
  name: SFB 901 - Subprojekt A3
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 10th International Conference on Web and Internet
  Economics (WINE)
series_title: LNCS
status: public
title: Multilevel Network Games
type: conference
user_id: '15415'
year: '2014'
...
---
_id: '412'
abstract:
- lang: eng
  text: In this paper we present and analyze HSkip+, a self-stabilizing overlay network
    for nodes with arbitrary heterogeneous bandwidths. HSkip+ has the same topology
    as the Skip+ graph proposed by Jacob et al. [PODC 2009] but its self-stabilization
    mechanism significantly outperforms the self-stabilization mechanism proposed
    for Skip+. Also, the nodes are now ordered according to their bandwidths and not
    according to their identifiers. Various other solutions have already been proposed
    for overlay networks with heterogeneous bandwidths, but they are not self-stabilizing.
    In addition to HSkip+ being self-stabilizing, its performance is on par with the
    best previous bounds on the time and work for joining or leaving a network of
    peers of logarithmic diameter and degree and arbitrary bandwidths. Also, the dilation
    and congestion for routing messages is on par with the best previous bounds for
    such networks, so that HSkip+ combines the advantages of both worlds. Our theoretical
    investigations are backed by simulations demonstrating that HSkip+ is indeed performing
    much better than Skip+ and working correctly under high churn rates.
author:
- first_name: Matthias
  full_name: Feldotto, Matthias
  id: '14052'
  last_name: Feldotto
  orcid: 0000-0003-1348-6516
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Kalman
  full_name: Graffi, Kalman
  last_name: Graffi
citation:
  ama: 'Feldotto M, Scheideler C, Graffi K. HSkip+: A Self-Stabilizing Overlay Network
    for Nodes with Heterogeneous Bandwidths. In: <i>Proceedings of the 14th IEEE International
    Conference on Peer-to-Peer Computing (P2P)</i>. ; 2014:1-10. doi:<a href="https://doi.org/10.1109/P2P.2014.6934300">10.1109/P2P.2014.6934300</a>'
  apa: 'Feldotto, M., Scheideler, C., &#38; Graffi, K. (2014). HSkip+: A Self-Stabilizing
    Overlay Network for Nodes with Heterogeneous Bandwidths. In <i>Proceedings of
    the 14th IEEE International Conference on Peer-to-Peer Computing (P2P)</i> (pp.
    1–10). <a href="https://doi.org/10.1109/P2P.2014.6934300">https://doi.org/10.1109/P2P.2014.6934300</a>'
  bibtex: '@inproceedings{Feldotto_Scheideler_Graffi_2014, title={HSkip+: A Self-Stabilizing
    Overlay Network for Nodes with Heterogeneous Bandwidths}, DOI={<a href="https://doi.org/10.1109/P2P.2014.6934300">10.1109/P2P.2014.6934300</a>},
    booktitle={Proceedings of the 14th IEEE International Conference on Peer-to-Peer
    Computing (P2P)}, author={Feldotto, Matthias and Scheideler, Christian and Graffi,
    Kalman}, year={2014}, pages={1–10} }'
  chicago: 'Feldotto, Matthias, Christian Scheideler, and Kalman Graffi. “HSkip+:
    A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths.” In
    <i>Proceedings of the 14th IEEE International Conference on Peer-to-Peer Computing
    (P2P)</i>, 1–10, 2014. <a href="https://doi.org/10.1109/P2P.2014.6934300">https://doi.org/10.1109/P2P.2014.6934300</a>.'
  ieee: 'M. Feldotto, C. Scheideler, and K. Graffi, “HSkip+: A Self-Stabilizing Overlay
    Network for Nodes with Heterogeneous Bandwidths,” in <i>Proceedings of the 14th
    IEEE International Conference on Peer-to-Peer Computing (P2P)</i>, 2014, pp. 1–10.'
  mla: 'Feldotto, Matthias, et al. “HSkip+: A Self-Stabilizing Overlay Network for
    Nodes with Heterogeneous Bandwidths.” <i>Proceedings of the 14th IEEE International
    Conference on Peer-to-Peer Computing (P2P)</i>, 2014, pp. 1–10, doi:<a href="https://doi.org/10.1109/P2P.2014.6934300">10.1109/P2P.2014.6934300</a>.'
  short: 'M. Feldotto, C. Scheideler, K. Graffi, in: Proceedings of the 14th IEEE
    International Conference on Peer-to-Peer Computing (P2P), 2014, pp. 1–10.'
date_created: 2017-10-17T12:42:12Z
date_updated: 2022-01-06T07:00:20Z
ddc:
- '040'
department:
- _id: '79'
- _id: '63'
- _id: '541'
doi: 10.1109/P2P.2014.6934300
external_id:
  arxiv:
  - '1408.0395'
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-16T11:34:00Z
  date_updated: 2018-03-16T11:34:00Z
  file_id: '1361'
  file_name: 412-FSG2014P2P.pdf
  file_size: 472321
  relation: main_file
  success: 1
file_date_updated: 2018-03-16T11:34:00Z
has_accepted_license: '1'
page: 1-10
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
publication: Proceedings of the 14th IEEE International Conference on Peer-to-Peer
  Computing (P2P)
status: public
title: 'HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths'
type: conference
user_id: '14052'
year: '2014'
...
---
_id: '17663'
abstract:
- lang: eng
  text: 'In this paper, we define and study a new problem, referred to as the Dependent
    Unsplittable Flow Problem (D-UFP). We present and discuss this problem in the
    context of large-scale powerful (radar/camera) sensor networks, but we believe
    it has important applications on the admission of large flows in other networks
    as well. In order to optimize the selection of flows transmitted to the gateway,
    D-UFP takes into account possible dependencies between flows. We show that D-UFP
    is more difficult than NP-hard problems for which no good approximation is known.
    Then, we address two special cases of this problem: the case where all the sensors
    have a shared channel and the case where the sensors form a mesh and route to
    the gateway over a spanning tree.'
author:
- first_name: R.
  full_name: Cohen, R.
  last_name: Cohen
- first_name: I.
  full_name: Nudelman, I.
  last_name: Nudelman
- first_name: Gleb
  full_name: Polevoy, Gleb
  id: '83983'
  last_name: Polevoy
citation:
  ama: Cohen R, Nudelman I, Polevoy G. On the Admission of Dependent Flows in Powerful
    Sensor Networks. <i>Networking, IEEE/ACM Transactions on</i>. 2013;21(5):1461-1471.
    doi:<a href="https://doi.org/10.1109/TNET.2012.2227792">10.1109/TNET.2012.2227792</a>
  apa: Cohen, R., Nudelman, I., &#38; Polevoy, G. (2013). On the Admission of Dependent
    Flows in Powerful Sensor Networks. <i>Networking, IEEE/ACM Transactions On</i>,
    <i>21</i>(5), 1461–1471. <a href="https://doi.org/10.1109/TNET.2012.2227792">https://doi.org/10.1109/TNET.2012.2227792</a>
  bibtex: '@article{Cohen_Nudelman_Polevoy_2013, title={On the Admission of Dependent
    Flows in Powerful Sensor Networks}, volume={21}, DOI={<a href="https://doi.org/10.1109/TNET.2012.2227792">10.1109/TNET.2012.2227792</a>},
    number={5}, journal={Networking, IEEE/ACM Transactions on}, author={Cohen, R.
    and Nudelman, I. and Polevoy, Gleb}, year={2013}, pages={1461–1471} }'
  chicago: 'Cohen, R., I. Nudelman, and Gleb Polevoy. “On the Admission of Dependent
    Flows in Powerful Sensor Networks.” <i>Networking, IEEE/ACM Transactions On</i>
    21, no. 5 (2013): 1461–71. <a href="https://doi.org/10.1109/TNET.2012.2227792">https://doi.org/10.1109/TNET.2012.2227792</a>.'
  ieee: R. Cohen, I. Nudelman, and G. Polevoy, “On the Admission of Dependent Flows
    in Powerful Sensor Networks,” <i>Networking, IEEE/ACM Transactions on</i>, vol.
    21, no. 5, pp. 1461–1471, 2013.
  mla: Cohen, R., et al. “On the Admission of Dependent Flows in Powerful Sensor Networks.”
    <i>Networking, IEEE/ACM Transactions On</i>, vol. 21, no. 5, 2013, pp. 1461–71,
    doi:<a href="https://doi.org/10.1109/TNET.2012.2227792">10.1109/TNET.2012.2227792</a>.
  short: R. Cohen, I. Nudelman, G. Polevoy, Networking, IEEE/ACM Transactions On 21
    (2013) 1461–1471.
date_created: 2020-08-06T15:22:05Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
doi: 10.1109/TNET.2012.2227792
extern: '1'
intvolume: '        21'
issue: '5'
keyword:
- Approximation algorithms
- Approximation methods
- Bandwidth
- Logic gates
- Radar
- Vectors
- Wireless sensor networks
- Dependent flow scheduling
- sensor networks
language:
- iso: eng
page: 1461-1471
publication: Networking, IEEE/ACM Transactions on
publication_identifier:
  issn:
  - 1063-6692
status: public
title: On the Admission of Dependent Flows in Powerful Sensor Networks
type: journal_article
user_id: '83983'
volume: 21
year: '2013'
...
---
_id: '17664'
author:
- first_name: Reuven
  full_name: Cohen, Reuven
  last_name: Cohen
- first_name: Ilia
  full_name: Nudelman, Ilia
  last_name: Nudelman
- first_name: Gleb
  full_name: Polevoy, Gleb
  id: '83983'
  last_name: Polevoy
citation:
  ama: 'Cohen R, Nudelman I, Polevoy G. On the Admission of Dependent Flows in Powerful
    Sensor Networks. In: <i>Infocom’2012, Orlando, Florida</i>. ; 2012.'
  apa: Cohen, R., Nudelman, I., &#38; Polevoy, G. (2012). On the Admission of Dependent
    Flows in Powerful Sensor Networks. In <i>Infocom’2012, Orlando, Florida</i>.
  bibtex: '@inproceedings{Cohen_Nudelman_Polevoy_2012, title={On the Admission of
    Dependent Flows in Powerful Sensor Networks}, booktitle={Infocom’2012, Orlando,
    Florida}, author={Cohen, Reuven and Nudelman, Ilia and Polevoy, Gleb}, year={2012}
    }'
  chicago: Cohen, Reuven, Ilia Nudelman, and Gleb Polevoy. “On the Admission of Dependent
    Flows in Powerful Sensor Networks.” In <i>Infocom’2012, Orlando, Florida</i>,
    2012.
  ieee: R. Cohen, I. Nudelman, and G. Polevoy, “On the Admission of Dependent Flows
    in Powerful Sensor Networks,” in <i>Infocom’2012, Orlando, Florida</i>, 2012.
  mla: Cohen, Reuven, et al. “On the Admission of Dependent Flows in Powerful Sensor
    Networks.” <i>Infocom’2012, Orlando, Florida</i>, 2012.
  short: 'R. Cohen, I. Nudelman, G. Polevoy, in: Infocom’2012, Orlando, Florida, 2012.'
date_created: 2020-08-06T15:22:24Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
extern: '1'
language:
- iso: eng
publication: Infocom'2012, Orlando, Florida
status: public
title: On the Admission of Dependent Flows in Powerful Sensor Networks
type: conference
user_id: '83983'
year: '2012'
...
---
_id: '17665'
author:
- first_name: Reuven
  full_name: Bar-Yehuda, Reuven
  last_name: Bar-Yehuda
- first_name: Gleb
  full_name: Polevoy, Gleb
  id: '83983'
  last_name: Polevoy
- first_name: Dror
  full_name: Rawitz, Dror
  last_name: Rawitz
citation:
  ama: 'Bar-Yehuda R, Polevoy G, Rawitz D. Bandwidth allocation in cellular networks
    with multiple interferences. In: <i>DIALM-PODC</i>. ; 2010:33-42.'
  apa: Bar-Yehuda, R., Polevoy, G., &#38; Rawitz, D. (2010). Bandwidth allocation
    in cellular networks with multiple interferences. In <i>DIALM-PODC</i> (pp. 33–42).
  bibtex: '@inproceedings{Bar-Yehuda_Polevoy_Rawitz_2010, title={Bandwidth allocation
    in cellular networks with multiple interferences}, booktitle={DIALM-PODC}, author={Bar-Yehuda,
    Reuven and Polevoy, Gleb and Rawitz, Dror}, year={2010}, pages={33–42} }'
  chicago: Bar-Yehuda, Reuven, Gleb Polevoy, and Dror Rawitz. “Bandwidth Allocation
    in Cellular Networks with Multiple Interferences.” In <i>DIALM-PODC</i>, 33–42,
    2010.
  ieee: R. Bar-Yehuda, G. Polevoy, and D. Rawitz, “Bandwidth allocation in cellular
    networks with multiple interferences,” in <i>DIALM-PODC</i>, 2010, pp. 33–42.
  mla: Bar-Yehuda, Reuven, et al. “Bandwidth Allocation in Cellular Networks with
    Multiple Interferences.” <i>DIALM-PODC</i>, 2010, pp. 33–42.
  short: 'R. Bar-Yehuda, G. Polevoy, D. Rawitz, in: DIALM-PODC, 2010, pp. 33–42.'
date_created: 2020-08-06T15:22:47Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
extern: '1'
language:
- iso: eng
page: 33-42
publication: DIALM-PODC
status: public
title: Bandwidth allocation in cellular networks with multiple interferences
type: conference
user_id: '83983'
year: '2010'
...