Resource auctions

Problem description 

Distributed systems are anticipated to process complex events closer to where the data are generated. As an example, one may think about the software recognising car number plates for toll stations; One could send the photo of the car's number plate to a central server, but it would require less communication bandwidth to do the image processing in the camera or in a local server at the toll station and just send the registration number as a text string. Systems processing significant amount of data must therefore carefully consider where to do the computation, where to do the caching, and how much communication will be needed for different application deployment scenarios.  

Some of the resources needed will most likely be provided by third parties. Continuing the previous example one may have a different tall station operator than the company invoicing the car owners and needing the information about the number plate. One certainly also uses communication and the communication infrastructure is most likely owned by a telecom operator. Should the network operator have other requests for the bandwidth, like multimedia streaming from different content providers like Netflix and HBO, it may want to maximize the proffit made on the communication network by pricing the bandwidth as high as possible. In our example, this makes our distributed car plate detection a competitor for bandwidth with the content providers, and such conflicts can be resolved by auctions. 

Here, the telecom provider may iteratively increase the price of the bandwidth until there is only one company left with the highest bid. If the winner does not need the full bandwidth, a secondary auction may be organised among the initial losers for the remaining communication bandwidth resources.  

Even though this idea is conceptually simple, it is hard to implement in practice in a distributed system, and even harder if the resources are bundled. Say for instance that the local image processing server used to identify the licence plates close to the tall station is also owned by the telecom company and located in the local 5G base station. Now the situation becomes more complex for the company invoicing the car owners: It can participate to two auctions, one for the computation and one for the communication, but if bandwidth is sold cheaply, there may be no need for the computation as the full image can easily be sent to the company's servers. On the other hand, if the bandwidth is expensive, the company may be willing to bid much more for the computational capacity in the base station as it is the total processing and communication cost that the company wants to minimize. Hence, communication and computation is a 'bundle' and the company would desire to bid on the joint bundle and not on the individual resources. Other companies may have different bundles of their choice, and the auction becomes a combinatorial auction. 

Research questions 

  • How can such resource auctions best be organised? 

  • What is the complexity of reaching a final resource allocation? Number of iterations, number of bids, number and size of the communication between the buyers and the sellers. 

  • How to organise resource auctions for undividable items? For instance, if you cannot bid on 0.56 CPU but either on one CPU or two CPUs? 

  • How to move from individual resource auctions to bundles of resources with a joint common value (bid), but an unknown split of value among the components of the bundle? 

  • Is it possible to train a deep reinforcement learning algorithm to decide on the right prices and allocations of resources from the input and output of the existing auction mechanisms? 

Methodology 

  • Economists have won Nobel prizes for their contributions to auction theory, and the first step would be to investigate existing proposals and suggest a taxonomy of different approaches leading to the selecting of the most promising approaches for resource allocation in distributed systems. 

  • The most promising auction mechanisms must be implemented to evaluate numerically the complexity involved. 

  • Promising deep reinforcement learning architectures should be evaluated against the implemented mechanisms to assess quality, performance, and complexity of approximating the auction prices and outcome. 

What you will learn 

  • Auction theory and practice that is highly relevant for both allocation problems and the financial sector. 

  • Modern deep reinforcement learning approximations to solve complex optimisation problems. 

  • Modelling large scale multi-tenant distributed systems with both resource providers and consumers. 

  • To assess and approach inherent barriers on scalability of complex combinatorial optimisation problems. 

References 

  • Peter Cramton et al. (2006): “Combinatorial auctions”, ISBN 978-0-262-03342-8, MIT Press 

Published Oct. 3, 2024 4:43 PM - Last modified Oct. 3, 2024 4:43 PM

Supervisor(s)

Scope (credits)

60