The futurists of tomorrow may have cause to thank Professor Peter Butkovič and Daniel Jones: the two Birmingham mathematicians have solved aspects of a max-algebra problem that is linked to game theory.
The futurists of tomorrow may have cause to thank Professor Peter Butkovič and Daniel Jones: the two Birmingham mathematicians have solved aspects of a max-algebra problem that is linked to game theory.
For Peter, who has been studying this area of mathematics for more than 40 years and is one of the world’s leading researchers in the field, the discovery came as a welcome surprise – in addition to what was already an exciting breakthrough.
‘I never expected there would be a link to game theory,’ admits Peter, Professor of Applied Discrete Mathematics and Deputy Head of the School of Mathematics. ‘Daniel and I verified the proof several times because we were so surprised. And it may turn out to be more important than we think it is.’
Daniel, one of Peter’s PhD students, adds: ‘Game theory is very popular at the moment; our research could be where the progress comes from.’
Peter and Daniel’s findings are detailed in a paper entitled ‘On special cases of the generalised max-plus eigenproblem’, which was published in the prestigious SIAM journal on matrix analysis and applications earlier this year and won them the College’s Paper of the Month award.
The long-standing problem the article addresses is known as the generalised max-plus eigenproblem (GEP), part of max-algebra (also known as tropical linear algebra or path algebra), which is an analogue of linear algebra where the operation of addition is replaced by maximisation and multiplication by conventional addition.
The first pioneer of max-algebra was Professor Ray Cuninghame-Green, whose initial paper was published in 1960 while he was working in the steel industry in Sheffield. ‘Ray was probably the first to realise that the maximum cycle mean is the principal max-algebraic eigenvalue of a matrix,’ says Peter. In 1975, Ray was appointed Professor of Industrial Mathematics at Birmingham; ten years later he and Peter met at a conference. ‘We started collaborating and carried on doing so for a very fruitful 20 years.’
Max-algebra was born out of trying to solve real-life problems in the Yorkshire steelworks, namely how to make operational tasks, such as production management, more time-efficient. ‘They were looking for a best organisation of production activities and they realised that a smart way of doing this would be to use mathematics where addition is replaced with maximisation,’ explains Peter.
To use a culinary analogy, if you want to serve up spaghetti Bolognese, you need to cook some spaghetti and you need to cook a sauce. If your family asks when they can expect to eat the dish, the answer is the greater of the two amounts of time needed to cook both elements. In an industrial environment, there may be hundreds of activities whose performance cannot be initiated before some other activities are completed.
Although seemingly simple, as is often the case in mathematics, this fast-growing area has many open problems, one of which is GEP.
‘The whole theory is about arranging processes in the most efficient way, and one related question is this: if you have two processes, such as industrial processes, you may wish to synchronise them so that they finish at the same time,’ explains Peter. ‘So it’s not just about doing something as quickly as possible, but also about synchronisation.’
There is a particular synchronisation problem that can be modelled as GEP and for which there is no efficient solution method yet known. There are, however, ‘very good reasons’ to believe that efficient solvability is possible.
‘There is excitement among our colleagues working in max-algebra that it’s not very long before we have an efficient solution that will be a big game-changer,’ declares Peter. ‘So we are trying to contribute toward this, and what our paper does is to show that certain special cases of this problem are indeed solvable. So it’s not – so far – solving the full generality, but there are a number of special cases that we can solve efficiently.’
‘We think these special cases are important in the sense that we have used new methods to solve them,’ says Daniel, who is in the fourth year of his PhD.
Peter adds: ‘This paper presents new approaches that could eventually lead to the resolution of the general case. In particular, it’s linking the problem with game theory. This provides an extra hope that it will be possible to do something in the near future to bring the problem to a general successful conclusion.’
