Congestion Games with Complementarities

Matthias Feldotto, Lennart Leder, Alexander Skopalik

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    Abstract

    We study a model of selfish resource allocation that seeks to incorporate dependencies among resources as they exist in modern networked environments. Our model is inspired by utility functions with constant elasticity of substitution (CES) which is a well-studied model in economics. We consider congestion games with different aggregation functions. In particular, we study Lp norms and analyze the existence and complexity of (approximate) pure Nash equilibria. Additionally, we give an almost tight characterization based on monotonicity properties to describe the set of aggregation functions that guarantee the existence of pure Nash equilibria.
    Original languageEnglish
    Title of host publicationAlgorithms and Complexity
    Subtitle of host publication10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings
    EditorsDimitris Fotakis, Aris Pagourtzis
    Pages222-233
    ISBN (Electronic)978-3-319-57586-5
    DOIs
    Publication statusPublished - 2017
    Event10th International Conference on Algorithms and Complexity - Multimedia Amphitheater of the National Technical University of Athens, Athens, Greece
    Duration: 24 May 201726 May 2017
    Conference number: 10
    http://www.corelab.ntua.gr/ciac2017/

    Publication series

    NameLecture Notes in Computer Science
    Volume10236

    Conference

    Conference10th International Conference on Algorithms and Complexity
    Abbreviated titleCIAC 2017
    CountryGreece
    CityAthens
    Period24/05/1726/05/17
    Internet address

    Keywords

    • Congestion games
    • Aggregation
    • L-p norms
    • Complementarities
    • Existence of equilibria
    • Approximate pure Nash equilibria

    Cite this