Monday, November 25, 2013

Networks, Crowds, and Markets Review: Parts I-IV


Full Book Text Available Here

Parts I-IV of this text cover graphs and networks, game theory, markets and auctions, and touch on information networks, search techniques, and advertising markets.

This book was interesting in that it introduced me to some new ideas, bordering on concepts I was familiar with, with a very basic level of mathematical understanding required.  I'm familiar with graphs from an algorithms point-of-view, so the sociological viewpoint in Part I was fresh to me, even though the material was not too advanced.  I had also never been exposed to the ideas in game theory or evolutionary game theory, so I thought they were valuable fresh conceptual tools.

Part I introduced a number of sociological concepts in networks to me.  Homophily is the tendency to befriend, bond with, and be associated with, people similar to yourself.  Triadic closure is the idea that 'triangular' relationships between 3 people are likely; if people A and B have bonds to a common C, it is likely that A and B will be associated.  Triadic closure can be extended by adding a notion of tie strength.  The Strong Triadic Closure property says that if A and B have strong ties to a common C, A and B are almost certainly associated.

An interesting global property that falls out of this local one is that 'local bridge' connections between cliques in networks are usually weak ties, because otherwise the Strong Triadic Closure property would mean that more people in the clique would be associated, and the bridge would no longer be a bridge.  The common-life corollary to this is that new job offers and opportunities often come from weak associations.

Structural balance is another (somewhat dangerous/unfortunate) idea that adds support and antagonism to networks, 'signing' them.  All edges between nodes in the network are labeled either with + for positive or supportive relationships or - for opposing, antagonistic relationships.  Structure balance looks at triangles of edges between nodes and says that +,+,+ triangles and +,-,- triangles are 'stable'.  +,+,- is unstable because it corresponds to the situation in which 2 mutual friends of a third-party dislike each other.  The third-party will pressure his friends to get past their grievances because it stresses the relationships.  -,-,- is unstable because the incentives are strong for 2 nodes in the triangle to 'team up' against the third.

Structure balance then states that global network properties occur if these structural balance properties hold locally.  In particular, if the network is fully-connected and all nodes have a positive/negative relationship with every other node, and the structural balance properties hold everywhere, the network will be divided into 2 opposing camps.  This can be applied towards explaining some of the vexing consequences of alliances in international relations.  The authors also generalize this in 2 dimensions, by removing the requirement that the graph be fully-connected and removing the requirement that the structure balance property hold locally everywhere.

The chapters on game theory were also useful to me, especially in terms of understanding how rational behavior can lead to socially stupid outcomes.  I feel like I have a better eye for incentives now, how they drive behavior, and how they could be adjusted for better overall outcomes.  The section on auctions was particularly helpful for the later sections on markets in a network context; the book built well off its foundational concepts there.

A book I am considering as a follow-on to Networks, Crowds, and Markets is Algorithmic Game Theory [http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf], which includes sections on mechanism design; the design of markets, auctions, and other mechanisms that try to make rational behavior of individual actors work for the social goals.  This book also has chapters on reputation systems, peer-to-peer systems, routing and allocation and prediction markets.

Parts III and IV are less foundational, and more focused on applying the earlier ideas in network contexts.  I'm not sure many of these ideas will be code-applicable for me yet, but I would feel more confident reasoning about the behavior of entities like Amazon, Google, and SaaS companies. After reading this I'd be in interested in looking at algorithms for determining prices and matchings, like balanced outcomes in the surplus-splitting game, or VCG prices for multi-buyer, multi-seller options, and how one would prove properties like balance, stability, and equilibria.  I'd be especially interested in algorithms over larger, non-trivial networks, results that take information asymmetry more into account.  Algorithmic Game Theory may address some of the former, and the later parts of Networks, Crowds and Markets the latter.

I'm not sure I'd recommend this book yet overall, the conceptual punch per page quotient doesn't seem too high.  The initial chapters make good expositions to networks and game theory in their own right.  I'll report up on final thoughts and the later parts of the book once I finish them.