logo epfl    School of Computer and Communication Sciences I&C LIA logo
Ecole Polytechnique Fédérale de Lausanne

EPFL > IC > LIA > Application Domains > Resource allocation

Artificial Intelligence Laboratory LIA


 

Resource allocation

Resource allocation is the problem of assigning a set of resources to tasks which need to be carried out. This assignment must respect two constraints: the resources must be capable of executing the task, and they must be available during the time that the task must be executed. Resource allocation is a fundamental problem with many practical applications. At the LIA, we have developed techniques for decomposing the problem into subparts which can be solved independently.

Distributed resource allocation is a special case of resource allocation, where the task of allocating the resources is distributed among a set of agents. In this direction, we have experimented with distributed resource allocation in a sensor network, and proposed some improvements to existing techniques.

Current projects:

  • Distributed Service Placements in a Peer-to-Peer Network: in this setting we have considered problems where a set of self-interested agents want to each place in-network processing operators on a set of servers. Each agent has its own private preferences about different combinations of operator placements. Each server in the overlay network is able to perform some set of operators, and servers differ in their network and computational characteristics. The task is to provide a distributed algorithm that finds the globally optimal allocation of operators to servers, such that the overall utility of all users is maximized. For more details, please refer to [Faltings et al., 2006].
  • Distributed Combinatorial Auctions: Combinatorial Auctions (CAs) are a popular means to allocate resources to multiple agents. In Cas, bidders can bid on bundles of goods (as opposed to bidding on single goods). Combinatorial bids can model both complementarity and substitutability among the goods, i.e. when the valuation for the bundle is more, respectively less than the sum of the valuations for individual items. In our setting the agents are distributed (geographically or logically), and form a problem graph in which neighbors are agents with whom their bids overlap. The objective is to find the feasible solution (i.e. declare bids as winning or losing such that no two winning bids share a good) that maximizes the total utility of the agents. Combinatorial auctions can be adopted as a stylized model of distributed allocation problems such as airport slot allocation and wireless spectrum allocation as discussed in the Introduction. In our DCOP model, each agent holds a variable for each one of its bids, with two possible values: 0 when the bid is rejected, and 1 when the bid is accepted. Any pair of overlapping bids (bids that share at least one good) is connected by a "at most one" constraint that specifies that they cannot be both accepted. When multiple bids are submitted by an agent then they can be connected by additional constraints to capture the bid logic, for instance exclusive-or constraints if only one bid can be accepted.

Past projects:

© 2011 EPFL all rights reserved Login