Abstract Network creation spel modell skapande och användningskostnader för nätverk som bildas av n själviska noder. Varje nod v kan köpa en uppsättning kanter, var och en för ett fast pris α > 0. Dess mål är att minimera sina privata kostnader, dvs. summan (SUM-game, Fabrikant et al., PODC 2003) eller max (MAXgame, Demaine et al., PODC 2007) av avstånd från v till alla andra noder plus priserna på köpta kanter. Ovanstående artiklar visar förekomsten av Nash equilibria samt övre och nedre gränser för priserna på anarki och stabilitet. I flera efterföljande dokument förbättrades dessa gränser för ett brett prisintervall. I detta dokument utvidgar vi dessa modeller genom att inkludera servicekvalitetsaspekter: Varje kant kan inte bara köpas till en fast kvalitet (den ena kantlängden) till ett fast pris α. I stället antar vi att kvalitetsnivåer (dvs. kantlängder) varierar i ett fast intervall [β,β], 0 <β ≤β. En nod kan nu inte bara välja vilken kant att köpa, men kan också välja sin kvalitet x, för priset p(x), för en given prisfunktion p. För både spel och alla prisfunktioner, visar vi att Nash Equilibria finns och att priset på stabilitet är antingen konstant eller beror endast på intervallet storlek tillgängliga kant längder. Våra huvudsakliga resultat är begränsade till priset av anarki. Vid SUM-spelet visar vi att de är tighta om prisfunktionerna sjunker tillräckligt snabbt.
I modellen av Cord-Landwehr et al. REF-agenter kan välja olika kvalitetsnivåer av en kant för olika priser, dvs. det betalda priset påverkar kantlängden.
Quality of Service in Network Creation Games
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Economics', 'Computer Science']}