Fair Division: How Mathematics Helps to Divide the Indivisible

Photo courtesy of Alexander Karpov

How can items be allocated among participants so that no one feels short-changed? Alexander Karpov, Assistant Professor at the Faculty of Economic Sciences, and his Singaporean colleague, Prof. Warut Suksompong, set out to find a mathematical answer to this question. In this interview, they discuss how a model of rational preferences is constructed, why one cannot rely on a simple sum of values, and where an algorithm that asks a minimal number of questions can be useful.

This article continues a series of publications devoted to the outcomes of long-term academic fellowships.

Alexander Karpov

— You worked with Prof. Warut Suksompong from the School of Computing at the National University of Singapore. How did you meet, and how did your collaboration develop?

— Warut Suksompong’s research interests are close to my own. We study computational problems in social choice theory. We did not know each other personally, but we have co-authors in common, and I was familiar with some of his work. As soon as the fellowship competition was announced, I wrote to him proposing a joint project, and he immediately agreed.

— Could you tell us about your research? What problem did you tackle with your Singaporean colleague?

— I work on developing mathematical models of collective preferences. As an illustration, one can look at voting models: they construct a single scale of the political spectrum (for example, right–left), and a voter’s preferences are determined by how far candidates are from their own position. In a similar way, other problems give rise to different structured systems of preferences.

Inspired by Prof. Suksompong’s work, which focuses on fair division problems, I proposed creating a model of participants’ preferences in such divisions.

A fair division problem is formulated as follows: there is a set of indivisible items that must be distributed among participants. The goal is to design an allocation algorithm that ensures a ‘fair’ division for any possible set of participants’ preferences. However, due to the enormous variety of possible preferences, there is no algorithm that satisfies all desirable properties simultaneously.

Our key objective is to construct a model of rational preferences for participants in a division and to formulate requirements for such preferences. Examples of these requirements include:

• Monotonicity. If set A contains all the items in set B plus some additional ones, then A is preferred to B.
• Independence. Preferences between sets should remain unchanged when identical items are added to both sets. For example, if ‘meat with potatoes’ is preferred to ‘pasta with fish’, this relationship should remain the same after adding a drink to each set.

As part of the study, we developed an algorithm for testing whether preferences satisfy the basic requirements of rationality, and we designed a preference elicitation algorithm that makes it possible to determine an individual’s preferences using the minimum possible number of questions, provided that those preferences possess known structural properties.

The traditional approach in applied research assumes that the value of a bundle is equal to the sum of the values of its elements. However, such a model is overly simplistic and does not reflect real human preferences. Therefore, the search for a compact mathematical model capable of describing a broad class of preferences remains an important scientific challenge.

— The National University of Singapore is a place where researchers from all over the world come together, and Asia is now emerging as a powerful centre of mathematical economics. Is there any distinctive ‘Asian’ approach in the work of Prof. Warut Suksompong—who was educated in the West but works in Asia—or is decision science already fully global and unified?

— Science is universal, and I do not see differences in how problems are approached. However, the history of particular research centres often reflects the priorities of society and the state. The National University of Singapore developed with the goal of supporting Singapore’s economic growth. All fields related to advanced technologies are at the highest level here. This leads to uneven development across disciplines. For instance, in global rankings, the National University of Singapore tends to rank higher in computer science than in economic theory. Recently, of course, the university has sought to achieve top positions across all disciplines, including the humanities, but technological development was the original priority.

— Could you tell us about your fellowship experience? Does the academic culture in Singapore differ from that in Europe?

— The National University of Singapore is truly a city within a city: it offers everything needed for a full life. Four bus routes run across the campus, and there are food courts and sports facilities, as well as its own hospital and concert hall.

The campus architecture is striking: each building is not only functional but also aesthetically expressive. Interestingly, campus designers took into account the principles of feng shui. As someone far removed from this philosophy, I simply found it very beautiful.

The university is genuinely global: more than half of its professors are international. Singapore is an important international hub where the offices of major corporations are concentrated. There is a clear sense of global competition for talent: the university’s graduates are in demand worldwide.

This clearly distinguishes the National University of Singapore from many European universities, which are often located in smaller towns and, due to geography, are less integrated into global processes.

— Are there plans to publish the results of the fellowship?

— Yes, we plan to submit the paper to the International Conference on Autonomous Agents and Multiagent Systems (AAMAS). In computer science, conference proceedings are considered just as prestigious as journal publications.