TY  - GEN
A1  - Bilo, Davide
A1  - Friedrich, Tobias
A1  - Lenzner, Pascal
A1  - Melnichenko, Anna
T1  - Geometric Network Creation Games
T2  - SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures
N2  - Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al. [PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.
KW  - Network creation games
KW  - edge-weighted networks
KW  - price of anarchy
KW  - Nash equilibrium
KW  - game dynamics
KW  - computational hardness
Y1  - 2019
SN  - 978-1-4503-6184-2
U6  - https://doi.org/10.1145/3323165.3323199
SP  - 323
EP  - 332
PB  - Association for Computing Machinery
CY  - New York
ER  - 
TY  - JOUR
A1  - Brückner, Michael
A1  - Kanzow, Christian
A1  - Scheffer, Tobias
T1  - Static prediction games for adversarial learning problems
JF  - Journal of machine learning research
N2  - The standard assumption of identically distributed training and test data is violated when the test data are generated in response to the presence of a predictive model. This becomes apparent, for example, in the context of email spam filtering. Here, email service providers employ spam filters, and spam senders engineer campaign templates to achieve a high rate of successful deliveries despite the filters. We model the interaction between the learner and the data generator as a static game in which the cost functions of the learner and the data generator are not necessarily antagonistic. We identify conditions under which this prediction game has a unique Nash equilibrium and derive algorithms that find the equilibrial prediction model. We derive two instances, the Nash logistic regression and the Nash support vector machine, and empirically explore their properties in a case study on email spam filtering.
KW  - static prediction games
KW  - adversarial classification
KW  - Nash equilibrium
Y1  - 2012
SN  - 1532-4435
VL  - 13
SP  - 2617
EP  - 2654
PB  - Microtome Publishing
CY  - Cambridge, Mass.
ER  -