On bipartite sum basic equilibria
| Autor: | Arnau Messegué, Carme Àlvarez |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Network creation game
Grafs Teoria de TheoryofComputation_GENERAL Binary logarithm Upper and lower bounds Nash equilibrium Combinatorics Graph theory symbols.namesake Sum basic Informàtica::Informàtica teòrica [Àrees temàtiques de la UPC] Diameter Bipartite graph symbols Algorithmic game theory Jocs Teoria de Undirected graph Game theory MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Trends in Mathematics ISBN: 9783030838225 UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| Popis: | A connected and undirected graph G of size n≥1 is said to be a sum basic equilibrium iff for every edge uv from G and any node v′ from G, when performing the swap of the edge uv for the edge uv′ the sum of the distances from u to all the other nodes is not strictly reduced. This concept comes from the so called Network Creation Games, a wide subject inside Algorithmic Game Theory that tries to better understand how Internet-like networks behave. It has been shown that the diameter of sum basic equilibria is 2O(logn√) in general and at most 2 for trees. In this paper we see that the upper bound of 2 not only holds for trees but for bipartite graphs, too. Specifically, we show that the only bipartite sum basic equilibrium networks are the complete bipartite graphs Kr,s with r,s≥1 . This work has been partially supported by funds from the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R) and from the Catalan Agency for Management of University and Research Grants (AGAUR, Generalitat de Catalunya) under project ALBCOM 2017-SGR-786. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|