| EPSRC Reference: |
EP/G000980/1 |
| Title: |
Designing Mechanisms for Automated Resource Allocation: A Case for Support |
| Principal Investigator: |
Fatima, Dr SS |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Loughborough University |
| Scheme: |
First Grant Scheme |
| Starts: |
30 October 2008 |
Ends: |
09 February 2012 |
Value (£): |
242,963
|
| EPSRC Research Topic Classifications: |
| Artificial Intelligence |
Fundamentals of Computing |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
05 Jun 2008
|
ICT Prioritisation Panel (June 2008)
|
Announced
|
|
|
Summary on Grant Application Form |
|
The proposed project aims to develop effective mechanisms for automating resource allocation (RA). The problem of resource allocation deals with the design of mechanisms for optimal allocation of a set of available resources to a set of participating agents that compete for them. These agents are self-interested and act strategically. This strategic behaviour affects the allocation of resources. Mechanisms must therefore be designed such that the allocation is optimal from a system wide perspective, despite the self-interest of the participants. RA has long been studied in game theory and economics, and mechanisms such as bargaining, auctions, and voting have been developed for optimal allocation of resources. However, because of new applications such as electronic trading that have arisen from the Internet, this problem is now receiving increasing attention in computer science. When considered in computer science, the goal is typically to automate the process of RA by implementing game theoretic mechanisms on computerized agents. However, this implementation is not straightforward. There are two main reasons for this. First, game theoretic mechanisms assume that the agents are perfectly rational (i.e., have unlimited computing power). However, in the context of automated RA that this project aims to focus on, the agents are computerized agents and have limited computational capabilities (i.e., they are boundedly rational). Moreover, these agents may have different computational capabilities (i.e., different rationalities). Hence, although game theoretic mechanisms are optimal in terms of allocation, they are hard to implement on machines with computational limitations. Second, game theoretic mechanisms are designed for scenarios in which RA is viewed as a one time activity in static environments. However, in many practical cases, RA must be done repeatedly in dynamic environments (i.e., in environments where the available resources and participants change with time). Against this background, the proposed research aims to design effective mechanisms that overcome these limitations. In order to achieve this goal, we aim to use game theory as a design principle but the primary emphasis will be on devising approximation algorithms for solving computationally hard RA problems. The focus will be on two types of mechanisms: bargaining (that involves two participant agents), and auctions and coalitions (that involve more than two participants). Within this context, the proposed project has the following main objectives: i) to design mechanisms that are approximately optimal in terms of their allocation but are computationally feasible, and ii) to investigate the economic consequences of computational limitations (i.e., how approximations affect the economic properties - both system level and individual level - with respect to the exactly optimal game theoretic mechanisms). Overall, this project has the potential to make it more attractive to use game theory as the basis for computing solutions to a range of practical problems such as electronic trading, and networks of distributed systems such as computational grids.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
http://www-staff.lboro.ac.uk/~cossf/EPSRC.html |
| Further Information: |
|
| Organisation Website: |
http://www.lboro.ac.uk |