Studiet av förhandlingar har en lång historia, men många grundläggande miljöer är fortfarande rika på olösta frågor. Överväg i synnerhet en uppsättning agenter som förhandlar med varandra, men i stället för par av agenter som interagerar isolerat, har agenter möjlighet att välja vem de vill förhandla med, längs kanten av en graf som representerar relationer mellan sociala nätverk. Området nätverksutbytesteori inom sociologi har utvecklat en stor mängd experimentella bevis för hur människor beter sig i sådana nätverksbundna förhandlingssituationer, och det är ett utmanande problem att utveckla modeller som är både matematiskt lätthanterliga och i allmänhet överens med resultaten av dessa experiment. Vi analyserar en naturlig teoretisk modell som uppstår i nätverk utbyte teori, som kan ses som en direkt förlängning av den välkända Nash förhandlingslösning till fallet med flera agenter interagerar på en graf. Även om denna generaliserade Nash förhandlingslösning är förvånansvärt effektiv på att plocka upp även subtila skillnader i förhandlingsmakt som har observerats experimentellt på små exempel, har det förblivit en öppen fråga att karakterisera de värden som tas av denna lösning på allmänna grafer, eller att hitta ett effektivt sätt att beräkna det. Här löser vi dessa frågor, karakteriserar de möjliga värdena i denna förhandlingslösning, och ger en effektiv algoritm för att beräkna uppsättningen möjliga värden. Vårt resultat utnyttjar kopplingar till strukturen för matchningar i grafer, inklusive nedbrytningsteorem för grafer med perfekta matchningar, och innebär också utveckling av nya tekniker. I synnerhet de värden vi söker visar sig motsvara en ny kombinatoriskt definierad punkt i det inre av en bråkdels avkoppling av det matchande problemet.
Dessutom kan vi behandla det mer allmänna fallet med noder med osymmetriska förhandlingsbefogenheter och generalisera resultatet av REF om förekomsten av NB-lösningar i detta sammanhang.
Balanced outcomes in social exchange networks
{'venue': "STOC '08", 'journal': None, 'mag_field_of_study': ['Computer Science']}