Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Economics Y3 > Economics of Networks and Institutions Revision > Flashcards

Economics of Networks and Institutions Revision Flashcards

1
Q

What is a network/graph?

A

A pair of nodes, and edges between any two nodes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a directed graph?

A

A graph with arrows

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

When are two nodes neighbours?

A

When there is an edge between them

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a path?

A

A sequence of nodes in which every consecutive pair is connected by an edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a cycle?

A

A path in which the first and last nodes are the same

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a connected graph?

A

A graph in which there is a path between any two nodes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the real network properties?

A
  1. Giant components. Most people are connected among themselves.
  2. Short paths. Most graphs have a surprisingly short average path length
  3. Triadic closure. We tend to observe triangles in networks. If a and b are friends, and so are a and c, it is likely that b and c will also eventually become friends
  4. High clustering coefficients. The clustering coefficient of a node is the probability that two randomly selected friends of x are also friends with each other. This is a property of nodes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the length of a path?

A

How many edges are between the first and last node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the diameter of a graph?

A

The maximum distance between any two nodes in a graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the degree of a node?

A

How many edges link to that node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Why is it suggested that weak ties are more valuable than strong ties?

A

(Granovetter) Strong ties have redundant information, while weak ties have new information. If you delete strong ties, the giant component shrinks steadily. If you delete weak ties, the giant component shrinks faster

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a bridge?

A

A weak tie that, if removed, would break the graph into two connected components

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the strong triadic closure property?

A

If we have AB and AC (both strong ties), we must have a tie between BC (either weak/strong)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the embeddedness of an edge AB?

A

The number of common neighbours shared by A and B. This is a property of edges. Edges with high embeddedness are highly central

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are the +s and -s of not being embedded?

A

+: More access to information from multiple groups, and opportunity to regulate flow and synthesize in new ways

-: Interactions are less embedded within a single group, and less protected by the presence of neighbours

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is degree centrality?

A

Number of friends / Total number of possible friends (N - 1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the problem with degree centrality?

A

It fails to acknowledge how many of your connections are central themselves, a critical failure in applications

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is betweeness centrality?

A

How many pairs of individuals would have to go through you in order to reach one another in the minimum number of steps

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are geodesic paths?

A

Shortest paths

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Name two other centrality measures

A
  1. Bonachich eigenvector centrality. It shows how central your own connections are, using adjacency matrix.
  2. Google’s PageRank. It counts the number and quality of links to a page to determine how important it is.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Define homophily, how do you measure it?

A

The principle saying that we tend to look similar to our friends.

Suppose we have p males and q females. Two males will be friends with probability p2, two females with probability q2, and male-female links exist with probability 2pq.

If the fraction of edges between m-f is less than 2pq, there is evidence of homophily

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Name and explain a solution to homophily

A

The Schelling model. We have a grid of squares, and each square is occupied by an x or o agent, or nobody. Each agent is happy if t out of 8 neighbours are of her own type, otherwise she moves.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What was Schelling’s finding?

A

In his model, you always end up with a completely segregated society. It shows that small preferences can create a crazy global phenomenon

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is a signed graph?

A

A graph in which every edge has a + sign or a - sign

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is a complete graph?

A

A graph in which every two nodes are connected by an edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

When is structural balance property?

A

A graph is structurally balanced if, for every set of three nodes, either all 3 of these edges are +, or exactly one of them is +

27
Q

What is the Structural Balance Theorem?

A

If a complete signed graph is balanced, then either all pairs of nodes are friends, or they can be divided into two groups, X and Y, such that every air of nodes in X like each other, every pair of nodes in Y like each other, and everyone in X is the enemy of everyone in Y.

28
Q

Explain how you would reverse prove the Structural Balance Theorem?

A

Start by assuming the graph is balanced, and prove the two group decomposition.

If everyone only has + edges, finished.

If the graph has at least one - edge, pick a random node and put together all of his friends , and put the enemies in another group.

29
Q

What is a game?

A

A game consists of a set of players, a set of strategies and a set of payoffs (a utility function that gives a number for each combination)

30
Q

When is a strategy strictly dominated?

A

There is another strategy that always gives a strictly higher payoff, no matter what other players do

31
Q

What is a pure strategy Nash equilibrium?

A

A strategy profile such that nobody has incentives to unilaterally deviate, given that everybody plays a strategy profile (a list of strategies, one for each player)

32
Q

What is the Nash Theorem?

A

Every finite game has an equilibrium point in mixed strategies: a probabilistic combination of pure strategies

33
Q

What is a finite game?

A

A game with:
1) A finite number of players
2) A finite set of strategies for each player

34
Q

What is the Braess paradox?

A

If you try to reduce commuting times and create more highways, you end up with more commuting.

Adding one extra strategy can make everyone worse off

35
Q

Do traffic networks always have a pure NEQ?

A

No.

One drive could shift their route to one that is better for them, increasing the delay for another driver, who then switches and continues the cascade

36
Q

What is a competitive equilibrium?

A

A pair of allocations and prices such that:

Demand = supply in all markets

Agents maximise their utility

37
Q

What is a constricted set?

A

A set of nodes s, such that:

|N(S)| < |S|

38
Q

What is a matching problem?

A

Two sets of agents, or one set of agents and one set of objects.

Participants have preferences of agents over other agents, or objects

Money typically can’t be used to determine the assignment

39
Q

Define perfect matching

A

A matching is perfect if every node is linked to exactly one node, on opposite sides

40
Q

Define a bipartite graph

A

A subgraph such that each node is linked to at most one other node

41
Q

What is Hall’s Matching Theorem?

A

A graph has no perfect matching if and only if it contains a constricted set

42
Q

How do we always get the stable ranking?

A

Deferred acceptance. In the marriage example:
Each man proposes to their most preferred woman, each woman rejects all except the best one she receives. She temporarily accepts this.

Each rejected man proposes to their second best woman, who rejects all apart from the best one. She temporarily accepts this.

This procedure continues until all women have received a proposal

43
Q

Name the properties of TTC

A
  1. Pareto optimal
  2. Individually rational
  3. Strategy-proof
  4. Unique core element
  5. Unique competitive equilibrium
44
Q

Explain the random serial dictatorship mechanism

A

One person chooses whatever is best for him. Then a second one, from whatever is left, and so on.

45
Q

Explain deferred acceptance in the marriage context

A

Each man proposes to his most preferred woman. Each woman rejects all except for the best one she receives. She temporarily accepts this proposal.

Each rejected man proposes to his second best woman. Each woman rejects all except for the best one she receives. She temporarily accepts this proposal.

Repeat until all women have received a proposal

The outcome is STABLE

46
Q

What is the Rural Hospital Theorem?

A

If I am single in one stable marriage, I am single in ALL stable marriages

47
Q

What is a core allocation?

A

An allocation is in the core if a group of agents cannot exchange their initial endowments and make at least some agents better off

48
Q

What is an interrupter in DA?

A

An interrupter is a man M who is temporarily accepted by a woman W in round t.

Because of him, the woman W rejects another man M’ in a later round, but eventually he gets rejected by woman W in an even later round.

49
Q

Explain the TTC mechanism in the school admissions context

A
  1. Students point to their favourite school. Schools point to their favourite student. Assign every student in a cycle to the school she points, and remove the student. The counter of each school in a cycle is reduced by one. If zero, remove the school.
  2. Each remaining student points to her favourite school among the remaining schools, and each remaining school points to the student with the highest priority. Repeat
50
Q

Explain EADA in the schooling model

A

Use DA and find the student optimal stable matching.

Find the last interrupter

Delete this school from the interrupter’s preference (do not let them apply to it)

Use DA again, repeat until there are no more interrpters

51
Q

Explain information networks

A

The basic units being connected are pieces of information, and links join pieces of information that are related to each other in some fashion

52
Q

Define a strongly connected component (SCC)

A

A directed graph is a subset of the nodes such that:
(i) every node in the subset has a path to every other
(ii) the subset is not part of some larger set with the property that every node can reach each other

53
Q

Explain how the web is a giant SCC

A

The Web contains a giant strongly connected component. A number of major search engines have links leading to directory-type pages from which you can eventually reach large companies and major educational institutions. Many of these pages link back to the starting pages.

All these pages can mutually reach one another, and hence all belong to the same strongly connected component

54
Q

Explain the Bow Tie structure

A

Classify nodes by their ability to reach and be reached from the giant SCC. The first two sets in this classification are:
(1) IN: nodes that can reach the giant SCC but cannot be reached from it - ‘upstream’
(2) OUT: nodes that can be reached from the giant SCC but cannot reach it - ‘downstream’

55
Q

Why are information retrieval systems problematic?

A

synonymy - multiple ways to say the same thing

polysemy - multiple meanings for the same terms

56
Q

What is the Weak Structural Balance Property

A

There is no set of three nodes such that the edges among them consist of exactly two positive edges and one negative edge

57
Q

What are the assumptions of games?

A
  • Each players knows everything about the structure of the game
  • Players want to maximise payoffs (rationality)
  • Everything a player cares about is summarized in the players payoffs
58
Q

What is a coordination game?

A

A game in which the players’ shared goal is to coordinate to the same strategy

59
Q

Define Pareto optimality in a game

A

A choice of strategies - one by each player - is Pareto optimal if there is no other choice of strategies in which all players receive payoffs at least as high, and at least one player receives a strictly higher payoff

60
Q

What is the social cost of a travel pattern?

A

The sum of the travel times incurred by all drivers when they choose a path

61
Q

What is the travel time function in network traffic?

A

The time it takes all drivers to cross the edge when there are x drivers using it

62
Q

Define the socially optimal combination in a game

A

A choice of strategies - one by each player - is a social welfare maximiser if it maximises the sum of the players’ payoffs

63
Q

What are the preference requirements of individual preferences in voting?

A

Completeness: For each pair of distinct alternatives the individual either prefers X to Y, or Y to X

Transitivity: If an individual prefers X to Y and Y to Z, then they should prefer X to Z

64
Q

Name the components of voting systems

A

Voters, alternatives, preferences of each voter over alternatives

Economics Y3 (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions