Israel CS THEORY DAY

Open University of Israel

Division of Computer Science

Date: 17.3.08

Speaker: Eva Tardos

Title: Bargaining and Trading in Networks.

Abstract:

Network games play a fundamental role in understanding behavior in many domains, ranging from communication networks through markets, to social networks. In this talk, we will consider bargaining and trading in a network setting, where a set of agents have the opportunity to choose whom they want to bargain or trade with, along the edges of a graph representing social-network relations or trade routes. In the bargaining context, we analyze a model arising in network exchange theory, which can be viewed as a direct extension of the well-known Nash bargaining solution for two player games. This model is known to be surprisingly effective at picking up even subtle differences in bargaining power that have been observed experimentally on small examples, but it has remained an open question to characterize the values taken by this solution on general graphs, or to find an efficient means to compute it. In the trading context, we consider a model with traders, where traders set prices strategically, and then buyers and sellers react to the prices they are offered. We characterize the outcomes in both models, thus providing graph-theoretic basis for quantifying the players’ relative amounts of power in the network. We also show that the outcomes are socially optimal and can be computed in polynomial time. Joint work with Jon Kleinberg, Larry Blume, and David Easley.