Invited Session Fri.3.MA 043

Friday, 15:15 - 16:45 h, Room: MA 043

Cluster 8: Game theory [...]

Analysis of equilibria in noncooperative games


Chair: Marc Uetz



Friday, 15:15 - 15:40 h, Room: MA 043, Talk 1

Martin Hoefer
Contribution games in networks

Coauthor: Elliot Anshelevich


Motivated by contribution scenarios in (social) networks, we analyze network contribution games in which each agent in a network has a budget of effort that he can contribute to different collaborative projects or relationships. Depending on the contribution of the involved agents a relationship will flourish or drown, and to measure success we use a reward function for each relationship. Every agent is trying to maximize the reward from all relationships that it is involved in. We consider pairwise equilibria of this game, and characterize the existence, computational complexity, and quality of equilibrium. Our results concern several natural classes of functions such as convex or concave rewards. We also discuss extensions towards altruistic behavior and different local reward sharing rules.



Friday, 15:45 - 16:10 h, Room: MA 043, Talk 2

Tobias Harks
Congestion games with variable demands

Coauthor: Max Klimm


We initiate the study of congestion games with variable
demands where the (variable) demand has to be assigned to exactly
one subset of resources. The players' incentives to use higher
demands are stimulated by non-decreasing and concave utility
functions. The payoff for a player is defined as the difference
between the utility of the demand and the associated cost
on the used resources. Although this class of non-cooperative
games captures many elements of real-world applications, it has not
been studied in this generality, to our knowledge, in the past.
We study the fundamental problem of the existence of pure Nash equilibria.
As our main result we give a complete characterizations of cost functions
that ensure the existence of at least one pure Nash equilibrium.



Friday, 16:15 - 16:40 h, Room: MA 043, Talk 3

Jasper de Jong
Decentralized mechanisms for throughput scheduling


Motivated by the organization of decentralized service systems, we study new models for throughput scheduling. In throughput scheduling, we have a set of jobs i with value wi, processing requirement pi, and deadline di, to be processed non-preemptively on a set of unrelated servers. The goal is to maximize the total value of jobs finished before their deadline. While several approximation algorithms with different performance guarantees exist for this and related models, we are interested in decentralized mechanisms where the servers act selfishly according to some given, simple protocol. We show by simple, combinatorial arguments that, when each server deploys an α-approximation locally, any Nash equilibrium still yields an (α+1)-approximation with respect to the global optimum. This bound is tight, even in the case of related machines, unit weights and unit processing times. For models with identical machines, the bound can be improved to \frac{\sqrt[α]{e}}{\sqrt[α]{e}-1}. Some of our results also extend to online models with corresponding competitive ratios.


  There are three major facts that should be watched out for in all payday loans in the United States. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.