Auctions, Evolution, and Multi-agent Learning
For a number of years we have been working towards the goal of automatically creating auction mechanisms, using a range of techniques from evolutionary and multi-agent learning. This paper gives an overview of this work. The paper presents results from se
- PDF / 1,261,087 Bytes
- 23 Pages / 430 x 660 pts Page_size
- 70 Downloads / 200 Views
Department of Computer Science, University of Liverpool, Ashton Building, Ashton Street, Liverpool L69, 3BX [email protected], [email protected] 2 Department of Computer Science, Graduate Center, City University of New York, 365 5th Avenue, New York, NY 10016, USA {kcai,jniu}@gc.cuny.edu 3 Department of Computer and Information Science, Brooklyn College, City University of New York, 2900 Bedford Avenue, Brooklyn, NY 11210, USA {parsons,sklar}@sci.brooklyn.cuny.edu
Abstract. For a number of years we have been working towards the goal of automatically creating auction mechanisms, using a range of techniques from evolutionary and multi-agent learning. This paper gives an overview of this work. The paper presents results from several experiments that we have carried out, and tries to place these in the context of the overall task that we are engaged in.
1 Introduction The allocation of resources between a set of agents is a challenging problem, and one that has been much studied in artificial intelligence. Resource allocation problems are especially difficult to solve efficiently in an open system if the values that agents place on resources, or the values of their human principals, are private and unobservable. In such a situation, the difficulty facing somebody wishing to allocate the resources to those who value them most highly, is that participating agents cannot necessarily be relied upon to report those values truthfully — there is nothing to prevent “greedy” agents from exaggerating their resource requirements. To overcome this problem, it has been suggested that resource allocation be solved using market mechanisms [4,32,59] in which agents support their value-claims with hard cash. This has two advantages. First it punishes greedy agents by making them pay for the resources that they have oversubscribed to. (Alternatively one can think of this as preventing agents from oversubscribing by forcing them to pay a higher price than they would otherwise have to pay for the resources they actually need.) Second, it allocates resources to the agents who pay the most, which should be the agents who value the resources most highly. Auctions are a subclass of market mechanisms that have received particular attention. This is due to the fact that, when well designed, auctions can achieve desired economic outcomes like high allocative efficiency. Designing mechanisms to achieve specific economic requirements, such high efficiency or maximal social welfare, against self-interested intelligent traders, is no trivial matter, as can be seen from accounts of the auction design process for the recent radio spectrum auctions in Europe [25] and the US [11,30]. The economic theory of K. Tuyls et al. (Eds.): Adaptive Agents and MAS III, LNAI 4865, pp. 188–210, 2008. c Springer-Verlag Berlin Heidelberg 2008
Auctions, Evolution, and Multi-agent Learning
189
mechanism design [20] approaches the task of designing efficient resource allocation mechanisms by studying the formal, analytical properties of alternative
Data Loading...
