On the Potential and Limitations of Proxy Voting: Delegation with Incomplete Votes Georgios Amanatidis1,5, Aris Filos-Ratsikas2, Philip Lazos3, Evangelos Markakis3,4,5, Georgios Papasotiropoulos4,6 1University of Essex. 2University of Edinburgh. 3Input Output (IOG). 4Athens University of Economics and Business. 5Archimedes/Athena Research Center. 6University of Warsaw. Abstract We study elections where voters are faced with the challenge of expressing pref- erences over an extreme number of issues under consideration. This is largely motivated by emerging blockchain governance systems, which include voters with different weights and a massive number of community generated proposals. In suchscenarios,itisnaturaltoexpectthatvoterswillhaveincompletepreferences, as they may only be able to evaluate or be confident about a very small propor- tion of the alternatives. As a result, the election outcome may be significantly affected, leading to suboptimal decisions. Our central inquiry revolves around whether delegation of ballots to proxies possessing greater expertise or a more comprehensive understanding of the voters’ preferences can lead to outcomes with higher legitimacy and enhanced voters’ satisfaction in elections where voters submit incomplete preferences. To explore its aspects, we introduce the following model: potential proxies advertise their ballots over multiple issues, and each voter either delegates to a seemingly attractive proxy or casts a ballot directly. Weidentifynecessaryandsufficientconditionsthatcouldleadtoasociallybetter outcomebyleveragingtheparticipationofproxies.Weaccompanyourtheoretical findings with experiments on instances derived from real datasets. Overall, our results enhance the understanding of the power of delegation towards improving election outcomes. Keywords:ComputationalSocialChoice;ProxyVoting;IncompletePreferences 4202 yaM 41 ]TG.sc[ 2v24650.9032:viXra 1 Introduction Broadly speaking, an election refers to a voting system in which a set of participants express their preferences over a set of possible issues or outcomes, and those are aggregated into a collective decision, typically with a socially desirable objective in mind. Besides their “traditional” applications such as parliamentary elections or referenda,electionsoftenunderpinthelivelihoodofmodernsystemssuchasblockchain governance (Kiayias and Lazos, 2022; Cevallos and Stewart, 2021) or participatory budgeting (Cabannes, 2004; Aziz and Shah, 2021). Quite often, voters are called to vote on an extremely high number of issues, rendering the accurate expression of their preferences extremely challenging. For instance, the Cardano blockchain uses Project Catalyst (https://projectcatalyst.io) to allocate treasury funds to community projects, and routinely receives several thousands of proposals per funding round. Another applicationcomesfromplatformsofcivicparticipation,wheretheusersexpresssupport on opinions or proposals (Halpern et al, 2023b). An unfortunate consequence of these election scenarios is that the voters will inevitably have a confident opinion only for a small number of issues (henceforth proposals), as investing enough time and effort to inform themselves about the sheer volume of proposals is clearly prohibitive. In turn, the “direct voting” outcome, even under the best intentions, will most likely be ineffective in capturing the desires of society, which it would, had the voters been sufficiently informed. A well-documented possible remedy to this situation is to allow for proxy voting (Cohensiusetal,2017),asysteminwhichthevotersdelegate theirvotestoproxies.The idea is that those proxies have the time and resources to study the different proposals carefully, and vote on behalf of the voters they represent. This in fact captures voting applications more broadly, where the reason for delegation might be a reluctance to express an opinion, lack of specialized knowledge, or even limited interest. When those proxies are part of an electorate together with other voters and proxies, the resulting systemisknownasliquid democracy (Kahngetal,2021;CaragiannisandMicha,2019). Liquid democracy has been scrutinized, with arguments presented in its favor (Becker et al, 2021; Halpern et al, 2023a; Revel et al, 2022) and against it (Caragiannis and Micha, 2019; Kahng et al, 2021), and at the same time it is being employed in real- world situations (Paulin, 2020) including settings similar to the one studied here, like the Project Catalyst. A takeaway message from the ongoing debate around delegative voting is that such processes might indeed be useful under the right circumstances. Extending this line of thought and motivated by the scenarios presented above, we aim to identify the potential and limitations of proxy voting with regard to achieving socially desirable outcomes, in settings with incomplete votes. More precisely, we aim to characterize what is theoretically possible with delegation, and what is impossible, even under idealized conditions. 1.1 Our Setting and Contribution We focus on elections in which the aim is to choose one proposal to be implemented fromarangeofmultipleproposals.Weintroduceamodelofproxyvoting,wherevoters 2 have intrinsic approval preferences over all proposals, which are only partially revealed orknowntothevotersthemselves.Asetofdelegation representatives (dReps) canthen advertise ballots over the proposals and the voters in turn may either delegate to a proxy, if there is sufficient agreement (i.e., over a certain agreement threshold between the proxy’s advertised ballot and the voter’s revealed preferences), or vote directly. The outcome of the election is the proposal with the largest approval score, assembled by the score from the ballots of the dReps (representing voters who delegated their vote) and the voters that vote directly. The core question we pose follows: “Is it possible for the dReps to advertise their preferences appropriately such that the outcome of the election has an approval score that is a good approximation of the best possible approval score; which would only be achievable if all voters had full knowledge of their preferences?” “Best-Case Scenario”. We study the aforementioned question by making the following assumptions: 1. The dReps are fully informed about the preferences of the voters, i.e., they know exactly the vector of intrinsic preferences for each voter. 2. The dReps themselves do not have actual preferences and their only goal is to achieve the best possible approximation of the optimal approval score. To do so they coordinate with each other and advertise their types accordingly. 3. Whentherearemultipleproposalswiththemaximumrevealedscore,tiesarebroken in favor of those with the highest intrinsic scores. One should not of course expect all of these assumptions to apply in practice. We would expect the dReps to be only partially informed about the preferences of the voters(e.g., via some probabilistic model) andto exhibit some sortof rational behavior (e.g., needing to be appropriately incentivized to advertise ballots that are aligned with socially-desirable outcomes). Still, studying “best-case scenario” is already instructive for results in all other regimes. In particular: • Our negative results (inapproximability bounds) immediately carry over to other settings as well, regardless of the choice of the dRep information model, the rationality model for the dReps, or the choice of the tie-breaking rule. In other words, we show that certain objectives are impossible, even when a set of fully- informed dReps coordinate to achieve the best outcome, hence they are certainly impossible for any other meaningful setting. • Our positive results (approximation guarantees) establish the limits of the afore- mentioned impossibilities: if something is not deemed impossible by our bounds, it should be the starting point of investigations for an information/rationality model chosen for the application at hand. Clearly, if our upper bounds establish that a certain number of dReps suffices to achieve a certain approximation in the “best-case scenario” setting, one should expect a slightly larger number of dReps to be needed in practice. 3 Our Results. We firstly present a strong impossibility, namely that for any agreement threshold higher than 50%, the best achievable approximation ratio is linear in the number of voters. On the positive side, we show that for an appropriate coherence notion of the instance, which captures the commonalities of the set of proposals that sets of voters are informed about, meaningful approximations are possible. For the natural case of an agreement threshold of 50%, we show that a single dRep is capable of achieving an approximation factor of 3, whereas only 2 dReps are sufficient to elect the optimal proposal. Most significantly, we present general theoretical upper and lower bounds on the achievable approximations, depending on the agreement threshold, the number of dReps, and the coherence of the instance. We complement our theoretical results with a set of experiments using the MovieLens dataset (Harper and Konstan, 2015), to measure the effects of proxy voting on realistic incomplete preferences. 1.2 Related Work We first comment on some works that are closer in spirit to ours. Meir et al (2021) propose a model with a similar objective, but focusing on the analysis of sortition, i.e., the approximation of the welfare achieved by selecting a random small-size committee. Inarelateddirection,Cohensiusetal(2017)analyzeparticulardelegationmechanisms, under elections with samples of voters located randomly in a metric space, according to some distribution. Our approach does not consider any randomization, neither for the voting rule nor for the preferences. Finally, Pivato and Soh (2020) also consider the performance of proxy voting, focusing on understanding when the proxy-elected outcome coincides with the outcome of direct voting. Again, the model of Pivato and Soh (2020) is randomized, where the voters delegate based on the probability of agreement to a proxy, and not based on a deterministic distance function. Moreover, no analysis of approximation guarantees is undertaken in the work of Pivato and Soh (2020). Our work can be seen as one that contributes to the corpus of findings in favor of proxy voting (Becker et al, 2021; Halpern et al, 2023a; Revel et al, 2022), albeit in a markedly different manner. There is significant work within the field of computational social choice on elections with incomplete votes. One stream has focused on the identification of possible and necessarywinnersbyexploringpotentialcompletionsofincompleteprofiles;seethework of Lang (2020) for an overview. Recent work has concentrated on the computational complexity of winner determination under various voting rules within the framework of incomplete information (Imber et al, 2022; Zhou et al, 2019; Baumeister and Dennisen, 2015). Another direction has studied the complexity of centralized interventions to reduceuncertainty(Alouf-Heffetzetal,2022)(e.g.,byeducatingaselectedsetofvoters or computing delegations via a centralized algorithm). Furthermore, there has been an exploration of the effect of minimizing the amount of information communicated (Kalech et al, 2011; Ayadi et al, 2019) as well as of the interplay between voters’ limited energy and social welfare (Terzopoulou, 2023). Considerable attention has been devoted to the exploration of efficient extensions of incomplete profiles to complete ones that satisfy desirable properties (Terzopoulou et al, 2021; Lackner, 2014; Elkind 4 et al, 2015). A conceptually related area focuses on distortion in voting, investigating the implications of applying rules to preferences that are less refined than the voters’ intrinsicpreferences(Anshelevichetal,2021).Beyondvotingscenarios,similarsolution concepts have been explored in domains such as fair division (Bouveret et al, 2010), hedonic and non-cooperative games (Kerkmann and Rothe, 2019; Brill et al, 2016). 2 Election Framework and Definitions In the current section we formally describe the main attributes of the election setting we study. Proposals and Voters. Let C = {1,2,...,m} be a set of candidate proposals, where for each proposal there are exactly two options: to be elected or not. Let also N ={1,2,...,n} be a set of voters responsible for determining the elected proposal. Each voter i∈N is associated with approval preferences v ∈{0,1}m over the set of i proposals; we refer those as true or intrinsic preferences. Here, 1 and 0 are interpreted as “accept” (or “support”) and “reject” (or “oppose”) a proposal, respectively. Crucial to our model is the fact that voters do not actually know their entire intrinsic preference vector, but only a subset of it; this could be due to the fact that they have put additional effort into researching only certain proposals to verify if they indeed support them or not, but not necessarily all of them. Formally, we will say that each voter i has revealed preferences v ∈{0,1,⊥}m, where ⊥ denotes that the (cid:98)i voter does not have an opinion on the corresponding proposal. As such, we have the following relations between v and v : i (cid:98)i ∀j ∈C : (v (j)=v (j))∨(v (j)=⊥). (cid:98)i i (cid:98)i The collection of proposals for which a voter i has developed an opinion is referred to as their revealed set, denoted by R :={j ∈C :v (j)=v (j)}. Let m :=|R |. Each i (cid:98)i i i i voter i also has an integer weight w ; in our work, it is without loss of generality to i assume that w =1 for all i∈N, as we can simply make w copies of voter i (with the i i same preferences), and all of our results go through verbatim. dReps. A delegation representative (dRep) is a “special” voter whose aim is to attract as many voters as possible to delegate their votes to her, and then participates in the election with the combined weight of those voters. In contrast with some of the literature, and consistently with the “best-case scenario” motivation (see Section 1.1), we view dReps as unweighted agents, devoid of personal preferences over the proposals, with the responsibility of facilitating the election of a proposal that attains substantial support from the voters. For any proposal j ∈C, every dRep has an advertised, “intended” vote (or type), t(j)∈{0,1}, which is visible by the voters. We assume here that dReps present votes forallproposals.1 Wewillsometimesabusethenotationandreferbytbothtothetype vector of a dRep as well as to the dRep itself. The distance between a voter i and a dRep of type t is calculated using the Hamming distance function and is dependent on 1 WecouldalsoallowdRepstoabstaininsomeproposals,andthiswouldnotmakeanydifferenceinour setting. 5 the revealed preferences of i and the advertised type of t in proposals that are revealed to i. Formally, let t be the projection of the type t to the proposals that belong to R . |i i Then we define the distance between a voter i and a dRep t as d(i,t):=H(v ,t ). (cid:98)i |i Agreement Threshold. For a voter to delegate their vote, they have to agree with the dRep in a certain number of proposals. This is captured by a threshold bound, any agreement above which results in delegation. To make this formal, we will assume that voter i delegates their vote to a dRep when their distance to the dRep’s type, taking into account only the voter’s revealed preferences, is at most ⌊mi−ki⌋, where 2 k is a parameter quantifying the reluctance of voter i to entrust their voting power i to a proxy. Obviously k ≤m , for every i, and we will mainly focus on scenarios in i i which all voters have the same parameter, thus k =k , for every voter i. For example, i when k =0, a voter delegates their vote if they agree with the dRep in at least half of the proposals in their revealed set; we will refer to this case as majority agreement (see also Fritsch and Wattenhofer (2022); Constantinescu and Wattenhofer (2023) for a use of a very similar threshold in a difference context). Given a dRep of type t, we say that t attracts a set of voters A(t):={i∈N :d(i,t)≤⌊mi−ki⌋}. Additionally we 2 define A(D), for a set of dReps D as m −k A(D):={i∈N :∃ t∈D s.t. d(i,t)≤⌊ i i⌋}. 2 If a voter is attracted by multiple dReps, we assume they delegate to any of them arbitrarily; this choice makes our positive results stronger, whereas, notably, our negative results work for any choice (e.g., even for the more intuitive choice of the closest, in terms of Hamming distance, accepted dRep). Preference Profiles. Let V =(v i ) i∈N and V(cid:98) =(v (cid:98)i ) i∈N . We call intrinsic preference profile P =(N,C,V)avotingprofilethatcontainstheintrinsicpreferencesofthevoters inN onproposalsfromC.Similarly,wecallrevealedpreferenceprofileP(cid:98) =(N,C,V(cid:98))the votingprofilethatcontainstheirrevealedpreferences.Finally,P(cid:98)D =(N,C,V(cid:98)∪D)refers to the preference profile on proposals from C, that contains the revealed preferences of the voters in N as well as the advertised types of the dReps in D. Approval Voting Winners. The winner of the election is the proposal with the highest (weighted) approval score. Formally, let sc(j) denote the score of a proposal j ∈ C in the profile P, i.e., the total weight of the voters i ∈ N such that v (j) = 1. i A proposal j ∈ C is the winning proposal in the profile P if sc(j) ≥ sc(j′),∀j′ ∈ C. Similarly, we define sc(j) and sc (j) to be the score of a proposal j ∈C in the profile (cid:98) (cid:98)D P(cid:98) and P(cid:98)D , respectively. Note that s (cid:98) c(j) represents the score that proposal j would attain if all voters were to vote directly and sc (j) comprises the scores of the dReps (cid:98)D (whose weight is the total weight of the voters they have attracted) and the scores of the voters that have not delegated their votes to any dRep, i.e., that are voting directly. Let win(P) := argmax{sc(j),j ∈ C} and opt(P) := sc(win(P)). The same notions can be extended to profiles P(cid:98) and P(cid:98)D . Tie-breaking for the winner: We assume that argmax{·} returns a single winning proposal rather than a winning set, according to some tie-breaking rule. Consistently 6 with our discussion on the “best-case scenario” (see Section 1.1), we assume that the tie-breaking is always in favor of the proposal with the maximum intrinsic score. Our goal is to select a set of λ dReps that will collectively (by participating in the election and representing voters according to the submitted thresholds) ensure that a proposal of high intrinsic approval score will be elected, as formally presented in the definition of the proxy selection problem, that follows. proxy selection(P,P(cid:98),k,λ) Input: An intrinsic voting profile P and a revealed voting profile P(cid:98) on a set C ofmproposalsandasetN ofnweightedvoters;thevoters’true(resp.revealed) preferences V (resp. V(cid:98) ); a parameter k, so that a voter i is attracted by a dRep with type t if d(i,t)≤⌊mi−k⌋; an upper bound λ on the number of dReps. 2 Output: Specify type vectors for all dReps in D, with |D| ≤ λ, such that win(P)=win(P(cid:98)D ). The performance of a suggested set of dReps is measured in terms of how well the intrinsic score of the winning proposal under their presence approximates the highest intrinsic approval score. Formally: Definition 1. Let ρ≥1. We say that a set of dReps D achieves a ρ-approximation if sc(win(P(cid:98)D ))≥ ρ 1sc(win(P)). One might be inclined to believe that attracting a sufficiently large set of voters is enough to achieve a significantly low approximation ratio guarantee. The following propositionestablishesthatthisisnotthecase.Itdemonstratesthattheattractionpart is only one component towards solving proxy selection, and, therefore, achieving good approximations requires further insights. Proposition 1. ItispossibleforasingledReptoattractn−1votersandstillachieve only an n-approximation. Proof. Consider an instance with n voters and four proposals. Voters’ intrinsic pref- erences are presented in the table below, where the revealed preferences are given in white background. I I I I 1 2 3 4 voter1 1 1 0 0 voters2,3,...,n 1 0 1 1 It is evident that win(P)=I , and opt(P)=n. At the same time the dRep that 1 votes in favor of all proposals attracts n−1 out of the n voters, namely all voters but voter 1. This means that sc (I )=|A(D)|=n−1 (where, recall that D is the set of (cid:98)D 1 dReps, here consisting of the single aforementioned dRep), while sc (I )=n, since (cid:98)D 2 both the dRep and voter 1 vote in favor of I . However, sc(I )=1= 1opt(P), and 2 2 n consequently, the dRep that votes in favor of all proposals, attracting n−1 of the voters, cannot yield an approximation factor better than n. 7 Beforeweproceed,wehighlightthatifthetie-breakingruleisnotinfavorofelecting the optimal proposal, then the situation can be much worse; in fact, the approximation can be infinite as demonstrated by the following example. Example 1. Consider an instance with n voters and m proposals. Voters’ intrinsic preferences are presented in the table below, where the revealed preferences are given in white background. I I I ··· I 1 2 3 m voter 1 1 0 1 ··· 1 . . . . . . . . . . . . . . . voter n 1 0 1 ··· 1 It holds that win(P) = I , and opt(P) = n. Suppose that we select as dRep the one 1 that advertises 1 for every proposal under consideration. Then, A(D)=N. However, the presence of this dRep in D implies that sc (j)=n, for every proposal j. Breaking (cid:98)D ties in an adversarial manner, results to the election of I , albeit sc(I ) = 0, which 2 2 leads to an infinite approximation factor. We conclude the section with the definition of an important notion for our work, that of a coherent set of voters, i.e., sets of voters with the same revealed sets. Several of our positive results will be parameterized by properties of those sets, such as the size of the largest coherent set. Definition 2. A set of voters N′ ⊆N is called coherent if R =R ,∀i,i′ ∈N′. An i i′ instance of proxy selection is called coherent if N is coherent. Importantly, given an instance of proxy selection, it is computationally easy to verify if it is coherent, or to find the largest coherent set of voters, via a simple algorithm. Lemma1. Givenaninstanceof proxyselection,wecaninpolynomialtimeidentify the largest coherent set and its size. Furthermore, we can in polynomial time decide if the instance is coherent. Proof. Thefirstpartofthestatementobviouslyimpliesthesecond,asitsimplyevolves checking whether the size of the largest coherent set is n. Now, given the intrinsic preferences P of an instance of proxy selection we can find the largest coherent set as follows. For every voter i, find a set of voters that can form a coherent set together with i, namely {i′ ∈N :R ≡R }. Among the sets obtained this way, select one of i i′ maximal cardinality. The described procedure runs in time O(n2m). 3 Theoretical Findings We start our investigation with the case of a single dRep (λ = 1). Our main result here is rather negative, namely that no matter how the dRep chooses their vote, the approximation ratio cannot be better than linear in the number of voters. 8 Theorem 2. For a single dRep and any k > 0, the approximation ratio of proxy selection is Ω(n). Proof. Consider an instance with an odd number of m>3 proposals and n=m−1 voters, where k >0,∀i∈[n], such that: i - For every voter i∈[n], their preferences with respect to proposal m are as follows: v (m)=1 and v (m)=⊥. i (cid:98)i - The remaining m − 1 proposals are partitioned in m−1 pairs, say 2 {1,2},{3,4},...,{m−2,m−1} and for each one of these m−1 pairs of proposals, 2 say {j,j+1}, there are two distinct voters, namely voters j and j+1, where voter j votes in favor of both proposals j and j+1 whereas voter j+1 votes in favor of proposal j but against proposal j+1; for every other proposal j′, the preferences of these voters are v (j′)=0 and v (j′)=⊥, where i∈{j,j+1}. i (cid:98)i Say that P and P(cid:98) are the intrinsic and revealed profiles of the created instance, respectively.Clearly,win(P)=mandopt(P)=n.WeclaimthatasingledRep,called t,regardlessoftheiradvertisedtype,willcontributetoelectingaproposalithatsatisfies sc(i)≤2, leading to an inapproximability of n. Towards this, first notice that t cannot 2 attract both voters of any pair. This is easy to see, as a distance of max{0,⌊mi−ki⌋} 2 for m =2 and k ≥1 means agreement on both revealed proposals. As a result, for i i any such pair of voters, t will either attract zero or one voter(s), given that any two voters do not share the same preferences with respect to both their revealed proposals. ConsiderfirstthescenariowhereA({t})=∅.Inthiscase,sincesc (m)=0<sc (j) (cid:98)D (cid:98)D for any proposal j ̸=m, it holds that there exists a proposal j′ such that win(P )=j′ D for which sc(j′)=2, or in other words, the direct voting will lead to the election of an outcome that is being accepted by exactly two voters. On the other hand, if t attracts at least one voter, say i where i is odd (resp. i is even), then t must have voted in favor of at least one proposal apart from proposal m, namely for proposal i (resp. for proposal i−1), or else i would not fully agree with t. But then, voter i+1 (resp. i−1), who is not attracted by t, is also voting in favor of proposal i (resp. for proposal i−1). This results to a proposal i such that sc (i) = sc (m)+1. Therefore, the winning (cid:98)D (cid:98)D proposal is not m but a proposal i for which sc(i)≤2. Theorem 2 should be interpreted as a very strong impossibility result since it holds even in the “best-case scenario” (see the discussion in Section 1.1). A natural follow-up question is whether some meaningful domain restriction can circumvent this impossibility.Forthis,wewillappealtothenotionofcoherentsetsofvoters,definedin Section2andwewillshowaboundedapproximationguaranteethatdegradessmoothly as the size of the largest coherent set grows and as the agreement threshold decreases. Theorem 3. For a single dRep, proxy selection admits an approximation ratio of (cid:110) (cid:111) min n,3n(k+2) , where S is the largest coherent set of voters in the instance. 2|S| 9 Proof. We denote by dRep0 and dRep1 the delegation representatives whose advertised types with respect to a proposal j ∈C, are as follows: (cid:40) 1, if j =win(P), dRep0(j)= dRep1(j)=1, ∀j ∈C. 0, otherwise. We begin with the following statement. It is a direct consequence of the proof of Theorem 14, which we will present later on in the text, but will also come in handy for the present proof. To maintain the flow of our presentation and prevent redundant repetition of arguments, we opted to use this forward reference. Claim 1. Consider a coherent instance of proxy selection, for any set of proposals, and any set of voters, either 1/3 of the voters agree with dRep0 on at least half the proposals, or the winning proposal of direct voting receives a score that is at least 1/3 of the votes. Next, we state and prove the following lemma. Lemma 2. In a coherent instance of proxy selection, either sc(win(P(cid:98)))≥ 2n , 3(k+2) or |A(dRep0)|≥ 2n . Hence, an approximation factor of 3(k+2) can be achieved. 3(k+2) 2 Proof of Lemma 2. Consider a coherent instance, and let R be the set of proposals thatarerevealedtoallvoters.Ifwin(P)∈R,thentheoptimalproposalwillbeelected by direct voting. Therefore, we focus on the case where win(P) ∈/ R. Suppose that there exists a proposal j′ ∈C such that sc(j′)≥ 2n . But then the proof follows by (cid:98) 3(k+2) the fact that sc(win(P(cid:98)))≥s (cid:98) c(win(P(cid:98)))≥s (cid:98) c(j′). So we can also assume that for every proposal j ∈C, it holds that sc(j)< 2n . To continue with the proof of the lemma, (cid:98) 3(k+2) we will need the following claim. Claim 2. Consider a coherent instance, with R being the set of proposals commonly revealed to all voters. Suppose also that sc(j)< 2n for any j ∈R. For any r ∈[k] (cid:98) 3(k+2) andforanysetS ⊆R ofr proposals,letZ(S ,dRep0)bethesetofvotersthattotally r r agree with dRep0 in all proposals of S . Then |Z(S ,dRep0)|≥ (k+2−r)n. r r (k+2) Proof of Claim 2. Wewillprovethestatementbyinductiononr.Toproveitforr =1, we define N := |{i ∈ N : v (j) = 0}|, for any proposal j ∈ C. Then, by the fact j (cid:98)i that sc(j)< 2n < n it holds that N ≥n− n ≥ (k+1)n, and the induction (cid:98) 3(k+2) (k+2) j (k+2) (k+2) base follows. Say now that the statement holds for a fixed r′ <k and call S ⊆R an r′ arbitrarysetofr′ proposals.WebuildasetS byaddingtoS anarbitraryproposal r′+1 r′ j ∈R\S . Observe that by the fact that sc(j)< 2n < n , it holds that at least r′ (cid:98) 3(k+2) (k+2) (|Z(S ,dRep0)|− n ) voters from Z(S ,dRep0) are voting against j. Therefore, r′ (k+2) r′ (k+2−r′)n n (k+2−(r′+1))n |Z(S ,dRep0)|≥ − = . r′+1 (k+2) (k+2) (k+2) Hence, Claim 2 indeed holds. 10 We now continue with proving Lemma 2. We fix r = k and a set S ⊆ R of k k proposals, in Claim 2. Note that by the discussion in Section 2, we know that k ≤m i for every voter i, and therefore |R|≥k, so that we can choose such a set S . We then k apply Claim 1 for the (coherent) subinstance induced by the voters in Z(S ,dRep0) k and the proposals in C\S . This implies that either at least |Z(Sk,dRep0)| voters agree k 3 with dRep0 in at least ⌈|C\Sk|⌉ proposals of C\S , or there is a proposal j ∈C\S 2 k k with sc(j)≥ |Z(Sk,dRep0)|. Using now Claim 2, we have that |Z(Sk,dRep0)| ≥ 2n , and (cid:98) 3 3 3(k+2) thus the second case is infeasible, since we have assumed that sc(j)< 2n , for any (cid:98) 3(k+2) j ∈C. Coming to the first case, we note that the voters that agree with dRep0 in at least ⌈|C\Sk|⌉ proposals of C \S , also agree with dRep0 in all proposals of S , by 2 k k definition. This leads to a total agreement with dRep0 of at least (cid:24) (cid:25) (cid:24) (cid:25) (cid:24) (cid:25) |C\S | m−k m+k k+ k =k+ ≥ . 2 2 2 Therefore,foreveryvoteri∈Z(S ,dRep0),itholdsthatd(i,dRep0)≤m−⌈m+k⌉= k 2 ⌊m−k⌋. This leads to |A(dRep0)| ≥ |Z(S ,dRep0)| ≥ 2n which, provided that 2 k 3(k+2) Claim 2 holds, completes the proof of the lemma. Applying Lemma 2 to the largest coherent set of the given instance immediately proves the statement of the theorem. An immediate but noteworthy corollary of Theorem 3 concerns majority agreement and coherent instances. Corollary 1. ForasingledRep,proxyselectionforcoherentinstancesandmajority agreement admits an approximation ratio of 3. Theattentivereadermighthaveobservedthatformajorityagreementandcoherent instances, the general impossibility result of Theorem 2 does not apply. In that case, one might wonder what the best achievable approximation ratio is. To partially answer this question we offer the following negative result. Theorem 4. Let ε > 0. For a single dRep, proxy selection does not admit a (1.6−ε) approximation, even for coherent instances and majority agreement. Proof. Consider an instance in which N = {v ,v ,...,v } and C = {c ,c ,c ,c }. 1 2 8 1 2 3 4 Suppose that v (c ) = 1 and that v (c ) = ⊥, for every voter i ∈ N. Furthermore, i 1 (cid:98)i 1 there is exactly one voter whose preferences with respect to proposals c ,c ,c belongs 2 3 4 in {110,101,011,100,010,001} and two voters that are voting for {111}. Note that in the current proof, for simplicity, we abuse the notation and use strings instead of ordered tuples to indicate voters’ preferences. In this instance, opt(P)=sc(c )=8 1 andsc(j)=5,∀j ∈C\{c }.Therefore,directvotingcannotresultinanapproximation (cid:98) 1 factor that is better than 8 = 1.6. We will prove that for any possible choice of 5 advertised ballot of a dRep, and if D ={t}, then sc(win(P(cid:98)D ))≤5, which again results to the claimed approximation factor. Figure 1 will be helpful as an illustration of the arguments that are going to be used. 11

We now continue with proving Lemma 2. We fix r = k and a set S ⊆ R of k k proposals, in Claim 2. Note that by the discussion in Section 2, we know that k ≤m i for every voter i, and therefore |R|≥k, so that we can choose such a set S . We then k apply Claim 1 for the (coherent) subinstance induced by the voters in Z(S ,dRep0) k and the proposals in C\S . This implies that either at least |Z(Sk,dRep0)| voters agree k 3 with dRep0 in at least ⌈|C\Sk|⌉ proposals of C\S , or there is a proposal j ∈C\S 2 k k with sc(j)≥ |Z(Sk,dRep0)|. Using now Claim 2, we have that |Z(Sk,dRep0)| ≥ 2n , and (cid:98) 3 3 3(k+2) thus the second case is infeasible, since we have assumed that sc(j)< 2n , for any (cid:98) 3(k+2) j ∈C. Coming to the first case, we note that the voters that agree with dRep0 in at least ⌈|C\Sk|⌉ proposals of C \S , also agree with dRep0 in all proposals of S , by 2 k k definition. This leads to a total agreement with dRep0 of at least (cid:24) (cid:25) (cid:24) (cid:25) (cid:24) (cid:25) |C\S | m−k m+k k+ k =k+ ≥ . 2 2 2 Therefore,foreveryvoteri∈Z(S ,dRep0),itholdsthatd(i,dRep0)≤m−⌈m+k⌉= k 2 ⌊m−k⌋. This leads to |A(dRep0)| ≥ |Z(S ,dRep0)| ≥ 2n which, provided that 2 k 3(k+2) Claim 2 holds, completes the proof of the lemma. Applying Lemma 2 to the largest coherent set of the given instance immediately proves the statement of the theorem. An immediate but noteworthy corollary of Theorem 3 concerns majority agreement and coherent instances. Corollary 1. ForasingledRep,proxyselectionforcoherentinstancesandmajority agreement admits an approximation ratio of 3. Theattentivereadermighthaveobservedthatformajorityagreementandcoherent instances, the general impossibility result of Theorem 2 does not apply. In that case, one might wonder what the best achievable approximation ratio is. To partially answer this question we offer the following negative result. Theorem 4. Let ε > 0. For a single dRep, proxy selection does not admit a (1.6−ε) approximation, even for coherent instances and majority agreement. Proof. Consider an instance in which N = {v ,v ,...,v } and C = {c ,c ,c ,c }. 1 2 8 1 2 3 4 Suppose that v (c ) = 1 and that v (c ) = ⊥, for every voter i ∈ N. Furthermore, i 1 (cid:98)i 1 there is exactly one voter whose preferences with respect to proposals c ,c ,c belongs 2 3 4 in {110,101,011,100,010,001} and two voters that are voting for {111}. Note that in the current proof, for simplicity, we abuse the notation and use strings instead of ordered tuples to indicate voters’ preferences. In this instance, opt(P)=sc(c )=8 1 andsc(j)=5,∀j ∈C\{c }.Therefore,directvotingcannotresultinanapproximation (cid:98) 1 factor that is better than 8 = 1.6. We will prove that for any possible choice of 5 advertised ballot of a dRep, and if D ={t}, then sc(win(P(cid:98)D ))≤5, which again results to the claimed approximation factor. Figure 1 will be helpful as an illustration of the arguments that are going to be used. 11 Fig. 1: The graph illustrates the voters’ preferences on the set of revealed proposals in the instance created for the proof of Theorem 4. Each boxed vertex represents the existence of a voter with the corresponding ballot, with respect to proposals c ,c ,c . 2 3 4 If a dRep advertises the ballot of a vertex v in this graph, they will attract all voters whose preferences are within a distance of 1 from v. • If t = 111, then A(D) equals the set of voters whose preferences belong in {111,110,101,011}. Therefore |A(D)|=5 and hence sc (c )=5. However c is (cid:98)D 1 2 both approved by the dRep and by a voter that doesn’t belong to A(D), consider, e.g., the voter who is voting for 100, which leads to sc (c ) = 6 and hence to (cid:98)D 2 a winning proposal win(P(cid:98)D ) such that s (cid:98) c D (I′) ≥ 6. Hence, win(P(cid:98)D ) ̸= c 1 , and, consequently, sc(win(P(cid:98)D ))=5. • If t = 110, then A(D) equals the set of voters whose preferences are {111, 110,100,010}. Therefore |A(D)| = 5 and hence sc (c ) = 5. Using the same (cid:98)D 1 rationale to before, one can observe that, again, sc(win(P(cid:98)D ))=5. The proof is identical for t=101 and t=011. • Ift=100,thenA(D)equalsthesetofvoterswhosepreferencesare{100,110,101}. Therefore |A(D)| = 3 and hence sc (c ) = 3. However c is both approved by (cid:98)D 1 2 the dRep and by the voter whose preference vector is 111, who does not belong to A(D), which leads to sc(win(P(cid:98)D ))=5. The proof is identical for t=010 and t=001. • If t = 000, then |A(D)| = 3, but sc (c ) = 4, which again leads to a winning (cid:98)D 2 proposal of sc(win(P(cid:98)D ))=5. We now note that if slightly relax our best-case scenario setting (see Section 1.1) and consider arbitrary tie-breaking rules, then we can strengthen Theorem 4 to the following impossibility result. Proposition 5. Let ε>0. For a single dRep, proxy selection does not admit a (2−ε)-approximationiftiesarebrokeninfavoroftheproposalwithmaximumrevealed score. Proof. The claim is straightforward if we consider an instance of two candidate pro- posals, namely c and c , and two voters whose preferences are depicted in the table 1 2 below. Note that only voters’ preferences with respect to c are revealed to them. 2 12 c c 1 2 voter 1 1 1 voter 2 1 0 Obviously, opt(P)=2 and opt(P(cid:98))=1. Furthermore any dRep can attract at most one voter and hence, for any D such that |D|=1, it holds that sc (c )≤sc (c ). In (cid:98)D 1 (cid:98)D 2 case of ties, these are once again broken in favor of the proposal of maximum approval score in the revealed profile, i.e. in favor of c , since sc(c )>0=sc(c ). Hence, in any 2 (cid:98) 2 (cid:98) 1 case, win(P(cid:98)D )=c 2 , and thus sc(win(P(cid:98)D ))=1, which equals 1 2 opt(P). Proposition 6. The instance used in Proposition 5 can be generalized towards proving that for any acceptance threshold k > 0, there exists an instance in which proxy selection does not admit a (2−ε)-approximation, for any ε > 0, if λ ≤ 2k−1, for arbitrary tie-breaking rules. Proof. Say that λ = 2k−1 and consider a coherent instance, where R = R , for any i voter i, with n = 2λ voters and m = R+1. Given the value of k, we define m such that k =R−1. The preferences of the voters are as follows: • Allvotersapproveproposal1,whichistheonlyproposalthatdoesnotbelongtoR. • Only the first λ voters approve proposal 2. • Only the 1st and 3rd group of λ voters approve proposal 3. 2 • Only the 1st, 3rd, 5th, 7th group of λ voters approve proposal 4. 4 . . . • Only voters {1,3,5,...,n−1} approve proposal m−1. • None of the voters approve proposal m. Clearly, the optimal proposal has an approval score of 2λ. Furthermore, ⌈R+k⌉= 2 ⌈2R−1⌉ = R and hence, any dRep, can attract at most one voter, and this can be 2 done only by advertising that voter’s ballot. As a consequence, introducing any set of dReps D, of size no more than λ, will result in sc (1)≤λ, but at the same time (cid:98)D sc (2) = sc(2) = λ. Breaking-ties in an adversarial manner, a proposal of intrinsic (cid:98)D (cid:98) approval score λ is being elected. To understand the power of coherence towards achieving good approximations, it is instructive to explore the limitations of the best possible dReps also on coherent instances. To this end, we provide a couple of results: the first generalizes Theorem 2 to be parameterized by the size of the largest coherent set, and the second shows robustness to coherent instances, as long as the agreement thresholds are sufficiently high. The take-away message of those results is that coherent sets are not a panacea, andcanresultinmeaningfulapproximationsonlyunderfurtherappropriateconditions. Theorem 7. Let ε>0. For a single dRep and any k >0, proxy selection does not admit an (cid:0) n −ε (cid:1)-approximation, where S is the largest coherent set of voters in the |S| instance. Proof. Recall that in the proof of Theorem 2, we designed an instance of proxy selection, in which every coherent set is formed by two voters, which implied 13 inapproximabilityof n.Atwhatfollows,wewillgeneralizethatconstructiontoinstances 2 with coherent sets of size up to any r >2. We create r/2 copies of each voter (more precisely, ⌊r/2⌋ copies of each voter with an odd index and ⌈r/2⌉ copies of each voter with an even index). Clearly, the new number of voters is now n′ =n· r. The analysis 2 from Theorem 2 directly carries over but now a proposal of score at most r gets elected instead of proposal m which has score n′. The maximum coherent set is of size r, and hence, the n′ inapproximability. r Theorem 8. Let ε>0. For a single dRep and k =m−2c(m), with c(m)∈o(m), the approximation ratio of proxy selection is Ω(n), even for coherent instances. Proof. Wearegoingtoconstructaninstancewhereallthevotersformasinglecoherent set of size n. Moreover, m =m−1 for all i∈[n]. Hence, we just write c rather than i c(m), i.e., k =m−1−2c. We assume that m=(n−1)(c+1)+1 and n≥4 (although any large enough m could be used). Further, in the created instance we have that • for every voter i∈[n], her preferences with respect to proposal m are as follows: v (m)=1 and v (m)=⊥, i (cid:98)i • voteri∈[n−1]approvesproposals(i−1)(c+1)+1,(i−1)(c+1)+2,...,i(c+1)and disapproves everything else (except for m, of course, but this does not belong to R , and the preference of voter n with respect to any proposal j satisfies v (j)=1. i (cid:98)i Clearly, the optimal solution satisfies n voters. Similarly to the proof of Theorem 7, we claim that a single dRep, t, regardless of their advertised type, will contribute to electing a proposal approved by at most two voters. Towards this, we begin by showing that t cannot attract more than one voter. First note that, for i,j ∈[n−1], we have H(v ,v )=2c+2. Also, for i∈[n−1], (cid:98)i (cid:98)j we have H(v ,v )=m−1−(c+1)≥3(c+1)+1−1−c−1=2c+2, where we used (cid:98)i (cid:98)n both m=(n−1)(c+1)+1 and n≥4 for the inequality. Now, suppose that t attracts at least two distinct voters, say i,j ∈[n]. Then, by the triangle inequality, we have (cid:22) (cid:23) (m−1)−(m−1−2c) 2c+2≤H(v ,v )≤d(i,t)+d(j,t)≤2 =2c, (cid:98)i (cid:98)j 2 which is a contradiction. We conclude that t may attract at most one voter. If t does not attract any voters, then all voters vote directly and this leads to the election of a proposal approved by exactly two voters. On the other hand, if t attracts one voter, say i, we claim that t must have voted in favor of at least one proposal other than m. Indeed, if t(j)=0 for every proposal j (except maybe for proposal m), then (cid:106) (cid:107) d(i,t) would be at least c+1> (m−1)−(m−1−2c) and they would not have attracted 2 voter i. As a result, a proposal of total approval 2 in the intrinsic profile is elected, instead of proposal m, and the n/2 inapproximability follows. We conclude our discussion for the case of one dRep with a complementary result of a computational nature: a theorem that establishes that finding a dRep to attract voters in a way that ultimately elects the optimal proposal is computationally hard. Consequently, proxy selection turns out to be challenging both from the standpoint of information theory and computational complexity. 14 m proposals c c c m+1 m+2 m+3 n voters [···] 1 0 0 2 special dummy voters 0 1 1 1 n−1 dummy voters 0 0 1 1 Fig. 2: The instance created in the proof of Theorem 9. Light gray cells correspond to preferences that are not revealed to the voters and dark gray cells correspond to preferences that are derived from instance I of mav. Theorem 9. The decision variant of proxy selection is NP-hard, even for majority agreement and a single dRep. Proof. We will establish NP-hardness for the decision version of proxy selection, where for some parameter r, we want to answer if there exists an advertised type for a dRep, so that the intrinsic score of the elected outcome is at least r. We will reduce from the problem minimax approval voting (mav) problem, which is a known NP-hard problem in voting theory. In mav, we are given an instance I of m binary proposals and n ballots where v ∈{0,1}m,i∈[n] and we are asked for a vector v for i which it holds that max H(v ,v)≤θ, where H is the Hamming distance between i∈[n] i two vectors of the same size. For the hardness of mav we refer to LeGrand et al (2007); Frances and Litman (1997). We note that the NP-hardness has been established for instances with m being even, and θ = m/2. Given such an instance, we create an instance I′ of proxy selection as follows: • We have m′ =m+3 binary candidate proposals: {c ,...,c ,c ,c ,c }, 1 m m+1 m+2 m+3 i.e., three additional proposals from I. • We have n voters corresponding to the voters of I, and an additional number of n+1 dummy voters, for a total of 2n+1 voters. • Foreveryvoteri∈[n],belongingtothegroupofthefirstnvoters,theirpreferences for the first m proposals in I′ are just as they are in I, and they are all revealed, so that m =m. The remaining three proposals are not visible for these voters i and their intrinsic preferences are that v (c )=1, v (c )=v (c )=0. i m+1 i m+2 i m+3 • For the dummy voters, none of them approve the first m proposals, which are also not revealed to them. As for the last three proposals, there are exactly two dummy voters, who will be referred to as the special dummy voters, who approve all three proposals, and all three are revealed to them. All the remaining n−1 dummy voters approve only the proposals c and c , which are revealed to m+2 m+3 them, whereas c is disapproved, and also not revealed to them. m+1 • We set r =n+2 and λ=1, i.e. we have only one dRep available. Hence we are looking for an advertised type of the dRep, so that the instrinsic score of the elected outcome is at least n+2. An illustrative exposition of voters’ ballots can be found in Fig. 2. Before we proceed, note that the only proposal that has an intrinsic score of n+2 is the proposal c ,whilealltheothershavelowerscores.Butc cannotbeelectedviaonlydirect m+1 m+1 15 voting, since it is not revealed to the first n voters. Hence, the question is whether there exists an advertised type for the dRep that can make c elected. m+1 For the forward direction, suppose that I is a YES-instance of mav. Then there exists a vector v ∈{0,1}m for which it holds that max H(v ,v)≤m/2. Consider i∈[n] i now that the dRep advertises the type t=(v,1,0,0). The dRep will attract the first n voters, since they agree with them in at least m/2 of their revealed proposals. She will not attract any of the dummy voters, all of which disagree with them on two proposals. Therefore, the dRep will have a weight of n, and since the dummy voters vote directly, the proposal c will collect a score of n+2 and will be the winner of the election. m+1 For the reverse direction, suppose that I is a NO-instance of mav. Then for any possible vector v ∈{0,1}m, it holds that there exists at least one voter i∗ ∈[n], such that H(v ,v)>m/2. Fix now such an arbitrary vector v ∈{0,1}m. We will consider i∗ all possible cases for the advertised type of the dRep, t, and show that c cannot m+1 get elected, i.e, I′ is a NO-instance. We use a natural tie-breaking rule that resolves any tie in favor of the proposal of maximum approval score in the revealed profile. Therefore, in all the cases below, any tie that involves proposals c ,c ,c is m+1 m+2 m+3 broken against c due to the fact that sc(c )<sc(c )=sc(c ). m+1 (cid:98) m+1 (cid:98) m+2 (cid:98) m+3 • Suppose that t=(v,0,x,y), for any x,y ∈{0,1}. It is easy to see that since the dRepdoesnotapprovec ,itisnotpossiblethatthisproposalwinstheelection. m+1 • Suppose that t = (v,1,0,0). In this case, the dRep does not attract any of the dummy voters. Hence, the proposals c and c receive a score of n+1. As m+2 m+3 for proposal c , it is crucial to note that since I is a NO-instance of mav, t m+1 can attract at most n−1 of the first n voters. Therefore together with the two special dummy voters, the proposal c will have a score of at most n+1. By m+1 the tie-breaking rule that we have assumed, this means that the winner of the election will be either c or c . m+2 m+3 • Suppose that t = (v,1,1,0), or t = (v,1,1,1), or t = (v,1,0,1). WLOG, we analyze the former. In this case, the dRep attracts all dummy voters. Hence, the dRep has a weight of at least n+1 and possibly more by some of the first n voters who delegate to her. Hence, the winner will either be some proposal that is approved by v and also has the highest approval rate among the voters who did not delegate to dRep, or there is a tie among all the proposals approved by t. By the tie-breaking rule, it is not possible that c is elected. m+1 We have established that no matter what the dRep advertises, it is impossible that c is elected, and hence I′ is a NO-instance, which concludes the proof. m+1 Importantly, we note that all of the approximation guarantees in our paper can be obtained in polynomial time. 3.1 Multiple dReps WenowturnourattentiontothecaseofmultipledReps(λ≥2),asthisisnotcaptured by the stark impossibility of Theorem 2. Is it perhaps possible to achieve much better approximations by using sufficiently many dReps? A reinforcing observation is that for majority agreement, 2 dReps actually suffice to elect the optimal proposal. 16 Theorem10. Whenλ=2,proxyselectionformajorityagreementcanbeoptimally solved. Proof. We denote by dRep0 and dRep1 the delegation representatives whose advertised typeswithrespecttoaproposalj ∈C areasfollows:dRep0(j)=0,dRep1(j)=1, ∀j ∈ C. Recall that dRep0 differs from dRep0 used e.g. in the proof of Theorem 3. We will make use of the following lemma, the proof of which is immediate and based on the fact that any voter’s ballot either contains at least as many zeros as ones or more ones than zeros. Lemma 3. In an instance of proxy selection, with k =0, each voter belongs either to A(dRep0) or to A(dRep1) (or both). A direct consequence of Lemma 3 is that if D ={dRep0,dRep1} then A(D)=N. Hence, if λ=2, we can retrieve the optimal solution. This is because each proposal will garner precisely as much support as win(P) since no delegate representative will vote in favor of a proposal without concurrently voting in favor of win(P). Therefore, win(P) will be elected, according to the tie-breaking rule. But what about instances in which voters are more discerning, indicated by larger values of k? Whether good approximations with multiple delegation representatives are achievable in general is still to be determined. We begin with coherent instances and we provide the following generalization of Theorem 10 specifically for this case. Theorem 11. When λ = 2k+1, proxy selection for coherent instances and any k ≥0 can be optimally solved. Proof. Let R be the set of commonly revealed proposals to the voters of the given instance. It is without loss of generality here to assume that win(P)∈/ R, or otherwise, the direct voting would result in the election of win(P). To create a set of dReps D, we fix an arbitrary set S ⊆ R, of k proposals, and for every possible binary vector k on S k , i.e., for every σ ∈2Sk , we add to D exactly two dReps, namely t σ,0 and t σ,1 , advertising the following, with respect to a proposal j:   σ(j), if j ∈S k , (cid:26) σ(j), if j ∈S , t σ,0 (j)= 1, if j =opt(P), t σ,1 (j)= k 1, otherwise.  0, otherwise. Toprovethestatement,itissufficient,toshowthatA(D)=N,i.e.,thatD canattract all voters from N. We fix an arbitrary voter i∈N. Definitely, there is a vector, say σ′, that defines a pair of dReps in D, say t and t (henceforth denoted by t and t ), σ′,0 σ′,1 1 2 such that i totally agrees in all proposals of S both with t and t . Formally, if for a k 1 2 given vector x and a set of proposals Y, we denote by x the projection of x to the |Y proposals in Y, the following holds: max{H(v ,t ),H(v ,t }=0 (1) (cid:98)i|Sk 1|Sk (cid:98)i|Sk 2|Sk Let R′ :=R \S =R\S and for z ∈{0,1} we define R′(z):=|{j ∈R′ :v =z}|. i i k k i i (cid:98)i 17 Then, either R′(0)≥R′(1), or R′(1)>R′(0). Therefore, i i i i (cid:22) |R′| (cid:23) min{H(v ,t ),H(v ,t }≤ i . (2) (cid:98)i|R i ′ 1|R i ′ (cid:98)i|R i ′ 2|R i ′ 2 Combining Equations (1) and (2), we have that voter i agrees either with t or with 1 t , in at least 2 (cid:24) |R′| (cid:25) (cid:24) m −k (cid:25) (cid:24) m +k (cid:25) k+ i =k+ i ≥ i 2 2 2 proposals. Consequently, every voter will delegate to a dRep from D and the optimal proposal will be elected. Theorem 11 provides a bound on the sufficient number of dReps required to make surethattheoptimalproposaliselectedandraisesaquestionregardingpositiveresults (both optimal and approximate) for not-necessarily-coherent instances. In Theorem 13 below we provide a generalized and more refined version of this result, that relates the achievable approximation with the required number of dReps and the parameters of the instance, but does not need to assume that the instances are coherent. 3.2 Beyond Coherent Instances Coherence has been proven to be very useful towards achieving meaningful approxima- tion guarantees. At what follows, we define a more refined notion, namely a quantified version of it, which provides further insights into the structure of instances and how these affect the achievable approximations. In particular, we use the notion of (x,δ)- coherent sets for sets of voters that have a common set of proposals of size x in their revealed sets, as well as at most δ additional proposals. Definition 3. A set of voters N′ ⊆ N is called (x,δ)-coherent if there exists a set X ⊆C suchthatforeveryi∈N thefollowinghold:X ⊆R ,|X|≥x,and|R \X|≤δ. i i Using Definition 3, we generalize the result of Theorem 3, with an additional loss in the factor that is dependent on the type of (x,δ)-coherent sets that an instance admits. Theorem 12. For a single dRep and for any δ>0, proxy selection admits an (cid:110) (cid:111) approximation ratio of min n,3n(k+δ+2) , where S is the largest (k+δ,δ)-coherent 2|S| set in the instance. Proof. By electing any proposal, one can straightforwardly obtain an approximation factor of n. For the remaining of the proof, say that 2n(k+δ+2) < n. Additionally, 2|S| for now and for ease of exposition, suppose that for every voter i∈N, it holds that v (win(P)) = 1, v (win(P)) = ⊥. At the end of the proof we will show that this i (cid:98)i assumption can be dropped. For the studied case, we will prove an approximation ratio of 3n(k+δ+2). 2|S| The proof follows the same rationale as the proof of Theorem 3, which was based on applying Lemma 2 to the largest coherent set of the instance. Similarly, to prove 18 Theorem 12, it suffices to prove an analogous lemma, that we state below. Recall that (cid:40) 1, if j =win(P), dRep0(j)= dRep1(j)=1, ∀j ∈C. 0, otherwise. Lemma 4. In an instance of proxy selection, with N being (k+δ,δ)-coherent, it either holds that sc(win(P(cid:98)))≥ 2n or |A(dRep0)|≥ 2n . 3(k+δ+2) 3(k+δ+2) Proof. Suppose that there exists a proposal j′ ∈C such that sc(j′)≥ 2n . Then (cid:98) 3(k+δ+2) theprooffollowsbythefactthatsc(win(P(cid:98)))≥s (cid:98) c(win(P(cid:98)))≥s (cid:98) c(j′).Sowecanassume that for every proposal j ∈C, it holds that sc(j)< 2n . Next, we state a claim (cid:98) 3(k+δ+2) whichisageneralizationofClaim2.ItsproofisalmostidenticaltotheproofofClaim2. Claim 3. Consider an instance where the set of voters N forms a (k+δ,δ)-coherent set,forsomeδ ≥0.Supposealsothatsc(j)< 2n ,foranyj ∈C.LetX betheset (cid:98) 3(k+δ+2) of commonly revealed proposals to all voters, which by definition satisfies |X|≥k+δ. For any set S ⊆X of r proposals, with r ∈[k+δ], let Z(S ,dRep0) be as defined in r r Claim 2. Then |Z(S ,dRep0)|≥ (k+2+δ−r)n. r (k+δ+2) We proceed with proving Lemma 4, using Claim 3. Fix r =k+δ in Claim 3, and let S ⊆X be a set of k+δ proposals. Let also C′ =X\S . We examine the number r r of voters who will eventually delegate to dRep0. We observe that every proposal of C′ belongs to the revealed set of any voter of Z(S ,dRep0). Therefore, we can apply Corollary 1 for Z(S ,dRep0) and C′. This r r implies that either there exists a proposal in C′ approved by Z(Sr,dRep0) voters or at 3 least Z(Sr,dRep0) voters agree with dRep0 on at least ⌈|C′|⌉ proposals. By Claim 3, we 3 2 know that |Z(S ,dRep0)|≥ 2n . Therefore, by the assumption we have made, it is r k+2+δ notpossibletohaveaproposalwithascoreof |Z(Sr,dRep0)|,hence,atleast 2·|Z(Sr,dRep0)| 3 3(k+δ+2) voters of Z(S ,dRep0) agree with dRep0 in at least ⌈|C′|⌉ proposals from C′. But, by r 2 the definition of Z(S ,dRep0), they also agree on the k+δ proposals of S . In total, r r their agreement with dRep0 is at least: (cid:24) |C′| (cid:25) (cid:24) m −k−δ−δ (cid:25) (cid:24) m +k (cid:25) k+δ+ ≥k+δ+ i ≥ i , 2 2 2 wherethefirstinequalityholdsduetothefactthat|C′|=|X|−(k+δ),andm ≤|X|+δ. i As a consequence all these voters, i.e., at least 2n in number, will delegate to 3(k+δ+2) dRep0. Hence, Lemma 4 holds and Theorem 12 follows, under the assumption that all voters secretly approve the optimal proposal. Suppose that in a given instance the assumption doesn’t hold. Focusing on the set of voters, called N′, that satisfy the assumption and applying the described procedure, one can prove that either there is a proposal of score at least 2|N′| or dRep0 attracts at least 2|N′| voters. Given 3(k+δ+2) 3(k+δ+2) that sc(win(P))=|N′|, an approximation ratio of 3(k+δ+2) is implied. 2 19 To conclude the proof, we note that the desired approximation ratio holds true by focusing on the set S, just like in Theorem 3. ThemainresultofthesubsectionisarelaxationofTheorem11.UnlikeTheorem11, thetheoremdoesnotrequireanystructuralassumptions,andrelatestheapproximation with the number of dReps, the threshold bound and the structure of the instance in terms of approximate coherence. Theorem13. Whenλ=min (cid:8) n,ζ2k+1(cid:9),proxyselectionadmitsanapproximation ratio of γ , where γ is the minimum number of (k,m−k)-coherent sets that can form 3ζ a partition of N, and ζ ≤γ with ζ ∈N. Proof. For ease of exposition we assume that for every voter i ∈ N, it holds that v (win(P))=1, v (win(P))=⊥. We note that this assumption is without any loss in i (cid:98)i the approximation factor, likewise in the proof of Theorem 12 in which we proved that focusing only on the set of voters that are secretly in favor of the optimal proposal does not affect the approximation ratio. Trivially, if we set D to consist of one dRep t for every voter v such that i i (cid:40) 1,if j =win(P) t (j)= i v (j),otherwise i thenA(D)=N andhencewin(P(cid:98)D )=win(P).Therefore,withndRepswecanretrieve the optimal solution and, as a consequence, the claimed approximation factor holds. We will now proceed with proving that whenever ζ2k+1 <n, we can use a set of dReps D, where |D|≤ζ2k+1, to elect a proposal j such that sc(j)≥ 3ζopt(P). γ We proceed with the following lemma, the proof of which is analogous to the proof of Theorem 11. Lemma 5. In an instance of proxy selection, in which N can be partitioned in at most γ (k,m−k)-coherent sets, proxy selection can be optimally solved if λ=γ2k+1. Using 2k+1 dReps for any of the sets described in the statement of the theorem, as indicated by Lemma 5, we can create a set of dReps D such that |D|≤γ2k+1 and A(D) = N. This proves the statement of the theorem for ζ = γ. Fix now a number ζ <γ. Among the γ sets produced by Lemma 5, let us focus on the ζ sets of largest size. Let also N′ ⊆N be the voters in these sets. Then we can create a set of dReps D′ ⊆D, such that |D′|≤ζ2k+1 and A(D′)⊇N′. But then, |A(D′)|≥|N′|. Although all dReps of D′ vote in favor of win(P) and this can indeed be the winning proposal of profile P , it may also be the case that win(P )̸=win(P). In D′ D′ fact, if some dReps from D′ that are voting in favor of win(P ), attract voters that D′ vote against win(P ), the intrinsic score of win(P ) may significantly differ from D′ D′ sc(win(P )). To avoid this behaviour we suggest to create a new set of dReps, say D′ D′′, by deleting from D′ all dReps of the form t , i.e., all dReps that are voting in σ,1 favor of proposals that do not belong in S , as defined in the proof of Theorem 11. k Interestingly |D′′|= |D′|. We will now compute |A(D′′)|. 2 20 Suppose first that the number of voters attracted by dReps in D′\D′′ is at most 2|N′|. Then, |A(D′′)|≥|N′|− 2|N′| = |N′|. 3 3 3 Before continuing we define α:=|∪ i∈N(cid:101) R i | and β :=min{|R i |,i∈N(cid:101)}, where N(cid:101) is anyoftheγ (k,m-k)-coherentsetsofthevoters’partition,asdescribedinthestatement of the Theorem. We call N the number of voters, attracted by dReps in D′ \D′′ and say that 1 N ≥ 2|N′|. But then, for every voter i∈N it holds that R (1)≥ |Ri| ≥ β. But then, 1 3 1 i 2 2 the total number of approvals in P(cid:98) for proposals in C \S k , equals (cid:80) i∈N1 R i (1) ≥ |N |β ≥ 2|N′|β = |N′|β.Alltheseapprovalsarespreadbetweenαproposals.Therefore, 1 2 3 2 3 there exists a proposal j ∈R for which sc(j)≥ |N′|β. (cid:98) 3α Consequently, either there is a proposal approved by |N′|β voters or there exists a 3α set of dReps D′′ that can attract |N′|β voters without voting in favor of a proposal 3α disapproved by a voter in A(D′′). Using the fact that |N′|≥ ζn≥ ζopt(P), we have γ γ an approximation ratio of γ · β . Obviously, if every of the considered ζ, out of the γ ζ 3α (k,m-k)-coherent sets, is coherent, then an approximation ratio of γ is implied. 3ζ An interesting corollary of Theorem 13 (which could also be deduced from the proof of Theorem 11) is the following: When aiming for an optimal solution with 2k+1 dReps, it’s not a necessity for instances to be coherent; rather, the key factor is the existence of a set of k proposals commonly revealed to all voters. We conclude the discussion on generalizations with the following theorem, for the case of majority agreement (k = 0), which generalizes Corollary 1 by relating the achievable approximation to the structure of the revealed sets, once again without the requirement of coherence. Theorem 14. ForasingledRep,proxy selectionformajorityagreementadmitsan approximation ratio of min (cid:8) n,3α(cid:9), where α:=|∪ R | and β :=min{|R |,i∈N}. β i∈N i i Proof. It is apparent that any instance of proxy selection, is approximable within a factor of n, since it holds that electing arbitrarily a proposal j ∈C results in a winning proposal that satisfies sc(j)≥1≥ 1opt(P). Therefore suppose that min{n,3α}= 3α. n β β We proceed by showing that there exists a ballot type, the advertisement of which, results to an attraction of at least half of the voters that vote in favor of the optimal proposal. Recall that (cid:40) 1, if j =win(P), dRep0(j)= dRep1(j)=1, ∀j ∈C. 0, otherwise. Note that dRep0 and dRep1 are not the “all-1-s” and the “all-0-s” dReps, but rather they both vote in favor for the optimal proposal. Therefore, the proof of the lemma, although not involved, is not immediate, in contrast to the proof of Lemma 3. Lemma 6. In an instance of proxy selection, with k = 0, it holds that max{|A(dRep0)|,|A(dRep1)|}≥ |N′|, where N′ ={i∈N :v (win(P))=1}. 2 i 21

Suppose first that the number of voters attracted by dReps in D′\D′′ is at most 2|N′|. Then, |A(D′′)|≥|N′|− 2|N′| = |N′|. 3 3 3 Before continuing we define α:=|∪ i∈N(cid:101) R i | and β :=min{|R i |,i∈N(cid:101)}, where N(cid:101) is anyoftheγ (k,m-k)-coherentsetsofthevoters’partition,asdescribedinthestatement of the Theorem. We call N the number of voters, attracted by dReps in D′ \D′′ and say that 1 N ≥ 2|N′|. But then, for every voter i∈N it holds that R (1)≥ |Ri| ≥ β. But then, 1 3 1 i 2 2 the total number of approvals in P(cid:98) for proposals in C \S k , equals (cid:80) i∈N1 R i (1) ≥ |N |β ≥ 2|N′|β = |N′|β.Alltheseapprovalsarespreadbetweenαproposals.Therefore, 1 2 3 2 3 there exists a proposal j ∈R for which sc(j)≥ |N′|β. (cid:98) 3α Consequently, either there is a proposal approved by |N′|β voters or there exists a 3α set of dReps D′′ that can attract |N′|β voters without voting in favor of a proposal 3α disapproved by a voter in A(D′′). Using the fact that |N′|≥ ζn≥ ζopt(P), we have γ γ an approximation ratio of γ · β . Obviously, if every of the considered ζ, out of the γ ζ 3α (k,m-k)-coherent sets, is coherent, then an approximation ratio of γ is implied. 3ζ An interesting corollary of Theorem 13 (which could also be deduced from the proof of Theorem 11) is the following: When aiming for an optimal solution with 2k+1 dReps, it’s not a necessity for instances to be coherent; rather, the key factor is the existence of a set of k proposals commonly revealed to all voters. We conclude the discussion on generalizations with the following theorem, for the case of majority agreement (k = 0), which generalizes Corollary 1 by relating the achievable approximation to the structure of the revealed sets, once again without the requirement of coherence. Theorem 14. ForasingledRep,proxy selectionformajorityagreementadmitsan approximation ratio of min (cid:8) n,3α(cid:9), where α:=|∪ R | and β :=min{|R |,i∈N}. β i∈N i i Proof. It is apparent that any instance of proxy selection, is approximable within a factor of n, since it holds that electing arbitrarily a proposal j ∈C results in a winning proposal that satisfies sc(j)≥1≥ 1opt(P). Therefore suppose that min{n,3α}= 3α. n β β We proceed by showing that there exists a ballot type, the advertisement of which, results to an attraction of at least half of the voters that vote in favor of the optimal proposal. Recall that (cid:40) 1, if j =win(P), dRep0(j)= dRep1(j)=1, ∀j ∈C. 0, otherwise. Note that dRep0 and dRep1 are not the “all-1-s” and the “all-0-s” dReps, but rather they both vote in favor for the optimal proposal. Therefore, the proof of the lemma, although not involved, is not immediate, in contrast to the proof of Lemma 3. Lemma 6. In an instance of proxy selection, with k = 0, it holds that max{|A(dRep0)|,|A(dRep1)|}≥ |N′|, where N′ ={i∈N :v (win(P))=1}. 2 i 21 Proof of Lemma 6. We will prove that any arbitrary voter i∈N′ belongs to at least one of A(dRep0) and A(dRep1). We focus on the proposals R′ =R \{win(P)}. Let i i R′(0) = |{j ∈ R′ : v (j) = 0}|, and similarly, R′(1) = |{j ∈ R′ : v (j) = 1}|. Then, i i (cid:98)i i i (cid:98)i trivially, it holds that either R′(0) ≥ R′(1) or R′(1) > R′(0). If win(P) ∈ R , voter i i i i i i agrees with both dRep0 and dRep1 on win(P), whereas if win(P) ̸∈ R , by the i definition of the distance function, win(P) does not affect the distance of voter i from any dRep. Hence in both cases, proposal win(P) does not contribute to the distance of i from the two dReps, and therefore, (cid:22) |R′| (cid:23) (cid:22) |R | (cid:23) min{d(i,dRep0),d(i,dRep1)}≤0+ i ≤ i , 2 2 wheretheminimumisachievedbydRep0ifR′(0)≥R′(1),andbydRep1otherwise. i i From Lemma 6 it holds that either dRep0 or dRep1 can attract at least half of the voters in N′. If this holds for D ={dRep0}, we are done, because either the optimal proposal wins the election, via dRep0, or another proposal wins through the voters who vote directly, in which case the intrinsic score of the winning proposal j is at least sc (j)≥A(D)≥ |N′| ≥ |N′| ≥ |N′|β = β opt(P). (cid:98)D 2 3 3α 3α Otherwise, if dRep1 attracts at least half of the voters in N′, say that all voters from a set N ⊆ N are being attracted by dRep1. Then, for every voter i ∈ N , let 1 1 R (0) = |{j ∈ R : v = 0}| and R (1) = |{j ∈ R : v = 1}|. It should hold that i i (cid:98)i i i (cid:98)i R (1)>R (0), due to the fact that i∈A(dRep1). We distinguish two cases: i i • Suppose that |N |≥ 2|N′|, For every voter i∈N it holds that R (1)≥ |Ri| ≥ β. 1 3 1 i 2 2 But then, the total number of approvals in P(cid:98) equals (cid:80) i∈N1 R i (1) ≥ |N 1 |β 2 ≥ 2|N′|β = |N′|β. All these approvals are spread between α proposals. Therefore, 3 2 3 there exists a proposal j ∈R for which sc(j)≥ |N′|β. (cid:98) 3α • Suppose now that |N | < 2|N′|. But in this case, the set of voters in N′ \N 1 3 1 should be attracted by dRep0, again by Lemma 6. In total, these are at least |N′|− 2|N′| = |N′|. Therefore, if D ={dRep0}, the delegation representative will 3 3 vote with a weight of at least |N′|, only in favor of win(P), which would result 3 in sc (win(P)) ≥ |N′|. Then, either win(P) will win the election achieving an (cid:98)D 3 optimal solution, or a proposal j ∈ C \{win(P)} will win. In the later case, it should hold that sc (j) ≥ sc (win(P)) ≥ |N′| ≥ |N′|β. However, dRep0(j) = 0 (cid:98)D (cid:98)D 3 3α and hence sc (j)=sc(j). (cid:98)D (cid:98) We proved that whenever win(P(cid:98)D )̸=win(P), there exists a proposal j ∈C such that sc(j)≥ |N′|β ≥ β ·opt(P). The fact that sc(j)≥sc(j), concludes the proof. (cid:98) 3α 3α (cid:98) 4 Experiments We complement our theoretical results with experiments on the performance of voting with proxies on realistic data sets where voters exhibit incomplete preferences. We highlight the effect that the number of dReps, revealed set sizes and thresholds have 22 on the total number of voters who delegate instead of voting directly, as well as the approximation compared to the optimal outcome. The first hurdle to overcome is that, by definition, it is not possible to find datasets containing both revealed and intrinsic preferences, since voters only submit the first of the two. We use the MovieLens dataset (Harper and Konstan, 2015) to circumvent this issue, as there is enough contextual information to calculate plausible intrinsic preferences given the revealed ones. This set contains the reviews (with scores ranging from 0.5 to 5.0) given by 162.541 users to 62.423 movies. Of course, not every user has reviewed every movie. Each movie is characterized by a set of genres and also has a relevancescorefor1.084differenttags,providedbytheusers.Usingthisinformationwe calculate a plausible intrinsic user-specific “rating” Rat for any non-reviewed movie i: i (cid:80) Rat ·sim(i,j) Rat = j∈R j , i (cid:80) sim(i,j) j∈R where sim is a similarity metric (taking into account tag and genre relevance) and R is the set of movies reviewed by the user, hence Rat is the rating that user gave to j moviej.Notethatthesemovieratingsarebetween0.5and5.0,andarethenconverted to approval preferences by comparing them with the average rating given by that user. To calculate sim(·,·) we use two vectors per movie i: • The tag vector: tag ∈[0,1]1084. i • The genre vector: genre ∈{0,1}20. i The actual similarity is given by (cid:32) (cid:33) genre ·genre sim(i,j)=1.2∥tag i −tag j ∥· 0.5+ i j . ∥genre ∥·∥genre ∥ i j In addition, we take a random sample of users and movies such that each user has reviewed at least 5% of the movies and no movie has been reviewed by more than 10% of the users. Specifically, we begin by sampling a large subset of 13000 users and 150 movies, and filter out the users that have reviewed fewer than 5% of those movies, as well as the movies that have been reviewed by more than 10% of the users. This makes the effect of delegation (and using multiple dReps in particular) more pronounced, as there are few completely uninformed users that would readily delegate and no clear pick for a best movie. To enable meaningful comparisons, we add a movie that has not been reviewed by any user, but is approved by all in their intrinsic ratings. Even though in theory finding the optimal set of dReps is computationally intractable (see Theorem 9), we use a greedy heuristic, which works well in practice. Specifically, we can build the type of a dRep t incrementally, proposal by proposal, settingt(j)=1ort(j)=0dependingonwhichattractsthemostvoters,assumingthat the voters’ revealed sets only include proposals up to proposal j. We can repeat this procedure to create multiple dReps, removing the users that have already delegated at the end of every iteration. We first measure the fraction of users that opted to delegate, as a function of the numberofdRepsandeithertheirk (forfixedm )(Figure3,left)ortheirm (Figure3, i i i 23 1.00 0.75 0.50 0.25 0 10 20 30 NumberofdReps etaRnoitageleD 1.0 0.8 k =0.0·m m =1.0·m i i i k i =0.2·m i 0.6 m i =0.75·m k =0.4·m m =0.5·m i i i k =0.6·m 0.4 m =0.25·m i i i k =0.8·m m =0.1·m i i i 0.2 0 10 20 30 NumberofdReps Fig. 3: The fraction of voters that chose to delegate as a function of the total number of dReps. 1.4 1.2 1.0 0 10 20 30 NumberofdReps oitaRnoitamixorppA 1.6 k =0.5·m m =1.0·m i i i k =0.6·m m =0.75·m i i i 1.4 k =0.7·m m =0.5·m i i i k =0.8·m m =0.25·m i i i k =0.9·m 1.2 m =0.1·m i i i 1.0 0 10 20 30 NumberofdReps Fig. 4: The quality of the approximation as a function of the total number of dReps. right). In the first case each k ranges from 0 up to 0.4m , indicating users increasing i i levels of user agreement required before delegating. In the second, each m ranges from i 0 to 0.8m, capturing increasingly detailed revealed user preferences (while keeping k = 0.2m ). To obtain these m s we start from the calculated intrinsic preferences i i i (of size m) and we then “hide” some coordinates, uniformly at random, yielding the sparserrevealedpreferences.Ourresultsshowthatitiseasiertoattractdelegationfrom voterswithsmallerrevealedsets(leadingtosmallercoherentsets)orwithlowerk ’s.It i turns out, that this also does indeed translate to better approximations of the optimal approval score (see Figure 4; created similarly to Figure 3). These results suggest that, interestingly, the case of coherent instances studied in many of our theoretical results seems to be the most challenging in practice. Notice that while the graphs in Figures 3 and 4 are qualitatively similar, there are certain important differences. Specifically, the clearly diminishing returns structure observed when the only objective is to attract delegation in Figure 3 is not present in Figure4.Thisisbecausewhileitgetsprogressivelymoredifficultto“cluster” voters,the 24 quality of the outcomes increases in ever bigger jumps: at the very top, the difference between the best and second-best proposals (movies) will be greater than the second- best and third-best and so on, until their quality plateaus. This is also why the “jumps” in the approximation are steeper in some regions: a certain number of dReps does not have any effect (because even though they attract delegation, they cannot change the winner), but then suddenly this changes. Each run is repeated 20 times for a more accurate empirical mean and standard deviation.Allexperimentsranona2021M1ProMacBookwith16gigabytesofmemory and 10 high-performance cores. The code (available at https://www.plazos.me/code/ DelegatedVoting/ is parallelized and requires a few hours to complete, including some initial preprocessing of the data. 5 Discussion and Future Directions In this paper, we proposed and studied a model for proxy voting where the (less- informed) voters delegate their votes to the (fully-informed) proxies (dReps), once a certain agreement between their ballots is reached, or they vote directly otherwise. Our findings encompass essential insights into comprehending what is possible (potential) and what is not (limitations) in this setting. By identifying structural properties and other restrictions, we managed to escape the strong impossibilities that we had established. The upper and lower bounds presented in our work are not always tight, and future work could focus on sharpening these bounds. Perhaps more interesting is the migration from the “best-case scenario” setting that we study in this work. This would most probably entail the following two components: - An information model for the dReps. It would be reasonable to assume that each delegate representative is correctly-informed about each voter i’s approval preference ofeachproposaljwithsomeprobabilityp ,orthattheyare(perfectlyorimperfectly) ij informed about a randomly-chosen set of proposals for each voter. - A rationality model for the dReps.Delegaterepresentativesmightnothaveanyincen- tivestocoordinatetowardsthesocially-desirableoutcome,andtheywouldneedtobe properly incentivized to do that, e.g., via the form of payments. Additionally, dReps could even have their own preferences regarding the proposals under consideration. One could think of many other examples or refinements of the above, and the appropriate choice of information/rationality model for the dReps would depend on the application at hand. Tie-breaking rules that do not necessarily favor the optimal proposal also worth studying. Regardless of these choices however, the results of the “best-casescenario” shouldbethestartingpointofanyinvestigationintothosesettings. Besidesthoseextensions,otherdirectionsthatweseeaspromisingroutesforfurther researchonthetopicincludedifferentdistancemetrics,differentvotingrules,themulti- winner setting, elections on interdependent proposals, as well as a partial delegation setting where voters can opt to delegate only on proposals for which they have no opinion. 25 References Alouf-Heffetz S, Bulteau L, Elkind E, et al (2022) Better collective decisions via uncertainty reduction. In: Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pp 24–30 Anshelevich E, Filos-Ratsikas A, Shah N, et al (2021) Distortion in social choice problems: The first 15 years and beyond. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI) Survey Track., pp 4294–4301 AyadiM,AmorNB,LangJ,etal(2019)Singletransferablevote:Incompleteknowledge and communication issues. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp 1288–1296 Aziz H, Shah N (2021) Participatory budgeting: Models and approaches. In: Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations. Springer, p 215–236 Baumeister D, Dennisen S (2015) Voter dissatisfaction in committee elections. In: Pro- ceedingsofthe14thInternationalConferenceonAutonomousAgentsandMultiAgent Systems (AAMAS), pp 1707–1708 Becker R, D’angelo G, Delfaraz E, et al (2021) Unveiling the truth in liquid democracy with misinformed voters. In: Proceedings of the 7th International Conference on Algorithmic Decision Theory (ADT), pp 132–146 BouveretS,EndrissU,LangJ(2010)Fairdivisionunderordinalpreferences:Computing envy-free allocations of indivisible goods. In: Proceedings of the 19th European Conference on Artificial Intelligence (ECAI), pp 387–392 Brill M, Freeman R, Conitzer V (2016) Computing possible and necessary equilibrium actions (and bipartisan set winners). In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pp 418–424 Cabannes Y (2004) Participatory budgeting: a significant contribution to participatory democracy. Environment and urbanization 16(1):27–46 Caragiannis I, Micha E (2019) A contribution to the critique of liquid democracy. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp 116–122 Cevallos A, Stewart A (2021) A verifiably secure and proportional committee elec- tion rule. In: Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, pp 29–42 Cohensius G, Mannor S, Meir R, et al (2017) Proxy voting for better outcomes. In: Proceedingsofthe16thConferenceonAutonomousAgentsandMultiAgentSystems 26 (AAMAS), pp 858–866 Constantinescu A, Wattenhofer R (2023) Computing the best policy that survives a vote. In: Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp 2058–2066 Elkind E, Faliszewski P, Lackner M, et al (2015) The complexity of recognizing incomplete single-crossing preferences. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), pp 865–871 Frances M, Litman A (1997) On covering problems of codes. Theory Computing Systems 30(2):113–119 Fritsch R, Wattenhofer R (2022) The price of majority support. In: Proceedings of the 21st International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp 436–444 Halpern D, Halpern JY, Jadbabaie A, et al (2023a) In defense of liquid democracy. In: Proceedings of the 24th ACM Conference on Economics and Computation (EC), p 852 Halpern D, Kehne G, Procaccia AD, et al (2023b) Representation with incomplete votes.In:Proceedingsofthe37thAAAIConferenceonArtificialIntelligence(AAAI), pp 5657–5664 Harper FM, Konstan JA (2015) The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems 5(4):1–19 Imber A, Israel J, Brill M, et al (2022) Approval-based committee voting under incomplete information. In: Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pp 5076–5083 Kahng A, Mackenzie S, Procaccia A (2021) Liquid democracy: An algorithmic perspective. Journal of Artificial Intelligence Research 70:1223–1252 Kalech M, Kraus S, Kaminka GA, et al (2011) Practical voting rules with partial information. In: Proceedings of the 10th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp 151–182 Kerkmann AM, Rothe J (2019) Stability in fen-hedonic games for single-player devia- tions. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp 891–899 Kiayias A, Lazos P (2022) Sok: Blockchain governance. In: Proceedings of the 4th ACM Conference on Advances in Financial Technologies (AFT), pp 61–73 Lackner M (2014) Incomplete preferences in single-peaked electorates. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pp 742–748 27 Lang J (2020) Collective decision making under incomplete knowledge: possible and necessary solutions. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pp 4885–4891 LeGrand R, Markakis E, Mehta A (2007) Some results on approximating the minimax solution in approval voting. In: Proceedings of the 6th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp 1185–1187 Meir R, Sandomirskiy F, Tennenholtz M (2021) Representative committees of peers. Journal of Artificial Intelligence Research 71:401–429 Paulin A (2020) An overview of ten years of liquid democracy research. In: The 21st Annual International Conference on Digital Government Research, pp 116–121 Pivato M, Soh A (2020) Weighted representative democracy. Journal of Mathematical Economics 88:52–63 Revel M, Halpern D, Berinsky A, et al (2022) Liquid democracy in practice: An empirical analysis of its epistemic performance. In: ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization Terzopoulou Z (2023) Voting with limited energy: A study of plurality and Borda. In: Proceedings of the 22nd International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp 2085–2093 Terzopoulou Z, Karpov A, Obraztsova S (2021) Restricted domains of dichotomous preferences with possibly incomplete information. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp 5726–5733 Zhou A, Yang Y, Guo J (2019) Parameterized complexity of committee elections with dichotomous and trichotomous votes. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp 503–510 28