TY - CONF
AU - Hamann, Heiko
AU - Schmickl, Thomas
AU - Kengyel, Daniela
AU - Zahadat, Payam
AU - Radspieler, Gerald
AU - Wotawa, Franz
ID - 19991
T2 - Principles and Practice of Multi-Agent Systems (PRIMA 2015)
TI - Potential of Heterogeneity in Collective Behaviors: A Case Study on Heterogeneous Swarms
ER -
TY - JOUR
AU - Valentini, Gabriele
AU - Hamann, Heiko
ID - 19992
JF - Swarm Intelligence
SN - 1935-3812
TI - Time-variant feedback processes in collective decision-making systems: influence and effect of dynamic neighborhood sizes
ER -
TY - CONF
AU - Dorigo, Marco
AU - Hamann, Heiko
AU - Valentini, Gabriele
ID - 20005
T2 - Proceedings of the 14th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2015)
TI - Efficient Decision-Making in a Self-Organizing Robot Swarm: On the Speed Versus Accuracy Trade-Off
ER -
TY - CONF
AU - Dorigo, Marco
AU - Hamann, Heiko
AU - Valentini, Gabriele
ID - 20006
T2 - AAAI-15 Video Proceedings
TI - Self-organized collective decisions in a robot swarm
ER -
TY - CONF
AB - Many markets have seen a shift from the idea of buying and moved to leasing instead. Arguably, the latter has been the major catalyst for their success. Ten years ago, research realized this shift and initiated the study of "online leasing problems" by introducing leasing to online optimization problems. Resources required to provide a service in an "online leasing problem" are no more bought but leased for different durations. In this paper, we provide an overview of results that contribute to the understanding of "online resource leasing problems".
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
ID - 266
T2 - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC)
TI - Online Resource Leasing
ER -
TY - THES
AU - Markarian, Christine
ID - 267
TI - Online Resource Leasing
ER -
TY - JOUR
AB - We consider structural and algorithmic questions related to the Nash dynamics of weighted congestion games. In weighted congestion games with linear latency functions, the existence of pure Nash equilibria is guaranteed by a potential function argument. Unfortunately, this proof of existence is inefficient and computing pure Nash equilibria in such games is a PLS-hard problem even when all players have unit weights. The situation gets worse when superlinear (e.g., quadratic) latency functions come into play; in this case, the Nash dynamics of the game may contain cycles and pure Nash equilibria may not even exist. Given these obstacles, we consider approximate pure Nash equilibria as alternative solution concepts. A ρ--approximate pure Nash equilibrium is a state of a (weighted congestion) game from which no player has any incentive to deviate in order to improve her cost by a multiplicative factor higher than ρ. Do such equilibria exist for small values of ρ? And if so, can we compute them efficiently?We provide positive answers to both questions for weighted congestion games with polynomial latency functions by exploiting an “approximation” of such games by a new class of potential games that we call Ψ-games. This allows us to show that these games have d!-approximate pure Nash equilibria, where d is the maximum degree of the latency functions. Our main technical contribution is an efficient algorithm for computing O(1)-approximate pure Nash equilibria when d is a constant. For games with linear latency functions, the approximation guarantee is 3+√5/2 + Oγ for arbitrarily small γ > 0; for latency functions with maximum degree d≥ 2, it is d2d+o(d). The running time is polynomial in the number of bits in the representation of the game and 1/γ. As a byproduct of our techniques, we also show the following interesting structural statement for weighted congestion games with polynomial latency functions of maximum degree d ≥ 2: polynomially-long sequences of best-response moves from any initial state to a dO(d2)-approximate pure Nash equilibrium exist and can be efficiently identified in such games as long as d is a constant.To the best of our knowledge, these are the first positive algorithmic results for approximate pure Nash equilibria in weighted congestion games. Our techniques significantly extend our recent work on unweighted congestion games through the use of Ψ-games. The concept of approximating nonpotential games by potential ones is interesting in itself and might have further applications.
AU - Caragiannis, Ioannis
AU - Fanelli, Angelo
AU - Gravin, Nick
AU - Skopalik, Alexander
ID - 320
IS - 1
JF - Transactions on Economics and Computation
TI - Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure
VL - 3
ER -
TY - GEN
AU - Pautz, Jannis
ID - 316
TI - Budget Games with priced strategies
ER -
TY - THES
AU - Jähn, Claudius
ID - 317
TI - Bewertung von Renderingalgorithmen für komplexe 3-D-Szenen
ER -
TY - THES
AU - Abshoff, Sebastian
ID - 270
TI - On the Complexity of Fundamental Problems in Dynamic Ad-hoc Networks
ER -