etd@IISc Collection:http://hdl.handle.net/2005/182014-10-31T06:51:04Z2014-10-31T06:51:04ZRainbow Connection Number Of Graph Power And Graph ProductsArunselvan, Rhttp://hdl.handle.net/2005/23832014-09-09T09:54:14Z2014-09-08T18:30:00ZTitle: Rainbow Connection Number Of Graph Power And Graph Products
Authors: Arunselvan, R
Abstract: The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. This graph parameter was introduced by Chartrand et al. in 2008. The problem has garnered considerable interest and several variants of the initial version have since been introduced. The rainbow connection number of a connected graph G is denoted by rc(G). It can be shown that the rainbow connection number of a tree on n vertices is n -1. Hence |G|-1 is an upper bound for rc(G)of any non-trivial graph G. For all non-trivial, bridge-less and connected graphs G, Basavaraju etal. Showed that rc(G) can be upper-bounded by a quadratic function of its radius. In addition they also proved the tightness of the bound. It is clear that we cannot hope to get an upper-bound better than |G| - 1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridge-less graphs whose rainbow connection numbers are linear functions of their radii? This question is of particular interest since the diameter is a trivial lower bound for rc(G). We answer in affirmative to the above question. In particular we studied three (graph) product operations (Cartesian, Lexicographic and Strong) and the graph powering operation. We were able to show that the rainbow connection number of the graph resulting from any of the above graph operations is upper-bounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.2014-09-08T18:30:00ZA Novel Game Theoretic And Voting Mechanism Based Approach For Carbon Emissions ReductionShelke, Sunil Sitaramhttp://hdl.handle.net/2005/23612014-08-07T05:31:36Z2014-08-06T18:30:00ZTitle: A Novel Game Theoretic And Voting Mechanism Based Approach For Carbon Emissions Reduction
Authors: Shelke, Sunil Sitaram
Abstract: Global warming is currently a major challenge facing the world. There are widespread ongoing efforts in the form of summits, conferences, etc., to find satisfactory ways of surmounting this challenge. The basic objective of all such efforts can be summarized as conception and formation of protocols to reduce the pace of global carbon levels. Game theory and mechanism design provide a natural modeling tool for capturing the strategic dynamics involved in global warming related problems. This dissertation explores for the first time the use of voting mechanisms in the context of solving the central problems, namely, allocation of emission caps and reduction quotas to strategic emitting agents (countries).
The contribution of this dissertation is two-fold. The first contribution is to develop an elegant game theoretic model that accurately captures the strategic interactions among different emitting agents in a global warming setting. This model facilitates a convenient way of exploring a mechanism design approach for solving important allocation problems in the global warming context. The second contribution is to propose and explore a novel approach, based on voting mechanisms, to solve two problems: (1) allocating emission caps and (2) allocating reduction quotas to strategic agents.
Our work investigates the use of voting mechanisms that satisfy four desirable properties:
(1) non-dictatorship, (2) strategy-proofness, (3) efficiency, and (4) anonymity. In particular, we explore the median selection, maximum order statistic selection, and general Kth order statistic selection voting mechanisms. Our results clearly show that only trivial allocations satisfy all the above properties simultaneously. We next investigate the use of voting mechanisms for the dual problem, namely, allocation of emission reductions to emitting agents. Here, we show that non-trivial allocations are possible, however an important property, individual rationality, might be compromised.
The investigations in the thesis bring out certain limitations in applying voting mechanisms that satisfy all the four properties above. Nevertheless, the insights obtained provide valuable guidelines for solving emission allocation related problems in a principled and informed way.2014-08-06T18:30:00ZGame Theoretic Models For Social Network AnalysisNarayanam, Ramasurihttp://hdl.handle.net/2005/23502014-08-01T05:27:24Z2014-07-31T18:30:00ZTitle: Game Theoretic Models For Social Network Analysis
Authors: Narayanam, Ramasuri
Abstract: With increasing demand for social network based activities, it is very important to understand not only the structural properties of social networks but also how social networks form, to better exploit their promise and potential. We believe the existing methods and tools for social network analysis have a major inadequacy: they do not capture the behavior (such as rationality and intelligence) of individuals nor do they model the strategic interactions that occur among these individuals. Game theory is a natural tool to overcome this inadequacy since it provides rigorous mathematical models of strategic interaction among autonomous, intelligent, and rational agents. This thesis brings out how a game theoretic approach helps analyze social networks better. In particular, we study three contemporary and pertinent problems in social networks using a game theoretic approach: determining influential individuals for viral marketing, community detection, and social network formation.
The first problem deals with determining influential nodes in social networks for diffusion of information. We present an efficient heuristic algorithm (SPIN) to this problem based on cooperative game theoretic techniques. The running time of SPIN is independent of the number of influential nodes to be determined. Moreover, unlike the popular benchmark algorithms, the proposed method works well with both submodular and non-submodular objective functions for diffusion of information.
In the second problem, we design a novel game theoretic approach to partition a given undirected, unweighted graph into dense subgraphs (or communities). The approach is based on determining a Nash stable partition which is a pure strategy Nash equilibrium of an appropriately defined strategic form game. In the proposed graph partitioning game, the nodes of the graph are the players and the strategy of a node is to decide to which community it ought to belong. The utility of each node is defined to depend entirely on the node’s local neighborhood. A Nash stable partition (NSP) of this game is a partition consisting of communities such that no node has incentive to defect from its community to any other community. Given any graph, we prove that an NSP always exists and we also derive a lower bound on the fraction of intra-community edges in any NSP. Our approach leads to an efficient heuristic algorithm to detect communities in social networks with the additional feature of automatically determining the number of communities.
The focus of the third problem is to understand the patterns behind the evolution of social networks that helps in predicting the likely topologies of social networks. The topology of social networks plays a crucial role in determining the outcomes in several social and economic situations such as trading networks, recommendation networks. We approach the problem of topology prediction in networks by defining a game theoretic model, which we call value function -allocation rule model, that considers four determinants of network formation. This model uses techniques from both cooperative game theory and non-cooperative game theory. We characterize the topologies of networks that are in equilibrium and/or socially efficient. Finally, we study the tradeoﬀs between equilibrium networks and efficient networks.2014-07-31T18:30:00ZTwo Player Game Variant Of The Erdos Szekeres ProblemParikshit, Khttp://hdl.handle.net/2005/23522014-08-01T09:43:03Z2014-07-31T18:30:00ZTitle: Two Player Game Variant Of The Erdos Szekeres Problem
Authors: Parikshit, K
Abstract: The following problem has been known for its beauty and elementary character. The Erd˝os Szekeres problem[7]:
For any integer k ≥ 3, determine if there exists a smallest positive integer N(k) such that any set of atleast N(k) points in general position in the plane(i.e no three points are in a line) contains k points that are the vertices of a convex k-gon.
The finiteness of (k)is proved by Erd˝os and Szekeres using Ramsey theory[7].
In 1978, Erd˝os [6] raised a similar question on empty convex k-gon (convex k-gon without out any interior points) and it has been extensively studied[18]. Several other variants like the convex k-gon with specified number interior points[2] and the chromatic variant[5] have been well studied.
In this thesis, we introduce the following two player game variant of the Erd˝os Szekeres problem: Consider a two player game where each player places a point in the plane such that the point set formed will not contain a convex k-gon. The game will end when a convex k-gon is formed and the player who placed the last point loses the game. In our thesis we show a winning strategy forplayer2inthe convex5-gongame and the empty convex5-gongame and argue that the game always ends in the 9th step.
We also give an alternative proof for the statement that any point set containing 10 or more points contains an empty convex 5-gon.2014-07-31T18:30:00Z