How to reach a joint decision with the smallest need for compromise Open Access

Need for joint decision-making. In many practical situations, people need to come up with a joint decision. For example, a country may need to select financial measures to boost the economy and decrease unemployment, a city may need to improve its public transportation system, etc.

To make a joint decision, we need to select an objective function. In each decision-making process, there are some numerical characteristics x₁, …, x_n that describe possible decisions. For example, in a country the quality of a decision can be characterized by the resulting increase in GDP x₁, the resulting decrease in unemployment x₂, etc. For a city-wide public transportation project, x₁ can be the decrease in average commute time, x₂ can be the decrease in pollution caused by cars, etc.

In general, everyone agrees that each of these characteristics should be as large as possible. The problem is that it is usually impossible to increase all of them. For example, one way to boost the country's gross domestic product (GDP) would be to outsource low-paying jobs to other countries and save money, but this may increase unemployment. In general, it is not possible to maximize two different objective functions: usually, when we maximize one of them, this does not make other objective functions maximum. Thus, when we make a decision, we need to select a single objective function u(x₁, …, x_n) that we should maximize.

Possibility of linearization. In many real-life situations, we are talking about decisions that, while important, do not drastically change our lives. For example, while it is desirable to have a better public transportation system, the resulting average decrease of, e.g. 10 min per day of commute time does not lead to a radical change in people's lives and habits. In such situations, the changes x_i are reasonably small. When the changes x_i are small, terms which are quadratic (or even higher order) in terms of x_i are much smaller than x_i and can, thus, be safely ignored in comparison with terms which are linear in x_i. Thus, we can expand the desired objective function in Taylor series and only keep linear terms in this expansion, i.e. consider objective functions of the type

As we have mentioned, for each of the characteristics x_i, the larger its value, the better. This means that increasing x_i should lead to a larger value of this objective function, i.e. that all coefficients c_i should be positive.

Let us simplify. If we take formula (1) literally, this would mean that to make a joint decision, we need to select n + 1 parameters c₀, c₁, …, c_n. The more parameters we need to select, the more complicated the selection task. We can make this task somewhat easier if we take into account that maximizing a function u(x₁, …, x_n) is equivalent to maximizing a “shifted” function u(x₁, …, x_n) − c₀. Indeed, which of the two numbers is larger will not change if we subtract the same constant from both numbers. The shifted objective function has a simplified form

where we only have n coefficients to determine.

We can simplify the situation even further if we take into account that which of the two numbers is larger will not change if we divide both numbers by the same positive constant. Thus, for each constant C, maximizing a function u(x₁, …, x_n) is equivalent to maximizing a “re-scaled” function u(x₁, …, x_n)/C. If we take C = c₁ + ⋯ + c_n, then we arrive at the problem of maximizing the expression

where the values

satisfy the condition

We will call the expression (2) a normalized utility function.

Because of condition (2), to describe a normalized utility function, we need to select n − 1 coefficients: e.g. once we have selected a₁, …, a_n−1, then we can use equation (3) to determine a_n as a_n = 1 − (a₁ + ⋯ + a_n−1).

What we mean by a compromise. Suppose that we have a group of p participants with normalized utility functions U₁(x), …, U_p(x). Based on these normalized utility functions, we need to form a new normalized utility function that the group will use to make a decision. A natural requirement is that if all p participants prefer an alternative x to an alternative y, then the group should also prefer x to y. Thus, we arrive at the following definition.

It is desirable to minimize compromising. The more people one has to coordinate a decision with, the fewer chances that each person's preferences will be properly taken into account. Therefore, when a large group of people need to make a decision, it is desirable to make sure that this decision can be reached by dividing all the people into small-size groups so that this decision can reach a compromise between the members of each group.

Resulting problem. In view of the above, it is important to find the smallest possible group size for which such a joint decision is always possible.

What we do in this paper. In this paper, we provide a solution to this problem. It turns out that this smallest size is n.

Relation to convexity. Our proof is based on the notion of convexity; see, e.g. Rockafeller (1997). For every finite set of points $a(1)=a1(1),…,an(1)$⁠, …, $a(k)=a1(k),…,an(k)$⁠, by their convex combination, we mean a point a = (a₁, …, a_n) for which

for some α_j ≥ 0 for which α₁ + ⋯ + α_k = 1, i.e. for which, for every i from 1 to n, we have

The set of all convex combinations is known as the convex hull of the points a⁽¹⁾, …, a^(k).

The relation between convexity and our problem is provided by the following lemma. To formulate this lemma, we will say that a normalized utility function U(x) = a₁ ⋅ x₁ + ⋯ + a_n ⋅ x_n is characterized by the point a = (a₁, …, a_n).

Proof of lemma. Let us first prove that if the point a⁽⁰⁾ is a convex combination of the points a⁽¹⁾, …, a^(p), i.e. if

for some non-negative coefficients α_j that add up to 1, then U₀(x) is a compromise between normalized utility functions U₁(x), …, U_p(x).

Indeed, let x = (x₁, …, x_n) and y = (y₁, …, y_n) be two alternatives for which U_j(x) ≥ U_j(y) for all i, i.e. for which

If we multiply both sides of this inequality by a non-negative number α_j ≥ 0, we conclude that

Adding the inequalities (5) corresponding to j = 1, …, p, we get

Taking into account formula (4), we conclude that

i.e. that U₀(x) ≥ U₀(y). So, U₀(x) is indeed a compromise between the normalized utility functions U₁(x), …, U_p(x).

Vice versa, let us prove that if U₀(x) is a compromise between normalized utility functions U₁(x), …, U_p(x), then the point a⁽⁰⁾ is a convex combination of the points a⁽¹⁾, …, a^(p). Let us prove this by contradiction. Let us assume that the point a⁽⁰⁾ that satisfies condition (3) is not a convex combination of the points a⁽¹⁾, …, a^(p); in other words, the point a does not belong to the convex hull of the points a⁽¹⁾, …, a^(p). All the points a⁽⁰⁾, a⁽¹⁾, …, a^(p) satisfy condition (3) and are, thus, located on a plane defined by this condition.

By the properties of convex sets, if two closed convex sets do not intersect, there exists a separating plane. A single point is, of course, a convex set, so there exists a plane that separates the point a⁽⁰⁾ from the points a⁽¹⁾, …, a^(p). If we connect all the points from this plane to the point (0, …, 0), we get a plane passing through 0 that separates the point a from all the points a^(j). In general, such a plane has the form

for some coefficients x_i. For the points on two sides of this plane, the expression a₁ ⋅ x₁ + ⋯ + a_n ⋅ x_n has different signs. Thus, the fact that the plane separates these points means that for the point a⁽⁰⁾ and for the points a^(j), this expression has different signs.

If the sign is negative for a⁽⁰⁾ and positive for all the points a^(j) with j ≥ 1, then we have U_j(x) > 0 for all j = 1, …, p and U₀(x) < 0. Here, $U(0→)=0$⁠, where we denoted $0→=def(0,…,0)$⁠. Thus, we have $Uj(x)>Uj0→$ for all j = 1, …, p but $U0(x)<U00→$⁠. This contradicts to our assumption that U₀(x) is a compromise between the normalized utility functions U₁(x), …, U_p(x).

Similarly, if the sign is positive for a⁽⁰⁾ and negative for all the points a^(j) with j ≥ 1, then we have $Uj0→>Uj(x)$ for all j = 1, …, p but $U00→<U0(x)$⁠, which also contradicts to our assumption. Thus, the point a cannot be outside the convex hull, so it must be inside the convex full. Lemma is proven.

Proving the first part of the proposition. Now that lemma is proven, let us show how this lemma leads to the proof of the first part of our main result. As we have mentioned, the utility functions of k = N ⋅ (d + 1) people can be represented by k points (a₁, …, a_n) from an (n − 1)-dimensional space determined by condition (3). It is known that any group of N ⋅ (d + 1) points in a d-dimensional space can be partitioned into subsets of size d + 1 so that there is a point that belongs to the convex hull of all these subsets. This result was first proven in Birch (1959) for dimension d = 2, then in Frick and Soberón (2020) for all dimensions d; see also Bárány (2022) for the general overview of this and related results. In our case, we have a space of dimension d = n − 1, so the above result indeed implies the first part of our proposition.

Proving the second part of the proposition. To prove this part, let us take N = n and N ⋅ (n − 1) = n ⋅ (n − 1) people with the utility functions corresponding to the following points:

1. we have n − 1 people with utility function corresponding to a⁽¹⁾ = (1, 0, …, 0),

2. we have n − 1 people with utility function corresponding to a⁽²⁾ = (0, 1, 0, …, 0), …,

3. for each i, we have n − 1 people with utility function corresponding to a⁽ⁱ⁾ = (0, …, 0, 1, 0 …, 0), with 1 on i-th place,…, and

4. we have n − 1 people with utility function corresponding to a⁽ⁿ⁾ = (0, …, 0, 1).

Let us show that no matter how we partition them into groups of n − 1, there will be no point common to the convex hulls of all these groups.

Suppose that we divide the original n ⋅ (n − 1) points into n groups c₁, …, c_n each of which contains n − 1 points. For each combination c_j of n − 1 points, their convex hull C_j is contained in the linear space L_j generated by the corresponding vectors. So, if there is a point common to all these convex hulls, this point should belong to the intersection L₁ ∩ … ∩ L_n of the corresponding linear spaces. Each of these linear spaces is a linear combination of some collection of some points a⁽ⁱ⁾. One can see the intersection L₁ ∩ … ∩ L_n of these linear spaces is a linear space generated by the intersection of these groups c₁ ∩ … ∩ c_n.

This intersection c₁ ∩ … ∩ c_n cannot contain the vector a⁽¹⁾: indeed, this would imply that the vector a⁽¹⁾ is contained in all n groups c₁, …, c_n that form this partition, and this cannot be since we only have n − 1 such vectors. Similarly, this intersection cannot contain any of the vectors a⁽ⁱ⁾. Thus, this intersection c₁ ∩ … ∩ c_n is empty, and the linear space L₁ ∩ … ∩ L_n generated by this intersection consists of the single point (0, …, 0). Since the intersection C₁ ∩ … ∩ C_n of the convex hulls is contained in the intersection L₁ ∩ … ∩ L_n of linear spaces, all the elements of this intersection – i.e. all the points which are common to all convex hulls – must be contained in the 1-element set {(0, …, 0)} – so this intersection should be either empty or consists of this point (0, …, 0). However, all the elements in each convex hull satisfy condition (3), but the point (0, …, 0) does not satisfy this condition. Thus, the intersection of the convex hulls must be empty – which is exactly what we wanted to prove.

The second part of the Proposition is proven, and thus, the Proposition itself is proven.

In this paper, we simply prove the existence of the desired partition into small groups. It is desirable to come up with an efficient algorithm for such a subdivision.