---
_id: '34040'
abstract:
- lang: eng
text: "Consider the practical goal of making a desired action profile played,\r\n\r\nwhen
the planner can only change the payoffs, bound by \r\n\r\nstringent constraints.\r\n\r\nApplications
include motivating people\r\n\r\nto choose the closest school, the closest subway
station, or to coordinate\r\n\r\non a communication protocol or an investment
strategy.\r\n\r\nEmploying subsidies and tolls, we adjust the game so that choosing
this predefined action profile\r\n\r\nbecomes strictly dominant. \r\n\r\nInspired
mainly by the work of Monderer and Tennenholtz,\r\n\r\nwhere the promised subsidies
do not materialise in the not played\r\n\r\nprofiles, we provide a fair and individually
rational game\r\n\r\nadjustment, such that the total outside investments sum up\r\n\r\nto
zero at any profile, thereby facilitating easy and frequent\r\n\r\nusage of our
adjustment without bearing costs, even if some\r\n\r\nplayers behave unexpectedly.
The resultant action profile itself needs no\r\n\r\nadjustment. Importantly, we
also prove that our adjustment minimises \r\n\r\nthe general transfer among all
such adjustments, counting the total subsidising and taxation."
author:
- first_name: Gleb
full_name: Polevoy, Gleb
id: '83983'
last_name: Polevoy
- first_name: Marcin
full_name: Dziubiński, Marcin
last_name: Dziubiński
citation:
ama: 'Polevoy G, Dziubiński M. Fair, Individually Rational and Cheap Adjustment.
In: De Raedt L, ed. Proceedings of the Thirty-First International Joint Conference
on Artificial Intelligence. International Joint Conferences on Artificial
Intelligence Organization; 2022. doi:10.24963/ijcai.2022/64'
apa: Polevoy, G., & Dziubiński, M. (2022). Fair, Individually Rational and Cheap
Adjustment. In L. De Raedt (Ed.), Proceedings of the Thirty-First International
Joint Conference on Artificial Intelligence. International Joint Conferences
on Artificial Intelligence Organization. https://doi.org/10.24963/ijcai.2022/64
bibtex: '@inproceedings{Polevoy_Dziubiński_2022, title={Fair, Individually Rational
and Cheap Adjustment}, DOI={10.24963/ijcai.2022/64},
booktitle={Proceedings of the Thirty-First International Joint Conference on Artificial
Intelligence}, publisher={International Joint Conferences on Artificial Intelligence
Organization}, author={Polevoy, Gleb and Dziubiński, Marcin}, editor={De Raedt,
Luc}, year={2022} }'
chicago: Polevoy, Gleb, and Marcin Dziubiński. “Fair, Individually Rational and
Cheap Adjustment.” In Proceedings of the Thirty-First International Joint Conference
on Artificial Intelligence, edited by Luc De Raedt. International Joint Conferences
on Artificial Intelligence Organization, 2022. https://doi.org/10.24963/ijcai.2022/64.
ieee: 'G. Polevoy and M. Dziubiński, “Fair, Individually Rational and Cheap Adjustment,”
in Proceedings of the Thirty-First International Joint Conference on Artificial
Intelligence, Vienna, 2022, doi: 10.24963/ijcai.2022/64.'
mla: Polevoy, Gleb, and Marcin Dziubiński. “Fair, Individually Rational and Cheap
Adjustment.” Proceedings of the Thirty-First International Joint Conference
on Artificial Intelligence, edited by Luc De Raedt, International Joint Conferences
on Artificial Intelligence Organization, 2022, doi:10.24963/ijcai.2022/64.
short: 'G. Polevoy, M. Dziubiński, in: L. De Raedt (Ed.), Proceedings of the Thirty-First
International Joint Conference on Artificial Intelligence, International Joint
Conferences on Artificial Intelligence Organization, 2022.'
conference:
end_date: 2022-07-29
location: Vienna
name: THE 31ST INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE
start_date: 2022-07-23
date_created: 2022-11-08T16:53:31Z
date_updated: 2022-11-08T17:34:36Z
department:
- _id: '63'
- _id: '541'
doi: 10.24963/ijcai.2022/64
editor:
- first_name: Luc
full_name: De Raedt, Luc
last_name: De Raedt
keyword:
- adjustment
- strictly dominant
- fairness
- individually rational
- transfer
- tax
- subsidy
language:
- iso: eng
main_file_link:
- url: https://www.ijcai.org/proceedings/2022/64
publication: Proceedings of the Thirty-First International Joint Conference on Artificial
Intelligence
publication_status: published
publisher: International Joint Conferences on Artificial Intelligence Organization
status: public
title: Fair, Individually Rational and Cheap Adjustment
type: conference
user_id: '83983'
year: '2022'
...
---
_id: '17667'
abstract:
- lang: eng
text: 'Resolving distributed attacks benefits from collaboration between networks.
We present three approaches for the same multi-domain defensive action that can
be applied in such an alliance: 1) Counteract Everywhere, 2) Minimize Countermeasures,
and 3) Minimize Propagation. First, we provide a formula to compute efficiency
of a defense; then we use this formula to compute the efficiency of the approaches
under various circumstances. Finally, we discuss how task execution order and
timing influence defense efficiency. Our results show that the Minimize Propagation
approach is the most efficient method when defending against the chosen attack.'
author:
- first_name: Ralph
full_name: Koning, Ralph
last_name: Koning
- first_name: Gleb
full_name: Polevoy, Gleb
id: '83983'
last_name: Polevoy
- first_name: Lydia
full_name: Meijer, Lydia
last_name: Meijer
- first_name: Cees
full_name: de Laat, Cees
last_name: de Laat
- first_name: Paola
full_name: Grosso, Paola
last_name: Grosso
citation:
ama: 'Koning R, Polevoy G, Meijer L, de Laat C, Grosso P. Approaches for Collaborative
Security Defences in Multi Network Environments. In: 2019 6th IEEE International
Conference on Cyber Security and Cloud Computing (CSCloud)/ 2019 5th IEEE International
Conference on Edge Computing and Scalable Cloud (EdgeCom). 2019 6th IEEE International
Conference on Cyber Security and Cloud Computing (CSCloud)/ 2019 5th IEEE International
Conference on Edge Computing and Scalable Cloud (EdgeCom). ; 2019:113-123. doi:10.1109/CSCloud/EdgeCom.2019.000-9'
apa: Koning, R., Polevoy, G., Meijer, L., de Laat, C., & Grosso, P. (2019).
Approaches for Collaborative Security Defences in Multi Network Environments.
In 2019 6th IEEE International Conference on Cyber Security and Cloud Computing
(CSCloud)/ 2019 5th IEEE International Conference on Edge Computing and Scalable
Cloud (EdgeCom) (pp. 113–123). https://doi.org/10.1109/CSCloud/EdgeCom.2019.000-9
bibtex: '@inproceedings{Koning_Polevoy_Meijer_de Laat_Grosso_2019, series={2019
6th IEEE International Conference on Cyber Security and Cloud Computing (CSCloud)/
2019 5th IEEE International Conference on Edge Computing and Scalable Cloud (EdgeCom)},
title={Approaches for Collaborative Security Defences in Multi Network Environments},
DOI={10.1109/CSCloud/EdgeCom.2019.000-9},
booktitle={2019 6th IEEE International Conference on Cyber Security and Cloud
Computing (CSCloud)/ 2019 5th IEEE International Conference on Edge Computing
and Scalable Cloud (EdgeCom)}, author={Koning, Ralph and Polevoy, Gleb and Meijer,
Lydia and de Laat, Cees and Grosso, Paola}, year={2019}, pages={113–123}, collection={2019
6th IEEE International Conference on Cyber Security and Cloud Computing (CSCloud)/
2019 5th IEEE International Conference on Edge Computing and Scalable Cloud (EdgeCom)}
}'
chicago: Koning, Ralph, Gleb Polevoy, Lydia Meijer, Cees de Laat, and Paola Grosso.
“Approaches for Collaborative Security Defences in Multi Network Environments.”
In 2019 6th IEEE International Conference on Cyber Security and Cloud Computing
(CSCloud)/ 2019 5th IEEE International Conference on Edge Computing and Scalable
Cloud (EdgeCom), 113–23. 2019 6th IEEE International Conference on Cyber Security
and Cloud Computing (CSCloud)/ 2019 5th IEEE International Conference on Edge
Computing and Scalable Cloud (EdgeCom), 2019. https://doi.org/10.1109/CSCloud/EdgeCom.2019.000-9.
ieee: R. Koning, G. Polevoy, L. Meijer, C. de Laat, and P. Grosso, “Approaches for
Collaborative Security Defences in Multi Network Environments,” in 2019 6th
IEEE International Conference on Cyber Security and Cloud Computing (CSCloud)/
2019 5th IEEE International Conference on Edge Computing and Scalable Cloud (EdgeCom),
2019, pp. 113–123.
mla: Koning, Ralph, et al. “Approaches for Collaborative Security Defences in Multi
Network Environments.” 2019 6th IEEE International Conference on Cyber Security
and Cloud Computing (CSCloud)/ 2019 5th IEEE International Conference on Edge
Computing and Scalable Cloud (EdgeCom), 2019, pp. 113–23, doi:10.1109/CSCloud/EdgeCom.2019.000-9.
short: 'R. Koning, G. Polevoy, L. Meijer, C. de Laat, P. Grosso, in: 2019 6th IEEE
International Conference on Cyber Security and Cloud Computing (CSCloud)/ 2019
5th IEEE International Conference on Edge Computing and Scalable Cloud (EdgeCom),
2019, pp. 113–123.'
conference:
name: 2019 6th IEEE International Conference on Cyber Security and Cloud Computing
(CSCloud)/ 2019 5th IEEE International Conference on Edge Computing and Scalable
Cloud (EdgeCom)
date_created: 2020-08-06T15:23:23Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
doi: 10.1109/CSCloud/EdgeCom.2019.000-9
extern: '1'
keyword:
- computer network security
- multinetwork environments
- multidomain defensive action
- task execution order
- timing influence defense efficiency
- distributed attacks
- collaborative security defence approach
- minimize propagation approach
- minimize countermeasure approach
- counteract everywhere approach
- Conferences
- Cloud computing
- Computer crime
- Edge computing
- Security
- Defense Approaches
- Multi-Domain Defense
- Collaborative Defense
- Defense Algorithms
- Computer Networks
language:
- iso: eng
main_file_link:
- url: https://ieeexplore.ieee.org/abstract/document/8854057/authors#authors
page: 113-123
publication: 2019 6th IEEE International Conference on Cyber Security and Cloud Computing
(CSCloud)/ 2019 5th IEEE International Conference on Edge Computing and Scalable
Cloud (EdgeCom)
publication_identifier:
issn:
- 'null'
quality_controlled: '1'
series_title: 2019 6th IEEE International Conference on Cyber Security and Cloud Computing
(CSCloud)/ 2019 5th IEEE International Conference on Edge Computing and Scalable
Cloud (EdgeCom)
status: public
title: Approaches for Collaborative Security Defences in Multi Network Environments
type: conference
user_id: '83983'
year: '2019'
...
---
_id: '8080'
abstract:
- lang: eng
text: This thesis investigates approximate pure Nash equilibria in different game-theoretic
models. In such an outcome, no player can improve her objective by more than a
given factor through a deviation to another strategy. In the first part, we investigate
two variants of Congestion Games in which the existence of pure Nash equilibria
is guaranteed through a potential function argument. However, the computation
of such equilibria might be hard. We construct and analyze approximation algorithms
that enable the computation of states with low approximation factors in polynomial
time. To show their guarantees we use sub games among players, bound the potential
function values of arbitrary states and exploit a connection between Shapley and
proportional cost shares. Furthermore, we apply and analyze sampling techniques
for the computation of approximate Shapley values in different settings. In the
second part, we concentrate on the existence of approximate pure Nash equilibria
in games in which no pure Nash equilibria exist in general. In the model of Coevolving
Opinion Formation Games, we bound the approximation guarantees for natural states
nearly independent of the specific definition of the players' neighborhoods by
applying a concept of virtual costs. For the special case of only one influential
neighbor, we even show lower approximation factors for a natural strategy. Then,
we investigate a two-sided Facility Location Game among facilities and clients
on a line with an objective function consisting of distance and load. We show
tight bounds on the approximation factor for settings with three facilities and
infinitely many clients. For the general scenario with an arbitrary number of
facilities, we bound the approximation factor for two promising candidates, namely
facilities that are uniformly distributed and which are paired.
author:
- first_name: Matthias
full_name: Feldotto, Matthias
id: '14052'
last_name: Feldotto
orcid: 0000-0003-1348-6516
citation:
ama: Feldotto M. Approximate Pure Nash Equilibria in Congestion, Opinion Formation
and Facility Location Games. Universität Paderborn; 2019. doi:10.17619/UNIPB/1-588
apa: Feldotto, M. (2019). Approximate Pure Nash Equilibria in Congestion, Opinion
Formation and Facility Location Games. Universität Paderborn. https://doi.org/10.17619/UNIPB/1-588
bibtex: '@book{Feldotto_2019, place={Universität Paderborn}, title={Approximate
Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games},
DOI={10.17619/UNIPB/1-588},
author={Feldotto, Matthias}, year={2019} }'
chicago: Feldotto, Matthias. Approximate Pure Nash Equilibria in Congestion,
Opinion Formation and Facility Location Games. Universität Paderborn, 2019.
https://doi.org/10.17619/UNIPB/1-588.
ieee: M. Feldotto, Approximate Pure Nash Equilibria in Congestion, Opinion Formation
and Facility Location Games. Universität Paderborn, 2019.
mla: Feldotto, Matthias. Approximate Pure Nash Equilibria in Congestion, Opinion
Formation and Facility Location Games. 2019, doi:10.17619/UNIPB/1-588.
short: M. Feldotto, Approximate Pure Nash Equilibria in Congestion, Opinion Formation
and Facility Location Games, Universität Paderborn, 2019.
date_created: 2019-02-25T13:03:02Z
date_updated: 2022-01-06T07:03:50Z
ddc:
- '000'
department:
- _id: '541'
- _id: '63'
doi: 10.17619/UNIPB/1-588
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2019-03-28T13:40:51Z
date_updated: 2019-03-28T13:40:51Z
file_id: '8715'
file_name: Approximate Pure Nash Equilibria in Congestion, Opinion Formation and
Facility Location Games.pdf
file_size: 3116177
relation: main_file
success: 1
file_date_updated: 2019-03-28T13:40:51Z
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- url: http://digital.ub.uni-paderborn.de/hs/download/pdf/3005508?originalFilename=true
place: Universität Paderborn
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '7'
name: SFB 901 - Subproject A3
status: public
supervisor:
- first_name: Alexander
full_name: Skopalik, Alexander
id: '40384'
last_name: Skopalik
title: Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility
Location Games
type: dissertation
user_id: '15415'
year: '2019'
...
---
_id: '5471'
abstract:
- lang: eng
text: "We characterise the set of dominant strategy incentive compatible (DSIC),
strongly budget balanced (SBB), and ex-post individually rational (IR) mechanisms
for the multi-unit bilateral trade setting. In such a setting there is a single
buyer and a single seller who holds a finite number k of identical items. The
mechanism has to decide how many units of the item are transferred from the seller
to the buyer and how much money is transferred from the buyer to the seller. We
consider two classes of valuation functions for the buyer and seller: Valuations
that are increasing in the number of units in possession, and the more specific
class of valuations that are increasing and submodular. \r\nFurthermore, we present
some approximation results about the performance of certain such mechanisms, in
terms of social welfare: For increasing submodular valuation functions, we show
the existence of a deterministic 2-approximation mechanism and a randomised e/(1-e)
approximation mechanism, matching the best known bounds for the single-item setting."
author:
- first_name: Philip
full_name: Lazos, Philip
last_name: Lazos
- first_name: Paul
full_name: Goldberg, Paul
last_name: Goldberg
- first_name: Alexander
full_name: Skopalik, Alexander
id: '40384'
last_name: Skopalik
- first_name: Matthias
full_name: Gerstgrasser, Matthias
last_name: Gerstgrasser
- first_name: Bart
full_name: de Keijzer, Bart
last_name: de Keijzer
citation:
ama: 'Lazos P, Goldberg P, Skopalik A, Gerstgrasser M, de Keijzer B. Multi-unit
Bilateral Trade. In: Proceedings of the Thirty-Third AAAI Conference on Artificial
Intelligence (AAAI). ; 2019. doi:10.1609/aaai.v33i01.33011973'
apa: Lazos, P., Goldberg, P., Skopalik, A., Gerstgrasser, M., & de Keijzer,
B. (2019). Multi-unit Bilateral Trade. Proceedings of the Thirty-Third AAAI
Conference on Artificial Intelligence (AAAI). Thirty-Third AAAI Conference
on Artificial Intelligence (AAAI), Honolulu, Hawaii, USA. https://doi.org/10.1609/aaai.v33i01.33011973
bibtex: '@inproceedings{Lazos_Goldberg_Skopalik_Gerstgrasser_de Keijzer_2019, title={
Multi-unit Bilateral Trade}, DOI={10.1609/aaai.v33i01.33011973},
booktitle={Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence
(AAAI)}, author={Lazos, Philip and Goldberg, Paul and Skopalik, Alexander and
Gerstgrasser, Matthias and de Keijzer, Bart}, year={2019} }'
chicago: Lazos, Philip, Paul Goldberg, Alexander Skopalik, Matthias Gerstgrasser,
and Bart de Keijzer. “ Multi-Unit Bilateral Trade.” In Proceedings of the Thirty-Third
AAAI Conference on Artificial Intelligence (AAAI), 2019. https://doi.org/10.1609/aaai.v33i01.33011973.
ieee: 'P. Lazos, P. Goldberg, A. Skopalik, M. Gerstgrasser, and B. de Keijzer, “
Multi-unit Bilateral Trade,” presented at the Thirty-Third AAAI Conference on
Artificial Intelligence (AAAI), Honolulu, Hawaii, USA, 2019, doi: 10.1609/aaai.v33i01.33011973.'
mla: Lazos, Philip, et al. “ Multi-Unit Bilateral Trade.” Proceedings of the
Thirty-Third AAAI Conference on Artificial Intelligence (AAAI), 2019, doi:10.1609/aaai.v33i01.33011973.
short: 'P. Lazos, P. Goldberg, A. Skopalik, M. Gerstgrasser, B. de Keijzer, in:
Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI),
2019.'
conference:
end_date: 2019-02-01
location: Honolulu, Hawaii, USA
name: Thirty-Third AAAI Conference on Artificial Intelligence (AAAI)
start_date: 2019-01-27
date_created: 2018-11-12T09:38:16Z
date_updated: 2022-01-06T07:01:55Z
ddc:
- '000'
department:
- _id: '541'
- _id: '63'
doi: 10.1609/aaai.v33i01.33011973
file:
- access_level: closed
content_type: application/pdf
creator: feldi
date_created: 2018-12-06T13:57:51Z
date_updated: 2018-12-06T13:57:51Z
file_id: '6018'
file_name: 1811.05130.pdf
file_size: 315877
relation: main_file
success: 1
file_date_updated: 2018-12-06T13:57:51Z
has_accepted_license: '1'
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '7'
name: SFB 901 - Subproject A3
publication: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence
(AAAI)
publication_status: published
status: public
title: ' Multi-unit Bilateral Trade'
type: conference
user_id: '15415'
year: '2019'
...
---
_id: '10281'
abstract:
- lang: eng
text: 'Competing firms tend to select similar locations for their stores. This phenomenon,
called the principle of minimum differentiation, was captured by Hotelling with
a landmark model of spatial competition but is still the object of an ongoing
scientific debate. Although consistently observed in practice, many more realistic
variants of Hotelling''s model fail to support minimum differentiation or do not
have pure equilibria at all. In particular, it was recently proven for a generalized
model which incorporates negative network externalities and which contains Hotelling''s
model and classical selfish load balancing as special cases, that the unique equilibria
do not adhere to minimum differentiation. Furthermore, it was shown that for a
significant parameter range pure equilibria do not exist. We derive a sharp contrast
to these previous results by investigating Hotelling''s model with negative network
externalities from an entirely new angle: approximate pure subgame perfect equilibria.
This approach allows us to prove analytically and via agent-based simulations
that approximate equilibria having good approximation guarantees and that adhere
to minimum differentiation exist for the full parameter range of the model. Moreover,
we show that the obtained approximate equilibria have high social welfare.'
author:
- first_name: Matthias
full_name: Feldotto, Matthias
id: '14052'
last_name: Feldotto
orcid: 0000-0003-1348-6516
- first_name: 'Pascal '
full_name: 'Lenzner, Pascal '
last_name: Lenzner
- first_name: Louise
full_name: Molitor, Louise
last_name: Molitor
- first_name: Alexander
full_name: Skopalik, Alexander
id: '40384'
last_name: Skopalik
citation:
ama: 'Feldotto M, Lenzner P, Molitor L, Skopalik A. From Hotelling to Load Balancing:
Approximation and the Principle of Minimum Differentiation. In: Proceedings
of the 18th International Conference on Autonomous Agents and MultiAgent Systems.
International Foundation for Autonomous Agents and Multiagent Systems; 2019:1949--1951.'
apa: 'Feldotto, M., Lenzner, P., Molitor, L., & Skopalik, A. (2019). From Hotelling
to Load Balancing: Approximation and the Principle of Minimum Differentiation.
In Proceedings of the 18th International Conference on Autonomous Agents and
MultiAgent Systems (pp. 1949--1951). Montreal QC, Canada: International Foundation
for Autonomous Agents and Multiagent Systems.'
bibtex: '@inproceedings{Feldotto_Lenzner_Molitor_Skopalik_2019, title={ From Hotelling
to Load Balancing: Approximation and the Principle of Minimum Differentiation},
booktitle={Proceedings of the 18th International Conference on Autonomous Agents
and MultiAgent Systems}, publisher={International Foundation for Autonomous Agents
and Multiagent Systems}, author={Feldotto, Matthias and Lenzner, Pascal and Molitor,
Louise and Skopalik, Alexander}, year={2019}, pages={1949--1951} }'
chicago: 'Feldotto, Matthias, Pascal Lenzner, Louise Molitor, and Alexander Skopalik.
“ From Hotelling to Load Balancing: Approximation and the Principle of Minimum
Differentiation.” In Proceedings of the 18th International Conference on Autonomous
Agents and MultiAgent Systems, 1949--1951. International Foundation for Autonomous
Agents and Multiagent Systems, 2019.'
ieee: 'M. Feldotto, P. Lenzner, L. Molitor, and A. Skopalik, “ From Hotelling to
Load Balancing: Approximation and the Principle of Minimum Differentiation,” in
Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent
Systems, Montreal QC, Canada, 2019, pp. 1949--1951.'
mla: 'Feldotto, Matthias, et al. “ From Hotelling to Load Balancing: Approximation
and the Principle of Minimum Differentiation.” Proceedings of the 18th International
Conference on Autonomous Agents and MultiAgent Systems, International Foundation
for Autonomous Agents and Multiagent Systems, 2019, pp. 1949--1951.'
short: 'M. Feldotto, P. Lenzner, L. Molitor, A. Skopalik, in: Proceedings of the
18th International Conference on Autonomous Agents and MultiAgent Systems, International
Foundation for Autonomous Agents and Multiagent Systems, 2019, pp. 1949--1951.'
conference:
location: Montreal QC, Canada
name: 18th International Conference on Autonomous Agents and MultiAgent Systems
date_created: 2019-06-20T14:46:08Z
date_updated: 2022-01-06T06:50:33Z
ddc:
- '004'
department:
- _id: '541'
- _id: '63'
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2019-08-26T11:10:02Z
date_updated: 2019-08-26T11:10:02Z
file_id: '12962'
file_name: 1903.04265.pdf
file_size: 698599
relation: main_file
success: 1
file_date_updated: 2019-08-26T11:10:02Z
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/citation.cfm?id=3331973
page: 1949--1951
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '7'
name: SFB 901 - Subproject A3
publication: Proceedings of the 18th International Conference on Autonomous Agents
and MultiAgent Systems
publication_status: published
publisher: International Foundation for Autonomous Agents and Multiagent Systems
status: public
title: ' From Hotelling to Load Balancing: Approximation and the Principle of Minimum
Differentiation'
type: conference
user_id: '477'
year: '2019'
...
---
_id: '2484'
abstract:
- lang: eng
text: We study the classic bin packing problem in a fully-dynamic setting, where
new items can arrive and old items may depart. We want algorithms with low asymptotic
competitive ratio while repacking items sparingly between updates. Formally, each
item i has a movement cost c_i >= 0, and we want to use alpha * OPT bins and incur
a movement cost gamma * c_i, either in the worst case, or in an amortized sense,
for alpha, gamma as small as possible. We call gamma the recourse of the algorithm.
This is motivated by cloud storage applications, where fully-dynamic bin packing
models the problem of data backup to minimize the number of disks used, as well
as communication incurred in moving file backups between disks. Since the set
of files changes over time, we could recompute a solution periodically from scratch,
but this would give a high number of disk rewrites, incurring a high energy cost
and possible wear and tear of the disks. In this work, we present optimal tradeoffs
between number of bins used and number of items repacked, as well as natural extensions
of the latter measure.
author:
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Matthias
full_name: Feldotto, Matthias
id: '14052'
last_name: Feldotto
orcid: 0000-0003-1348-6516
- first_name: Anupam
full_name: Gupta, Anupam
last_name: Gupta
- first_name: Guru
full_name: Guruganesh, Guru
last_name: Guruganesh
- first_name: 'Amit '
full_name: 'Kumar, Amit '
last_name: Kumar
- first_name: Sören
full_name: Riechers, Sören
last_name: Riechers
- first_name: David
full_name: Wajc, David
last_name: Wajc
citation:
ama: 'Feldkord B, Feldotto M, Gupta A, et al. Fully-Dynamic Bin Packing with Little
Repacking. In: Chatzigiannakis I, Kaklamanis C, Marx D, Sannella D, eds. 45th
International Colloquium on Automata, Languages, and Programming (ICALP 2018).
Vol 107. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl,
Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik; 2018:51:1-51:24. doi:10.4230/LIPIcs.ICALP.2018.51'
apa: 'Feldkord, B., Feldotto, M., Gupta, A., Guruganesh, G., Kumar, A., Riechers,
S., & Wajc, D. (2018). Fully-Dynamic Bin Packing with Little Repacking. In
I. Chatzigiannakis, C. Kaklamanis, D. Marx, & D. Sannella (Eds.), 45th
International Colloquium on Automata, Languages, and Programming (ICALP 2018)
(Vol. 107, pp. 51:1-51:24). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum
fuer Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2018.51'
bibtex: '@inproceedings{Feldkord_Feldotto_Gupta_Guruganesh_Kumar_Riechers_Wajc_2018,
place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics
(LIPIcs)}, title={Fully-Dynamic Bin Packing with Little Repacking}, volume={107},
DOI={10.4230/LIPIcs.ICALP.2018.51},
booktitle={45th International Colloquium on Automata, Languages, and Programming
(ICALP 2018)}, publisher={Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
author={Feldkord, Björn and Feldotto, Matthias and Gupta, Anupam and Guruganesh,
Guru and Kumar, Amit and Riechers, Sören and Wajc, David}, editor={Chatzigiannakis,
Ioannis and Kaklamanis, Christos and Marx, Dániel and Sannella, DonaldEditors},
year={2018}, pages={51:1-51:24}, collection={Leibniz International Proceedings
in Informatics (LIPIcs)} }'
chicago: 'Feldkord, Björn, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar,
Sören Riechers, and David Wajc. “Fully-Dynamic Bin Packing with Little Repacking.”
In 45th International Colloquium on Automata, Languages, and Programming (ICALP
2018), edited by Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx,
and Donald Sannella, 107:51:1-51:24. Leibniz International Proceedings in Informatics
(LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik,
2018. https://doi.org/10.4230/LIPIcs.ICALP.2018.51.'
ieee: B. Feldkord et al., “Fully-Dynamic Bin Packing with Little Repacking,”
in 45th International Colloquium on Automata, Languages, and Programming (ICALP
2018), Prag, 2018, vol. 107, pp. 51:1-51:24.
mla: Feldkord, Björn, et al. “Fully-Dynamic Bin Packing with Little Repacking.”
45th International Colloquium on Automata, Languages, and Programming (ICALP
2018), edited by Ioannis Chatzigiannakis et al., vol. 107, Schloss Dagstuhl--Leibniz-Zentrum
fuer Informatik, 2018, pp. 51:1-51:24, doi:10.4230/LIPIcs.ICALP.2018.51.
short: 'B. Feldkord, M. Feldotto, A. Gupta, G. Guruganesh, A. Kumar, S. Riechers,
D. Wajc, in: I. Chatzigiannakis, C. Kaklamanis, D. Marx, D. Sannella (Eds.), 45th
International Colloquium on Automata, Languages, and Programming (ICALP 2018),
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, pp.
51:1-51:24.'
conference:
end_date: 2018-07-13
location: Prag
name: 45th International Colloquium on Automata, Languages, and Programming (ICALP
2018)
start_date: 2018-07-10
date_created: 2018-04-24T15:21:56Z
date_updated: 2022-01-06T06:56:39Z
ddc:
- '000'
department:
- _id: '541'
- _id: '63'
doi: 10.4230/LIPIcs.ICALP.2018.51
editor:
- first_name: Ioannis
full_name: Chatzigiannakis, Ioannis
last_name: Chatzigiannakis
- first_name: Christos
full_name: Kaklamanis, Christos
last_name: Kaklamanis
- first_name: Dániel
full_name: Marx, Dániel
last_name: Marx
- first_name: Donald
full_name: Sannella, Donald
last_name: Sannella
external_id:
arxiv:
- '1711.01231'
file:
- access_level: closed
content_type: application/pdf
creator: feldi
date_created: 2018-10-31T16:58:18Z
date_updated: 2018-10-31T16:58:18Z
file_id: '5227'
file_name: LIPIcs-ICALP-2018-51.pdf
file_size: 723824
relation: main_file
success: 1
file_date_updated: 2018-10-31T16:58:18Z
has_accepted_license: '1'
intvolume: ' 107'
language:
- iso: eng
page: 51:1-51:24
place: Dagstuhl, Germany
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '4'
name: SFB 901 - Project Area C
- _id: '5'
name: SFB 901 - Subproject A1
- _id: '7'
name: SFB 901 - Subproject A3
- _id: '16'
name: SFB 901 - Subproject C4
publication: 45th International Colloquium on Automata, Languages, and Programming
(ICALP 2018)
publication_identifier:
isbn:
- 978-3-95977-076-7
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Fully-Dynamic Bin Packing with Little Repacking
type: conference
user_id: '14052'
volume: 107
year: '2018'
...
---
_id: '2831'
abstract:
- lang: eng
text: 'We consider a market where final products or services are compositions of
a number of basic services. Users are asked to evaluate the quality of the composed
product after purchase. The quality of the basic service influences the performance
of the composed services but cannot be observed directly. The question we pose
is whether it is possible to use user evaluations on composed services to assess
the quality of basic services. We discuss how to combine aggregation of evaluations
across users and disaggregation of information on composed services to derive
valuations for the single components. As a solution we propose to use the (weighted)
average as aggregation device in connection with the Shapley value as disaggregation
method, since this combination fulfills natural requirements in our context. In
addition, we address some occurring computational issues: We give an approximate
solution concept using only a limited number of evaluations which guarantees nearly
optimal results with reduced running time. Lastly, we show that a slightly modified
Shapley value and the weighted average are still applicable if the evaluation
profiles are incomplete.'
author:
- first_name: Matthias
full_name: Feldotto, Matthias
id: '14052'
last_name: Feldotto
orcid: 0000-0003-1348-6516
- first_name: Claus-Jochen
full_name: Haake, Claus-Jochen
id: '20801'
last_name: Haake
- first_name: Alexander
full_name: Skopalik, Alexander
id: '40384'
last_name: Skopalik
- first_name: Nadja
full_name: Stroh-Maraun, Nadja
id: '13264'
last_name: Stroh-Maraun
citation:
ama: 'Feldotto M, Haake C-J, Skopalik A, Stroh-Maraun N. Disaggregating User Evaluations
Using the Shapley Value. In: Proceedings of the 13th Workshop on Economics
of Networks, Systems and Computation (NetEcon 2018). ; 2018:5:1-5:6. doi:10.1145/3230654.3230659'
apa: Feldotto, M., Haake, C.-J., Skopalik, A., & Stroh-Maraun, N. (2018). Disaggregating
User Evaluations Using the Shapley Value. In Proceedings of the 13th Workshop
on Economics of Networks, Systems and Computation (NetEcon 2018) (pp. 5:1-5:6).
Irvine, California, USA. https://doi.org/10.1145/3230654.3230659
bibtex: '@inproceedings{Feldotto_Haake_Skopalik_Stroh-Maraun_2018, title={Disaggregating
User Evaluations Using the Shapley Value}, DOI={10.1145/3230654.3230659},
booktitle={Proceedings of the 13th Workshop on Economics of Networks, Systems
and Computation (NetEcon 2018)}, author={Feldotto, Matthias and Haake, Claus-Jochen
and Skopalik, Alexander and Stroh-Maraun, Nadja}, year={2018}, pages={5:1-5:6}
}'
chicago: Feldotto, Matthias, Claus-Jochen Haake, Alexander Skopalik, and Nadja Stroh-Maraun.
“Disaggregating User Evaluations Using the Shapley Value.” In Proceedings of
the 13th Workshop on Economics of Networks, Systems and Computation (NetEcon 2018),
5:1-5:6, 2018. https://doi.org/10.1145/3230654.3230659.
ieee: M. Feldotto, C.-J. Haake, A. Skopalik, and N. Stroh-Maraun, “Disaggregating
User Evaluations Using the Shapley Value,” in Proceedings of the 13th Workshop
on Economics of Networks, Systems and Computation (NetEcon 2018), Irvine,
California, USA, 2018, pp. 5:1-5:6.
mla: Feldotto, Matthias, et al. “Disaggregating User Evaluations Using the Shapley
Value.” Proceedings of the 13th Workshop on Economics of Networks, Systems
and Computation (NetEcon 2018), 2018, pp. 5:1-5:6, doi:10.1145/3230654.3230659.
short: 'M. Feldotto, C.-J. Haake, A. Skopalik, N. Stroh-Maraun, in: Proceedings
of the 13th Workshop on Economics of Networks, Systems and Computation (NetEcon
2018), 2018, pp. 5:1-5:6.'
conference:
end_date: 2018-06-18
location: Irvine, California, USA
name: The 13th Workshop on the Economics of Networks, Systems and Computation (NetEcon
2018)
start_date: 2018-06-18
date_created: 2018-05-22T10:28:51Z
date_updated: 2022-01-06T06:58:01Z
ddc:
- '040'
department:
- _id: '541'
- _id: '63'
- _id: '205'
- _id: '475'
doi: 10.1145/3230654.3230659
file:
- access_level: closed
content_type: application/pdf
creator: nmaraun
date_created: 2018-08-15T07:30:50Z
date_updated: 2018-08-15T07:30:50Z
file_id: '3910'
file_name: Disaggregating User Evaluations Using the Shapley Value.pdf
file_size: 1450171
relation: main_file
success: 1
file_date_updated: 2018-08-15T07:30:50Z
has_accepted_license: '1'
language:
- iso: eng
page: 5:1-5:6
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '7'
name: SFB 901 - Subproject A3
publication: Proceedings of the 13th Workshop on Economics of Networks, Systems and
Computation (NetEcon 2018)
publication_identifier:
isbn:
- 978-1-4503-5916-0
publication_status: published
status: public
title: Disaggregating User Evaluations Using the Shapley Value
type: conference
user_id: '14052'
year: '2018'
...
---
_id: '3851'
author:
- first_name: Samuel
full_name: Koop, Samuel
last_name: Koop
citation:
ama: Koop S. Congestion Games mit gewichteten Strategien. Universität Paderborn;
2018.
apa: Koop, S. (2018). Congestion Games mit gewichteten Strategien. Universität
Paderborn.
bibtex: '@book{Koop_2018, title={Congestion Games mit gewichteten Strategien}, publisher={Universität
Paderborn}, author={Koop, Samuel}, year={2018} }'
chicago: Koop, Samuel. Congestion Games mit gewichteten Strategien. Universität
Paderborn, 2018.
ieee: S. Koop, Congestion Games mit gewichteten Strategien. Universität Paderborn,
2018.
mla: Koop, Samuel. Congestion Games mit gewichteten Strategien. Universität
Paderborn, 2018.
short: S. Koop, Congestion Games mit gewichteten Strategien, Universität Paderborn,
2018.
date_created: 2018-08-08T11:56:37Z
date_updated: 2022-01-06T06:59:45Z
department:
- _id: '541'
- _id: '63'
language:
- iso: ger
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '7'
name: SFB 901 - Subproject A3
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Alexander
full_name: Skopalik, Alexander
id: '40384'
last_name: Skopalik
title: Congestion Games mit gewichteten Strategien
type: bachelorsthesis
user_id: '14052'
year: '2018'
...
---
_id: '17651'
abstract:
- lang: eng
text: 'Consider mitigating the effects of denial of service or of malicious traffic
in networks by deleting edges. Edge deletion reduces the DoS or the number of
the malicious flows, but it also inadvertently removes some of the desired flows.
To model this important problem, we formulate two problems: (1) remove all the
undesirable flows while minimizing the damage to the desirable ones and (2) balance
removing the undesirable flows and not removing too many of the desirable flows.
We prove these problems are equivalent to important theoretical problems, thereby
being important not only practically but also theoretically, and very hard to
approximate in a general network. We employ reductions to nonetheless approximate
the problem and also provide a greedy approximation. When the network is a tree,
the problems are still MAX SNP-hard, but we provide a greedy-based 2l-approximation
algorithm, where l is the longest desirable flow. We also provide an algorithm,
approximating the first and the second problem within {\$}{\$}2 {\backslash}sqrt{\{}
2{\backslash}left| E {\backslash}right| {\}}{\$}{\$}and {\$}{\$}2 {\backslash}sqrt{\{}2
({\backslash}left| E {\backslash}right| + {\backslash}left| {\backslash}text {\{}undesirable
flows{\}} {\backslash}right| ){\}}{\$}{\$}, respectively, where E is the set of
the edges of the network. We also provide a fixed-parameter tractable (FPT) algorithm.
Finally, if the tree has a root such that every flow in the tree flows on the
path from the root to a leaf, we solve the problem exactly using dynamic programming.'
author:
- first_name: Gleb
full_name: Polevoy, Gleb
id: '83983'
last_name: Polevoy
- first_name: Stojan
full_name: Trajanovski, Stojan
last_name: Trajanovski
- first_name: Paola
full_name: Grosso, Paola
last_name: Grosso
- first_name: Cees
full_name: de Laat, Cees
last_name: de Laat
citation:
ama: 'Polevoy G, Trajanovski S, Grosso P, de Laat C. Removing Undesirable Flows
by Edge Deletion. In: Kim D, Uma RN, Zelikovsky A, eds. Combinatorial Optimization
and Applications. Cham: Springer International Publishing; 2018:217-232.'
apa: 'Polevoy, G., Trajanovski, S., Grosso, P., & de Laat, C. (2018). Removing
Undesirable Flows by Edge Deletion. In D. Kim, R. N. Uma, & A. Zelikovsky
(Eds.), Combinatorial Optimization and Applications (pp. 217–232). Cham:
Springer International Publishing.'
bibtex: '@inproceedings{Polevoy_Trajanovski_Grosso_de Laat_2018, place={Cham}, title={Removing
Undesirable Flows by Edge Deletion}, booktitle={Combinatorial Optimization and
Applications}, publisher={Springer International Publishing}, author={Polevoy,
Gleb and Trajanovski, Stojan and Grosso, Paola and de Laat, Cees}, editor={Kim,
Donghyun and Uma, R. N. and Zelikovsky, AlexanderEditors}, year={2018}, pages={217–232}
}'
chicago: 'Polevoy, Gleb, Stojan Trajanovski, Paola Grosso, and Cees de Laat. “Removing
Undesirable Flows by Edge Deletion.” In Combinatorial Optimization and Applications,
edited by Donghyun Kim, R. N. Uma, and Alexander Zelikovsky, 217–32. Cham: Springer
International Publishing, 2018.'
ieee: G. Polevoy, S. Trajanovski, P. Grosso, and C. de Laat, “Removing Undesirable
Flows by Edge Deletion,” in Combinatorial Optimization and Applications,
2018, pp. 217–232.
mla: Polevoy, Gleb, et al. “Removing Undesirable Flows by Edge Deletion.” Combinatorial
Optimization and Applications, edited by Donghyun Kim et al., Springer International
Publishing, 2018, pp. 217–32.
short: 'G. Polevoy, S. Trajanovski, P. Grosso, C. de Laat, in: D. Kim, R.N. Uma,
A. Zelikovsky (Eds.), Combinatorial Optimization and Applications, Springer International
Publishing, Cham, 2018, pp. 217–232.'
date_created: 2020-08-06T15:19:36Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
editor:
- first_name: Donghyun
full_name: Kim, Donghyun
last_name: Kim
- first_name: R. N.
full_name: Uma, R. N.
last_name: Uma
- first_name: Alexander
full_name: Zelikovsky, Alexander
last_name: Zelikovsky
extern: '1'
keyword:
- flow
- Red-Blue Set Cover
- Positive-Negative Partial Set Cover
- approximation
- tree
- MAX SNP-hard
- root
- leaf
- dynamic programming
- FPT
language:
- iso: eng
page: 217-232
place: Cham
publication: Combinatorial Optimization and Applications
publication_identifier:
isbn:
- 978-3-030-04651-4
publisher: Springer International Publishing
status: public
title: Removing Undesirable Flows by Edge Deletion
type: conference
user_id: '83983'
year: '2018'
...
---
_id: '17666'
abstract:
- lang: eng
text: 'Software Defined Networks (SDN) and Network Function Virtualisation (NFV)
provide the basis for autonomous response and mitigation against attacks on networked
computer infrastructures. We propose a new framework that uses SDNs and NFV to
achieve this goal: Secure Autonomous Response Network (SARNET). In a SARNET, an
agent running a control loop constantly assesses the security state of the network
by means of observables. The agent reacts to and resolves security problems, while
learning from its previous decisions. Two main metrics govern the decision process
in a SARNET: impact and efficiency; these metrics can be used to compare and evaluate
countermeasures and are the building blocks for self-learning SARNETs that exhibit
autonomous response. In this paper we present the software implementation of the
SARNET framework, evaluate it in a real-life network and discuss the tradeoffs
between parameters used by the SARNET agent and the efficiency of its actions.'
author:
- first_name: R.
full_name: Koning, R.
last_name: Koning
- first_name: B.
full_name: de Graaff, B.
last_name: de Graaff
- first_name: Gleb
full_name: Polevoy, Gleb
id: '83983'
last_name: Polevoy
- first_name: R.
full_name: Meijer, R.
last_name: Meijer
- first_name: C.
full_name: de Laat, C.
last_name: de Laat
- first_name: P.
full_name: Grosso, P.
last_name: Grosso
citation:
ama: Koning R, de Graaff B, Polevoy G, Meijer R, de Laat C, Grosso P. Measuring
the efficiency of SDN mitigations against attacks on computer infrastructures.
Future Generation Computer Systems. 2018. doi:https://doi.org/10.1016/j.future.2018.08.011
apa: Koning, R., de Graaff, B., Polevoy, G., Meijer, R., de Laat, C., & Grosso,
P. (2018). Measuring the efficiency of SDN mitigations against attacks on computer
infrastructures. Future Generation Computer Systems. https://doi.org/10.1016/j.future.2018.08.011
bibtex: '@article{Koning_de Graaff_Polevoy_Meijer_de Laat_Grosso_2018, title={Measuring
the efficiency of SDN mitigations against attacks on computer infrastructures},
DOI={https://doi.org/10.1016/j.future.2018.08.011},
journal={Future Generation Computer Systems}, author={Koning, R. and de Graaff,
B. and Polevoy, Gleb and Meijer, R. and de Laat, C. and Grosso, P.}, year={2018}
}'
chicago: Koning, R., B. de Graaff, Gleb Polevoy, R. Meijer, C. de Laat, and P. Grosso.
“Measuring the Efficiency of SDN Mitigations against Attacks on Computer Infrastructures.”
Future Generation Computer Systems, 2018. https://doi.org/10.1016/j.future.2018.08.011.
ieee: R. Koning, B. de Graaff, G. Polevoy, R. Meijer, C. de Laat, and P. Grosso,
“Measuring the efficiency of SDN mitigations against attacks on computer infrastructures,”
Future Generation Computer Systems, 2018.
mla: Koning, R., et al. “Measuring the Efficiency of SDN Mitigations against Attacks
on Computer Infrastructures.” Future Generation Computer Systems, 2018,
doi:https://doi.org/10.1016/j.future.2018.08.011.
short: R. Koning, B. de Graaff, G. Polevoy, R. Meijer, C. de Laat, P. Grosso, Future
Generation Computer Systems (2018).
date_created: 2020-08-06T15:23:11Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
doi: https://doi.org/10.1016/j.future.2018.08.011
extern: '1'
keyword:
- Software defined networks
- Network function virtualization
- Cyber attacks
- Cyber security
- Defense efficiency
- Overlay networks
language:
- iso: eng
publication: Future Generation Computer Systems
publication_identifier:
issn:
- 0167-739X
status: public
title: Measuring the efficiency of SDN mitigations against attacks on computer infrastructures
type: journal_article
user_id: '83983'
year: '2018'
...