Agreement, Information and Time in Multiagent Systems

Lakkaraju, Kiran

Permalink

https://hdl.handle.net/2142/14569 Copy

Description

Title

Agreement, Information and Time in Multiagent Systems

Author(s)

Lakkaraju, Kiran

Issue Date

2010-01-06T16:12:40Z

Director of Research (if dissertation) or Advisor (if thesis)

Gasser, Les

Doctoral Committee Chair(s)

Gasser, Les

Committee Member(s)

• Agha, Gul A.
• Gupta, Indranil
• Gmytrasiewicz, Piotr
• Swarup, Samarth

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Multiagent Systems
• Agreement Problems
• Emergence of Norms and Conventions.

Abstract

This dissertation studies multiagent agreement problems -- problems in which a population of agents must agree on some quantity or behavior in a distributed manner. Agreement problems are central in many areas, from the study of magnetism (Ising model), to understanding the diffusion of innovations (such as the diffusion of hybrid corn planting in Illinois), to modeling linguistic change. The thesis of this dissertation is that the ability for agents to optimally allocate resources towards 1) gaining information from which to infer the agreeing population's global agreement state (``information gathering'') and 2) effectively using that information to make convergence decisions that move towards agreement (``information use''), are the fundamental factors that explain the performance of a distributed agreement-seeking collective, and that variations on these processes capture all prevalent styles of agreement problems. In this dissertation we develop a taxonomic framework that organizes a wide range of agreement problems according to constraints on information gathering and information use. We explore two specific instances of agreement problems in more depth; the first modulates information gathering by constraining the ability of agents to communicate; the second modulates information use by constraining the ability of agents to change states. An understanding of these two components will allow the application of insights from fields such as statistical physics, distributed algorithms, and multiagent systems to bear on language -- and in turn carry insights from linguistic agreement to these fields. Note, however, that the purpose of this dissertation is not to model natural phenomena, but rather to explore, through abstract models, some of the fundamental processes that underlie natural phenomena. Our first contribution is to develop the \emph{Distributed Optimal Agreement} framework -- a taxonomic framework through which we can formally identify potential constraints on the two processes of information gathering and use. Our second contribution is to develop an understanding of the \emph{Fundamental Agreement Tradeoff}, which is a relation between the effort an agent expends to gather information, the accuracy of the information gathered, and the amount of time it takes for a population to reach agreement. We develop the \gssm\ process as a way to explore the fundamental agreement tradeoff by modulating the amount of effort an agent can expend, which in turn affects the accuracy of information gathered. We show, surprisingly, that a population can reach agreement quickly even with a minimal expenditure of effort. This result has impact for any setting in which communication is a resource intensive procedure (e.g., energy constrained sensor networks). We provide extensive numerical simulations of the \gssm\ process in a variety of settings. In addition, we we analytically show that the \gssm\ process reaches agreement under a mean-field assumption. Our third contribution is to study agreement in complex spaces with boundedly rational agents where there are significant restrictions on communication. We develop the \emph{Distributed Constraint Agreement} problem (which itself is a type of agreement problem that can be captured by the DOA framework) in order to explore the impact of bounded rationality and communication on agreement in complex spaces. As an example scenario we abstractly model the linguistic phenomenon of the Great English Vowel Shift (GEVS) -- a shift in the pronunciation of certain vowels that took place between 1450 and 1750. We define a simple algorithm and through extensive simulation show that a vowel shift could have occurred if a new population of linguistic users, with slightly different pronunciations, entered the linguistic community. These results lend support to the ``migration'' hypothesis for the GEVS -- that due to casualties from the Black Death the linguistic composition of upper class England changed to incorporate individuals with different pronunciations. Together, these three contributions move us closer to forming a general theory of agreement.

Graduation Semester

2009-12

Permalink

http://hdl.handle.net/2142/14569

Copyright and License Information

Copyright 2009 Kiran Lakkaraju

Owning Collections