Networks, Crowds, and Markets Exam Study Guide

High-yield vocabulary flashcards covering graph theory, network structure, game theory, and market mechanisms from the Networks, Crowds, and Markets exam study guide.

Simple Undirected Graph

nodes and undirected edges with no self-loops and at most one edge per pair

Handshaking Lemma

sum of all node degrees equals twice the number of edges

Giant Connected Component

connected component containing a significant fraction of all network nodes

Bridge

edge whose removal increases the number of connected components

Local Bridge

edge whose endpoints have no friends in common and whose deletion increases distance past two

Strong Triadic Closure Property

rule requiring a tie between two neighbors when a node has strong ties to both

Structural Balance

property of a signed complete graph where every triangle has one or three positive edges

The Balance Theorem

principle stating a balanced complete network is all positive or divided into two friendly factions with negative edges between them

Bipartite Graph

graph whose nodes split into two disjoint sets with all edges connecting across sets

Strongly Connected Component

maximal subset of directed graph nodes where every node reaches every other via directed paths

The Bow-Tie Structure of the Web

macro structure consisting of the giant SCC, IN, OUT, and disconnected components

Strictly Dominated Strategy

strategy yielding a strictly lower payoff than another regardless of the opponent's choice

Pure-Strategy Nash Equilibrium

strategy profile where no player has an incentive to unilaterally deviate

Pareto Optimality

social efficiency where no player can be made better off without harming another

Mixed Strategy

probability distribution over available pure strategies

Indifference Principle

rule in mixed equilibria stating mixed pure strategies yield identical expected payoffs

Braess's Paradox

phenomenon where adding a new road to a network increases total equilibrium travel time

The Matching Theorem

rule stating a perfect matching exists if and only if no constricted set exists

Market-Clearing Prices

prices where the preferred-seller graph contains a perfect matching for buyers

Weakly Dominant Strategy

bidding one's true valuation in second-price auctions

Winner's Curse

common-value auction phenomenon where the winner is the bidder who most grossly overestimated value

Balanced Outcome in Exchange Networks

stable exchange network outcome with equal gains relative to network outside options