UNIVERSITY COLLEGE LONDON
DEPARTMENT OF ECONOMICS
Economics BSc (Econ)
Third Year – Term 2
NETWORK SCIENCE FOR
ECONOMISTS
ECON0123
Rodrigo Antón García
rodrigo.garcia.20@ucl.ac.uk
London, 2023
,
, Contents
Topic 1 – Overview and Basics of Graph Theory.
o Topic 1.1 – Introduction to Networks. 1
o Topic 1.2 – Formal Definitions. 4
Topic 2 – Optimization on Network and Congestion Games.
o Topic 2.1 – The Transportation Problem. 9
o Topic 2.2 – The Assignment Problem. 10
o Topic 2.3 – The Shortest Path Problem. 11
o Topic 2.4 – The Minimum Spanning Problem. 15
o Topic 2.5 – The Maximum Flow Problem. 16
o Topic 2.6 – Congestion Games. 19
Topic 3 – Auctions and Sponsored Search Auctions.
o Topic 3.1 – General Auction Theory. 26
o Topic 3.2 – Auctions with Complete Information. 27
o Topic 3.3 – Auctions with Incomplete Information. 29
o Topic 3.4 – The SIPV Environment and Revenue Maximization. 32
o Topic 3.5 – Sponsored Search Auctions and Matching Markets. 33
o Topic 3.6 – The VCG Mechanism and The Generalized SP Auction. 36
o Topic 3.7 – Multi-unit Auctions: Discriminatory, Uniform and Vickrey. 39
Topic 4 – Marriage Markets and Assignments.
o Topic 4.1 – Basic Matching: The Two-Sided One-to-One Matching Model.41
o Topic 4.2 – Medical Matching: The Many-to-One Matching Model. 48
o Topic 4.3 – Assignment Problems: One-to-One Priority Model. 51
Topic 5 – Matching Markets and Trading Networks.
o Topic 5.1 – Matching Markets: Direct Trade. 54
o Topic 5.2 – Matching Markets with Intermediaries: Trading Networks. 62
,Topic 6 – Network Effects.
o Topic 6.1 – Introducing Network Effects: Equilibria and Dynamics. 70
o Topic 6.2 – Populations and Industries with Network Effects. 73
o Topic 6.3 – The Economic Theory in Network Effects. 76
Topic 7 – Cascades and Epidemics.
o Topic 7.1 – Diffusion in Networks and Modelling Diffusion. 80
o Topic 7.2 – Cascading and Clusters. 81
o Topic 7.3 – Weak Ties, Thresholds, Knowledge and Collective Action. 82
o Topic 7.4 – Cascade Capacity. 84
o Topic 7.5 – Epidemics and Branching Process. 85
o Topic 7.6 – The SIR Model, SIS Model and SIRS Model. 88
o Topic 7.7 – Transient Contacts and the Dangers of Concurrency. 92
Topic 8 – Markets with Network Goods.
o Topic 8.1 – Network Effects. 93
o Topic 8.2 – Markets for a Single Network Good. 94
o Topic 8.3 – Markets for Several Network Goods. 99
Topic 9 – Strategies for Network Goods.
o Topic 9.1 – Choosing How to Compete. 106
o Topic 9.2 – Strategies in Standard Wars. 110
o Topic 9.3 – Public Policy in Network Markets. 112
Topic 10 – Markets with Intermediated Goods.
o Topic 10.1 – Intermediaries as Dealers. 115
o Topic 10.2 – Intermediaries as Matchmakers. 120
o Topic 10.3 – Intermediaries as Two-Sided Platforms. 122
,ECON0123 – Network Science for Economists Rodrigo Antón García
ECON0123: NETWORK SCIENCE FOR ECONOMISTS
Topic 1 – Overview and Basics of Graph Theory.
o Topic 1.1 – Introduction to Networks.
Networks are a representation of the interaction structure among units. In social and
economic networks, the units (nodes) are agents or firms.
- At a broader level, network science deals with all kinds of interactions: Information
transmission, Information exchange, Web links, Trade, Credit and financial flows,
Friendship, Trust, Spread of epidemics, Diffusion of ideas and innovation, etc.
A graph is a set of nodes linked by edges. We can represent networks as graphs,
depicting the pattern of links (edges) between different units (nodes).
• Types of Networks.
- Social and Economic Networks: A set of people or groups with a pattern of
contacts or interactions among them. Examples: Facebook, Friendship Networks,
Business Relations Between Companies, Intermarriages in Families, Labour Markets.
- Information Networks: A set of information sources with a pattern of connections
among them. Examples: Citations between academic papers, World Wide Web,
Semantic Maps (how words or concepts link to each other).
- Technological Networks: Typically designed for the distribution of commodities or
services. Examples: Infrastructures (routers and domains for Internet), Power Grid,
Transportation Networks (Road, Rail, Airline, Mail).
- How Small is the World?
Hungarian writer Frigyes Karinthy (1887–1938) suggested in a play that any two people
were linked through at most five acquaintances. This came to be known as the small
world phenomenon. This was in a sense the birth of the importance of network science.
Laten on, the sociologist Stanley Milgram made it famous in his 1967 study (largely
disputed) where he analysed the average path length for social networks of people in
the United States. In his study, Milgram asked the residents of Wichita and Omaha to
reach a target person by sending a letter to an acquaintance, who would then do likewise
etc., until the target person was reached, with the idea of then measuring how many
“intermediate nodes” were needed to link the original sender and the effective targets.
Supposedly, 42 of the 160 letters made it to their target, with a median number of
intermediates equal to 5.5. This is how the idea of six degrees of separation was born.
Six Degrees of Separation is the idea that all people are six or fewer social connections
away from each other, effectively making "friend of a friend" chain statements common.
There are similar studies for other networks. Albert, et al (1999) estimated that in 1998
it took on average 11 clicks to go from one random website to another (800M websites).
1
,ECON0123 – Network Science for Economists Rodrigo Antón García
• Networks and “Small World”.
Suppose that each node has ! neighbours and that each of the ! neighbors have !
neighbors. Suppose (unrealistically) that the neighbours have no common neighbours.
Then, in two steps, we can reach ! ! other nodes. Repeating the same reasoning (and
the same unrealistic assumption), in " steps we can reach ! " other nodes.
If the network has # = ! " nodes, then the degree of separation (average distance) is,
ln #
"=
ln !
Note that our unrealistic assumption rules out triadic relations (or clustering phenomena),
that are common in social networks, weblinks, etc.
People connect to others in remote parts through connectors (political representatives,
relative in a different city, etc.) Models of small world networks try to capture this pattern.
• Social and Economic Networks.
Most networked interactions involve a human element. Much of network analysis puts
some focus on social and economic networks, even for understanding communication
networks. In this course, the main focus of are (social and) economic networks.
We superimpose agents’ interactions on the pattern of linkages that forms the structure
of the network to answer the following questions: Will you lend money to your friend?
Will you follow your neighbours’ advice? Will you imitate their behaviour?
Note that since most of these decisions are strategic, we will need a pinch of game theory.
A research question of interest would be to analyse what do different (social, economic,
etc.) networks have in common. For example, diffusion of new technologies and spread
of epidemics have common features in their dynamics. Does this mean that they obey
the same logic? Should we have a single theory to explain both?
- Networks in Sociology.
Sociology deals with group interactions, where network structure is naturally important.
Notions such as social capital, power, or leadership may be understood by studying the
network of interactions within groups.
Sociology used to be mostly descriptive and nonmathematical. Can the study of
networks bring more analytic power to sociology? What is “social power” related to?
What kind of relationships does a leader of the community needs in a community? Or
about dynamics of groups: is a book or karate club likely to splinter into two groups?
2
,ECON0123 – Network Science for Economists Rodrigo Antón García
- Power in Networks.
The Medici became the most influential family in 15th century Florence. The Medici
started out less powerful than other families, both in terms of political dominance of
Florentine institutions and economic wealth. How did they achieve their prominence?
An interesting explanation is offered by Padgett and Ansell (1993): they became the most
powerful family because of their role in the social network of Florence.
Using a measure of centrality called betweenness taking values in [0, 1], the Medici
score 0.522 while no other family scores above 0.255.
This suggests that the Medici may have had a central role in holding the network of
influential families in Florence together and so it effectively gained power via this channel.
- Networks in Economics.
Economics deals with the allocation of scarce resources, including: trades, cooperation
vs. competition, information exchange and aggregation, technology adoption, etc.
Much of this allocation takes place in networked situations. Usually economics consider
either one of two extremes:
1) Markets, with anonymous interactions. For example, Competitive Equilibrium.
2) Few Player Games, with specific identities. For example, Bargaining and Auctions.
The question that an economist would be interest if we can develop new insights by
analysing the network of relations underlying the process that drives an allocation?
- Example 1: How Do People Find Jobs?
Myers and Shultz (1951) and Rees and Shultz (1970) documented that most workers
find their jobs through a “social contact” whereas Granovetter (1973) shows that most
people find jobs through acquaintances (weak ties), not close friends. Is this a puzzle?
No, because people have many more acquaintances than friends. Yet, there is more.
The property of strong triadic closure states: if 1 and 2 are friends, and 2 and 3 are friends,
then 1 and 3 are very likely to be(come) friends. Thus, you are more likely to get referrals
to an unknown manager through an acquaintance than a friend. This kind of weak ties
are important in understanding social capital or, in manager speak, the value of networking.
- Example 2: How Do Businesses Develop and Exploit Trust?
Munshi (2009) studies the Indian diamond industry (about 14% of total merchandise
exports). This sector is dominated by a few small subcastes (Marwaris, Palanpuris,
Kathiawaris), similar to how Antwerp and New York diamond trade used to be dominated
by ultra-Orthodox Jews. In the past, Marwaris and Palanpuris used to be dominant.
However, in the 1980s, Kathiawaris took over. Why did this change take place?
3
, ECON0123 – Network Science for Economists Rodrigo Antón García
India does not produce rough diamonds, that are usually imported from Antwerp.
Because legal contracts are difficult to enforce, especially for small traders, trust relations
are important. Marwaris and Palanpuris had an institutionalized relationship with Antwerp
(opening branches of their firms). Over time, their intermarriage rates went down,
suggesting that network relationships matter less.
- More Examples.
How do people learn about new products? A “viral” video. “Cult following” for movies.
How does a new technology spread? Hybrid corn in the United States in the early 20th
century. Prescription of new medications in the Midwest in the 1960s.
How do people form their political, social and religious opinions? Word-of-mouth from
early adopters or other news sources? Imitate family, friends and neighbours?
Have the tremendous advances in information and communication technology changed
the nature of social networks? Karinthy suggested that the world had become small at in
the early 20th century. Has it become smaller now?
Social networks may be embedded in communication media. Do new communication
mediums such as Meta change what information we obtain and how we process it?
Social networks expand or hinder information opportunities? Most people use new
mediums to communicate with a small group of like-minded people. This may not
guarantee access to a greater diversity of opinions. Greater access to information
competes for attention. This may increase herding (excessive copying of others’
behaviour and information) instead of the wisdom of the crowd (information aggregation).
- Network Science.
The antecedents of network science center around mathematical graph theory, a
subfield of discrete mathematics which started with Euler’s work (1736) on the
Königsberg bridges problem and sociology. In recent years, powerful computers have
incremented the capabilities of networks as they can gather and analyze large scale data.
The new analytical approach involves finding statistical properties that characterize the
structure of networks and ways to measure them, creating models of networks (e.g.,
Erdös-Renyi) and predicting behaviour of networks on the basis of structural properties.
o Topic 1.2 – Formal Definitions.
A Network (Graph) ! = ($, &) has two parts, a set of / elements, called Nodes (vertices),
and a set 0 of pairs of nodes, called Links (edges). The link (2, 3) joins the nodes 2 and 3.
Thus, write 3 ∈ / if 3 is a node in this network, and (2, 3) ∈ 0 if there is a link from 2 to 3.
Two nodes are Adjacent (connected/neighbours) if there is a link between them.
4
