Dissertation:
Cost sharing and clustering under distributed competition

No Thumbnail Available
Date
2007
Editors
Hoefer, Martin
relationships.isEditorOf
Contact
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
DOI (citable link)
ArXiv-ID
International patent number
Link to the license
Project
EU project number
Open Access publication
Restricted until
Title in another language
Kostenaufteilung und Graphenclustering bei verteiltem Wettbewerb
Research Projects
Organizational Units
Journal Issue
Publication type
Dissertation
Publication status
Abstract
In dieser Arbeit werden zwei grundlegende Modelle für nicht-kooperative Spiele vorgestellt, mit denen sich verteilt geplante Netzwerke analysieren lassen. Das Ziel ist ein verbessertes Verständnis der Konflikte und Dynamiken, die durch wirtschaftliche Interessen und Einflüsse sozialer Netzwerke auf Entscheidungen von Akteuren entstehen. Aspekte wie Existenz, Berechenbarkeit und soziale Güte stabiler Zustände wie reiner und approximativer Nash Gleichgewichte stehen bei der Analyse der Modelle im Vordergrund.

Im ersten Teil der Arbeit werden Spiele betrachtet, in denen Spieler eine Menge von Rohstoffeinheiten kaufen und deren Kosten aufteilen müssen. Jeder Spieler hat eine bestimmte Anforderung an die Art und Menge der gekauften Einheiten. Die Spieler können Beiträge für den Kauf von Rohstoffen anbieten. Eine Einheit gilt als gekauft wenn der Gesamtbeitrag aller Spieler ihre Kosten übersteigt. Ein Spieler möchte seine Anforderung mit möglichst geringem eigenen Kostenbeitrag erfüllen. Dieser abstrake Ansatz wird auf mehrere Probleme aus dem Bereich Service Installation, Facility Location und Netzwerkdesign angewendet. Daraus entstehen einfache Modelle für fundamentale Fragestellungen im Internet. Generell gibt es schon für sehr kleine Instanzen der Spiele keine oder nur sehr teuere reine Nash Gleichgewichte. Dagegen gibt es für einige Teilklassen der Spiele approximative Nash Gleichgewichte mit kleinen konstanten Gütegarantien. Diese Zustände können auch effizient berechnet werden. In den Algorithmen werden bestehende Techniken aus der linearen Optimierung sowie neue kombinatorische Ansätze verwendet.

Im zweiten Teil der Arbeit wird Clustering von Graphen spieltheoretisch untersucht. Jeder Spieler ist ein Knoten im Graph und entscheidet, welchem von mehreren möglichen Clustern er angehört. Der Wert einer Entscheidung für den Spieler hängt dabei von der Entscheidung der anderen Spieler und der Struktur des Netzwerkes ab. Die betrachteten Spiele sind Polymatrix- und Potenzialspiele, in denen die Bewertungen eines Zustands bekannte Indizes für Clusterings nachbilden. Der Schwerpunkt der Analyse liegt auf der Dauer von better-response Dynamiken und der Berechenbarkeit von guten Nash Gleichgewichten und sozial optimalen Zuständen. Zuerst werden Spiele untersucht, die sich aus zwei Teilspielen zusammensetzen, einem für verbundene und einem für nicht verbundene Spieler. Für eine Klasse von Spielen mit 2 Strategien können das beste Nash Gleichgewicht und sozial optimale Zustände einfach charakterisiert und effizient berechnet werden. Danach werden Spiele auf Basis des populären Index Modularity betrachtet. Das Hauptresultat ist ein Beweis der NP-Härte für das Finden des besten Nash Gleichgewichts und des sozial optimalen Zustands. Dies liefert die ersten grundlegenden theoretischen Einsichten in die Modularity-Optimierung und bestätigt eine zuvor in der Literatur formulierte Vermutung über den Komplexitätsstatus.
Summary in another language
In this thesis we consider two fundamental models for non-cooperative games to analyze networks created and operated by distributed selfish agents. The goal is to advance the understanding of dynamics and trade-offs that are created by selfish incentives and influences of social networks on decision making. Our analyses concentrate on existence, complexity, and social value of stable states like exact and approximate Nash equilibria.

The first part of the thesis deals with a class of games in which players must share the cost a set of resource units. Every player has a constraint on the type and number of units that should be bought. Players can offer payments for the purchase of resource units. If the total sum of payments offered by the players exceeds the cost, a unit is considered bought. Every player strives to satisfy his constraint using the smallest possible investment. Within this abstract framework several problems addressing aspects like service installation, facility location, or network design are considered as a game. In general, exact Nash equilibria do not exist or can be very expensive, even for small instances of the games. However, for some subclasses of games there are approximate Nash equilibria with small constant approximation ratios. In addition, these states can be computed using efficient algorithms composed of existing linear programming techniques as well as new combinatorial approaches.

The second part of the thesis concentrates on game-theoretic models for graph clustering. Every player is a vertex in a graph and decides to which of several possible clusters he belongs. The value of this decision depends on the decisions of other players and the structure of the graph. The games considered are polymatrix and potential games, in which social welfare is equivalent to well-known clustering indices for graphs. The analysis concentrates on the length of best-reponse paths and the computation of best Nash equilibria and social optimum states. In the first model, games are composed of two smaller games, one for connected players and one for unconnected players. In a special class of games with 2 strategies, the best Nash equilibrium and the social optimum state can be computed efficiently. Then, the approach is used to formulate games based on the popular index "modularity". The main result is a proof of NP-hardness for the problem of finding the best Nash equilibrium and the social optimum state. This provides the first fundamental insights into modularity optimization and corroborates a conjecture about the complexity, which was previously formulated in the literature.
Subject (DDC)
004 Computer Science
Keywords
Cost Sharing , Non-cooperative Games
Published in
Conference
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690HOEFER, Martin, 2007. Cost sharing and clustering under distributed competition [Dissertation]. Konstanz: University of Konstanz
BibTex
@phdthesis{Hoefer2007shari-6000,
  year={2007},
  title={Cost sharing and clustering under distributed competition},
  author={Hoefer, Martin},
  address={Konstanz},
  school={Universität Konstanz}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/6000">
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Hoefer, Martin</dc:contributor>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:08:40Z</dc:date>
    <dcterms:issued>2007</dcterms:issued>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6000/1/Cost_sharing_and_clustering_under_distributed_competition.pdf"/>
    <dc:format>application/pdf</dc:format>
    <dc:language>eng</dc:language>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:08:40Z</dcterms:available>
    <dc:creator>Hoefer, Martin</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6000/1/Cost_sharing_and_clustering_under_distributed_competition.pdf"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6000"/>
    <dcterms:alternative>Kostenaufteilung und Graphenclustering bei verteiltem Wettbewerb</dcterms:alternative>
    <dcterms:title>Cost sharing and clustering under distributed competition</dcterms:title>
    <dcterms:abstract xml:lang="deu">In dieser Arbeit werden zwei grundlegende Modelle für nicht-kooperative Spiele vorgestellt, mit denen sich verteilt geplante Netzwerke analysieren lassen. Das Ziel ist ein verbessertes Verständnis der Konflikte und Dynamiken, die durch wirtschaftliche Interessen und Einflüsse sozialer Netzwerke auf Entscheidungen von Akteuren entstehen. Aspekte wie Existenz, Berechenbarkeit und soziale Güte stabiler Zustände wie reiner und approximativer Nash Gleichgewichte stehen bei der Analyse der Modelle im Vordergrund.&lt;br /&gt;&lt;br /&gt;Im ersten Teil der Arbeit werden Spiele betrachtet, in denen Spieler eine Menge von Rohstoffeinheiten kaufen und deren Kosten aufteilen müssen. Jeder Spieler hat eine bestimmte Anforderung an die Art und Menge der gekauften Einheiten. Die Spieler können Beiträge für den Kauf von Rohstoffen anbieten. Eine Einheit gilt als gekauft wenn der Gesamtbeitrag aller Spieler ihre Kosten übersteigt. Ein Spieler möchte seine Anforderung mit möglichst geringem eigenen Kostenbeitrag erfüllen. Dieser abstrake Ansatz wird auf mehrere Probleme aus dem Bereich Service Installation, Facility Location und Netzwerkdesign angewendet. Daraus entstehen einfache Modelle für fundamentale Fragestellungen im Internet. Generell gibt es schon für sehr kleine Instanzen der Spiele keine oder nur sehr teuere reine Nash Gleichgewichte. Dagegen gibt es für einige Teilklassen der Spiele approximative Nash Gleichgewichte mit kleinen konstanten Gütegarantien. Diese Zustände können auch effizient berechnet werden. In den Algorithmen werden bestehende Techniken aus der linearen Optimierung sowie neue kombinatorische Ansätze verwendet.&lt;br /&gt;&lt;br /&gt;Im zweiten Teil der Arbeit wird Clustering von Graphen spieltheoretisch untersucht. Jeder Spieler ist ein Knoten im Graph und entscheidet, welchem von mehreren möglichen Clustern er angehört. Der Wert einer Entscheidung für den Spieler hängt dabei von der Entscheidung der anderen Spieler und der Struktur des Netzwerkes ab. Die betrachteten Spiele sind Polymatrix- und Potenzialspiele, in denen die Bewertungen eines Zustands bekannte Indizes für Clusterings nachbilden. Der Schwerpunkt der Analyse liegt auf der Dauer von better-response Dynamiken und der Berechenbarkeit von guten Nash Gleichgewichten und sozial optimalen Zuständen. Zuerst werden Spiele untersucht, die sich aus zwei Teilspielen zusammensetzen, einem für verbundene und einem für nicht verbundene Spieler. Für eine Klasse von Spielen mit 2 Strategien können das beste Nash Gleichgewicht und sozial optimale Zustände einfach charakterisiert und effizient berechnet werden. Danach werden Spiele auf Basis des populären Index Modularity betrachtet. Das Hauptresultat ist ein Beweis der NP-Härte für das Finden des besten Nash Gleichgewichts und des sozial optimalen Zustands. Dies liefert die ersten grundlegenden theoretischen Einsichten in die Modularity-Optimierung und bestätigt eine zuvor in der Literatur formulierte Vermutung über den Komplexitätsstatus.</dcterms:abstract>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
  </rdf:Description>
</rdf:RDF>
Internal note
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Contact
URL of original publication
Test date of URL
Examination date of dissertation
September 20, 2007
Method of financing
Comment on publication
Alliance license
Corresponding Authors der Uni Konstanz vorhanden
International Co-Authors
Bibliography of Konstanz
Refereed
Link to research data
Description of supplementary data