Cooperation is a central topic in multiagent systems research. In typical scenarios, agents, with only limited information and capabilities, must cooperate with others to achieve their goals. However, as agents are often only interested in their own welfare, cooperation takes place only if they gain by doing so. How benefits are divided, therefore, plays a crucial role in determining the success of partnerships.
In my thesis, I study the problem of payoff division using coalitional game theory. This theory examines how to divide payoffs among agents so as to achieve fairness and stability. My contributions include both computational and conceptual advances of the theory. From a computational standpoint, I investigate how to efficiently find "good" division of payoffs. From a conceptual standpoint, I study how to extend the theory to capture characteristics of realistic multiagent systems.
First, I propose two new schemes for representing coalitional games— marginal contribution nets and multi-attribute representation. I show that these schemes generalize past approaches, and reduce the space required to represent coalitional games by significant amounts. Further, they confer concomitant savings in computation—by exploiting the structure exposed by these schemes, I develop algorithms that efficiently find fair and stable payoff divisions in these games.
Second, I examine how to model updates and uncertainties in coalitional games. Both concepts are important for modeling multiagent systems in practice. For updates, I study how to efficiently update payoff divisions to maintain fairness or stability as the underlying game evolves. For uncertainties, I introduce Bayesian coalitional games which extend classical coalitional game theory to account for imperfect information, and I generalize the stability criterion of the core to the new setting.
|Advisor:||Shoham, Yoav, Goel, Ashish, Roughgarden, Tim|
|School Location:||United States -- California|
|Source:||DAI-B 69/05, Dissertation Abstracts International|
|Subjects:||Economic theory, Computer science|
|Keywords:||Algorithms, Coalitional games, Complexity, Cooperative game theory, Multiagent systems, Representation|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be