# aggregation_of_continuous_preferences_in_one_dimension__f9c54f0f.pdf Aggregation of Continuous Preferences in One Dimension Alberto Del Pia1 , Duˇsan Knop2 , Alexandra Lassota3 , Krzysztof Sornat4 and Nimrod Talmon5 1University of Wisconsin-Madison, USA 2Czech Technical University in Prague, Czech Republic 3Eindhoven University of Technology, Netherlands 4AGH University, Poland 5Ben-Gurion University of the Negev, Israel delpia@wisc.edu, dusan.knop@fit.cvut.cz, a.a.lassota@tue.nl, sornat@agh.edu.pl, talmonn@bgu.ac.il We develop a general, formal model of social choice in which voters have continuous preferences over a one-dimensional space. Our model is parameterized by different restrictions that we introduce regarding the way voter preferences change in time as well as the optimization criteria (that correspond to a normative continuum of fairness definitions) desired from an aggregation method that outputs a continuous, one-dimensional curve given such inputs. We discuss the applicability of the model to different real-world situations and, as a first step towards an analysis of the different model realizations, we concentrate on identifying those cases that are computationally feasible to compute. 1 Introduction Social choice theory offers algorithms that aggregate voter preferences and output various aggregated outputs, such as in single-winner elections [Sen, 1986], multiwinner elections [Faliszewski et al., 2017], and participatory budgeting [Aziz and Shah, 2021]. These examples, however, are all of a discrete flavor and with a simple structure. In particular, both the output (the name of a single candidate, the names of the k committee members, the names of the projects to fund) as well as the input (i.e., voter preferences) are discrete. Indeed, some social choice settings are continuous (most notably perhaps are randomized mechanisms and portioning methods [Airiau et al., 2023]), however, there is a general need for devising aggregation algorithms that are able to output more structurally-involved, continuous outputs. Correspondingly, here we are interested in social choice settings in which both the inputs (i.e., voter preferences) as well as the output (the aggregated result) are continuous. Consider first the following example usecases. Deciding on a monetary policy: One of the important features of a monetary system is its policy, where one of the main goals of such a policy is to stabilize the economy using certain policy tools [Friedman, 1995]. These tools include setting the interest rates, adjusting the reserve requirements for banks, and continuously buying and selling various securities. Consider, say, a group of experts, each with its own idea on a certain issue such as the required change in the interest rate for the coming year: as each of these experts may have different preferences regarding the ideal monetary policy, those individual preferences may be aggregated to a single, agreeable policy.1 Optimizing production: In industrial production environments, certain time-based estimations and decisions have to be made. Two of the most fundamental ones include estimating the future product demand and, based on such estimations, decide the future product supply [Levinsohn and Petrin, 2003]. Correspondingly, consider a group of experts that may also include certain data-intensive artificial experts each with its own estimation and preferences, and consider the need for a method that aggregates these. Controlling energy usage and consumption: For many energy sources (e.g., electricity), the energy cost is not only affected by the sheer amount of consumed energy but also on how the consumption is spread in time [Johnson et al., 2011]. In particular, as the cost of producing electricity increase dramatically in times of peak demand, many systems aim at so-called flattening the curve (of household electricity demand) [Barker et al., 2012]. Correspondingly, consider an agent community (say, residents of some residential complex) where different agents may have different preferences regarding the consumption of energy in time. For sustainability reasons as well as for purely economical reasons, there is a need to aggregate those preferences to come to a single, agreeable energy consumption curve. Collaborative forecasting: Consider a set of sensors/machines/agents, each of which is producing a forecast for, say, next weeks weather. These predictions may be aggregated to arrive to a single, agreeable forecast [Leutbecher and Palmer, 2008]. Space-based preferences: The above scenarios relate to aggregating time-based preferences. There are, however, similar scenarios that involve aggregating space- 1In this context, we mention cryptoeconomical situations involving time-based bonding curves [Zargham et al., 2020], Conviction Voting [Emmett, 2019], and Commitment Voting [Berg et al., 2020]. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) based preferences. E.g., a group of agents wishing to jointly decide on a water policy [Perret, 2002]. More abstractly, in such applications as described above, we are interested in aggregation methods that take continuous, one-dimensional voter preferences and output a continuous, one-dimensional output. To the best of our knowledge, no solutions are currently available for such social choice settings.2 Thus, motivated by such scenarios and by the lack of appropriate aggregation algorithms for their instances in this paper we develop a formal model for the aggregation of continuous preferences in one dimension and suggest several corresponding aggregation algorithms for such situations. As our model is novel, we are mainly interested in understanding what is possible to compute in our model i.e., what realizations of the model and which special cases of it have a mathematical structure that admits efficient aggregation algorithms. Generally speaking, we observe that, while the model is computationally intractable in its most generality, it admits efficient, exact algorithms for certain aggregation functions and certain restrictions on voter preferences. In what follows, after reviewing related work (Section 2), we describe our parameterized formal model (Section 3). Then, we present our theoretical results (which are formally summarized in Section 3.2): a proof of the general computational intractability of the model is described in Section 4; algorithms for basic aggregation functions are described in Section 5; and efficient algorithms for linear inputs and output are described in Section 6. We end with a future-facing discussion. 2 Related Work Our work has some relation with the relatively-new line of work on perpetual social choice [Bulteau et al., 2021; Lackner, 2020; Lackner and Maly, 2021]. However, while the model of perpetual social choice deals with preferences that may change between timesteps, it is nevertheless a discrete model of preferences and aggregation. (Note that there is also work on perpetual fair division [Igarashi et al., 2024].) Another related work is that of Lodi et al. [2022] who consider a time-based model of decision making; while their model (and focus) is of a somewhat continuous flavour, it is significantly different than ours, in particular by their model of individual utilities. We also mention the work of Bredereck et al. [2022] regarding a sequence of committee elections that does not directly fit within the framework of perpetual social choice but is of a somewhat similar style of a repeated, discrete decision making flavor. A different line of work within social choice that relates to our work considers settings that have some continuous ingredients. For example, some papers consider a model of divisible participatory budgeting [Freeman et al., 2021] (also referred to as portioning [Airiau et al., 2023]), in which the 2Indeed, models developed by political economists, such as the spatial model of elections [Enelow and Hinich, 1984] concentrate on continuous preferences, however differ in that we concentrate on continuous functions as modeling both voter preferences and the output of the aggregation process. aggregated output is a division of a joint budget (usually represented pictorially as a pie chart). Another example include probabilistic social choice [Brandt, 2017], in particular aggregation methods that are randomized and thus can be viewed as outputing a probability distribution that may be continuous. Yet a different flavor of continuity in social choice corresponds to the line of work on so-called society graphs: here, the electorate is treated as a continuous entity [Faliszewski et al., 2022; Gonen et al., 2023]. Somehow farther away is the vast literature on economic forecasting [Elliott and Timmermann, 2013]. In a way, our work can be applied on top of methods of traditional forecasting in that we offer a principled way of aggregating different forecasters. Note, however, that in our settings the ground truth (i.e., an ultimately perfect prediction) is not always the goal, as we concentrate on the collaborative aspects that relate to representation and equality in the decision-making mechanisms (as such, situations that have some subjective aspects perhaps fit better to our model). In this context, our work also has a similar structure to work on ensemble learning [Dong et al., 2020] in which several machine learning models are aggregated to create one, hopefully better, model. Here, again, we differ also as we concentrate on a social choice perspective over such aggregation indeed, the different q-norms we use correspond to a continuum of normative fairness guarantees, ranging from a utilitarian extreme (with q = 1) to an egalitarian extreme (with q = ). Another scientific field that relates to our work is decision theory [De Groot, 2004] in which (sometimes continuous) values are to be decided in an uncertain environment. 3 Formal Model We describe our general model. Our model consists of a continuous time axis T; we normalize the time axis so that T = [0, 1], and we use t T (i.e., 0 t 1) to denote points in time. We consider a decision space S = [0, 1] (corresponding to selecting a value between 0 and 1). By V = {v1, . . . , vn} we denote a set of voters, where each voter vi provides her ideal point for each point in time: formally, v V is a continuous function v: T S where v(t) is the ideal point of v at time t. A solution W : T S is a continuous function as well. Example 1. Consider V = {v1, v2, v3} with v1(t) = 0.5, v2(t) = 0.75, and v3(t) = t. For such voter preferences, a solution W may be, e.g., W(t) = 0.5. Given voter preferences as above, we define a general framework for corresponding objective functions for our aggregation methods to pursue. First, we define the cost of a solution for a voter in a certain timepoint; then, the cost of a solution for a voter; and, then, the cost of a solution to the voter community (which we aim at minimizing): We define a measure on the decision space to define the timepoint-cost of voter v at time t with respect to some solution W, as: cost(v, t, W) = |v(t) W(t)| . Based on the values of the timepoint-cost functions that we get for each t T, we define an (aggregated) Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) cost function for a voter v with respect to some solution W: cost(v, W). We use several specific functions as cost(v, W); in particular, Lp norms the continuous counterpart of p-norms, parameterized by p [1, ]: costp(v, W) = Z T costp(v, t, W)dt 1 In particular, cost (v, W) = maxt T cost(v, t, W). Based on these (aggregated) cost values for each voter v V , we define a total cost function cost(W) (for V ) that we wish to minimize. We use several specific functions as cost(W); in particular, q-norms (over the voters), parameterized by q [1, ]: v V costq(v, W) In particular, cost (W) = maxv V cost(v, W). When p and q are clear by the context, we shorten the notation and use cost(W) to denote the cost of the solution W. Example 2. Let V and W be the same voter set and possible solution as in Example 1 and consider the following: For p = 1 and q = 1 we have cost(W) = cost1(v1, W) + cost1(v2, W) + cost1(v3, W) = 0 + 0.25 + 0.25 = 0.5. For p = 1 and q = we have cost(W) = max(cost1(v1, W), cost1(v2, W), cost1(v3, W)) = max(0, 0.25, 0.25) = 0.25. For p = and q = 1 we have cost(W) = cost (v1, W) + cost (v2, W) + cost (v3, W) = 0 + 0.25 + 0.5 = 0.75. For p = and q = we have cost(W) = max(cost (v1, W), cost (v2, W), cost (v3, W)) = max(0, 0.25, 0.5) = 0.5. Note that, for mathematical clarity, we have chosen an optimization-oriented exposition (in which the aggregation goal is to minimize some norms). Indeed, an equivalent exposition may use axiomatic properties defining that an aggregation method is deemed fair if it satisfies the axiom of maximizing some norms. In particular the continuum of values for the q-norms corresponds to the normative tradeoff between the utilitarian extreme (with q = 1) and the egalitarian extreme (with q = ). 3.1 Notation Let C : T S denotes a class of all continuous functions. By L: T S, we define a class of linear functions. For a natural number n we use [n] = {1, 2, . . . , n}. Our CONTINUOUS VOTING model has four parameters: 1. the input functions type: Tinput C, 2. the output functions type: Toutput C, 3. the parameter p of the Lp norm that defines the aggregation of the timepoint-cost of a voter to its cost. We refer to this Lp as the time-aggregation method; and, 4. the parameter q of the q-norm that defines the objective function we wish to minimize. We refer to this q-norm as the voter-aggregation method. Accordingly, for specific values of Tinput, Toutput, p, and q, we write (Tinput, Toutput, p, q)-CV to denote the corresponding computational problem, i.e., the problem of optimally aggregating input preferences from Tinput into a solution in Toutput where the minimization is over Lp norm timeaggregation and q-norm voter-aggregation. We note that depending on the specific values of Tinput (resp. Toutput) an input (resp. output) may be defined as an oracle (e.g., in the case of general continuous functions) or by numerical values (e.g., a linear function may be defined by two numerical values). In this paper, the use of these approaches is clear from the context. 3.2 Summary of the Results Throughout the paper we study the computational complexity of identifying optimal solutions for the different realizations of our formal model. These are our main results: General intractability: We establish, in Theorem 1, the computational intractability of our problem. Indeed, that is not surprising, albeit crucial as a starting point. General continuous functions: We then consider general continuous functions; in Theorem 2, we show that: For any Tinput C, (Tinput, C, 1, 1)-CV is polynomial-time solvable; i.e., for any input type and output type, as long as we use an L1 timeaggregation function and summing voters costs, we can provide an optimal solution oracle in polynomial time (and using at most one oracle access to every input function); and, for any Tinput C, (Tinput, C, , )-CV is polynomial-time solvable; i.e., similarly to the above, albeit with L time-aggregation function and taking maximum over voters costs. Linear functions: We then go on to consider linear functions; we show that: (L, L, , q)-CV is ϵ-approximable in polynomial time (Theorem 3); (L, L, , )-CV is polynomial time solvable (Theorem 4); (L, L, , 1)-CV is polynomial time solvable (Theorem 5); and (L, L, 1, q)-CV is ϵ-approximable in polynomial time (Theorem 7). Indeed, constraining the input and output functions may be a too-strong of a restriction for many of the applications of our model (recall the applications described in Section 1). Nevertheless, we wish to note that: scientifically, as we concentrate on the basic question of what is feasible to compute in our model, starting from certain restrictions is natural; mathematically, as the results of Section 6 demonstrate, even the linear case is highly challenging to analyze; Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) algorithmically, using the positive algorithmic results for linear inputs may be a step towards the design of efficient algorithms for more involved inputs such as, e.g., piecewise linear functions. They can reasonably approximate general continuous functions, and thus are closer to the applications described in Section 1. It is, nevertheless, not trivial to get a reasonable approximation guarantee in general, as the loss on approximation depends both on the number of intervals as well as the volatility of the original functions over these intervals; practically, the results of Section 5 show that, for basic aggregation functions, also general continuous functions (which correspond to the applications described in Section 1) admit efficient aggregation. In particular, we show, using quite elegant results, that for p = q = 1 (which corresponds to utilitarian aggregation over pragmatic voters whose satisfaction is their average satisfaction over time) and for p = q = (which corresponds to egalitarian aggregation over pessimstic voters whose satisfaction is their worst satisfaction over time) efficient aggregation is possible. 4 General Intractability As expected, our model is generally computationally intractable. Below, we show that already a specific model realization is NP-hard. In particular, let Fz C be a family of continuous functions that are divisible into z equal intervals in time (each interval of length 1/z) such that, in each interval, the function is either constant 0 or constant 1. Therefore, every function from Fz is represented by z bits. Continuity is obtained by defining f(i/z) = 0.5 for every f Fz and i {0, 1, . . . z} and connecting the intervals using two linear segments (of gradients z3 and z3). Formally, we connect points (p i , f(p i )) and (p+ i , f(p+ i )) via a point (i/z, 0.5), where p i = i/z 0.5/z3 and p+ i = i/z + 0.5/z3. Theorem 1. (Fz, Fz, 1, )-CV is NP-hard. We prove NP-hardness of (Fz, Fz, 1, )-CV by considering its decision variant where in the input we are additionally given a number r R 0. The question to decide is whether the input (Fz, Fz, 1, )-CV instance has an objective value smaller or equal to r. We construct a polynomial-time reduction from the CLOSEST STRING problem, which is NPhard even on the binary alphabet [Frances and Litman, 1997; Bulteau et al., 2014]. For space constraints, the proof is deferred to the full version of the paper. 5 Basic Cases We observe that for cases when p = q = 1 or p = q = , if an output function is not restricted, i.e., it can be any continuous function, then we can provide an optimal solution oracle in polynomial time. Note that this holds for every class of input functions. Theorem 2. For every Tinput C, we can provide oracles for (Tinput, C, 1, 1)-CV and (Tinput, C, , )-CV in polynomial time and using at most one oracle access to every input function. Proof. We describe the solution for these two cases separately. The case of (Tinput, C, 1, 1)-CV: for this case, a solution W is, intuitively, the median of votes at time t. In the case of even number of voters, we interpolate between the two middle votes. Formally, for t T, we order {v1(t), v2(t), . . . , vn(t)} in a non-decreasing way (this requires one oracle access to every input function). We denote this ordered sequence as Vt. We define an optimal solution W as follows: 2 n is odd, 2 + 1 n is even. The case of (Tinput, C, , )-CV: for this case, an optimal solution W is the mid-range of an interval spanned between a minimum and a maximum vote at time t. Formally: max v V v(t) min v V v(t) . Example 3. Consider the setting of Example 1. Then, following the algorithms described in Theorem 2 we have that: For p = q = 1, an optimal solution is: 1/2 for t [0, 0.5), t for t [0.5, 0.75), 3/4 for t [0.75, 1). For p = q = , an optimal solution is: t/2 + 3/8 for t [0, 0.5), 5/8 for t [0.5, 0.75), t/2 + 1/4 for t [0.75, 1). 6 Linear Inputs and a Linear Output In this section, we assume that voters provide linear functions, and our goal is to obtain a linear function. Formally, for voter vi, i [n], we let the function vi : [0, 1] R be defined by vi(t) := ait + bi, for ai, bi R. The solution W : [0, 1] R is defined by W(t) := at + b, for a, b R. We first consider the case with p = and then the case with p = 1. Below we show that we can solve the case of p = , for any q, to any ϵ-accuracy, in polynomial time. We also show that in two special cases, we can solve this case exactly in polynomial time. We need some structural lemmas first. In particular, we start with a lemma, which shows that the cost function of a single voter i, denoted by cost(vi, W), is a piecewise linear convex function, i.e., it can be written as the maximum of a finite number of affine linear functions. Lemma 1. In the (L, L, , q) case, we have cost(vi, W) = max{b bi, b + bi, (a + b) (ai + bi), (a + b) + (ai + bi)}. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) Proof. By definition, cost(vi, W) is the following function of (a, b) R2: cost(vi, W) := max t [0,1]{|(at + b) (ait + bi)|}. Since the function (at+b) (ait+bi) is linear, we can write cost(vi, W) in the form cost(vi, W) = max t {0,1}{|(at + b) (ait + bi)|} = max{|b bi|, |(a + b) (ai + bi)|} = max{b bi, b + bi, (a + b) (ai + bi), (a + b) + (ai + bi)}. This finishes the proof. The next lemma shows that, whenever the functions cost(vi, W) are convex, then so is our objective function, which is the function from R2 to R defined by i=1 cost(vi, W)p ! 1 Lemma 2. Assume that the functions cost(vi, W), for i {1, 2, . . . , n}, are convex. Then, the function i=1 cost(vi, W)p ! 1 is convex, for every p 1. Proof. Consider the function h: Rn R defined by i=1 max{xi, 0}p ! 1 This function is convex and nondecreasing. Since the functions cost(vi, W), for i [n], are convex, we conclude that h(cost(v1, W), . . . , cost(vn, W)) is a convex function of W (see Vector composition in Section 3.2.4 in [Boyd and Vandenberghe, 2014]). Since cost(vi, W) is nonnegative for each i [n], we have that cost(W) = h(cost(v1, W), . . . , cost(vn, W)) , so our conclusion is that cost(W) is convex. We are now ready to prove the main results of this section. Theorem 3. The (L, L, , q) case can be solved to any ϵaccuracy in polynomial time. Proof. Our problem can then be cast as the following optimization problem: min cost(W) s.t. 0 b 1 0 a + b 1 , where cost(W) is the function from R2 to R defined by i=1 cost(vi, W)p ! 1 From Lemma 1, we know that cost(vi, W) is a piecewise linear convex function, for every i [n]. From Lemma 2, we know that cost(W) is convex as well, for every p 1. In this optimization problem, we have two variables, a and b, the objective function cost(W) is convex, and the feasible region is a quadrilateral sandwiched between balls with center (0, 0.5) and radii 0.3 and 1.2. Theorem 4.3.13 in [Gr otschel et al., 1988] implies that this optimization problem can be solved to any ϵ-accuracy in polynomial time, and we refer to the statement of this result for details. Next, we show that two important special cases can be solved exactly in polynomial time via linear programming. Theorem 4. The (L, L, , ) case is solvable in polynomial time. Proof. Our problem can then be cast as the following optimization problem: min cost(W) s.t. 0 b 1 0 a + b 1 , where cost(W) is the function from R2 to R defined by cost(W) := max i [n]{cost(vi, W)} . From Lemma 1, we obtain that cost(W) can be written as the maximum of the 4n affine linear functions b bi, b + bi, (a + b) (ai + bi), (a + b) + (ai + bi), for i [n]. The above optimization problem can then be cast as the following linear programming problem (see Section 1.3 in [Bertsimas and Tsitsiklis, 1997]): min z s.t. z b bi i [n] z b + bi i [n] z (a + b) (ai + bi) i [n] z (a + b) + (ai + bi) i [n] 0 b 1 0 a + b 1 . It is well-known that linear programming problems can be solved in polynomial time via the ellipsoid algorithm or interior point methods [Bertsimas and Tsitsiklis, 1997]. Theorem 5. The (L, L, , 1) case is solvable in polynomial time. For space constraints, the proof is deferred to the full version of the paper. We go on to consider p = 1. Below, we show that we can solve the case with p = 1, for any q, to any ϵ-accuracy, in polynomial time. To prove this result, we use Theorem 5.5 in [Bauschke et al., 2016]. Thus, we now state this result and introduce the Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) required notation3. In the following, X is an Euclidean space and I is a nonempty finite set. Definition 1 (Compatible system of sets [Bauschke et al., 2016]). Let A := {Ai}i I be a system of convex subsets of X, and let A := S i I Ai. We say that A is a compatible system of sets if i I j I i = j cl Ai cl Aj ri A = Ai Aj ri A, where cl is the closure and ri is the relative interior of a set. Let f : X R {+ }. The domain of f is Df := {x X | f(x) < + }. f is said to be proper if Df = . In the following, F := {fi}i I is a system of proper convex functions from X to R {+ } and f := mini I fi is the piecewise-defined function associated with F. For x X, I(x) := {i I | x Dfi} is the active index set function. Definition 2 (Compatible system of functions [Bauschke et al., 2016]). We say that F is a compatible system of functions if, for every i I, fi|Dfi is continuous and i I j I i = j Dfi Dfj = fi|Dfi Dfj fj|Dfi Dfj . (2) Theorem 6 (Theorem 5.5 in [Bauschke et al., 2016]). Assume that F is a compatible system of functions, that each fi is differentiable on int Dfi = , and that the following hold: (a) Df = S i I Dfi is convex and at least 2-dimensional. (b) {Dfi}i I is a compatible system of sets. (c) There exists a finite subset E of X such that x (int Df) \E {i, j} I(x) lim z x z int Dfi fi(z) = lim z x z int Dfj fj(z) exists. Then f is convex. Theorem 7. The (L, L, 1, q) case can be solved to any ϵaccuracy in polynomial time. Proof. First, we obtain the cost function of a single voter i, denoted by cost(vi, W). From simple geometric arguments, we write cost(vi, W) as a function of (a, b) R2 as follows: cost(vi, W) = quad(a, b) if b < bi, a + b > ai + bi lin(a, b) if b < bi, a + b ai + bi quad(a, b) if b bi, a + b < ai + bi lin(a, b) if b bi, a + b ai + bi, quad(a, b) = (b bi)2 + (a + b ai bi)2 lin(a, b) = ( a 2b + ai + 2bi)/2. 3For further background, we refer the reader to [Bauschke and Combettes, 2011; Mordukhovich and Nam, 2013]. Claim 1. The function cost(vi, W) is a convex function from R2 to R. Proof of Claim. To prove this claim, we use Theorem 6 (Theorem 5.5 in [Bauschke et al., 2016]). Let X := R2 and I := {1, 2, 3, 4}. We define the following four functions fi, for i I: f1(a, b) := 0 if (a, b) = (ai, bi) quad(a, b) if (a, b) = (ai, bi), b bi, a + b ai + bi + otherwise, f2(a, b) := lin(a, b) if b bi, a + b ai + bi + otherwise, f3(a, b) := 0 if (a, b) = (ai, bi) quad(a, b) if (a, b) = (ai, bi), b bi, a + b ai + bi + otherwise, f4(a, b) := lin(a, b) if b bi, a + b ai + bi + otherwise. The domains of the above four functions Dfi, for i I, are: Df1 : = {x R2 | f1(x) < + } = {x R2 | b bi, a + b ai + bi}, Df2 : = {x R2 | f2(x) < + } = {x R2 | b bi, a + b ai + bi}, Df3 : = {x R2 | f3(x) < + } = {x R2 | b bi, a + b ai + bi}, Df4 : = {x R2 | f4(x) < + } = {x R2 | b bi, a + b ai + bi}. We now check that F := {fi}i I is a compatible system of functions. First, for every i I, fi|Dfi is continuous. Thus, we only need to check that condition (2) holds. For (i, j) {(1, 3), (2, 4)}, we have Dfi Dfj = {(ai, bi)} and fi(ai, bi) = fj(ai, bi) = 0. For (i, j) = (1, 2), we have Df1 Df2 = {x R2 | b bi, a + b = ai + bi}, and for every (a, b) in this set, f1(a, b) = f2(a, b) = (bi b)/2. For (i, j) = (2, 3), we have Df2 Df3 = {x R2 | b = bi, a + b ai + bi}, and for every (a, b) in this set, f2(a, b) = f3(a, b) = (ai a)/2. For (i, j) = (3, 4), we have Df3 Df4 = {x R2 | b bi, a + b = ai + bi}, and for every (a, b) in this set, f3(a, b) = f4(a, b) = (b bi)/2. For (i, j) = (4, 1), we have Df4 Df1 = {x R2 | b = bi, a + b ai + bi}, and for every (a, b) in this set, f4(a, b) = f1(a, b) = (a ai)/2. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) This completes the proof that F := {fi}i I is a compatible system of functions. Next, we see that each fi is indeed differentiable on int Dfi. In fact, we have quad(a, b) = (b bi)2 + (a ai + b bi)2 2(a ai)2 + a ai + b bi , 2(b bi) + 2(a ai + b bi) lin(a, b) = ( 0.5, 1) . We have Df = S i I Dfi = R2, which is convex and 2dimensional. Thus, condition (a) in the statement of Theorem 6 is satisfied. Next, we observe that condition (b) in the statement of Theorem 6 is satisfied, i.e., that {Dfi}i I is a compatible system of sets. This is simply because each Dfi is closed and convex. Consider now condition (c) in the statement of Theorem 6 with E := {(ai, bi)}. Due to this definition of E, it suffices to check the condition for the following pairs (i, j): (1, 2), (2, 3), (3, 4), (4, 1). For (i, j) = (1, 2), for every ( a, b) {x R2 | b < bi, a + b = ai + bi}, we have lim (a,b) ( a, b) (a,b) int Df1 f1(a, b) = lim (a,b) ( a, b) (a,b) int Df2 f2(a, b) = ( 0.5, 1) . For (i, j) = (2, 3), for every ( a, b) {x R2 | b = bi, a + b < ai + bi}, we have lim (a,b) ( a, b) (a,b) int Df2 f2(a, b) = lim (a,b) ( a, b) (a,b) int Df3 f3(a, b) = ( 0.5, 1) . For (i, j) = (3, 4), for every ( a, b) {x R2 | b > bi, a + b = ai + bi}, we have lim (a,b) ( a, b) (a,b) int Df3 f3(a, b) = lim (a,b) ( a, b) (a,b) int Df4 f4(a, b) = (0.5, 1) . For (i, j) = (4, 1), for every ( a, b) {x R2 | b = bi, a + b > ai + bi}, we have lim (a,b) ( a, b) (a,b) int Df4 f4(a, b) = lim (a,b) ( a, b) (a,b) int Df1 f1(a, b) = (0.5, 1) . This completes the proof that condition (c) in the statement of Theorem 6 is satisfied. We can now apply Theorem 6 and obtain that the function f := mini I fi is convex. This concludes the proof of the claim because we have f cost(vi, W). Our problem can then be cast as the following optimization problem: min cost(W) s.t. 0 b 1 0 a + b 1, where cost(W) is the function from R2 to R defined by i=1 cost(vi, W)p ! 1 From Claim 1, we know that cost(vi, W) is convex, for every i {1, 2, . . . , n}. From Lemma 2, we know that cost(W) is convex as well, for every p 1. In this optimization problem, we have two variables, a and b, the objective function cost(W) is convex, and the feasible region is a quadrilateral sandwiched between balls with center (0, 0.5) and radii 0.3 and 1.2. Theorem 4.3.13 in [Gr otschel et al., 1988] implies that this optimization problem can be solved to any ϵ-accuracy in polynomial time, and we refer to the statement of this result for details. 7 Discussion We have proposed a model of social choice that evolves around fair aggregation of continuous preferences in one dimension. We have discussed several of its usecases and positioned it within the literature on computational social choice. By employing techniques from continuous optimization, we were able to show that even though the corresponding optimization problem is generally computationally intractable there are special cases for which efficient exact and approximate algorithms exist. Here we discuss several avenues for future research: Proportionality: Here we considered one form of proportionality w.r.t. different values of the Lp norms we use. Considering other forms of proportionality, including formulating corresponding axiomatic properties is a natural future research direction. E.g., a possible adaptation of Proportional Justified Representation [Fern andez et al., 2017] may be that each group of voters that is sufficiently-large and for which the average pairwise distance is not too large shall have some upper-bounded average distance to the aggregated output. Stability: In some applications it is natural to aim at some form of stability with respect to the intensity and frequency of the changes in the aggregated output. In the context of our model, we may thus require that the derivative of the aggregated output is upper bounded by some predefined value. Studying such domain restrictions for our model is thus of interest. Model variations: Other possibilities for modeling our setting may be with different elicitation (e.g., letting voters not only specify their ideal point for each point in time, but more involved preferences); different utility functions (e.g., corresponding to arbitrary metric on [0, 1]); and different aggregated output (e.g., returning several functions and not only one, i.e., a committee of functions). Furthermore, a corresponding online model (in which voter preferences change as a result of the partial aggregated values) is an interesting and wellmotivated model to study. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) Acknowledgments This research was initiated at the Lorentz Center Workshop on Advanced Optimization for Social Choice (Leiden, 11 15 July, 2022). Alberto Del Pia was partially funded by AFOSR grant FA9550-23-1-0433. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the Air Force Office of Scientific Research. Duˇsan Knop was supported by the European Union under the project Robotics and Advanced Industrial Production (reg. no. CZ.02.01.01/00/22 008/0004590). Krzysztof Sornat was partially supported by the SNSF Grant 200021 200731/1 and the European Research Council (ERC) under the European Union s Horizon 2020 research and innovation programme (grant agreement No 101002854). Nimrod Talmon was supported by the Israel Science Foundation (ISF; Grant No. 630/19). Finally, we would like to thank the anonymous reviewers for their helpful comments. [Airiau et al., 2023] St ephane Airiau, Haris Aziz, Ioannis Caragiannis, Justin Kruger, J erˆome Lang, and Dominik Peters. Portioning using ordinal preferences: Fairness and efficiency. Artificial Intelligence, 314:103809, 2023. [Aziz and Shah, 2021] Haris Aziz and Nisarg Shah. Participatory budgeting: Models and approaches. Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations, pages 215 236, 2021. [Barker et al., 2012] Sean Barker, Aditya Mishra, David Irwin, Prashant Shenoy, and Jeannie Albrecht. Smartcap: Flattening peak electricity demand in smart homes. In Proceedings of the 10th IEEE International Conference on Pervasive Computing and Communications (Per Com 2012), pages 67 75, 2012. [Bauschke and Combettes, 2011] Heinz H. Bauschke and Patrick L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2011. [Bauschke et al., 2016] Heinz H. Bauschke, Yves Lucet, and Hung M. Phan. On the convexity of piecewise-defined functions. ESAIM: COCV, 22(3):728 742, 2016. [Berg et al., 2020] Chris Berg, Sinclair Davidson, and Jason Potts. Commitment voting: A mechanism for intensity of preference revelation and long-term commitment in blockchain governance. https://ssrn.com/abstract= 3742435, 2020. [Available online at SSRN 3742435; accessed 10-January-2024]. [Bertsimas and Tsitsiklis, 1997] Dimitris. Bertsimas and John N. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997. [Boyd and Vandenberghe, 2014] Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2014. [Brandt, 2017] Felix Brandt. Rolling the dice: Recent results in probabilistic social choice. In Trends in Computational Social Choice, pages 3 26. AI Access, 2017. [Bredereck et al., 2022] Robert Bredereck, Till Fluschnik, and Andrzej Kaczmarczyk. When votes change and committees should (not). In Proceedings of the 31th International Joint Conference on Artificial Intelligence (IJCAI 2022), pages 144 150, 2022. [Bulteau et al., 2014] Laurent Bulteau, Falk H uffner, Christian Komusiewicz, and Rolf Niedermeier. Multivariate algorithmics for NP-hard string problems. Bulletin European Association for Theoretical Computer Science, 114, 2014. [Bulteau et al., 2021] Laurent Bulteau, Noam Hazon, Rutvik Page, Ariel Rosenfeld, and Nimrod Talmon. Justified representation for perpetual voting. IEEE Access, 9:96598 96612, 2021. [De Groot, 2004] Morris H De Groot. Optimal Statistical Decisions. John Wiley & Sons, 2004. [Dong et al., 2020] Xibin Dong, Zhiwen Yu, Wenming Cao, Yifan Shi, and Qianli Ma. A survey on ensemble learning. Frontiers of Computer Science, 14:241 258, 2020. [Elliott and Timmermann, 2013] Graham Elliott and Allan Timmermann. Handbook of Economic Forecasting. Elsevier, 2013. [Emmett, 2019] Jeff Emmett. Conviction voting: A novel continuous decision making alternative to governance. https://blog.giveth.io/conviction-voting-a-novelcontinuous-decision-making-alternative-to-governanceaa746cfb9475, 2019. [Online; accessed 10-January-2024]. [Enelow and Hinich, 1984] James M Enelow and Melvin J Hinich. The Spatial Theory of Voting: An Introduction. Cambridge University Press, 1984. [Faliszewski et al., 2017] Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Multiwinner voting: A new challenge for social choice theory. In Trends in Computational Social Choice, pages 27 47. AI Access, 2017. [Faliszewski et al., 2022] Piotr Faliszewski, Rica Gonen, Martin Kouteck y, and Nimrod Talmon. Opinion diffusion and campaigning on society graphs. Journal of Logic and Computation, 32(6):1162 1194, 2022. [Fern andez et al., 2017] Luis S anchez Fern andez, Edith Elkind, Martin Lackner, Norberto Fern andez Garc ıa, Jes us Arias-Fisteus, Pablo Basanta-Val, and Piotr Skowron. Proportional justified representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI 2017), pages 670 676, 2017. [Frances and Litman, 1997] Moti Frances and Ami Litman. On covering problems of codes. Theory of Computing Systems, 30:113 119, 1997. [Freeman et al., 2021] Rupert Freeman, David M Pennock, Dominik Peters, and Jennifer Wortman Vaughan. Truthful aggregation of budget proposals. Journal of Economic Theory, 193:105234, 2021. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) [Friedman, 1995] Milton Friedman. The Role of Monetary Policy. Springer, 1995. [Gonen et al., 2023] Rica Gonen, Martin Kouteck y, Roei Menashof, and Nimrod Talmon. Heuristics for opinion diffusion via local elections. In Proceedings of the 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023), pages 144 158, 2023. [Gr otschel et al., 1988] Martin Gr otschel, L aszl o Lov asz, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1988. [Igarashi et al., 2024] Ayumi Igarashi, Martin Lackner, Oliviero Nardi, and Arianna Novaro. Repeated fair allocation of indivisible items. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024), pages 9781 9789, 2024. [Johnson et al., 2011] Matthew P Johnson, Amotz Bar-Noy, Ou Liu, and Yi Feng. Energy peak shaving with local storage. Sustainable Computing: Informatics and Systems, 1(3):177 188, 2011. [Lackner and Maly, 2021] Martin Lackner and Jan Maly. Perpetual voting: The axiomatic lens. ar Xiv preprint ar Xiv:2104.15058, 2021. [Lackner, 2020] Martin Lackner. Perpetual voting: Fairness in long-term decision making. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), pages 2103 2110, 2020. [Leutbecher and Palmer, 2008] Martin Leutbecher and Tim N Palmer. Ensemble forecasting. Journal of Computational Physics, 227(7):3515 3539, 2008. [Levinsohn and Petrin, 2003] James Levinsohn and Amil Petrin. Estimating production functions using inputs to control for unobservables. The Review of Economic Studies, 70(2):317 341, 2003. [Lodi et al., 2022] Andrea Lodi, Sriram Sankaranarayanan, and Guanyi Wang. A framework for fair decision-making over time with time-invariant utilities. ar Xiv preprint ar Xiv:2212.10070, 2022. [Mordukhovich and Nam, 2013] Boris S. Mordukhovich and Nguyen Mau Nam. An Easy Path to Convex Analysis and Applications. Morgan & Claypool Publishers, 2013. [Perret, 2002] Sylvain R Perret. Water policies and smallholding irrigation schemes in South Africa: A history and new institutional challenges. Water Policy, 4(3):283 300, 2002. [Sen, 1986] Amartya Sen. Social choice theory. Handbook of Mathematical Economics, 3:1073 1181, 1986. [Zargham et al., 2020] Michael Zargham, Jamsheed Shorish, and Krzysztof Paruch. From curved bonding to configuration spaces. In Proceedings of IEEE International Conference on Blockchain and Cryptocurrency (ICBC 2020), pages 1 3, 2020. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)