# As Time Goes By: Adding a Temporal Dimension
Towards Resolving Delegations in Liquid Democracy

Evangelos Markakis  Georgios Papasotiropoulos  Athens University of Economics
and Business, Athens, Greece Input Output Global (IOG)

###### Abstract

In recent years, the study of various models and questions related to Liquid
Democracy has been of growing interest among the community of Computational
Social Choice. A concern that has been raised, is that current academic
literature focuses solely on static inputs, concealing a key characteristic of
Liquid Democracy: the right for a voter to change her mind as time goes by,
regarding her options of whether to vote herself or delegate her vote to other
participants, till the final voting deadline. In real life, a period of
extended deliberation preceding the election-day motivates voters to adapt
their behaviour over time, either based on observations of the remaining
electorate or on information acquired for the topic at hand. By adding a
temporal dimension to Liquid Democracy, such adaptations can increase the
number of possible delegation paths and reduce the loss of votes due to
delegation cycles or delegating paths towards abstaining agents, ultimately
enhancing participation. Our work takes a first step to integrate a time
horizon into decision-making problems in Liquid Democracy systems. Our
approach, via a computational complexity analysis, exploits concepts and tools
from temporal graph theory which turn out to be convenient for our framework.

##  1 Introduction

Liquid Democracy (LD) is a novel voting framework that aspires to
revolutionize the typical voter’s perception of civic engagement and
ultimately elevate both the quantity and quality of community involvement. At
its core, LD is predicated on empowering voters to determine their mode of
participation. This can be achieved by either casting a vote directly, as in
direct democracy, or by entrusting a proxy to act on their behalf, as in
representative democracy. Notably, delegations are transitive, meaning that a
delegate’s vote can be delegated afresh, and at the end of the day a voter
that has decided to cast a ballot, votes with a weight dependent on the number
of agents that she represents, herself included. As a result of its
flexibility, LD is alleged to reconcile the appeal of direct democracy with
the practicality of representative democracy, yielding the best of both
worlds. The origin of the “liquid” metaphor remains a matter of debate up to
date, with one view being that it stems from the ability of votes to flow
along delegation paths, while an alternative view argues that it arises from
the ability of voters to revoke delegation approvals and continuously adjust
their choices. As we will justify shortly after, current work tends to
forcefully support the second opinion.

According to [6] there is a number of features that suffice to establish a
framework as a Liquid Democracy one. Most of them are related to the
transitivity property and to the options given to the voters about casting a
ballot or choosing representatives. These are more or less taken into account
in all relevant works that come from the field of Computational Social Choice.
A further aspect, called Instant Recall, encompasses the ability of voters to
withdraw their delegation at any time. As a matter of fact, in practice,
elections allow for extended (sometimes structured) periods of deliberation,
until the votes are finalized, and Liquid Democracy could serve as a means of
debate empowerment. A revocation of delegation may occur due to disagreements
with a delegate’s post-delegation choices, doubts on the integrity of one’s
behavior, or an agent’s further understanding of the issue under
consideration. A characteristic that is being shared by all the works in the
AI community is that they all seem to ignore the Instant Recall feature, and
examine isolated static delegation profiles. This oversight was identified and
criticized by the team behind the LiquidFeedback platform [2], the most
influential and large scale experiment of LD. In [3], inter alia, they claim
the following:

In a governance system with a continuous stream of decisions, we expect that
participants observe the actions (and even non-actions) of other participants,
in particular the activities of their (direct and indirect) delegates as well
as the activities of other participants, who they consider as delegates. Based
on their observations, we expect participants to adapt their own behaviour in
respect to setting, changing, and removing delegations and their own
participation. Based on the track records of the participants, a network of
trust or dynamic scheme of representation proves itself to be a responsible
power structure. […] We believe that the effects that occur through
observation and adaptation over time are an essential prerequisite for a
comprehensive understanding of liquid democracy, (which) requires a broader
view, namely adding a temporal dimension to delegation models.

Leaving aside the lack of temporal aspects in the literature, there are also
additional concerns to address in traditional LD models. A crucial
disadvantage is that we may experience delegation cycles or delegation paths
towards abstainers, which result to inevitably lost votes. A way that has been
suggested in theory [24, 32, 10] and has been implemented in practice [26], in
order to mitigate such issues is to allow each delegating agent to specify an
entire set of agents she approves as potential representatives together with a
ranking among them that indicates her preferences. Nevertheless, even with
these efforts, the discussed issues may still arise at the election-day. And
here is where the temporal dimension can come into play! The main focus of our
work is in proposing a framework that leverages temporal information to
address the identified concerns, while also providing a valuable tool for
deliberation.

In particular, our aim is to study the existence of efficient delegation rules
that fulfill certain desirable axioms. A delegation rule is a centralized
algorithm that takes as input the available information of the deliberation
phase and prescribes for each non-abstaining participant a delegation path to
a voter who casts a ballot. The main properties that we would like our rules
to satisfy are described below.

Time-Conscious Delegation Rules. We view the temporal dimension as an
important feature in the design of delegation rules. To demonstrate this,
consider an election where the information at the very end of the deliberation
phase can only produce a path to a cycle or to an abstainer, for some voter.
Our main insight is that one way to resolve such scenarios is to look into
approvals expressed during the previous time steps of the deliberation phase.
Our work operates under the premise that if a voter $v$ decides to trust
another voter $u$, at a given moment in time, say $t$, then $v$ accepts any
decisions made by $u$ at time $t$ or earlier (up to a certain number of time
steps prior to $t$, which could be given as a parameter by voter $v$). This is
because the decision to approve a delegation to $u$ is based on what $v$
observes in the previous time steps and up until time $t$. However, voter $v$
still retains the right to revoke her approval to $u$ at a later point in
time. If this occurs, then voter $u$ is permitted to represent $v$ only if she
chooses an action that she had declared at or before time $t$. We refer to the
rules that produce delegation paths respecting in such a way the ordering of
the time-instants at which a delegation is made available, as time-conscious
(for a formal definition refer to Section 2). In our model, time-conscious
delegation rules can guarantee the absolute approval of a delegating voter to
her ultimate representative.

Confluent Delegation Rules. In models incorporating multiple, ranked,
delegations, as the one under consideration, an esteemed property is
confluence, which posits that each voter should have at most one other
immediate representative in the final outcome [10]. This desirable attribute
guarantees that every voter is instructed to take a single action among the
three options: vote, abstain, or delegate her own and all received ballots to
a specific voter. On the contrary, a non-confluent rule may prompt a voter to
delegate different ballots received from different voters to different
representatives (and even delegate her own ballot to yet another
representative). Such suggestions can be challenging for a voter to follow. In
addition to its intuitive nature, confluence is also significant for
maintaining transparency and preserving the high level of accountability
inherent in classical Liquid Democracy, as highlighted in [24].

###  1.1 Contribution

Conceptually, we view as our main contribution that we explicitly add a
temporal dimension to (a generalization of) an existing framework. Hence this
is putting a stake in the ground in bridging a significant research gap
identified by practitioners. We then study the compatibility of computational
tractability with desirable properties of delegation rules, with the objective
of reducing the loss of votes resulting from delegation cycles or paths
towards abstaining agents, and ultimately enhance the electorate’s
participation. Namely we are interested in polynomially computable rules that
maximize the total utility of the electorate and at the same are time-
conscious and confluent. Unfortunately, despite the natural appeal of these
requirements, it turns out that this is too much to ask for: our results
demonstrate that such a delegation rule does not exist, unless P=NP, even for
simple variants of our model. Therefore, the best one could hope for is to
design efficient procedures that sacrifice one of the considered axioms.
Alternatively, one can also study more restricted models in which all the
desired properties can be simultaneously satisfied. Indeed, we offer positive
results in both directions, circumventing the NP-hardness results in several
cases. Finally, we believe that our work is making a pioneering contribution
to the Computational Social Choice literature, by incorporating concepts and
techniques from temporal graph theory, which is a novel approach in the field.

###  1.2 Related Work

We discuss first some works related to Liquid Democracy, in a way that “begins
at the beginning”, following the suggestion made to the White Rabbit in
“Alice’s Adventures in Wonderland”. The author of that novel, Charles Dodgson
(also known by his pen name Lewis Carroll), as early as 1884 [12], considers
an idea that was meant to be of vital importance for what we call Liquid
Democracy today. According to [1], it seems that he is the one that, before
all else, discussed the aspect of giving the agents the power to transfer to
others their acquired votes. On the other hand, it was Gordon Tullock [43] who
initiated the discussion about models that aspire to occupy the ground between
direct and representative democracy, by suggesting a model that allows voters
to decide whether they are interested in casting a ballot or delegate to
another voter. Shortly after, unlike Tullock’s suggestion, James Miller [36],
brought forward the idea that voters should not only choose their mode of
participation but should also enjoy the ability to retract a previously given
delegation in a day-to-day basis. At what concerns the nomenclature of LD, the
precise origins are unknown. The best one could refer to, is its seemingly
first [37] recorded appearance (in an obsolete wiki, preserved only on the
Internet Archive [41, 40]), in which a user nicknamed “sayke” discoursed about
a voting system that lies between direct and representative democracy and aims
at increasing civic engagement. However, none of these sources discussed
explicitly the aspect of transitivity of votes, as Dodgson did. Reinventions,
amendments and compositions of these ideas started to appear at the early 00’s
and we refer to [23] for an overview of them. The earliest published works
that incorporate the aspects of LD, (roughly) as we consider it today are [22,
25, 8, 15]. Nowadays, Liquid Democracy is one of the most active research
areas in Computational Social Choice [9, 38].

As already mentioned, the primary motivation of our work is due to [3] and the
framework we suggest is a generalization of the model in [10]. Furthermore,
our optimization objective coincides with the one in [21, 33]. To our
knowledge, our work is the first that incorporates temporal aspects in LD
models. Many different models and questions related to Liquid Democracy have
been examined. Indicatively, recently published works explored aspects
including, the study of voting power concentration through the lens of
parameterized complexity [18], the efficiency of altering delegations to
achieve consistency in participatory budgeting settings [28], the application
of power indices and criticality analysis to voters [16], and the evaluation
of LD’s epistemic performance [39].

##  2 Temporal Liquid Democracy Elections

We consider elections in which a set $V$ of $n$ voters should reach a decision
on a certain issue. Apart from voting themselves, the participants are given
two additional options: abstaining or delegating to other voters. The voters
also have some time available to consider what to do (e.g. to get informed on
the issue at hand or to observe other voters’ choices) and they are allowed to
change their mind, perhaps multiple times, until the actual election-day. We
say that such an election is a Temporal Liquid Democracy Election, a t-LD
election in short, if it consists of two phases:

  * •

A deliberation phase of $L$ rounds, where at every time-instant $t\in[L]$,
each voter $v$, has to choose whether to personally vote or not. If she
decides to cast a ballot, we consider this as her final decision that will not
change in the remaining time-steps. As long as a voter $v$ has not decided to
cast a ballot herself till time $t$, she is asked to specify the following:

    * -

A set of approved voters $S_{v}^{t}\subseteq V\setminus\\{v\\}$ (which may be
the empty set, if $v$ wants to abstain at round $t$), indicating the voters
that she trusts to cast a ballot on her behalf, possibly with different levels
of confidence. These voters may in turn also be willing to delegate their vote
to other participants as well.

    * -

A (weak) preference ranking over the voters in $S_{v}^{t}$, which induces a
partition of $S_{v}^{t}$ into preference groups, according to $v$. This is
accompanied by a positive integer score $sc_{v}^{t}(i)$, indicating the
utility or happiness level that $v$ experiences if a voter from her $i$-th
most preferred group at time $t$, will ultimately be selected as her immediate
representative.

    * -

A non-negative integer-valued trust-horizon parameter $\delta_{v}^{t}$, with
$\delta_{v}^{t}\leq t-1$, by which, she indicates approval for the views held
by any voter in $S_{v}^{t}$ up to $\delta_{v}^{t}$ time-steps prior to time-
instant $t$.

  * •

A casting phase, in which all the voters that, during the deliberation phase,
expressed willingness to vote (and only these), eventually cast a ballot on
the issue under consideration. Every voter who did not previously declare an
intention to vote, is being assigned a representative and a pre-specified
delegation rule, that takes into account the entire deliberation phase, is
being used to make such decisions. The winner(s) of the election are elected
using a weighted voting rule, where the weight of a voter is determined based
on the number of voters that she represents.

For an illustrative exposition of our model we refer to the example provided
at the end of the section. We now elaborate on the input that is required from
the voters, during the deliberation phase. The preference ranking facilitates
voters to express different levels of confidence towards other participants
who could potentially represent them. Also, the scoring function allows the
model to capture the cases where a voter is willing to either increase her
scores over rounds due to becoming gradually more informed about another
voters’ opinions or in the opposite direction, decrease scores due to becoming
more hesitant about who represents her. Realistically, we expect voters to
have just a few preference groups, and hence they do not need to submit too
many numerical parameters. Furthermore, the intuition behind the trust-horizon
parameters is that the decision of a voter $v$ to approve a delegation to $u$
at time $t$, can be based only on looking at the behavior of $u$ in the
previous rounds and up until time $t$ of the deliberation phase. Since a voter
$v$ may not agree with $u$ in all previous time steps, the parameter
$\delta_{v}^{t}$ specifies that $v$ agrees with the choices made by $u$ at any
preceding time that is no more than $\delta_{v}^{t}$ time-instants before $t$.
A simple case to have in mind is when $\delta_{v}^{t}=t-1$ (i.e., $v$ trusts
whatever $u$ has chosen at any time in the past). If this property holds for
every voter $v$ and for any $t\in[L]$, we say that the election profile is of
retrospective trust. Finally, note that under the suggested model, the voters’
declared sets, their preference orders, their scores and trust-horizon
parameters may change arbitrarily between subsequent time-instants.

Variants of the Model and Practical Considerations. Customization is key to
the proposed decision-making model, which offers a range of possibilities to
enhance its practicality and reproducibility. For instance, it would be more
natural to allow a voter to specify a different time-horizon parameter for
each of her approved representatives. Notably, our findings are not impacted
by the assumption of a uniform trust-horizon for approved representatives.
Furthermore, we have assumed that once a voter expresses the desire to cast a
ballot, she will no longer change her opinion until the election-day. This
assumption is justified by the fact that once a voter has committed to
becoming more informed on the topic, participating in further deliberation is
deemed redundant. Nonetheless, the assumption is made only for technical
convenience and could be dropped. Moreover, although our aim is to examine the
model in its fullest generality, we stress that in potential real-life
implementations, the voters may not need to submit all the information that we
have described in every round. In particular, the scoring function could be
automatically generated by the system, given the (weak) ranking on $S_{v}^{t}$
submitted by each voter. E.g., one could use the Borda-scoring function (as in
[10]), under which, at any time-instant, a voter assigns a score of 1 to her
last preference group, a score of $2$ to her second to last group, etc) or any
other appropriate method. We highlight that our model is a strict
generalization of the model considered in [10], not only because of the
temporal dimension but also because of the more general scoring functions that
we allow. The trust-horizon parameter could also be pre-specified, so that the
voters do not need to submit any information regarding it, either by assuming
that the trust of every voter goes arbitrarily back in time or for a fixed
number of steps prior to each approval. Finally, if voters have the same
preferences for consecutive time-steps, they would not need to re-specify
them.

Delegation Rules. In the elections we consider, we essentially have three
types of participants. We refer to the voters that declared intention to vote
as casting voters, and these will be the only voters who will indeed finally
cast a ballot at the election-day. Furthermore, the non-casting voters that
will abstain from the election are precisely those who do not approve anyone
at the final time-step, e.g. a voter $v$ such that $S_{v}^{L}=\emptyset$. We
refer to such voters as abstaining voters. Finally, the rest of the voters
will be called delegating voters. As evident from Section 1, and as will be
further illustrated by the example at the end of this section, the temporal
dimension could be considered valuable when the examination of the isolated
instance at $t=L$ cannot produce a feasible solution (i.e. delegation cycles
or paths towards abstainers are unavoidable) or its feasible solutions are not
good enough. A delegation rule is a mechanism that ’resolves delegations’ and
addresses such problematic cases, or in other words, a procedure that
ultimately assigns to each delegating voter, a casting voter, possibly via
following some path of trust relationships. More formally, a delegation rule
is a function that takes as input the voters’ preferences, as reported during
the entire deliberation phase of a t-LD election, and outputs a path to a
casting voter, for every delegating voter. A valid delegation rule should ask
casting voters to vote, abstaining voters to abstain and should not suggest
any delegation path towards an abstainer or introduce delegation cycles.

Temporal Graphs. The driving force in our work is to model and analyze t-LD
elections using principles from temporal graph theory. We start with a basic
overview of the concept and the terminology of temporal graphs and following
this, we will introduce some notation that we will use in the remainder. In
high level, a temporal graph is nothing more than a simple, called static,
graph in which a temporal dimension is being added, i.e., a graph that may
change over time. Frequently, a temporal (multi)graph is being expressed as a
time-based sequence of static graphs. For convenience, we will use an
equivalent definition, under which, a (directed) temporal (multi)graph
$G(V,E,\tau,L)$ is determined by a set of vertices $V$, a (multi)set of
directed, temporal edges $E$, a discrete time-labelling function $\tau$ that
maps every edge of $E$ to a subinterval of $[1,L]$, and a lifespan
$L\in\mathbb{N}$. If the edges of $E$ are weighted according to a function
$w:E\rightarrow\mathbb{N}$, then we say that $G$ is weighted. The interval
$\tau(e)$, for an edge $e$, indicates that $e$ is available at the time-
instants that belong to $\tau(e)$. We say that each edge $e$ is assigned an
interval labeling $\tau(e)=[s_{e},t_{e}]$, (possibly, $s_{e}=t_{e}$ if the
edge is available for a single time-instant) and by allowing $G$ to be a
multigraph111We are using multigraphs instead of (simple) graphs merely for
technical convenience, and we note that, alternatively, one could work with
graphs by letting $\tau$ be a function that maps edges to a set of
subintervals of $[1,L]$.  it is permitted for an edge to be present in
multiple (disjoint) time-intervals. Unless otherwise stated, henceforth, by
the term graph, we denote a weighted directed temporal multigraph. For more
details on temporal graphs we refer to a relevant survey [35], as well as to
the fundamental and influential works [30, 31, 34]. The static variant of a
temporal graph is the static graph that emerges if we ignore the time-labels
of its edges. We call a graph temporal directed tree rooted at vertex $r$ if
its static variant contains a directed path towards $r$ from every other
vertex and its undirected variant is a tree. A crucial concept for our work,
in the context of temporal graphs, is the notion of time-conscious paths, that
satisfy a monotonicity property regarding the temporal dimension of their
edges. Consider a temporal graph $G(V,E,\tau,L)$, coupled with a tuple
$\delta_{v}=(\delta_{v}^{t})_{t\in[L]}\in\mathbb{N}^{[L]}$ for every vertex
$v$ of $V$. Let also $\delta=(\delta_{v})_{v\in V}$. We say that a path in $G$
from $v_{1}$ to $v_{k+1}$ is $\delta$-time-conscious if it can be expressed as
an alternating sequence of vertices and temporal edges
$(v_{i},(e_{i},t_{i}),v_{i+1})_{i\in[k]}$, such that for every $i\in[k]$ it
holds that $e_{i}=(v_{i},v_{i+1})\in E$, $t_{i}\in\tau(e_{i})$ and for every
$i\in[k-1]$ it holds that $t_{i}\geq t_{i+1}\geq
t_{i}-\delta_{v_{i}}^{t_{i}}$. Similar notions have been applied to various
domains including convenient flight connections detection [44], information
diffusion [27] and infectious disease control through contact tracing [5]. In
the remainder of Section 2, it will become more clear how this notion fits in
our framework. We also call $\delta$-time-conscious, a temporal directed tree,
rooted at a vertex $r$, if all its paths towards $r$ are $\delta$-time-
conscious. Finally, we conclude by noting that illustrative examples of some
of the terminology discussed here, can be found at Appendix B.

Modelling t-LD Elections as Temporal Graphs. The deliberation phase of a t-LD
election can be modeled as a weighted directed temporal multigraph
$G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta)$ that is formed by

  * •

a vertex in $V$ for every voter of the electorate, as well as a special vertex
$\triangledown$, connected only with the casting voters,

  * •

a multiset $E$ of temporal edges that represent the approvals for delegation
or ballot casting per round via a function $\tau$ that assigns a time-label to
every edge,

  * •

a lifespan $L$ that represents the duration of the deliberation phase,

  * •

a function $w$ that assigns a weight to every edge $(v,u)$ of $E$, according
to $sc_{v}^{t}$, provided that $t\in\tau((v,u))$,

  * •

a vector $\delta$ that, for every voter $v$, contains a tuple
$(\delta_{v}^{t})_{t\in[L]}$, as declared by $v$ during the deliberation
phase. For convenience, we allow $\delta$ to have some empty entries,
corresponding to casting voters or to time steps during which the
corresponding voter abstained.

We note that if a casting voter had indicated preferences for potential
representatives before deciding to cast a ballot, these preferences, and their
corresponding edges, can be safely disregarded. More precisely, only the
following two types of edges may exist: directed edges of the form $e=(v,u)$
for $v\in V\setminus C$ and $u\in V$ with $\tau(e)=[s_{e},t_{e}]$, indicating
that at any time-instant $t\in[s_{e},t_{e}]$, voter $u$ belongs to
$S_{v}^{t}$, and directed edges $e=(v,\triangledown)$ for $v\in C$ with
$\tau(e)=[s_{e},L]$, indicating that from time $s_{e}$ and onwards, voter $v$
agrees to cast a ballot. Furthermore, we will proceed by assuming that the set
of voters $V$ is implicitly partitioned into three sets, as has been explained
before: the set of casting voters $C$, the set of abstaining voters $A$ and
the set of delegating voters $D$. More formally, $C=\\{v\in
V:(v,\triangledown)\in E\\}$, $A=\\{v\in V\setminus
C:L\notin\tau((v,u)),\text{for any }(v,u)\in E\\}$ and $D=V\setminus(C\cup
A)$. The weight function $w$ indicates the cardinal preferences of a voter, as
implied by the scores that accompany her preference rankings during the
deliberation phase. Additionally, for convenience, we set to zero the weights
of edges $(v,u)$ such that $v$ corresponds to a casting or an abstaining
voter. This choice can be justified by the upcoming discussion of the
optimization objective in the “Electorate’s Satisfaction” paragraph. Given a
graph $G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta)$ that models a t-LD
election, a delegation rule returns, for every delegating voter $v$, a
weighted directed temporal path from $v$ to $\triangledown$. Such a path
infers an assignment of every delegating voter to a casting one. A delegation
rule is called efficient if its output can be computed in polynomial time in
the input size.

Axiomatic Principles. We discuss here the axioms that constitute the main
focus of our work, namely time-consciousness and confluence. We have
extensively discussed these two properties in the analogous paragraphs of
Section 1 and we now formally define them using the framework of temporal
graphs. Given a graph $G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta)$ that
models a t-LD election, a delegation rule is

  1. 1.

time-conscious, if for every delegating voter $v$, the delegation path output
for $v$ is a $\delta$-time-conscious directed temporal path,

  2. 2.

confluent, if the union of the paths output for all the delegating voters is a
directed temporal tree, rooted at vertex $\triangledown$, that spans the
vertices of $V\setminus A$.

The definition of time-consciousness guarantees that all paths suggested by
the delegation rule satisfy the constraints imposed by the voters, regarding
their trust-horizon parameters. Hence, for any edge $(v,u)$ in an output path,
$u$ must choose an action (edge) that she had declared at a time that was
approved by $v$. The definition of confluence guarantees that for every
delegating voter $v$, there is a unique path to a casting voter, that is
intended to serve both $v$ and all voters who delegated to $v$. In Appendix B
we provide examples of time-conscious and confluent solutions, for further
illustration.

Electorate’s Satisfaction. We make the usual assumptions for Liquid Democracy
models that (a) voters completely trust their representatives and (b) trust
between voters is transitive. This implies that if voter $v$ accepts voter $u$
as her potential representative, she concurs with any subsequent choice made
by $u$ and also extends trust to any voter $w$ who may be entrusted by $u$.
Hence, we note that the utility experienced by a delegating voter from a
delegation rule can be considered as a local one, being contingent solely on
the voter’s immediate representative and not influenced by further choices
made by the chosen representative. Hence the utility of a delegating voter,
under a delegation rule, can be determined by the score that she declared for
her immediate representative, specified by the rule. Note that two different
time-instants $t,t^{\prime}$ may exist such that $u\in S_{v}^{t}\cap
S_{v}^{t^{\prime}}$. In these cases, given that the output of a delegation
rule is a set of temporal paths, if the rule suggests a delegation from $v$ to
$u$, it also explicitly specifies the time-instant at which the delegation
will occur, say e.g. at time $t^{\prime}$ and, thereby the utility of $v$ is
equal to $sc_{v}^{t^{\prime}}(i)$, if $u$ belongs to the $i$-th most preferred
group of $v$, at time $t^{\prime}$. Regarding now the casting voters, we do
not take into account their utility since their will to cast a ballot has been
realized; we do the same for abstaining voters. We consider as infeasible
every solution that asks a casting (resp. abstaining) voter to delegate her
ballot or abstain (resp. vote), and hence, our focus will be on the welfare of
the delegating voters. Finally, the quality of a rule is assessed by the total
satisfaction it elicits from the electorate which is expressed as the sum of
utilities of all delegating voters. Our optimization objective then is to
maximize the electorate’s satisfaction, as defined by the resolve-delegation
problem below.

resolve-delegation
---
Instance: |  A graph $G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta)$ that represents the deliberation phase of a t-LD election.
Goal: |  Compute a weighted directed temporal path from each delegating voter to $\triangledown$, with the aim of maximizing the total utility derived from the delegating voters, defined as the sum of the weights of the paths’ first edges.

Example. As an illustration, consider the following instance of a t-LD
election with 5 rounds and 6 voters, namely Alice, Bob, Charlie, Daisy, Elsa,
and Fred. Their preferences are outlined below:

  * •

Alice initially intended to delegate to Charlie. In the second round, she
decided to get informed about the considered issue and vote.

  * •

Bob did not participate in the deliberation phase during the first round, but
approved Alice in the second round. In the third round, he revoked his
approval of Alice and instead approved Chris and Elsa. Bob’s approval of Elsa
remained until the final round.

  * •

Charlie approved Alice only in the beginning of the election. He also approved
Bob in the first and third round, but removed his approval (and abstained) in
the second round. In the fourth round, Charlie approved both Daisy and Fred,
but he removed his approval of Daisy in the final round.

  * •

Daisy expressed interest in being a casting voter from the beginning until the
end of the deliberation phase.

  * •

Although Elsa intended to delegate her ballot to Fred at certain times,
ultimately both refrained from participating in the election.

The described instance can be visualized using the graph shown in the side
figure. We assume that $\delta_{B}^{t}=1$ and $\delta_{C}^{t}=t-1$ for every
$t\in\\{1,2,\dots,5\\}$. The scores assigned by the voters to their approved
representatives are encoded by the form of the edges, where curly edges have
weight $1$, straight edges have weight $2$, and double-lined edges have weight
$3$. Dotted edges indicate the casting voters. The labels of the edges
represent the time-intervals of their presence. In this instance, Alice and
Daisy form the set of casting voters, while Elsa and Fred abstain. Therefore,
edge $(A,C)$ can be removed, since Alice will definitely cast a ballot. In a
$\delta$-time conscious solution, Bob would not delegate to Charlie, since no
$\delta$-time-conscious path to $\triangledown$ using the edge $(B,C)$ exists,
for instance, edge $(C,A)$ violates the time-horizon declared by Bob.
Similarly, Charlie would not delegate neither to Alice nor to Bob at time $1$.
Since we do not allow Bob to delegate to an abstainer, he must delegate to
Alice, whom she trusted at time $2$. Then, there are two possible outcomes for
the delegation rule, depending on the choice made for Charlie. The edge that
maximizes Charlie’s utility is $(C,D)$. Therefore, the optimal delegation rule
that is both time-conscious and confluent, would suggest the set of paths
$\\{((C,D),(D,\triangledown)),((B,A),(A,\triangledown))\\}$, achieving a total
satisfaction score of $4$. Finally, in this example it is plainly evident how
the temporal dimension comes to the rescue: if one were to focus solely on the
snapshot taken at time $5$, disregarding the information garnered from the
deliberation phase, the only option would be to ask Bob and Charlie to
delegate to abstaining voters. Instead, our framework utilizes the information
obtained throughout the deliberation phase to propose an outcome that avoids
paths towards abstainers and delegating cycles.

##  3 Computational Complexity of Resolving Delegations in t-LD elections

In this section we explore the compatibility of the axioms we have put forward
from Sections 1 and 2, with efficient computation. We highlight that all the
missing proofs from the paper can be found in the Supplementary Material of
our work. Unfortunately, our first result shows that it is impossible to have
polynomially computable utility maximizing delegation rules that satisfy
simultaneously the axioms of time-consciousness and confluence, unless P=NP,
even under simple and natural restrictions. Before stating the result, we
discuss the types of instances for which we establish hardness. To begin with,
it is expected that in real-life elections, voters tend to exhibit a
relatively stable and consistent opinion over time, and do not revise their
preferences numerous times during the deliberation phase, due to the effort it
would require to gather and process new information. Similarly, it is
reasonable to expect that due to limited cognitive capacity, the voters are
only able to partition their accepted representatives into a few disjoint
preference groups. The theorem that follows demonstrates that the
computational intractability of resolve-delegation persists even when we limit
the voters to changing their minds at most once during the deliberation phase
and partitioning their accepted representatives into at most two groups, at
each round. Furthermore, it holds even for instances of retrospective trust,
and with Borda-scoring functions. Therefore, the primary takeaway is that
incorporating temporal aspects in conjunction with natural requirements does
come at a computational cost.

######  Theorem 1.

resolve-delegation in a time-conscious and confluent manner is NP-hard, even
for profiles of retrospective trust and under the Borda-scoring function.

###### Proof.

We provide here a description of the reduction and defer the proof to Appendix
A. Given a graph $G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta)$ and a
parameter $k$, we call $\Pi$ the decision variant of resolve-delegation in a
time-conscious and confluent manner, which asks for the existence of a
solution with total satisfaction at least $k$. At what follows, we provide a
reduction to $\Pi$ from the NP-hard problem [27] minimum temporal spanning
tree (t-mst), which we formally define shortly. Before moving on to the
definition of t-mst, we note that in temporal graph theory the term time-
respecting is being used to describe, a temporal path
$(v_{i},(e_{i},t_{i}),v_{i+1})_{i\in[\ell]}$, such that for every
$i\in[\ell]$, it holds that $e_{i}=(v_{i},v_{i+1})$, $t_{i}\in\tau(e_{i})$,
and $1\leq t_{1}\leq t_{2}\leq\dots\leq t_{\ell}\leq L$ (also called “journey”
or simply “temporal” in the related literature). We also refer to Appendix B
for an example. The difference between time-respecting and $\delta$-time-
conscious paths is that the paths of the former type are formed by edges whose
time-stamps are in non-decreasing order of visiting, in contrast to the paths
of the latter type, whose edges have time-stamps in non-increasing order, and
on top of that, satisfy a waiting-time constraint indicated by vector
$\delta$.

In the t-mst problem, we are given a temporal graph
$G^{\prime}(V^{\prime},E^{\prime},\tau^{\prime},L^{\prime},w^{\prime})$, as
well as a root vertex $u_{0}^{\prime}\in V^{\prime}$ and an integer
$k^{\prime}$. We are asked for a directed temporal tree of $G^{\prime}$,
called $T^{\prime}$, of edge set $E^{\prime\prime}$, that spans the vertices
of $V^{\prime}$ and that has a time-respecting path from $u_{0}^{\prime}$ to
every vertex of $V^{\prime}$, such that $\sum_{e\in
E^{\prime\prime}}w^{\prime}(e)\leq k^{\prime}$. Note that t-mst is NP-hard
even for the case where $w^{\prime}(e)\in\\{1,2\\},\forall e\in E^{\prime}$,
and for every $v\in V^{\prime}$ there exists a $u\in V^{\prime}$, such that
$L^{\prime}\in\tau^{\prime}((u,v))$. It is without loss of generality to
assume that $u_{0}^{\prime}$ has no in-coming edges in $E^{\prime}$.
Furthermore, the hardness holds for instances in which for any pair of
vertices $u,v$ of the input graph
$G^{\prime}(V^{\prime},E^{\prime},\tau^{\prime},L^{\prime},w^{\prime})$,
either $(u,v)\notin E^{\prime}$, or there are two copies, $e_{1}$ and $e_{2}$
of $(u,v)$ in the multiset $E^{\prime}$. In the second case, it also holds
that
$\tau^{\prime}(e_{1})=[1,L^{\prime}-1],\tau^{\prime}(e_{1})=[L^{\prime},L^{\prime}]$
and that $w^{\prime}(e_{1})=2,w^{\prime}(e_{2})=1$.

Given such an instance
$(G^{\prime}(V^{\prime},E^{\prime},\tau^{\prime},L^{\prime},w^{\prime}),u_{0}^{\prime},k^{\prime})$
of t-mst we create an instance
$(G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta),k)$ of $\Pi$ as follows:

  * •

let $L=L^{\prime}$,

  * •

for every vertex $u^{\prime}\in V^{\prime}$ we add a vertex $u\in V$,

  * •

for every directed edge $(u^{\prime},v^{\prime})\in E^{\prime}$ we add a
directed edge $(v,u)$ such that $w(v,u)=3-w^{\prime}(u^{\prime},v^{\prime})$
(recall that $w^{\prime}(u^{\prime},v^{\prime})\in\\{1,2\\}$) and
$\tau((v,u))=\tau^{\prime}((u^{\prime},v^{\prime}))$,

  * •

we add a special vertex $\triangledown$ and a directed edge
$e=(u_{0},\triangledown)$ such that $w(e)=0$ and $\tau(e)=[1,L]$,

  * •

we add one more special vertex $a\in V$,

  * •

for every $t\in[L]$ and $v\in V$ such that there exists in $E$ an out-going
edge from $v$ at time $t$ of weight $2$ but not of weight $1$, we add an edge
(called “dummy”) $e=(v,a)$ such that $w(e)=1$ and $\tau(e)=[t,t]$,

  * •

for every vertex $v\in V\setminus\\{a\\}$ that corresponds to a non-casting
voter and for every $t\in[L]$, we set $\delta_{v}^{t}=t-1,$

  * •

we set $k$ to be $3(n-1)-k^{\prime}$.

For the remainder of the proof, we refer to Appendix A. ∎

We will now explore roads to circumvent the impossibility result of Theorem 1.
Our proposal is to relinquish either the necessity for efficiency or one of
the axioms of time-consciousness and confluence, in hopes of solving resolve-
delegation. Our findings show that this strategy proves successful for some of
the problems that emerge, which highlights that Theorem 1 is not devastating.
Notably, most of the suggested procedures are simple enough and therefore are
confirmed as strong contenders for practical applications.

We begin with studying the easiest variant of resolve-delegation in which the
requirement of time-consciousness is being disregarded. This is mainly done
for the sake of completeness since studying it requires overlooking the
temporal dimension of the instance, which is the defining characteristic of
our work. In order to solve efficiently resolve-delegation in a confluent but
not necessarily time-conscious manner, the delegation rule can treat any input
submitted by a voter at any time as if it was not subject to time-related
constraints. Since confluence implies that the output should be a directed
tree, and since the utility of each delegating voter is determined by its
outgoing edge, then all edges of the tree with non-zero weight will contribute
exactly once to the total satisfaction, and therefore, the objective is to
find a (static) directed tree of maximum total weight, that is rooted at
$\triangledown$ and spans the vertices of $V\setminus A$. To solve this
problem we leverage the well-known algorithm by Edmonds [20] (also
independently discovered in [7, 14] and improved in [42]) for the directed
analog of the classic minimum spanning tree problem.222To be noted that in
[10], a confluent delegation rule, referred to as MinSum, has been proposed,
under a more restricted voting framework compared to ours, and its polynomial
time computability has been very recently established [17], using an approach
that is also based on Edmonds’ algorithm. In this problem, given a weighted
directed static graph $G(V,E,w)$ and a designated vertex $r\in V,$ we are
asked for a subgraph $T$ of $G$, the undirected variant of which is a tree, of
minimum total cost, such that every vertex of $G$ is reachable from $r$ by a
directed path in $T$. It is important to note that in our case, the paths we
need to compute are towards a fixed vertex, rather than originate from it. To
apply Edmonds’ algorithm, we adjust graph $G$ to an appropriate graph
$G^{\prime}$, as indicated by Procedure 1.

######  Theorem 2.

Procedure 1 solves resolve-delegation in a confluent manner, in polynomial
time.

1. A confluent and efficient utility maximizing delegation rule for input $G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta)$.

We now shift our focus to efficient utility maximizing delegation rules that
satisfy time-consciousness but are not necessarily confluent. Despite not
necessarily resulting in a tree structure, such a rule should still suggest a
precise path to a casting voter for every delegating voter $v$. Then, the
utility of $v$ will be derived from her immediate representative (i.e., the
weight of the first edge) in that path, regardless of whether other paths
going through $v$ may exist for serving other voters who have delegated to
$v$. The question of why non-confluent delegation rules merit investigation is
discussed in [10]. It was discovered that, among a large family of delegation
rules, only non-confluent rules possessed the potential to satisfy the axiom
of copy-robustness, an axiom that is also motivated by practical
considerations [4]. Moreover, there are non-confluent rules with desirable
properties that have been previously studied, such as the Depth-First-
Delegation rule that precludes the possibility of Pareto-dominated delegations
[32]. Hence, it is not unprecedented to sacrifice confluence on the altar of
attaining other desirable attributes. However, quite surprisingly, even in the
absence of a requirement for a confluent rule, resolve-delegation remains NP-
hard, as shown by the following theorem. Notably, the result holds even for
simple scenarios that involve only a brief deliberation phase, uniform trust-
horizon parameters across all voters and a lone delegating voter and it is
orthogonal to the result of Theorem 1 since it explicitly uses the fact that
the considered elections are not of retrospective trust.

######  Theorem 3.

resolve-delegation in a time-conscious manner is NP-hard, even for profiles
with only a single delegating voter.

Continuing with our study of efficient utility-maximizing delegation rules
that are time-conscious but not necessarily confluent, we now turn to
exploring potential workarounds to the impossibility result of Theorem 3. To
overcome the computational intractability, we restrict ourselves to the still
hard variant where the voters share the same time-horizon parameter and
propose the following relaxations:

  * (a)

Assuming retrospective trust profiles, i.e. $\delta_{v}^{t}=t-1$, for every
voter $v$ and for every time-step $t$ such that $v$ approves to delegate her
ballot at time $t$. These profiles are motivated by the fact that in real
life, we do not expect voters to change their opinion in an arbitrary manner,
and hence it is likely that a delegating voter trusts another voter for all
the previous time instants before $t$.

  * (b)

Permitting walks instead of only paths, or in other words allowing for
revisits to vertices, along a path from a delegating voter to a casting one.
This enlarges the solution space and can be helpful towards achieving time-
consciousness in certain instances, as it may be necessary to go through a
cycle before being able to satisfy the time constraints. For an illustration,
we refer to Appendix B.

The approach of neglecting confluence, enables the development of local
delegation rules, likewise the rules studied in [11], that make a decision for
every voter completely independent of the choices made for the rest of the
electorate. For the two relaxations suggested in the previous discussion, we
suggest a simple procedure that, in high level, visits every vertex $v$,
corresponding to a delegating voter $v$, in a sequential manner, and for each
such vertex, it detects a feasible, i.e. $\delta$-time-conscious, way to reach
$\triangledown$, that uses the out-going edge of $v$ of maximum possible
weight. The aforementioned way of reaching a casting voter can be computed by
a suitable modification of the temporal analog of the Breadth-First search
algorithm from [34], in the case where the input profile is of retrospective
trust and by using the polynomial procedure that is based on Dijkstra’s
algorithm, from [5], in the case where walks are allowed and all voters share
the same trust-horizon parameter.

Concerning the first relaxation, in [34], a polynomial-time algorithm was
suggested to solve a (more general than what we need in our setting) problem,
called foremost path. In this, we are given a (unweighted) directed temporal
graph $G(V,E,\tau,L)$, a source vertex $v\in V$, a sink vertex $u\in V$, and a
time-instant $t_{start}\in[L]$, and we are asked to compute333To be more
precise, the goal is to select the path that minimizes the arrival time but
for our purposes, this objective is superfluous (but harmless). a time-
respecting path from $v$ to $u$, that starts no sooner than $t_{start}$ (or
report that such a path does not exist). Recall that, the definition of a
time-respecting path has been provided in the proof of Theorem 1.

For the second relaxation, we give first the following definition: Given, a
temporal graph $G(V,E,\tau,L,\delta)$ in which all entries of the vector
$\delta$ coincide with a fixed value $\Delta$, a temporal walk $p$ of $G$ of
length $\ell$, say $p=(v_{i-1},(e_{i},t_{i}),v_{i})_{i\in[\ell]}$ such that
$v_{i}$’s are not necessarily all pairwise distinct, is called
$\Delta$-restless if for every $i\in[\ell]$ it holds that
$e_{i}=(v_{i-1,}v_{i})$ and that $t_{i}\in\tau(e_{i})$ and for $i\in[\ell-1]$
it holds that $t_{i}\leq t_{i+1}\leq t_{i}+\Delta$. To solve efficiently the
relaxation of resolve-delegation in a time-conscious manner, when walks are
allowed, we will utilize the procedure from [5], that outputs444Once again,
the problem studied in [5] is more general than the problem we need to
consider here, both in terms of the input graph and the optimization
objective(s), but it can be easily adapted to meet our requirements. a
$\Delta$-restless temporal walk between two specified vertices, for any fixed
parameter $\Delta$. For compactness, we provide a unified presentation of the
positive results, under Procedure 2, which handles both relaxations. In the
statement and analysis of this procedure, we will use the term journey to
refer either to a path when dealing with the first relaxation or to a walk
when discussing the second relaxation.

######  Theorem 4.

Procedure 2 solves resolve-delegation in a time-conscious manner, in
polynomial time, for profiles of retrospective trust. Moreover, the same holds
for the variant of the problem where walks are allowed, for profiles in which
there is a common, fixed trust-horizon parameter, for all voters and all time-
steps.

2. A time-conscious and efficient utility maximizing delegation rule for input $G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta)$ applicable for profiles of retrospective trust or profiles in which walks are allowed.

We conclude with studying the problem resolve-delegation in a time-conscious
and confluent manner, but now without the requirement of computational
efficiency. Clearly, if polynomial solvability is no longer a worry, a
straightforward brute-force procedure, that in time exponential in the number
of edges and in $L$ examines all possible trees, can be utilized to maximize
the voters’ satisfaction. However, our objective goes beyond this. First, we
aim at developing a procedure that could be well-suited for scenarios where
the deliberation phase is prolonged, being exponentially dependent in only one
of its input parameters. Additionally, observing that the most definitive
parameter of resolve-delegation is the number of delegating voters $|D|$
(upper bounded by $n$), we focus on designing an algorithm with a running time
exponentially dependent only on $|D|$, which would be suitable for practical
use in any relatively small community. Yet, this is not possible without
further assumptions, given the negative result of Theorem 3, that holds even
for a single delegating voter. As before, we resort to instances of t-LD
elections of retrospective trust and obtain the following result.

######  Theorem 5.

resolve-delegation in a time-conscious and confluent manner is solvable in
time exponential in $|D|$ and polynomial in the remaining input parameters,
for profiles of retrospective trust.

##  4 Conclusions

Succinctly speaking, the main attributes of Liquid Democracy are the (i)
voters’ ability to cast a ballot, (ii) ability to delegate voting rights,
(iii) transitivity of delegations, (iv) ability for topic-specific
delegations, (v) ability to modify or recall a delegation. Our work is the
first, upon our knowledge, in the Computational Social Choice literature, that
studies a model that satisfies every each of the above features. Motivated by
the suggestion of [3], on the addition of a temporal dimension in the
algorithmic considerations of LD models, and building upon [10], we studied a
LD framework from a viewpoint that lies in the middle ground between
algorithmic and axiomatic approaches. We intentionally gave significant
emphasis on developing a general model for incorporating temporal aspects and
we feel it opens up the way for several promising avenues for future research.
The first is to examine whether time-consciousness (or other time-related
axioms) is compatible with established axioms for LD frameworks. Also an
intriguing topic is to identify further realistic families of instances for
which all properties studied here can be simultaneously satisfied. It would
also be interesting to check whether the positive results we present still
apply for further generalizations of t-LD elections, e.g. when voters are able
to use a more powerful language to express complex preferences. The delegating
voters’ preferences over the final representatives and the casting voters’
preferences over the issue at hand, as well as an egalitarian objective or
restrictions on the maximum in-degree or on the maximum path-length in the
output of a delegation rule, deserve further examination. We finally suggest
experimental or empirical evaluations of LD frameworks that take into account
temporal considerations.

## References

  * [1] Jan Behrens, ‘The origins of liquid democracy’, The Liquid Democracy Journal, 5, (2017).
  * [2] Jan Behrens, Axel Kistner, Andreas Nitsche, and Björn Swierczek, The principles of LiquidFeedback, Interacktive Demokratie, 2014.
  * [3] Jan Behrens, Axel Kistner, Andreas Nitsche, and Björn Swierczek, ‘The temporal dimension in the analysis of liquid democracy delegation graphs’, The Liquid Democracy J., 7, (2021).
  * [4] Jan Behrens and Björn Swierczek, ‘Preferential delegation and the problem of negative voting weight’, The Liquid Democracy Journal, 3, (2015).
  * [5] Matthias Bentert, Anne-Sophie Himmel, André Nichterlein, and Rolf Niedermeier, ‘Efficient computation of optimal temporal walks under waiting-time constraints’, Applied Network Science, 5(1), 1–26, (2020).
  * [6] Christian Blum and Christina Isabel Zuber, ‘Liquid democracy: Potentials, problems, and perspectives’, Journal of Political Philosophy, 24(2), 162–182, (2016).
  * [7] Frederick Bock, ‘An algorithm to construct a minimum directed spanning tree in a directed network’, Developments in operations research, 29–44, (1971).
  * [8] Paolo Boldi, Francesco Bonchi, Carlos Castillo, and Sebastiano Vigna, ‘Viscous democracy for social networks’, Communications of the ACM, 54(6), 129–137, (2011).
  * [9] Markus Brill, ‘Interactive democracy’, Proceedings of the AAMAS, 1183–1187, (2018).
  * [10] Markus Brill, Théo Delemazure, Anne-Marie George, Martin Lackner, and Ulrike Schmidt-Kraepelin, ‘Liquid democracy with ranked delegations’, Proceedings of the AAAI, 36(5), 4884–4891, (2022).
  * [11] Ioannis Caragiannis and Evi Micha, ‘A contribution to the critique of liquid democracy’, Proceedings of the IJCAI, (2019).
  * [12] Lewis Carroll, The principles of parliamentary representation, Harrison and Sons, 1884.
  * [13] Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche, ‘Finding temporal paths under waiting time constraints’, Algorithmica, 83(9), 2754–2802, (2021).
  * [14] Yoeng-Jin Chu, ‘On the shortest arborescence of a directed graph’, Scientia Sinica, 14, 1396–1400, (1965).
  * [15] Gal Cohensius, Shie Mannor, Reshef Meir, Eli A. Meirom, and Ariel Orda, ‘Proxy voting for better outcomes’, Proceedings of the AAMAS, 858–866, (2017).
  * [16] Rachael Colley, Théo Delemazure, and Hugo Gilbert, ‘Measuring a priori voting power–taking delegations seriously’, arXiv preprint arXiv:2301.02462, (2023).
  * [17] Rachael Colley, Umberto Grandi, and Arianna Novaro, ‘Unravelling multi-agent ranked delegations’, Proceedings of the AAMAS, 36(1), 1–35, (2022).
  * [18] Palash Dey, Arnab Maiti, and Amatya Sharma, ‘On parameterized complexity of liquid democracy’, Conference on Algorithms and Discrete Applied Mathematics, 83–94, (2021).
  * [19] Stuart Dreyfus and Robert A. Wagner, ‘The steiner problem in graphs’, Networks, 1(3), 195–207, (1971).
  * [20] Jack Edmonds, ‘Optimum branchings’, Mathematics and the Decision Sciences, 1(335-345), 25, (1968).
  * [21] Bruno Escoffier, Hugo Gilbert, and Adèle Pass-Lanneau, ‘The convergence of iterative delegations in liquid democracy in a social network’, Proceedings of the SAGT, 284–297, (2019).
  * [22] Bryan Ford, ‘Delegative democracy’, Technical report, (2002).
  * [23] Bryan Ford.  Delegative democracy revisited.  https://bford.info/2014/11/16/deleg.html, 2014.  Accessed: 2023-05-09.
  * [24] Paul Gölz, Anson Kahng, Simon Mackenzie, and Ariel D Procaccia, ‘The fluid mechanics of liquid democracy’, ACM Transactions on Economics and Computation, 9(4), 1–39, (2021).
  * [25] James Green-Armytage, ‘Direct voting and proxy voting’, Constitutional Political Economy, 26(2), 190–220, (2015).
  * [26] Steve Hardt and Lia Lopes, ‘Google votes: A liquid democracy experiment on a corporate social network’, (2015).
  * [27] Silu Huang, Ada Wai-Chee Fu, and Ruifeng Liu, ‘Minimum spanning trees in temporal graphs’, Proceedings of the ACM SIGMOD, 419–430, (2015).
  * [28] Pallavi Jain, Krzysztof Sornat, and Nimrod Talmon, ‘Preserving consistency for liquid knapsack voting’, Proceedings of the EUMAS, 221–238, (2022).
  * [29] Mark Jones, Daniel Lokshtanov, M.S. Ramanujan, Saket Saurabh, and Ondřej Suchỳ, ‘Parameterized complexity of directed steiner tree on sparse graphs’, Proceedings of the ESA, 671–682, (2013).
  * [30] David Kempe, Jon Kleinberg, and Amit Kumar, ‘Connectivity and inference problems for temporal networks’, Proceedings of the STOC, 504–513, (2000).
  * [31] Vassilis Kostakos, ‘Temporal graphs’, Physica A: Statistical Mechanics and its Applications, 388(6), 1007–1023, (2009).
  * [32] Grammateia Kotsialou and Luke Riley, ‘Incentivising participation in liquid democracy with breadth-first delegation’, Proceedings of the AAMAS, 638–644, (2020).
  * [33] Evangelos Markakis and Georgios Papasotiropoulos, ‘An approval-based model for single-step liquid democracy’, Proceedings of the SAGT, 360–375, (2021).
  * [34] George Mertzios, Othon Michail, Ioannis Chatzigiannakis, and Paul Spirakis, ‘Temporal network optimization subject to connectivity constraints’, Proc. of the ICALP, 657–668, (2013).
  * [35] Othon Michail, ‘An introduction to temporal graphs: An algorithmic perspective’, Internet Mathematics, 12(4), 239–280, (2016).
  * [36] James C. Miller, ‘A program for direct and proxy voting in the legislative process’, Public choice, 7(1), 107–113, (1969).
  * [37] Alois Paulin, ‘Through liquid democracy to sustainable non-bureaucratic government’, Proceedings of the International Conf. for E-democracy and open government, 205–217, (2014).
  * [38] Alois Paulin, ‘An overview of ten years of liquid democracy research’, The Annual International Conference on Digital Government Research, 116–121, (2020).
  * [39] Manon Revel, Daniel Halpern, Adam Berinsky, and Ali Jadbabaie, ‘Liquid democracy in practice: An empirical analysis of its epistemic performance’, ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization, (2022).
  * [40] “sayke".  Liquid democracy.  https://web.archive.org/web/20040726071737/twistedmatrix.com/wiki/python/LiquidDemocracy, 2004\.  Accessed: 2023-05-09.
  * [41] “sayke".  The liquid democracy voting system.  https://web.archive.org/web/20040518131300/twistedmatrix.com/wiki/python/LiquidDemocracyVotingSystem, 2004\.
  * [42] Robert Endre Tarjan, ‘Finding optimum branchings’, Networks, 7(1), 25–35, (1977).
  * [43] Gordon Tullock, ‘Proportional representation.’, Toward a Mathematics of Politics, 144–157, (1967).
  * [44] Huanhuan Wu, James Cheng, Yiping Ke, Silu Huang, Yuzhen Huang, and Hejun Wu, ‘Efficient algorithms for temporal path computation’, IEEE Transactions on KDE, 28(11), (2016).

Technical Appendix

##  Appendix A Missing Proofs From Section 3

###  A.1 Proof of Theorem 1

The special cases for which the hardness holds, stated in the statement of the
theorem, simply follow by the construction. We make the following observations
regarding the deliberation phase of the t-LD elections represented by $G$.

  * -

The only vertex that has an out-going edge to $\triangledown$ is $u_{0}$. Such
an edge is available at the final time-instant $L$ and thus the voter that
corresponds to $u_{0}$ agrees to cast a ballot till the end of the election;
which makes her the only casting voter.

  * -

The only vertex that doesn’t have an out-going edge at time $L$ is $a$. More
precisely, $a$ has no out-going edges during $[1,L]$ and thus the
corresponding voter opts to abstain from the beginning until the end of the
election; which makes her the only abstaining voter.

  * -

The weights of the out-going edges of every vertex $v$ of
$V\setminus\\{\triangledown,u_{0}\\}$ at any time-instant $t$, indeed express
a weak ranking over the voters that are being approved by $v$ at time $t$, due
to the dummy edges.

Before continuing, we observe that vertex $a$ as well as the edges towards $a$
do not affect the rest of the reduction since such edges do not belong to any
path to $\triangledown$, and are not part of any feasible solution of $\Pi$.
Hence, it is safe to focus on the subgraph of $G$ induced by
$V\cup\\{\triangledown\\}\setminus\\{a\\},$ which, for simplicity, will be
called $G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta)$, from now on.

For the forward direction, say that $(G^{\prime},u_{0}^{\prime},k^{\prime})$
is a YES-instance of t-mst having $T^{\prime}$ as a certificate. We will prove
that $(G,k)$ is also a YES-instance of $\Pi$. We select an arbitrary path
$p^{\prime}$ of $T^{\prime}$ that has $u_{0}^{\prime}$ as its source vertex,
and we rename its vertices and edges so as
$p^{\prime}=(u_{i-1}^{\prime},(e_{i}^{\prime},t_{i}),u_{i}^{\prime})_{i\in[q]},$
for some $q\in\\{1,2,\dots,n\\}$. Since $T^{\prime}$ is a subgraph of
$G^{\prime}$, the existence in $p^{\prime}$ of the edge
$e_{i}^{\prime}=(u_{i-1}^{\prime},u_{i}^{\prime})$, for $i\in[q]$ and for
which $t_{i}\in\tau(e_{i}^{\prime})$ implies the existence of an edge
$e_{i}=(u_{i},u_{i-1})$ in $G$ that is present at time $t_{i}$. Combining
these edges we prove the existence of a path
$p=(u_{i},(e_{i},t_{i}),u_{i-1})_{i\in[q]}$, in $G$. Since $p^{\prime}$ is
time-respecting, it holds that $1\leq t_{i-1}\leq t_{i}\leq L,i\in\\{2,3,\dots
q\\},$ and hence, given that the elections represented by $G$ are of
retrospective trust, $p^{\prime}$ is a $\delta$-time-conscious path. Finally,
the path $p\cup(((u_{0},\triangledown),1),\triangledown)$ is a $\delta$-time-
conscious path from $u_{q}$ to $\triangledown$. Combining such paths for every
vertex $u_{q}\in V\setminus\\{u_{0}\\}$, we can create a subgraph $T$ of $G$
that is a $\delta$-time-conscious tree rooted at $\triangledown$ that spans
the vertices of $V\cup\\{\triangledown\\}$.

We now focus on the cost of the edges in $T$. The cost of all edges of
$T^{\prime}$ is a sum of values $w^{\prime}(e_{i}^{\prime})\in\\{1,2\\}$ and
the number of edges in $T^{\prime}$ are exactly $n-1$, where
$n=|V^{\prime}|=|V|$. Lets call $d_{T^{\prime}}$ the number of edges of weight
$2$ in $T^{\prime}$ then $n-1+d_{T^{\prime}}\leq k^{\prime}.$ Furthermore, it
holds that for every edge of weight $2$ (resp. 1) in $T^{\prime}$ there is an
edge of weight $1$ (resp. 2) in $T$ and vice versa. Given that
$w(u_{0},\triangledown)=0,$ the total weight of edges of $T$ is

$\displaystyle n-1+(n-1-d_{T^{\prime}})=2(n-1)+(n-1)-k^{\prime}\geq k.$

For the reverse direction suppose that there is a directed temporal tree $T$
that verifies a YES-solution of $\Pi$ and say that $E_{T}$ is its edge set.
Since $T$ is rooted at $\triangledown$ and the only edge incident to it is
$e=(u_{0},\triangledown),$ then $e$ is definitely part of $T$. Consider the
graph $T^{\prime}$ that corresponds to the subgraph of $G^{\prime}$ that
contains $e$ as well as an edge $(u^{\prime},v^{\prime})$ if and only if
$(v,u)$ belongs to $E_{T}\setminus\\{e\\}$. The fact that $T^{\prime}$ is a
time-respecting directed temporal tree that spans the vertices of $G^{\prime}$
and has a path from $u_{0}^{\prime}$ to every vertex of $G^{\prime}$, follows
by similar arguments to the forward direction of the proof.

We now need to prove that the total weight of the edges of $T^{\prime}$ is at
most $k^{\prime}$. It is known that the total weight of the edges of $T$ is at
least $k=3(n-1)-k^{\prime}$. Lets call $d_{T}$ the number of edges of weight
$2$ in $T$, then $(n-1)+d_{T}\geq 3(n-1)-k^{\prime}.$ Since every edge of
weight $2$ (resp. $1$) of $G^{\prime}$ corresponds to an edge of weight $1$
(resp. $2$) in $G$ and vice versa, the total weight of the edges in
$T^{\prime}$ equals

$(n-1)+(n-1-d_{T})\leq 2(n-1)+(n-1-3(n-1)+k^{\prime})=k^{\prime},$

and this concludes the NP-hardness proof. ∎

###  A.2 Proof of Theorem 2

It is immediate that the complexity of Procedure 1 is polynomial in the input
size. The fact that the output of Procedure 1 is a directed temporal tree that
spans the vertices of $(V\cup\\{\triangledown\\})\setminus A$ follows from the
fact that Edmonds’ algorithm returns a tree that spans the set of vertices of
$G^{\prime}$, which equals $(V\cup\\{\triangledown\\})\setminus A$.
Additionally, the result of the run of Edmonds’ algorithm is a graph in which
every vertex of $G^{\prime}$ is reachable from $\triangledown$. Given that
every edge of $G^{\prime}$ has a corresponding edge in $G$ of reverse
orientation, it holds that the output of Procedure 1 contains a path to
$\triangledown$ from every vertex of $V\setminus A$. Note also that Procedure
1 is a valid delegation rule since it assures that abstaining voters will not
be asked to vote or to delegate their rights, that delegating voters will not
be asked to delegate to an abstaining one and that casting voters will be
asked to cast a ballot. The proof of these claims is straightforward.

We finally need to argue about the optimality of the algorithm concerning the
maximization of electorate’s satisfaction. This follows by the fact that any
solution by Edmonds for $(G^{\prime},\triangledown)$ corresponds to a feasible
solution of resolve-delegation, with the same cost, and vice versa. ∎

###  A.3 Proof of Theorem 3

Given a graph $G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta)$ that models the
deliberation phase of a t-LD election and a parameter $k$, we call $\Pi$ the
decision variant of the problem resolve-delegation in a time-conscious manner,
which asks for the existence of a solution with total satisfaction at least
$k$. At what follows, we provide a reduction to $\Pi$, from a problem called
restless temporal path, that was shown to be NP-hard555The NP-hardness result
from [13] pertains to the undirected variant of the problem. Nevertheless, an
analogous result can be shown for the directed variant by a straightforward
transformation. in [13].

In the restless temporal path we are given, a temporal graph
$G^{\prime}(V^{\prime},E^{\prime},\tau^{\prime},L^{\prime})$, two distinct
vertices $x,y$ of $V^{\prime}$ and an integer $\Delta$. The question is to
determine whether a $\Delta$-restless path from $x$ to $y$ exists in
$G^{\prime}$, where a temporal path
$p=(v^{\prime}_{i-1},(e_{i}^{\prime},t_{i}),v^{\prime}_{i})_{i\in[\ell]}$ is
called $\Delta$-restless if for all $i\in[\ell]$, it holds that
$e_{i}^{\prime}=(v^{\prime}_{i-1},v^{\prime}_{i})$,
$t_{i}\in\tau^{\prime}(e_{i}^{\prime})$, and for all $i\in[\ell-1]$ we have
$t_{i}\leq t_{i+1}\leq t_{i}+\Delta$ (in case $t_{1}+\Delta>L$, the rightmost
inequality is trivially satisfied); an example of such a path is provided in
Appendix B. The hardness holds even for temporal graphs with a lifespan of $3$
time instants and even if $\Delta=1$.

Given an instance
$(G^{\prime}(V^{\prime},E^{\prime},\tau^{\prime},L^{\prime}),x,y,\Delta)$ of
restless temporal path we create an instance
$(G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta),k)$ of $\Pi$ as follows:

  * •

let $L=L^{\prime}+1$,

  * •

let $G$ be the reversed graph of $G^{\prime}$, i.e. $V=V^{\prime}$ and for
every edge $e^{\prime}=(v,u)$ of $E^{\prime}$ we add an edge $e=(u,v)$ in $E$
such that $\tau(e)=\tau^{\prime}(e^{\prime})$ and $w(e)=1$,

  * •

we add in the vertex set of $G$ a special vertex $\triangledown$ and in $E$ an
edge $(x,\triangledown)$ with $w((x,\triangledown))=0$ and
$\tau((x,\triangledown))=[1,L]$,

  * •

for every edge $(v,u)$ and for every time-instant $t\in[L]$ such that $v\neq
x$ and $t\in\tau((v,u))$, we set $\delta_{v}^{t}=\min\\{t-1,\Delta\\}$,

  * •

we add a dummy vertex $a$ with no out-going edges and an edge $(y,a)$ with
$w((y,a))=1$ and $\tau((y,a))=[L,L]$,

  * •

we set $k=1$.

We proceed with a few observations on the profile of t-LD elections that $G$
models. First, we have that at time $L$ all voters that correspond to vertices
other than $x,y$ want to abstain, since there are no edges in $G^{\prime}$
that are present at time $L^{\prime}+1$. On the other hand, the only edge
towards $\triangledown$ in $G$ has $x$ as its head, and therefore, $x$
corresponds to the only casting voter. Therefore, the only delegating voter in
the created instance is $y$, since it corresponds to the only vertex that has
an outgoing edge to a vertex other than $\triangledown$, at the final time-
instant. Furthermore, since all approved representatives of $y$ are tied in
the first place of her ranking, and given that the only edge towards
$\triangledown$ is from $x$, asking for a time-conscious solution with a total
utility of at least $1$ is equivalent to determining whether a time-conscious
path from $y$ to $x$ exists.

For the forward direction, say that $p$ is a directed $\Delta$-restless path
from $x$ to $y$ that verifies that $(G^{\prime},x,y)$ is a YES-instance of the
restless temporal path problem. Then, the edges of $G$ that correspond to
edges of $p$ in $G^{\prime}$ induce a path from $y$ to $x$ in $G$, since they
are of reverse orientation, and consequently a path from $y$ to
$\triangledown$. To prove that the path, called $p^{\prime}$, from $y$ to
$\triangledown$ is $\delta$-time-conscious, we focus on an arbitrary pair of
consecutive edges of $p$, namely
$((u,v),t^{\prime}),((v,z),t^{\prime\prime})$. Given that $p$ is
$\Delta$-restless in $G^{\prime}$, it holds that $t^{\prime}\leq
t^{\prime\prime}$ and that $t^{\prime\prime}\leq t^{\prime}+\Delta$. But then,
by the construction of $G$, the path $p^{\prime}$ includes the following two
edges: $((z,v),t^{\prime\prime}),((v,u),t^{\prime})$, for which
$t^{\prime\prime}\geq t^{\prime}\geq
t^{\prime\prime}-\Delta=t^{\prime\prime}-\delta^{t^{\prime\prime}}_{z}$. By
applying the same argument for each pair of consecutive edges of $p$, we
conclude that $p^{\prime}$ is indeed $\delta$-time-conscious.

For the reverse direction, say that
$(G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta),k)$ is a YES-instance of
$\Pi$, or in other words that there exists a $\delta$-time-conscious path from
$y$ to $\triangledown$. Given that the only edge towards $\triangledown$ is
from $x$ and that it is present at any time-step of the deliberation phase,
there also exists a $\delta$-time-conscious path, say $p$, from $y$ to $x$. In
analogy to the forward direction, selecting an edge $(u,v)$ of $E^{\prime}$ if
and only if the edge $(v,u)$ of $E$ belongs to $p$, establishes a
$\Delta$-restless path from $x$ to $y$ in $G^{\prime}$, verifying that
$(G^{\prime}(V^{\prime},E^{\prime},\tau^{\prime},L^{\prime}),x,y)$ is a YES-
instance of restless temporal path. ∎

###  A.4 Proof of Theorem 4

It is immediate that the complexity of Procedure 2 is polynomial in the input
size and that the procedure returns a valid delegation rule as it does not ask
abstaining voters to vote or delegate their rights, it does not ask a
delegating voter to delegate to an abstainer, and it asks every casting voter
to cast a ballot. Therefore, we only need to prove that the output is indeed a
set of feasible $\delta$-time-conscious paths from all delegating voters to
$\triangledown$, that maximizes the electorate’s utility.

We begin by proving that the journeys returned by Procedure 2 indeed maximize
the electorate’s utility, assuming that the if and else blocks in lines 8 and
11 output a feasible solution, whenever there exists one. To that end, we
first note that since it is sufficient to return a journey from a vertex $v$
to $\triangledown$ that is totally independent from the returned journey from
every other vertex to $\triangledown$, the maximization of the utility of the
electorate boils down to the problem of maximizing the utility of every
individual voter. Consider now a delegating voter $v$. Since Procedure 2
examines the out-going edges of $v$ in order of decreasing weight, and it
stops at the very first time it finds a feasible solution for $v$, this is
obviously a solution of maximum utility for $v$.

To prove feasibility of the outcome, starting from the case where the input
profiles are of retrospective trust, we claim that the replacement of the edge
time-labels ensures that a time-respecting path from $v$ to $\triangledown$ in
$G^{\prime}$ corresponds to a $\delta$-time-conscious path from $v$ to
$\triangledown$ in $G$. Say that two consecutive edges $e_{1}^{\prime}$ and
$e_{2}^{\prime}$ are being used in such a time-respecting path, at time-
instants $t_{1}^{\prime}$ and $t_{2}^{\prime}$ respectively. Then,
$t_{1}^{\prime}\leq t_{2}^{\prime}$. Equivalently, there are two consecutive
edges in $G$, say $e_{1}$ and $e_{2}$ that are present at time-instants
$t_{1}$ and $t_{2}$ respectively. Since $t_{1}^{\prime}\leq t_{2}^{\prime}$,
it also holds that $L+1-t_{1}\leq L+1-t_{2}$ and therefore, $t_{1}\geq t_{2}$.
Hence $e_{1}$ can be placed before $e_{2}$ in a $\delta$-time-conscious path
in $G$, provided that the input is of retrospective trust. By the optimality
of the outcome of the algorithm for solving foremost path, from [34], one can
deduce a feasible time-respecting path from $v$ to $\triangledown$ in
$G^{\prime}$, which in turn implies the existence of a $\delta$-time-conscious
path from $v$ to $\triangledown$ in $G$.

Coming now to the case where walks are allowed, the feasibility follows by the
algorithm suggested in [5] for determining whether a $\Delta$-restless walk
between two specified vertices exist. We need again to use similar arguments
to the ones used for the retrospective trust case, showing that the
replacement of the edge time-labels in the first lines of Procedure 2, ensures
that a $\Delta$-restless path from $v$ to $\triangledown$ in $G^{\prime}$
corresponds to a $\delta$-time-conscious path from $v$ to $\triangledown$ in
$G$. ∎

###  A.5 Proof of Theorem 5

We suggest a procedure which consists of two components: a reduction from
resolve-delegation in a time-conscious and confluent manner to the directed
minimum steiner tree (d-mst) problem and an execution of an appropriate
algorithm for the latter. We begin with defining d-mst. In that, we are given
a (static) directed edge-weighted graph
$G^{\prime}(V^{\prime},E^{\prime},w^{\prime})$, where
$w^{\prime}:E^{\prime}\rightarrow\mathbb{N}$, a source $r^{\prime}\in
V^{\prime}$, a set of vertices $\hat{V}\subseteq V^{\prime}$ called terminals,
and we are asked for a subgraph of $G^{\prime}$ that includes a directed path
from $r^{\prime}$ to any (terminal) vertex of $\hat{V}$, of minimum possible
total weight.

Given a graph $G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta)$ that models the
deliberation phase of a t-LD election of retrospective trust, we refer to
$\Pi$ as the resolve-delegation problem in a time-conscious and confluent
manner. We will present a reduction from $\Pi$ to d-mst. Consider an instance
of $\Pi$, say $G(V\cup\\{\triangledown\\},E,\tau,L,w,\delta)$. We will now
construct an instance
$(G^{\prime}(V^{\prime},E^{\prime},w^{\prime}),r^{\prime},\hat{V})$ of d-mst,
and an example of the proposed construction can be found in Figure 1.

  * •

we add a source $r^{\prime}$ in $V^{\prime}$, that corresponds to
$\triangledown$,

  * •

we add a (terminal) vertex $v^{\prime}$ in $\hat{V}$, for every vertex $v$ of
$D$, a (non-terminal) vertex $v^{\prime}$ in $V^{\prime}\setminus\hat{V}$, for
every vertex $v$ of $C$ and we call all such vertices “special”,

  * •

for every edge $e=(u,v)\in E$ such that $u\in D$ and
$v\in(V\cup\\{\triangledown\\})\setminus A$ and for every $t\in\tau(e)$, we
add a (non-terminal) vertex named $(e,t)$ in $V^{\prime}\setminus\hat{V}$,

  * •

for every pair of edges $e_{1}=(u,v),e_{2}=(v,z)$ of $E$, such that
$u,v,z\in(V\cup\\{\triangledown\\})\setminus A$ and for every
$t_{1}\in\tau(e_{1})$ and $t_{2}\in\tau(e_{2})$ with $t_{1}\geq t_{2}$, we add
in $E^{\prime}$ a directed edge from $(e_{2},t_{2})$ to $(e_{1},t_{1})$
(provided that these vertices exist) of weight $max(u)-w(e_{1})+min(u)$, where
$max(u)$ (resp. $min(u)$) is the maximum (resp. minimum) weight of out-going
edges of $u$, available at any time-instant,

  * •

for every edge $e=(v,\triangledown)\in E$ and for every $t\in\tau(e)$, we add
in $E^{\prime}$ a directed edge from $r^{\prime}$ to $(e,t)$ of zero weight,

  * •

for every edge $e=(u,v)\in E$ such that $u\in D$ and
$v\in(V\cup\\{\triangledown\\})\setminus A$ and for every $t\in\tau(e)$, we
add in $E^{\prime}$ a directed edge from $(e,t)$ to $u^{\prime}$ of zero
weight.

Figure 1: The weighted directed temporal graph of an instance of problem $\Pi$
(left) that corresponds to a t-LD election with 1 abstaining voter $(E)$, 2
casting voters $(A,D)$ and 2 delegating voters $(B,C)$ and the weighted
directed static graph of the corresponding instance of d-mst (right), where
circled vertices indicate terminals. Dashed, curly and straight edges are of
weights $0,1$ and $2$, respectively.

At what follows we will prove that every feasible solution for an instance of
$\Pi$, given by a graph $G$ of total utility at least $k$, implies the
existence of a feasible solution for d-mst in
$(G^{\prime},r^{\prime},\hat{V})$ of cost at most $k^{\prime}$, and vice
versa, where $k^{\prime}=\sum_{u\in D}(max(u)+min(u))-k$. We start with the
forward direction. We need to show that given a $\delta$-time-conscious
temporal tree of $G$, called $T$, which spans the vertices of $V\setminus A$,
is rooted at $\triangledown$ and its total weight is at least $k$, one can
deduce a feasible solution $T^{\prime}$ of weight at most $k^{\prime}$ in the
created instance of d-mst. Obviously $T$ induces a path from every vertex
$v\in V\setminus A$ to $\triangledown$, which is of unit length if $v\in C$,
and of length greater than $1$, otherwise. For such a path of unit length,
there is also a directed path from $r^{\prime}$ to $v^{\prime}$ in
$G^{\prime}$, that is of zero cost, which is formed by the edges
$(r^{\prime},((v^{\prime},\triangledown),$L$))$ and
$(((v^{\prime},\triangledown),$L$),v^{\prime})$. Hence, the non-terminal
vertex that corresponds to a casting voter, can be reached from $r^{\prime}$
with no cost, using exactly 2 edges. Let all such pairs of edges belong to
$T^{\prime}$.

We move on to temporal paths of length greater than 1 in $T$. We select an
arbitrary path $p$ of $T$ having $\triangledown$ as its sink vertex and a
vertex $u_{0}$, that corresponds to a delegating voter, as its source, and we
rename its vertices and edges so as $u_{q}=\triangledown$ and
$p=(u_{i-1},(e_{i},t_{i}),u_{i})_{i\in[q]},$ for some $q\in[n]$. Since $p$ is
a $\delta$-time-conscious path, for $i\in[q]$, it holds that
$e_{i}=(u_{i-1},u_{i})$, $t_{i}\in\tau(e_{i})$ and, furthermore, for
$i\in[q-1]$ it holds that $t_{i}\geq t_{i+1}$. By the construction, there also
exists a path $p^{\prime}$ in $G^{\prime}$ that can be expressed by the
sequence of vertices
$\\{r^{\prime},((u^{\prime}_{q-1},u^{\prime}_{q}),t_{q}),((u^{\prime}_{q-2},u^{\prime}_{q-1}),t_{q-1}),\ldots,((u^{\prime}_{1},u^{\prime}_{2}),t_{2}),((u^{\prime}_{0},u^{\prime}_{1}),t_{1}),u^{\prime}_{0}\\}$.
All in all we have constructed a directed path from $r^{\prime}$ to
$u^{\prime}_{0}$, and $u^{\prime}_{0}$ is a terminal vertex since $u_{0}$
corresponds to a delegating voter. By repeating the same procedure for every
path $p$ of $T$ that has $\triangledown$ as its source, we can form a subgraph
of $G^{\prime}$, say $T^{\prime}$, that consists of paths from $r^{\prime}$ to
every terminal vertex of $\hat{V}$.

It remains to be proven that $T^{\prime}$ is a tree of cost no more than
$k^{\prime}$. Firstly, suppose that the undirected variant of $T^{\prime}$
contains a cycle. By a similar reasoning to the above, we can prove that the
undirected variant of $T$ would also contain a cycle, which is a
contradiction. We will now prove that if the total weight of the edges in $T$
is at least $k$ then the weight of the edges in $T^{\prime}$ is at most
$k^{\prime}$. Observe that for every vertex $v\in V\setminus A$, there is only
one other vertex $u\in(V\cup\\{\triangledown\\})\setminus A$, such that
$(v,u)$ in $T$ (and similarly for $T^{\prime}$) and say that, for convenience,
the weight of an edge $(v,u)$ that belongs to $T$ is denoted by $w(v)=w(v,u)$.
Then, the total weight of the edges in $T$ is $\sum_{v\in D}w(v)\geq k.$ Let
us now focus on a pair of paths of $T$ and $T^{\prime}$, namely $p$ and
$p^{\prime}$ respectively. Say that
$p=(u_{i-1},(e_{i},t_{i}),u_{i})_{i\in[q]}$ and that $p^{\prime}$ is being
formed by following the sequence of vertices
$\\{((u^{\prime}_{q-1},u^{\prime}_{q}),t_{q}),((u^{\prime}_{q-2},u^{\prime}_{q-1}),t_{q-1}),\dots,((u^{\prime}_{1},u^{\prime}_{2}),t_{2}),((u^{\prime}_{0},u^{\prime}_{1}),t_{1})\\}$
in $G^{\prime}$. The weight of all edges in $p$ equals
$w(e_{1})+w(e_{2})+\dots+w(e_{q-1})+w(e_{q})=w(u_{0})+w(u_{1})+\dots+w(u_{q-2})+w(u_{q-1})$.
On the other hand, the weight of all edges in $p^{\prime}$ equals
$max(u_{q-1})-w(u_{q-1})+min(u_{q-1})+max(u_{q-2})-w(u_{q-2})+min(u_{q-2})+\dots+max(u_{0})-w(u_{0})+min(u_{0})$.
Hence, for every such pair of paths, if $w_{p}$ is the total weight of the
path $p$ (similarly for $p^{\prime}$) and if $N_{p}$ is the set of non-sink
vertices of path $p$, i.e. $N_{p}=\\{u_{0},u_{1},\dots,u_{q-1}\\}$, then

$w_{p^{\prime}}=\sum_{u\in N_{p}}(max(u)+min(u))-w_{p}.$

Before continuing, we note that any rooted directed (towards the root) tree
with $\ell$ leaves can be divided into paths $P_{1},P_{2},\dots,P_{\ell}$,
such that every path has a leaf as its source and every vertex (other than the
root) belongs to exactly one path as a non-sink vertex. These paths can be
created with the following procedure: Initially say that only the root of the
tree belongs to a set $X$. Select as $P_{1}$ any path from a leaf to the root
and say that from now on, $X$ also contains the vertices of $P_{1}$. For
$i=2,$ select the path that does not use any vertex of $X$ as a non-sink
vertex, starting from an unexplored leaf and ending at a vertex of $X$ and
call it $P_{i}$; add the vertices of $P_{i}$ to $X$ and repeat for
$i=3,\dots,\ell$.

Therefore, $T$ can be represented as a collection of, say $\ell(T)$, such
paths in a way that each of its vertices (other than the root) appears in that
collection as a non-sink vertex exactly once. If we call $w_{P_{i}}$ the total
weight of edges in $P_{i}$, then the cost of $T$ can be expressed as
$\sum_{i\in[\ell(T)]}w_{P_{i}}$, and thus, the cost of $T^{\prime}$ can be
expressed as

$\displaystyle\sum_{i\in[\ell(T)]}$ $\displaystyle\big{(}\sum_{u\in
N_{P_{i}}}(max(u)+min(u))-w_{P_{i}}\big{)}\leq$ $\displaystyle\sum_{u\in D}$
$\displaystyle(max(u)+min(u))-k=k^{\prime}$

For the reverse direction, we firstly note that it is without loss of
generality to assume that any optimal d-mst of $G^{\prime}$ contains a path
from $\triangledown$ to any special (terminal or non-terminal) vertex, since
every special non-terminal vertex $v^{\prime}$ can be reached from
$r^{\prime}$ at no cost by following the edges
$(r^{\prime},((v^{\prime},\triangledown),L))$ and
$(((v^{\prime},\triangledown),L),v^{\prime})$, which definitely exist. The
rest of the proof follows from the same arguments presented in the forward
direction.

Given an instance
$(G^{\prime}(V^{\prime},E^{\prime},w^{\prime}),r^{\prime},\hat{V},k^{\prime})$,
the d-mst can be solved in time $O^{*}(3^{|\hat{V}|})$ by a modification of
the classical algorithm for the (undirected) minimum steiner tree problem
[19], where the $O^{*}$ notation denotes the suppression of factors polynomial
in the input size. Further improvements on the running time have also been
suggested, as outlined in greater detail in [29]. By our construction it holds
that $|\hat{V}|=|D|$. Hence, resolve-delegation in a time-conscious and
confluent manner is solvable in time exponential only in the number of
delegating voters of the instance, for t-LD elections of retrospective trust.
∎

##  Appendix B Illustrative Examples

This section aims to clarify some of the technical terms and concepts used in
our work, through simple illustrative examples. The graphs in Figure 2 will be
used as references throughout this section. For ease of presentation, we have
labeled each edge of the graphs in Figure 2 with the corresponding time
instant in which the edge is available, since in these particular examples, we
have assumed that each edge is available for only one time instant.
Specifically, we use the label $t$ to denote the time interval $[t,t]$.

  * •

Rooted directed trees. In $G_{1}$, we observe a static variant of a temporal
directed tree that cannot be said to be rooted at any of its vertices.
However, by replacing the edge $(v_{1},y_{1})$, with its opposite direction, a
directed tree rooted at $u_{1}$ is being produced.

  * •

Time-conscious paths. Consider $G_{2}$ to be a temporal graph with a lifespan
of $5$, and say that $d_{v}^{t}=2$ for every vertex $v$ and for every time-
instant $t\in{1,2,\dots,5}$. In this case, the only $\delta$-time-conscious
path from $y_{2}$ to $u_{2}$ is $(y_{2},x_{2},w_{2},u_{2})$. On the other
hand, if $d_{y_{2}}^{t}=4$ for every time-instant $t\in{1,2,\dots,5}$, then
all paths from $y_{2}$ to $u_{2}$ except $(y_{2},w_{2},u_{2})$ are
$\delta$-time-conscious.

  * •

Confluent vs non-confluent rules. Suppose $G_{3}$ represents the unweighted
variant of the static graph that arises from a temporal graph that models a
t-LD election in which $x_{3}$ and $y_{3}$ are casting voters, $w_{3}$ is an
abstaining voter, and $x_{3}$ is the most preferred representative of $v_{3}$.
Any confluent voting rule should output either $(v_{3},x_{3})$ or
$(v_{3},y_{3})$, but not both, and should not output $(w_{3},y_{3})$. However,
if the path that is formed by the edges $(u_{3},v_{3})$ and $(v_{3},x_{3})$ is
an infeasible option (perhaps due to the time-horizon parameters of the
voters), a non-confluent voting rule might propose $x_{3}$ as the
representative for $v_{3}$ and $y_{3}$ as the representative for $u_{3}$, via
any of the available paths.

  * •

Restless paths. The notion of $\Delta$-restless paths has been used in the
proof of Theorem 3. In $G_{4}$, there are two possible paths from $u_{4}$ to
$x_{4}$, but only the path that goes through $w_{4}$ is 2-restless.

  * •

Time-respecting paths. This concept has been crucially utilized in the proof
of Theorem 1, as well as in Procedure 2. In $G_{5}$, there are three paths of
length 2, but only the one that uses the edges $(u_{5},v_{5})$ and
$(v_{5},x_{5})$ is time-respecting.

  * •

Restless walks vs paths. The importance of allowing walks instead of paths in
the search for restless journeys becomes evident when examining the graph
$G_{6}$. Specifically, the absence of an $1$-restless path from $u_{6}$ to
$w_{6}$ contrasts with the existence of an $1$-restless walk, by utilizing the
cycle between $v_{6},x_{6},y_{6}$, highlighting the potential for creating
more feasible options with the latter approach.

Figure 2: Graphs that serve to demonstrate key concepts and terminology used
in our work. In the order presented, they correspond to the following
concepts: rooted directed trees ($G_{1}$), time-conscious paths ($G_{2}$),
confluent delegation rules ($G_{3}$), restless paths ($G_{4}$), time-
respecting paths ($G_{5}$), and restless walks ($G_{6}$). An edge labeled $t$
is available only during the time-interval $[t,t]$.