Vi fortsätter att studera effekterna av själviskt beteende i problemet med nätverksdesign. Vi tillhandahåller nya gränser för priset på stabilitet för nätdesign med rättvis kostnadsfördelning för oriktade grafer. Vi anser att det mest allmänna fallet, för vilket den mest kända övre gränsen är Harmonic nummer H n, där n är antalet agenter, och den mest kända nedre gränsen är 12/7  och 1.778. Vi presenterar en icke-trivial nedre gräns på 42/23  och 1.8261. Dessutom visar vi att för två spelare är priset på stabilitet exakt 4/3, medan för tre spelare är det minst 74/48  på 1.542 och högst 1.65. Detta är de första förbättringarna på gränsen till H n för allmänna nät. I synnerhet visar detta en åtskillnad mellan priset på stabilitet på oriktade grafer och priset på riktade grafer, där H n är tight. Tidigare var en sådan lucka bara känd för de fall där alla spelare har en delad källa, och för vägda spelare.
REF visar övre gränser på 1,65 respektive 4/3 för två respektive tre spelare.
On the price of stability for undirected network design. WAOA
{'venue': 'Lecture Notes in Computer Science', 'journal': 'Lecture Notes in Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}