Grant: Discovery Grants Program - Individual
University of British Columbia
$24,000.00
Competitive Multiagent Systems: Bridging the Gap between Theory and Practice
EF 2008-09
Résumé
Competitive multiagent systems are environments in which two or more self-interested agents interact. It is this ingredient of self-interest that makes a multiagent system ``competitive": agents' desires cannot be relied upon to coincide. Game theory is the dominant approach used to study such environments. Unfortunately, a significant gap still exists between theory and practice. For example, game-theoretic models are typically very small and are built on the assumptions that agents are omniscient (hold no false beliefs) and utility-maximizing (computationally-unbounded). Even if such an agent did exist, existing theories would not tell him how to reason about more limited competitors. Approaches to resource allocation usually assume that goods for sale cannot be resold and are unique (i.e., they are available only in the one-shot market being designed), that agents face no transaction costs or budgets, that markets can be redesigned without any constraints, and that agents know their valuations for the goods being allocated. In practical settings of interest, some or even all of these assumptions can fail to hold.
I aim to join the researchers who are taking steps towards bridging this gap. This task will not be accomplished easily or all at once: it is not for a lack of effort or insight that current theories have been unable to move beyond the restrictive assumptions mentioned above. However, past work has shown that it is often possible to make game-theoretic models better reflect practical domains when doing so is the explicit focus of the work. Furthermore, the computational approach offers promise: techniques like simulation, approximation and adaptation offer hope in settings where the analytical methods usually favoured by game theorists have fallen short. Because of the fundamental importance of the research problem---both to computer science and to the economy---a research push in this direction is needed.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
298165-2007
Name nom
LeytonBrown, Kevin
Department département
Computer Science
Organization id
2
Institution établissement
University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2008
Competition year année de concours
2007
Award amount
24000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
9999
Area of application group en
Not available
Area of application group fr
Non disponible
Area of application en
Not available
Area of application fr
Non disponible
Research subject code
2800
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Artificial intelligence (computer vision, use2603)
Research subject fr
Intelligence artificielle (vision artificielle, utiliser 2603)
Partie
2
Nb partie
5
Application title
Competitive Multiagent Systems: Bridging the Gap between Theory and Practice
Keyword
NA
Application summary
Competitive multiagent systems are environments in which two or more self-interested agents interact. It is this ingredient of self-interest that makes a multiagent system ``competitive": agents' desires cannot be relied upon to coincide. Game theory is the dominant approach used to study such environments. Unfortunately, a significant gap still exists between theory and practice. For example, game-theoretic models are typically very small and are built on the assumptions that agents are omniscient (hold no false beliefs) and utility-maximizing (computationally-unbounded). Even if such an agent did exist, existing theories would not tell him how to reason about more limited competitors. Approaches to resource allocation usually assume that goods for sale cannot be resold and are unique (i.e., they are available only in the one-shot market being designed), that agents face no transaction costs or budgets, that markets can be redesigned without any constraints, and that agents know their valuations for the goods being allocated. In practical settings of interest, some or even all of these assumptions can fail to hold.
I aim to join the researchers who are taking steps towards bridging this gap. This task will not be accomplished easily or all at once: it is not for a lack of effort or insight that current theories have been unable to move beyond the restrictive assumptions mentioned above. However, past work has shown that it is often possible to make game-theoretic models better reflect practical domains when doing so is the explicit focus of the work. Furthermore, the computational approach offers promise: techniques like simulation, approximation and adaptation offer hope in settings where the analytical methods usually favoured by game theorists have fallen short. Because of the fundamental importance of the research problem---both to computer science and to the economy---a research push in this direction is needed.