Internal Structure And Dynamic Decisions For Coalitions On Graphs

Abstract

The notions of collaboration, advantage, cost and impact are investigated in this dissertation, following are the details. Contribution to Cooperation between Agents for Routing in an Unknown Graph Using Reinforcement LearningFirst of all this work investigates the cooperation between agents to achieve a common goal. The problem of steering a swarm of autonomous agents out of an unknown maze to some goal located at an unknown location is discussed in this context. The routing algorithm given here provides a mechanism for storing data based on the experiences of previous agents visiting a node that results in routing decisions that improve with time.Contribution to Coalitional Advantage in Agents and Structure in Coalitions on GraphsNext a certain graphical coalitional game is introduced, where the internal topology of the coalition depends on a prescribed communication graph structure among the agents. Three measures of the contributions of agents to a coalition are introduced: marginal contribution, competitive contribution, and altruistic contribution. Results are established regarding the dependence of these three types of contributions on the graph topology, and changes in these contributions due to changes in graph topology. Based on these different contributions, three online sequential decision games are defined on top of the graphical coalitional game. The stable graphs under each of these sequential decision games are studied. Contribution to Coalitional Cost and Advantage in Agents and Structure in Coalitions on GraphsHere a Positional Cost is also introduced. Based on the advantage and cost, a notion of Net Payoff or Allocation is defined; this notion is used to further define three measures of net advantages. Taking maximization of these measures of net advantages as the objective functions of agents, three online sequential decision games are defined. A threshold of cost is reached above which no agent is interested to stay in a coalition irrespective of their motives.Contribution to Coalitional Advantage in Agents and Structure in Coalitions on DigraphsNovel digraph structures, are defined. The marginal contribution made by an agent in a digraph is introduced. Results are established regarding the dependence of marginal contributions on the graph topology, and changes in these contributions due to changes in graph topology. Based on marginal contributions, and by varying the rules of the game, three online sequential decision games are defined on top of the graphical coalitional game. The stable graphs under each of these sequential decision games are studied, and give the structures of the coalitions that form in each sequential game.Contribution to Coalitional Impact of Agents on Other AgentsFinally the notion of impact of one agent in the coalition upon the other agents is investigated, and a complete impact propagation framework is proposed. The analogy of impact propagation is use to present a comprehensive, and integrated framework to compute the impact made by a scientific work, a scientist, an institution, and a scientific journal.