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.
Organisations
Publications
Buermann J
(2020)
Multi-Robot Adversarial Patrolling Strategies via Lattice Paths
Buermann J
(2020)
Fair Allocation of Resources with Uncertain Availability
Buermann J
(2022)
Multi-robot adversarial patrolling strategies via lattice paths
in Artificial Intelligence
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N509747/1 | 30/09/2016 | 29/09/2021 | |||
| 1953259 | Studentship | EP/N509747/1 | 30/09/2017 | 31/12/2020 | Jan Burmann |
| Description | Two settings of efficiently using resources in uncertain settings have been considered and several fundamental results have been achieved. The first setting is a new problem of fairly dividing a homogeneous resource with uncertain availability which has been mathematically modelled. 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 their 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. 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. The second setting is in the area of security and considers the optimal usage of robots to patrol perimeters and fences. In the problem it is assumed that an intruder is able to learn the strategy of the robots and therefore is able to attempt to breach the perimeter at the least defended position. The aim is to determine a strategy that under this assumption still has the highest probability of detecting the intruder. The work has determined the possible strategies in a new way utilising a combinatorial modelling called lattice paths. This contributes to understand possible strategies and their results better as well as allows the calculation of optimal strategies to be done significantly faster. The introduction of the combinatorial technique may be applied to other related settings considering more complicated intrusion attempts or wider areas, and therefore further contribute to the field of patrolling and security in general. |
| Exploitation Route | For the resource allocation problem, 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. For the patrolling problem, the research establishes a new technique which can be applied to analyse and devise patrolling strategies. Hence, it could be applied to several related settings. Furthermore, the presented algorithms to calculate patrolling strategies could be used to program the behaviour of patrolling robots. The speed-up provided allows strategies to be updated or calculated closer to real-time and with less storage than previously possible. |
| Sectors | Aerospace Defence and Marine Communities and Social Services/Policy Digital/Communication/Information Technologies (including Software) Energy Environment |