Chapter Notes [1]

Ch 6 - Games Games where players aim to maximise their payoff and know the entire structure of the game. Decisions are made simultaneously and independently. Dominant Strategy - regardless of what action the other player takes one strategy is always better than all others. Player wish to maximise payoff so not socially optimal - PRISONER’S DILEMMA Best Response - the best choice for one player, given the belief about the strategy other player will take. Nash Equilibrium - when one strategy is best response to another and vice versa. Exists when no player has an incentive to change their strategy as they will be worse off. Mixed Nash Equilibrium - allows randomisation of actions and looks at the probability with each player chooses an action meaning we now have a set of strategies. Focal Points act as a means for choosing between multiple equilibria - external and internal factors. Pareto Optimality - no other choice of strategies where all players receive the same payoff and at least one player receives a higher payoff. Social Optimality - maximises sum of the players payoff. Extensive Form Games - player make choices one after each other and always choose action that maximises their payoff. Equilibrium in game tree is called SUBGAME PERFECT EQUILIBRIA which is a NE in normal form but may not be the case vice versa. In normal form players can pre commit to actions which cannot occur in extensive form games.

Ch 9 - Auctions Seller does not know buyer’s values and buyer’s do not know each others values. Ascending Bid/Second Price Auctions - item goes to the second highest bidder and buyer’s either submit all their bids at the same time or seller gradually raises price and bidders drop out until one bidder remains. Descending Bid/First Price Auctions - item goes to the highest bidder and buyers either submit their bids at the same time or seller gradually lowers price until first bidder accepts price. Dominant strategy for second price auctions is to bid truthfully. Dominant strategy for first price auctions is to shade bid slightly downward and the amount depends on the number of other bidders.

Ch 14 - Link Analysis and Web Search Hubs and Authorities - each link from a page A to B is an endorsement by A to B. Therefore, the greater the number of endorsements the more authority it has so the higher in the ranking it goes. The best hubs are those who endorse the best authorities. Bipartite Graph with hubs on one side and authorities on the other. Algorithm - 1. Each page gets a authority value equal to the number of links it has from hubs. 2. Each hub gets a hub score equal to the sum of the authority values of the pages it endorses. 3. Process is repeated with new values 4. Normalise value by dividing by total sum. Pagerank - Endorsements are passed from one page to other pages and pages with more authority can make stronger endorsements as they have a larger fraction of the endorsements in the whole web of pages. Algorithm - 1. Each page is given a pagerank of 1/n. 2. For each page the page rank is divided equally between the pages that it points to. If it has no outgoing edges it retains all its page rank. 4. Each pages page rank is updated by summing up the fraction of pagerank it receives from all of its incoming edges. Scaling Pagerank ensures that the ‘wrong’ nodes do not get all the pagerank so after each calculation we scale down each page rank by a factor ‘s’ and distribute this leftover page rank equally between all pages.

Ch 17 - Direct Benefits You can incur an explicit benefit when you align your behaviour with the behaviour of others. When there are no network effects then the max price an individual is willing to pay for an item is their intrinsic value for this item - r(x). Equilibrium occurs when r(x*) = p*. When there are network effects the max price an individual is willing to pay for an item is their intrinsic value and the number of other people using the item - r(x)f(z). Self fulfilling expectations for a quantity of consumers z at price p* is when; every consumer makes the same prediction about the fraction of consumers using the item and then if every consumer x decides to buy based on whether r(x)f(z) is at least p*, then eventually the fraction of consumers that adopt the item will be z. Equilibrium occurs when r(z)f(z) = p*. Stable equilibrium is when consumers do not make perfect prediction of z but the demand gets pushed back to the value of the equilibrium z. Equilibrium is unstable when demand gets pushed away from the value of the equilibrium when consumers do not make the perfect prediction. A tipping point is an equilibrium value z that can predict the success of a good.

Ch 19 - Cascading Behaviour in Networks Individuals make decisions based on the choices of their neighbours. Each individual has a threshold level and exactly this fraction of more than this fraction of his neighbours adopt A then he too will switch to behaviour A. There is assumed to be a set of initial adopters and each node is assumed to have the same threshold level q = b/a+b. There are two equilibriums; when all nodes adopt A and when all nodes adopt B. Whether a complete cascade occurs depends on network structure, threshold level and initial adopters. Tightly-knit communities can stop a complete cascade but can be overcome by reducing threshold level by increasing payoffs of product A or by convincing a small number of nodes in the tightly-knit community to adopt A. Blocking cluster - a set of nodes which have a density p if every node in the subset S has at least a fraction p of its edges go to nodes S i.e. number of edges in S/total number of edges. If you have a blocking cluster with a density greater than 1-q then a complete cascade will not form and vice versa. If each node has a different threshold level, the role of threshold level plays an important role in choice of initial adopters i.e. choose those nodes that are connected to nodes with low threshold levels as they are seen to be easily influenced.

Ch 6

Ch 9

Ch 14

Ch 17

Ch 19