---
_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. Proceedings of the 7th International Symposium
on Algorithmic Game Theory (SAGT). Lecture Notes in Computer Science. ; 2014:110-121.
doi:10.1007/978-3-662-44803-8_10'
apa: Drees, M., Riechers, S., & Skopalik, A. (2014). Budget-restricted utility
games with ordered strategic decisions. In R. Lavi (Ed.), Proceedings of the
7th International Symposium on Algorithmic Game Theory (SAGT) (pp. 110–121).
https://doi.org/10.1007/978-3-662-44803-8_10
bibtex: '@inproceedings{Drees_Riechers_Skopalik_2014, series={Lecture Notes in Computer
Science}, title={Budget-restricted utility games with ordered strategic decisions},
DOI={10.1007/978-3-662-44803-8_10},
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 Proceedings of the 7th
International Symposium on Algorithmic Game Theory (SAGT), edited by Ron Lavi,
110–21. Lecture Notes in Computer Science, 2014. https://doi.org/10.1007/978-3-662-44803-8_10.
ieee: M. Drees, S. Riechers, and A. Skopalik, “Budget-restricted utility games with
ordered strategic decisions,” in Proceedings of the 7th International Symposium
on Algorithmic Game Theory (SAGT), 2014, pp. 110–121.
mla: Drees, Maximilian, et al. “Budget-Restricted Utility Games with Ordered Strategic
Decisions.” Proceedings of the 7th International Symposium on Algorithmic Game
Theory (SAGT), edited by Ron Lavi, 2014, pp. 110–21, doi:10.1007/978-3-662-44803-8_10.
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. Proceedings of the 7th International
Symposium on Algorithmic Game Theory (SAGT). LNCS. ; 2014:294.'
apa: 'Abshoff, S., Cord-Landwehr, A., Jung, D., & Skopalik, A. (2014). Brief
Announcement: A Model for Multilevel Network Games. In R. Lavi (Ed.), Proceedings
of the 7th International Symposium on Algorithmic Game Theory (SAGT) (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 Proceedings
of the 7th International Symposium on Algorithmic Game Theory (SAGT), 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 Proceedings of the 7th International
Symposium on Algorithmic Game Theory (SAGT), 2014, p. 294.'
mla: 'Abshoff, Sebastian, et al. “Brief Announcement: A Model for Multilevel Network
Games.” Proceedings of the 7th International Symposium on Algorithmic Game
Theory (SAGT), 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: Proceedings of the 10th International
Conference on Web and Internet Economics (WINE). LNCS. ; 2014:30-43. doi:10.1007/978-3-319-13129-0_3'
apa: Feldotto, M., Gairing, M., & Skopalik, A. (2014). Bounding the Potential
Function in Congestion Games and Approximate Pure Nash Equilibria. In Proceedings
of the 10th International Conference on Web and Internet Economics (WINE)
(pp. 30–43). https://doi.org/10.1007/978-3-319-13129-0_3
bibtex: '@inproceedings{Feldotto_Gairing_Skopalik_2014, series={LNCS}, title={Bounding
the Potential Function in Congestion Games and Approximate Pure Nash Equilibria},
DOI={10.1007/978-3-319-13129-0_3},
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 Proceedings of the 10th International Conference on Web and Internet Economics
(WINE), 30–43. LNCS, 2014. https://doi.org/10.1007/978-3-319-13129-0_3.
ieee: M. Feldotto, M. Gairing, and A. Skopalik, “Bounding the Potential Function
in Congestion Games and Approximate Pure Nash Equilibria,” in Proceedings of
the 10th International Conference on Web and Internet Economics (WINE), 2014,
pp. 30–43.
mla: Feldotto, Matthias, et al. “Bounding the Potential Function in Congestion Games
and Approximate Pure Nash Equilibria.” Proceedings of the 10th International
Conference on Web and Internet Economics (WINE), 2014, pp. 30–43, doi:10.1007/978-3-319-13129-0_3.
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: Proceedings of the 17th. International Workshop on Approximation
Algorithms for Combinatorial Optimization Problems (APPROX). LIPIcs. ; 2014:242-257.
doi:10.4230/LIPIcs.APPROX-RANDOM.2014.242'
apa: Hansknecht, C., Klimm, M., & Skopalik, A. (2014). Approximate pure Nash
equilibria in weighted congestion games. In Proceedings of the 17th. International
Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)
(pp. 242–257). https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242
bibtex: '@inproceedings{Hansknecht_Klimm_Skopalik_2014, series={LIPIcs}, title={Approximate
pure Nash equilibria in weighted congestion games}, DOI={10.4230/LIPIcs.APPROX-RANDOM.2014.242},
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 Proceedings of the 17th.
International Workshop on Approximation Algorithms for Combinatorial Optimization
Problems (APPROX), 242–57. LIPIcs, 2014. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242.
ieee: C. Hansknecht, M. Klimm, and A. Skopalik, “Approximate pure Nash equilibria
in weighted congestion games,” in Proceedings of the 17th. International Workshop
on Approximation Algorithms for Combinatorial Optimization Problems (APPROX),
2014, pp. 242–257.
mla: Hansknecht, Christoph, et al. “Approximate Pure Nash Equilibria in Weighted
Congestion Games.” Proceedings of the 17th. International Workshop on Approximation
Algorithms for Combinatorial Optimization Problems (APPROX), 2014, pp. 242–57,
doi:10.4230/LIPIcs.APPROX-RANDOM.2014.242.
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: Proceedings of the 10th International Conference
on Web and Internet Economics (WINE). LNCS. ; 2014:480-485. doi:10.1007/978-3-319-13129-0_43'
apa: Gairing, M., Kotsialou, G., & Skopalik, A. (2014). Approximate pure Nash
equilibria in Social Context Congestion Games. In Proceedings of the 10th International
Conference on Web and Internet Economics (WINE) (pp. 480–485). https://doi.org/10.1007/978-3-319-13129-0_43
bibtex: '@inproceedings{Gairing_Kotsialou_Skopalik_2014, series={LNCS}, title={Approximate
pure Nash equilibria in Social Context Congestion Games}, DOI={10.1007/978-3-319-13129-0_43},
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 Proceedings of
the 10th International Conference on Web and Internet Economics (WINE), 480–85.
LNCS, 2014. https://doi.org/10.1007/978-3-319-13129-0_43.
ieee: M. Gairing, G. Kotsialou, and A. Skopalik, “Approximate pure Nash equilibria
in Social Context Congestion Games,” in Proceedings of the 10th International
Conference on Web and Internet Economics (WINE), 2014, pp. 480–485.
mla: Gairing, Martin, et al. “Approximate Pure Nash Equilibria in Social Context
Congestion Games.” Proceedings of the 10th International Conference on Web
and Internet Economics (WINE), 2014, pp. 480–85, doi:10.1007/978-3-319-13129-0_43.
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: Proceedings of the 4th International Conference on Simulation
and Modeling Methodologies, Technologies and Applications (SIMULTECH 2014).
; 2014:625-630. doi:10.5220/0005110406250630'
apa: Feldotto, M., & Skopalik, A. (2014). A Simulation Framework for Analyzing
Complex Infinitely Repeated Games. In Proceedings of the 4th International
Conference on Simulation and Modeling Methodologies, Technologies and Applications
(SIMULTECH 2014) (pp. 625–630). https://doi.org/10.5220/0005110406250630
bibtex: '@inproceedings{Feldotto_Skopalik_2014, title={A Simulation Framework for
Analyzing Complex Infinitely Repeated Games}, DOI={10.5220/0005110406250630},
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 Proceedings of the 4th International
Conference on Simulation and Modeling Methodologies, Technologies and Applications
(SIMULTECH 2014), 625–30, 2014. https://doi.org/10.5220/0005110406250630.
ieee: M. Feldotto and A. Skopalik, “A Simulation Framework for Analyzing Complex
Infinitely Repeated Games,” in Proceedings of the 4th International Conference
on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH
2014), 2014, pp. 625–630.
mla: Feldotto, Matthias, and Alexander Skopalik. “A Simulation Framework for Analyzing
Complex Infinitely Repeated Games.” Proceedings of the 4th International Conference
on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH
2014), 2014, pp. 625–30, doi:10.5220/0005110406250630.
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: Proceedings of the 10th International Conference on Web and Internet Economics
(WINE). LNCS. ; 2014:435-440. doi:10.1007/978-3-319-13129-0_36'
apa: Abshoff, S., Cord-Landwehr, A., Jung, D., & Skopalik, A. (2014). Multilevel
Network Games. In Proceedings of the 10th International Conference on Web and
Internet Economics (WINE) (pp. 435–440). https://doi.org/10.1007/978-3-319-13129-0_36
bibtex: '@inproceedings{Abshoff_Cord-Landwehr_Jung_Skopalik_2014, series={LNCS},
title={Multilevel Network Games}, DOI={10.1007/978-3-319-13129-0_36},
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 Proceedings of the 10th International Conference
on Web and Internet Economics (WINE), 435–40. LNCS, 2014. https://doi.org/10.1007/978-3-319-13129-0_36.
ieee: S. Abshoff, A. Cord-Landwehr, D. Jung, and A. Skopalik, “Multilevel Network
Games,” in Proceedings of the 10th International Conference on Web and Internet
Economics (WINE), 2014, pp. 435–440.
mla: Abshoff, Sebastian, et al. “Multilevel Network Games.” Proceedings of the
10th International Conference on Web and Internet Economics (WINE), 2014,
pp. 435–40, doi:10.1007/978-3-319-13129-0_36.
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: Proceedings of the 14th IEEE International
Conference on Peer-to-Peer Computing (P2P). ; 2014:1-10. doi:10.1109/P2P.2014.6934300'
apa: 'Feldotto, M., Scheideler, C., & Graffi, K. (2014). HSkip+: A Self-Stabilizing
Overlay Network for Nodes with Heterogeneous Bandwidths. In Proceedings of
the 14th IEEE International Conference on Peer-to-Peer Computing (P2P) (pp.
1–10). https://doi.org/10.1109/P2P.2014.6934300'
bibtex: '@inproceedings{Feldotto_Scheideler_Graffi_2014, title={HSkip+: A Self-Stabilizing
Overlay Network for Nodes with Heterogeneous Bandwidths}, DOI={10.1109/P2P.2014.6934300},
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
Proceedings of the 14th IEEE International Conference on Peer-to-Peer Computing
(P2P), 1–10, 2014. https://doi.org/10.1109/P2P.2014.6934300.'
ieee: 'M. Feldotto, C. Scheideler, and K. Graffi, “HSkip+: A Self-Stabilizing Overlay
Network for Nodes with Heterogeneous Bandwidths,” in Proceedings of the 14th
IEEE International Conference on Peer-to-Peer Computing (P2P), 2014, pp. 1–10.'
mla: 'Feldotto, Matthias, et al. “HSkip+: A Self-Stabilizing Overlay Network for
Nodes with Heterogeneous Bandwidths.” Proceedings of the 14th IEEE International
Conference on Peer-to-Peer Computing (P2P), 2014, pp. 1–10, doi:10.1109/P2P.2014.6934300.'
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. Networking, IEEE/ACM Transactions on. 2013;21(5):1461-1471.
doi:10.1109/TNET.2012.2227792
apa: Cohen, R., Nudelman, I., & Polevoy, G. (2013). On the Admission of Dependent
Flows in Powerful Sensor Networks. Networking, IEEE/ACM Transactions On,
21(5), 1461–1471. https://doi.org/10.1109/TNET.2012.2227792
bibtex: '@article{Cohen_Nudelman_Polevoy_2013, title={On the Admission of Dependent
Flows in Powerful Sensor Networks}, volume={21}, DOI={10.1109/TNET.2012.2227792},
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.” Networking, IEEE/ACM Transactions On
21, no. 5 (2013): 1461–71. https://doi.org/10.1109/TNET.2012.2227792.'
ieee: R. Cohen, I. Nudelman, and G. Polevoy, “On the Admission of Dependent Flows
in Powerful Sensor Networks,” Networking, IEEE/ACM Transactions on, vol.
21, no. 5, pp. 1461–1471, 2013.
mla: Cohen, R., et al. “On the Admission of Dependent Flows in Powerful Sensor Networks.”
Networking, IEEE/ACM Transactions On, vol. 21, no. 5, 2013, pp. 1461–71,
doi:10.1109/TNET.2012.2227792.
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: Infocom’2012, Orlando, Florida. ; 2012.'
apa: Cohen, R., Nudelman, I., & Polevoy, G. (2012). On the Admission of Dependent
Flows in Powerful Sensor Networks. In Infocom’2012, Orlando, Florida.
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 Infocom’2012, Orlando, Florida,
2012.
ieee: R. Cohen, I. Nudelman, and G. Polevoy, “On the Admission of Dependent Flows
in Powerful Sensor Networks,” in Infocom’2012, Orlando, Florida, 2012.
mla: Cohen, Reuven, et al. “On the Admission of Dependent Flows in Powerful Sensor
Networks.” Infocom’2012, Orlando, Florida, 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: DIALM-PODC. ; 2010:33-42.'
apa: Bar-Yehuda, R., Polevoy, G., & Rawitz, D. (2010). Bandwidth allocation
in cellular networks with multiple interferences. In DIALM-PODC (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 DIALM-PODC, 33–42,
2010.
ieee: R. Bar-Yehuda, G. Polevoy, and D. Rawitz, “Bandwidth allocation in cellular
networks with multiple interferences,” in DIALM-PODC, 2010, pp. 33–42.
mla: Bar-Yehuda, Reuven, et al. “Bandwidth Allocation in Cellular Networks with
Multiple Interferences.” DIALM-PODC, 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'
...