Speaker:
Dennis Olivetti

Title:
Pareto and Nash stability in Social Distance Games

Abstract:

We consider Social Distance Games, that is coalition formation games in which agent utilities are proportional to their harmonic centralities in the respective coalitions. We investigate Social Distance Games using cooperative and non cooperative game theoretic concepts like Pareto and Nash Stability. In Nash stable outcomes, no agent can improve her utility by unilaterally changing her coalition. In Pareto stable outcomes, coalitions are stable under the deviation of the grand coalition, as they do not permit a simultaneous deviation by all the agents making all of them weakly better off and some strictly better off. First, we provide bounds on the price of anarchy, stability, and Pareto optimality. Then, we show that, while Social Distance Games always admit a Nash equilibrium, it is NP-hard to find a social welfare maximizing one. Finally, we show negative results concerning the game convergence.

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

For the season programme, please see the seminar webpage.