Mechanism Design for the Reliable Distribution of Resources

Lead Research Organisation: University of Southampton
Department Name: Electronics and Computer Science

Abstract

The world is becoming more and more technology driven, with more reliance and dependence on computers by all age groups. Increased computation allows different service providers the opportunity for better resource allocation for their clients whilst simultaneously enabling clients to better adjust variable factors to suit their lifestyle or needs. Areas of application include the smart grid which allows more fine grained control over electricity distribution including local energy exchanges as well as electric vehicle charging; and the allocation and pricing of parking spaces. Despite their differences in service and circumstance, these problems exhibit similar challenges with optimal resource distribution. In this project, we will apply mechanism design and find mechanisms that allow efficient allocation of resources whilst taking into account the rational behaviour of participants as well as other potential uncertainties. Hence, we aim to improve system usage and efficacy by designing algorithms that not only ensure good distribution of resources, but also work robustly under uncertainty and guarantee that all users can confidently utilise the system without the risk of selfish behaviour costing their use of the system.

Publications

10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/N509747/1 01/10/2016 30/09/2021
1953259 Studentship EP/N509747/1 01/10/2017 30/09/2020 Jan Burmann
 
Description A new problem of fairly dividing a homogeneous resource with uncertain availability has been mathematically modelled and some fundamental results have been achieved. In more detail, the work considered the problem of homogeneous divisible resources. Resource of this type include electricity, estates, storage space, bandwidth or (processing) time. Despite its importance, the division of homogeneous resources has received less attention than other fair division problems. This is especially true when the availability of the resource is uncertain. An example of uncertain resources and the relevance are local energy markets which use renewable energy sources to supply local households. The available amount of energy is not known before the moment of production e.g. photovoltaic production depends on the weather.

The problem has been modelled as a fair division problem where the resource has to be allocated to several agents (e.g. parties, households or people). The uncertain resource is modelled as different amounts of resource each available with a specified probability. The agents have been modelled to prefer amounts of energy dependent on the probability of the allocated amounts. For the fairness criterion, envy-freeness has been considered. Envy-freeness is a natural fairness criterion which requires that no agent prefers another agent's allocation over his/her own.

The work has established some results. Firstly, that the problem is intractable in the sense of computational complexity, i.e. finding an optimal solution might require more resources than adequate. Secondly, that there can be a big trade-off between fairness and efficiency, where efficiency refers to giving the resource to the agent who needs it the most. Thirdly, an algorithm for small numbers of agents which are satisfied with a specified amount of resource has be devised.

The work opens up further research question. These include trade-offs between fairness and efficiency. In particular, finding an algorithm that allows finding solutions of diminished efficiency but which is available in reasonable time. Moreover, the problem so far assumes that the agents cooperate with the system. Another interesting research question would be to analyse the effects of self-interested agents.
Exploitation Route The outcomes establish a new problem with real world applications and various directions for further research. Academically, the results form the foundations of the problem. There are numerous directions to further investigate this problem. Moreover, the problem highlights how a problem inherent uncertainty can enrich the possibilities. This might be applicable to related areas.

At this point, the results are quite technical with limited direct non-academic application. Nevertheless, the results and possible future results have implications and are interesting to various areas. This includes the aforementioned energy sector and future energy systems. Moreover, one of the outcomes so far is a first algorithm to distribute uncertain available homogeneous resources for smaller instances.
Sectors Communities and Social Services/Policy,Digital/Communication/Information Technologies (including Software),Energy