Roll Number
11I190011
Category
TA
Topics for PhD Qualifiers
Compulsory Subject: (i) Optimisation Techniques, (ii) Stochastic Models
Elective 1: Probability Theory
Elective 2: Game Theory
Elective 1: Probability Theory
Elective 2: Game Theory
Elective1
Probability Theory:
Classes of Sets (Semi-Algebras, Algebras, Sigma-Algebras, pi-systems, lambda-systems),
Measures (finite additivity/sub-additivity, countable sub-additivity, monotone continuity from above and below, outer measures, Caratheodory's Extension Theorems, Lebesegue measure on R),
Random Variables and Integration (Random Variables on a Countable Space and their Expectations, Markov's Inequality, Chebyshev's Inequality, Construction of the Probability Measure, Null Sets, Probability Measures on R, the distribution or law of a random variable, Simple Random Variables and their Expectations, Any general Random Variable and its Expectation, Monotone Convergence Theorem, Bounded Convergence Theorem, Dominated Convergence Theorem, Fatous' Lemma, Comparison of Reimann and Lebesgue Integral, Jensen's Inequality, Holder's Inequality, Minkowski's Inequality, Cauchy Schwartz Inequality)
Product Spaces, Product Measures, Fubini-Tonelli Theorem,
Independence (Independent Events and Random Variables, Borel-Cantelli Lemma, Kolmogorov's Zero-One Law, tail sigma-algebras)
Convergence of Random Variables (almost sure convergence, convergence in probability, L^p convergence, complete convergence),
Weak Convergence of Probability Measures (Polish Spaces, homeomorphisms, uniform integrability of random variables, Space of Probability Measures: regularity, separating class, tight, Prohorov Topology, Portmonteau Theorem, separability of P(S), Skorohod's Theorem, L^p Spaces, dual spaces, Riesz Representation Theorem, Scheffe's Theorem)
Conditional Expectation and Martingales; Supermartingales and Submartingales, Martingale Inequalities, Martingale Convergence Theorems.
Classes of Sets (Semi-Algebras, Algebras, Sigma-Algebras, pi-systems, lambda-systems),
Measures (finite additivity/sub-additivity, countable sub-additivity, monotone continuity from above and below, outer measures, Caratheodory's Extension Theorems, Lebesegue measure on R),
Random Variables and Integration (Random Variables on a Countable Space and their Expectations, Markov's Inequality, Chebyshev's Inequality, Construction of the Probability Measure, Null Sets, Probability Measures on R, the distribution or law of a random variable, Simple Random Variables and their Expectations, Any general Random Variable and its Expectation, Monotone Convergence Theorem, Bounded Convergence Theorem, Dominated Convergence Theorem, Fatous' Lemma, Comparison of Reimann and Lebesgue Integral, Jensen's Inequality, Holder's Inequality, Minkowski's Inequality, Cauchy Schwartz Inequality)
Product Spaces, Product Measures, Fubini-Tonelli Theorem,
Independence (Independent Events and Random Variables, Borel-Cantelli Lemma, Kolmogorov's Zero-One Law, tail sigma-algebras)
Convergence of Random Variables (almost sure convergence, convergence in probability, L^p convergence, complete convergence),
Weak Convergence of Probability Measures (Polish Spaces, homeomorphisms, uniform integrability of random variables, Space of Probability Measures: regularity, separating class, tight, Prohorov Topology, Portmonteau Theorem, separability of P(S), Skorohod's Theorem, L^p Spaces, dual spaces, Riesz Representation Theorem, Scheffe's Theorem)
Conditional Expectation and Martingales; Supermartingales and Submartingales, Martingale Inequalities, Martingale Convergence Theorems.
Elective2
Game Theory:
Strategic Form Games (Domination, Elimination of Dominated Strategies, Two-Player Zero Sum Games, Matrix Games, MinMax Solution Concept, Bimatrix Games, N-Person Games in Normal Form, Nash Equilibrium: Existence, Properties, Stability, Pure Strategies solution, Mixed Strategies Solution; Games with Perfect Information, Games with Imperfect Information)
Games with Incomplete Information (Common Knowledge, Aumann's Model of Incomplete Information, Information Sets, Correlated Equilibrium Concept: Definition and Properties)
Extensive Form Games (Zero Sum Games: Single Act Games and Multi Act Games, Non-Zero Sum Games: Single Act Games (pure Nash Concept, Behavioral and Mixed Solutions Concept) and Multi Act Games (Pure Strategy Nash Equilibria, Behavioral and mixed equilibrium strategy), Sub-game perfect Equilibrium, Rationalizability, Backward Induction, Perfect Equilibrium, Sequential Equilibrium, Games with Perfect and Imperfect Equilibrium, Stackelberg Equilibrium solution concept)
Strategic Form Games (Domination, Elimination of Dominated Strategies, Two-Player Zero Sum Games, Matrix Games, MinMax Solution Concept, Bimatrix Games, N-Person Games in Normal Form, Nash Equilibrium: Existence, Properties, Stability, Pure Strategies solution, Mixed Strategies Solution; Games with Perfect Information, Games with Imperfect Information)
Games with Incomplete Information (Common Knowledge, Aumann's Model of Incomplete Information, Information Sets, Correlated Equilibrium Concept: Definition and Properties)
Extensive Form Games (Zero Sum Games: Single Act Games and Multi Act Games, Non-Zero Sum Games: Single Act Games (pure Nash Concept, Behavioral and Mixed Solutions Concept) and Multi Act Games (Pure Strategy Nash Equilibria, Behavioral and mixed equilibrium strategy), Sub-game perfect Equilibrium, Rationalizability, Backward Induction, Perfect Equilibrium, Sequential Equilibrium, Games with Perfect and Imperfect Equilibrium, Stackelberg Equilibrium solution concept)
PhD. Supervisor (if decided)
Prof. K S Mallikarjuna Rao
Proposed Research Plan (if decided)
When we study strategic interaction in large populations (i.e., there are infinite number of agents), a logically sound assumption is that each agent interacts with only some of the agents in the whole population (i.e., the number of agents in the neighbourhood of any given agent is finite). Therefore, although the population is large, strategic interactions occur over a finite set of agents. Such a system is called a local interaction system. In addition to such a system, if each agent has a set of available actions and a pay-off defined for each pair of interaction, then the corresponding game is called a local interaction game. If an agent has to choose a constant action for all of its neighbours, modelling the strategic interaction of all the agents in the network becomes an interesting problem. This is the most general version of the problem that I would like to address in the future.
Currently in the literature, the problem has been looked at under a simplifying assumption - every agent has the same two actions available to her throughout the game. Under this assumption, the game can and has been studied for two different set-ups - when the interactions are stochastic and when they are deterministic. Furthermore, the game can be considered when the network structure is given or we can model the game as a network formulation game.
In either scenario, the game is defined as follows: each agent has two available actions - a and b. Given an edge (i,j), or an edge (i,j) is said to be formed such that if both the agents i and j play the same action a, each gets a pay-off of q, while if they play the same action b, each gets a pay-off of (1-q). If the agents i and j play different different actions, then each gets a pay-off of 0. Such a generalised framework to the problem, as described above was given by Morris. As can be seen, therefore, the total payoff of a player is the sum of the payoffs which she has with each of her neighbours. Since the degree of node i is |N(i)| and considering the number of neighbours of i playing b to be N_b(i), the payoff to player i from choosing a would be q*(|N(i)| - N_b(i)) and from choosing b would be (1-q)*N_b(i). Hence, the best response strategy for agent i is to adopt b if N_b(i) > q*|N(i)| and to adopt a if N_b(i) <= q|N(i)|. Such a model as described above is one of the many diffusion models, so called, because there is a diffusion or dissemination of behaviour through informative relationships due to the formation of edges.
A number of qualitative insights can be derived from the simple diffusion model due to Morris. A network where all nodes play a is a state of equilibrium of the game as is the state where all nodes play b. Consider now a network where all nodes initially play a and a small number of nodes are forced to adopt strategy b (thus, constituting the seed). Under this setup, every node would have a best response update based on the following rule: switch to b if enough of your neighbours have already adopted b. Contagion is said to occur if action b can spread from a finite set of players to the whole population. It is shown by Morris that there is a contagion threshold such that contagion occurs if and only if the parameter q is less than the contagion threshold. In particular the contagion threshold is always at most 1/2 so that b needs to be the risk-dominant action in order to spread. However, this condition is not sufficient and gives a number of characterisations of the contagion threshold and also shows that low contagion threshold implies the existence of equilibria where both actions are played.
However, in particular, Lelarge has considered a simpler model of cascades based on the general framework as given by Morris. In this cascading model, he has considered the number of agents to be n (finite) and then he has studied the sequence of random networks generated as n increases to infinity. For the formation of the random networks, he has assumed the Configuration Model, which was first introduced by Bender and Canfield and was further elaborated on with intricate details by Bollobas.
In the Configuration Model, we work with a given degree sequence of a network with n nodes: (d_1,d_2, ... ,d_n), instead of the degree distribution which usually forms the basis for network formation in random networks. Furthermore, it is assumed that the given degree sequence should be such that the sum of the degrees is even. This assumption is required for the algorithm by which the configuration model is formed. Assign to each node, stubs or half edges according to the given degree sequence (d_1, d_2, ... , d_n). In other words, let us construct a sequence where, node i is listed d_i times. Now, from this sequence, let two elements be picked up at random and the corresponding edge be formed between the two respective nodes and also let those two elements be deleted from the sequence. This is precisely why the sum of the degrees was taken to be even, so that no element is left over. The random multi-graph so formed is the random network formed by the configuration model.
It must be specifically noted that several self-loops and parallel edges can form for the same node and pair of nodes respectively. But, all the analysis that is done for a random network is done for simple networks. Hence, conditioned on this random multi-graph G^*(n,d), where, n is the finite number of players and d is the degree sequence, being a simple graph, we obtain a uniformly distributed random network with the given degree sequence, which we denote by G(n,d). This conditioning to obtain the resulting simple graph is due to Janson and Molloy and Reed.
Now, in Lelarge, n increases to infinity and the degree sequence follows certain regularity conditions. In Morris, the contagion threshold of a connected infinite network is defined as the maximum threshold q = q_c at which a finite set of initial adopters of the other strategy b, that can cause a complete cascade, i.e. the resulting cascade of adoptions of b eventually causes every node to switch from a to b. In Lelarge it is further assumed that the initial adopters are forced to play $b$ forever in the game, such that the diffusion model becomes monotone and the number of players playing b is non-decreasing. He refers to this model as the permanent adoption model. Under such considerations, Lelarge investigates the equilibrium of the game and answers when can there be a co-existent equilibrium of a and b and when it is that the network goes to the equilibrium of everyone playing b.
As far as my future work is concerned, we would like to analyse the game under both stochastic as well as deterministic best-response dynamics. Under each such dynamic, especially the stochastic game, we would like to determine a sufficient characterisation on the contagion threshold, given by q_c, as defined above. The next question that we would like to look at is when does the equilibrium of the local interaction game have the co-existence of both the actions a and b. How many agents should change their actions from a state of pure equilibrium (i.e., the entire population playing one of the two actions) in order to affect each agent in the population to change their actions is the biggest question. Given the network structure, we would also like to study who these agents need to be. These two questions essentially provide answers to the notion of the Law of the Few. Finally, we would like to address all of these above questions after removing the assumption of each agent having just two actions.
Currently in the literature, the problem has been looked at under a simplifying assumption - every agent has the same two actions available to her throughout the game. Under this assumption, the game can and has been studied for two different set-ups - when the interactions are stochastic and when they are deterministic. Furthermore, the game can be considered when the network structure is given or we can model the game as a network formulation game.
In either scenario, the game is defined as follows: each agent has two available actions - a and b. Given an edge (i,j), or an edge (i,j) is said to be formed such that if both the agents i and j play the same action a, each gets a pay-off of q, while if they play the same action b, each gets a pay-off of (1-q). If the agents i and j play different different actions, then each gets a pay-off of 0. Such a generalised framework to the problem, as described above was given by Morris. As can be seen, therefore, the total payoff of a player is the sum of the payoffs which she has with each of her neighbours. Since the degree of node i is |N(i)| and considering the number of neighbours of i playing b to be N_b(i), the payoff to player i from choosing a would be q*(|N(i)| - N_b(i)) and from choosing b would be (1-q)*N_b(i). Hence, the best response strategy for agent i is to adopt b if N_b(i) > q*|N(i)| and to adopt a if N_b(i) <= q|N(i)|. Such a model as described above is one of the many diffusion models, so called, because there is a diffusion or dissemination of behaviour through informative relationships due to the formation of edges.
A number of qualitative insights can be derived from the simple diffusion model due to Morris. A network where all nodes play a is a state of equilibrium of the game as is the state where all nodes play b. Consider now a network where all nodes initially play a and a small number of nodes are forced to adopt strategy b (thus, constituting the seed). Under this setup, every node would have a best response update based on the following rule: switch to b if enough of your neighbours have already adopted b. Contagion is said to occur if action b can spread from a finite set of players to the whole population. It is shown by Morris that there is a contagion threshold such that contagion occurs if and only if the parameter q is less than the contagion threshold. In particular the contagion threshold is always at most 1/2 so that b needs to be the risk-dominant action in order to spread. However, this condition is not sufficient and gives a number of characterisations of the contagion threshold and also shows that low contagion threshold implies the existence of equilibria where both actions are played.
However, in particular, Lelarge has considered a simpler model of cascades based on the general framework as given by Morris. In this cascading model, he has considered the number of agents to be n (finite) and then he has studied the sequence of random networks generated as n increases to infinity. For the formation of the random networks, he has assumed the Configuration Model, which was first introduced by Bender and Canfield and was further elaborated on with intricate details by Bollobas.
In the Configuration Model, we work with a given degree sequence of a network with n nodes: (d_1,d_2, ... ,d_n), instead of the degree distribution which usually forms the basis for network formation in random networks. Furthermore, it is assumed that the given degree sequence should be such that the sum of the degrees is even. This assumption is required for the algorithm by which the configuration model is formed. Assign to each node, stubs or half edges according to the given degree sequence (d_1, d_2, ... , d_n). In other words, let us construct a sequence where, node i is listed d_i times. Now, from this sequence, let two elements be picked up at random and the corresponding edge be formed between the two respective nodes and also let those two elements be deleted from the sequence. This is precisely why the sum of the degrees was taken to be even, so that no element is left over. The random multi-graph so formed is the random network formed by the configuration model.
It must be specifically noted that several self-loops and parallel edges can form for the same node and pair of nodes respectively. But, all the analysis that is done for a random network is done for simple networks. Hence, conditioned on this random multi-graph G^*(n,d), where, n is the finite number of players and d is the degree sequence, being a simple graph, we obtain a uniformly distributed random network with the given degree sequence, which we denote by G(n,d). This conditioning to obtain the resulting simple graph is due to Janson and Molloy and Reed.
Now, in Lelarge, n increases to infinity and the degree sequence follows certain regularity conditions. In Morris, the contagion threshold of a connected infinite network is defined as the maximum threshold q = q_c at which a finite set of initial adopters of the other strategy b, that can cause a complete cascade, i.e. the resulting cascade of adoptions of b eventually causes every node to switch from a to b. In Lelarge it is further assumed that the initial adopters are forced to play $b$ forever in the game, such that the diffusion model becomes monotone and the number of players playing b is non-decreasing. He refers to this model as the permanent adoption model. Under such considerations, Lelarge investigates the equilibrium of the game and answers when can there be a co-existent equilibrium of a and b and when it is that the network goes to the equilibrium of everyone playing b.
As far as my future work is concerned, we would like to analyse the game under both stochastic as well as deterministic best-response dynamics. Under each such dynamic, especially the stochastic game, we would like to determine a sufficient characterisation on the contagion threshold, given by q_c, as defined above. The next question that we would like to look at is when does the equilibrium of the local interaction game have the co-existence of both the actions a and b. How many agents should change their actions from a state of pure equilibrium (i.e., the entire population playing one of the two actions) in order to affect each agent in the population to change their actions is the biggest question. Given the network structure, we would also like to study who these agents need to be. These two questions essentially provide answers to the notion of the Law of the Few. Finally, we would like to address all of these above questions after removing the assumption of each agent having just two actions.