Research On Auction And Coalition Formation In Multi-Agent Systems

Auction is a kind of resource allocation method. It is efficient and operational and can get maximal utility for every participant under suitable auction mechanisms. As an approach for negotiation, auction can be used in almost every aspect of multi agents systems (MAS). It can achieve different kinds of one to one or one to many allocations of tasks, resources or revenues according to the agent's computational capability, communication ability, the characters of resources, the demand of system quality such as real time property or maximal utility.In the study of multi agent auction, traditionally, resources are allocated according to price only. However, resources have not only one attribute. For a task, the attributes may include price, when the task will be finished, the quality the task finished etc. The consideration for multi attribute is a familiar sight existing in auction. This dissertation summarizes the existing problems of multi attribute auction and develops a new kind of multi attribute auction model, mainly studying work include:(1) A generalized auction model is presented. Based on the general model, a new kind of multi attribute auction model is developed, i.e., VAMA model. VAMA model is an extension of Vickrey auction in the multi attribute environment. Some useful properties have been proofed such as false-name proof and the strategies of seller and buyer in this model have been analyzed.(2) Usually, the mechanisms are centralized and been controlled by auctioneers. In an open environment, other participants cannot accept this and demand supervising the process of the mechanisms. Under this consideration, decentralized implement of a mechanism become important. Based the model of VAMA, a decentralized implement of VAMA is presented.(3) In multi agent auction, every participant has its bias, so they may give different price for some item. But, usually, they do not want to publish its bias for that may be taken advantage of in other occasions. The bias is its private information, in a good mechanism, it should consist of the protect mechanism.Aiming at this, a security multi attribute auction is presented. This model restricts the range of bids but it is easy understood. Furthermore, comparing to Felix Brandt's schema the fundament of security is extended.In addition, this dissertation discussed the relationship between auction and other multi agent technologies especially the coalition formation problem. Some useful approaches about the usage of auction method in coalition problem are presented.