Förhandlingsnätverk modellerar sociala eller ekonomiska situationer där agenter försöker bilda det mest lukrativa partnerskapet med en annan agent bland flera alternativ. Det har varit en uppsjö av ny forskning som studerar Nash förhandlingslösningar (även kallade "balanserade resultat") i förhandlingsnätverk, så att vi nu vet när sådana lösningar finns, och även att de kan beräknas effektivt, även av marknadsagenter beter sig på ett naturligt sätt. I detta arbete studerar vi en generalisering av Nash-förhandlingarna, som modellerar möjligheten till ojämlika "förhandlingskrafter". Denna generalisering infördes i [KB+10], där det visades att motsvarande "ojämlik uppdelning" (UD) lösningar existerar om och endast om Nash förhandlingslösningar finns, och även att en viss lokal dynamik konvergerar till UD-lösningar när de existerar. Den gräns på konvergenstiden som uppnåtts för denna dynamik var emellertid exponentiell i nätstorlek för det ojämlika uppdelningsfallet. Denna gräns är snäv, i den meningen att det finns fall där dynamiken i [KB+10] konvergerar först efter exponentiell tid. Andra metoder, såsom Kleinberg och Tardos, generaliserar inte till det osymmetriska fallet. Därför har frågan om beräkningsförmåga för UD-lösningar förblivit öppen. I detta dokument tillhandahåller vi ett FPTAS för beräkning av UD-lösningar, när sådana lösningar finns. På en graf G = (V, E) med vikter (dvs. parvis vinstchanser) jämnt avgränsad ovan av 1, vår FPTAS finner en  till-UD lösning i tid poly( och V, 1/ på). Vi tillhandahåller också en snabb lokal algoritm för att hitta en lösning som ger ytterligare motivering för att en marknad kan hitta en sådan lösning.
I ett parallellt arbete av en av oss REF visas det att den naturliga dynamiken kan ta exponentiellt lång tid att konvergera när det gäller ojämlika förhandlingsbefogenheter.
An FPTAS for Bargaining Networks with Unequal Bargaining Powers
{'venue': 'Lecture Notes in Computer Science 6484 Springer (2010) 282-293', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}