Technion, IEM faculty - E-Commerce Research seminar

Speaker: Amitabh Trehan
Title: Composition Games for Distributed Systems: the EU Grant games
Date: 15/01/2012
Time: 10:30
Place: Bloomfield-527
Abstract:  <>

Or read it here:
A traditional distributed system is often designed by some central
manufacturer and owned by some central owner. However, increasingly,
more modern distributed systems are composed of components, each owned
by a different owner. Moreover, such systems are formed rather
distributively, by people teaming up to pool their resources together.
For example, many Peer to Peer (P2P) networks are composed of nodes
belonging to different persons, who would like to gain by the
cooperation. In this paper, we consider ways by which people make
distributed decisions regarding this composition of such systems,
attempting to realize high values. We initiate the evaluation of those
ways, by the quality of the resulting systems. We concentrate on
settings in which a node can increase its utility by connecting to other
nodes. However, the node must also pay a cost that increases with the
size of the system. The right balance is achieved by the right size
group of nodes. We address this issue using game theory, and refer to
games in such settings as European Union grant games. For such a game,
we study its price of anarchy (and also the strong price of anarchy) --
the ratio between the average (over the system's components) value of
the optimal possible system, and the average value for the system formed
in the worst equilibrium. We formulate and analyze three intuitive games
and show how simple changes in the protocol can improve the price of
anarchy drastically. In particular, we identify two important properties
for a low price of anarchy: agreement in joining the system, and the
possibility of appealing a rejection from a system. We show that the
latter property is especially important if there are some pre-existing
constraints regarding who may collaborate (or communicate) with whom.
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from:  <>