Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Convergence of Iterative Delegations in Liquid Democracy in a Social
  Network   Liquid democracy is a collective decision making paradigm which lies between
direct and representative democracy. One of its main features is that voters
can delegate their votes in a transitive manner such that: A delegates to B and
B delegates to C leads to A indirectly delegates to C. These delegations can be
effectively empowered by implementing liquid democracy in a social network, so
that voters can delegate their votes to any of their neighbors in the network.
However, it is uncertain that such a delegation process will lead to a stable
state where all voters are satisfied with the people representing them. We
study the stability (w.r.t. voters preferences) of the delegation process in
liquid democracy and model it as a game in which the players are the voters and
the strategies are their possible delegations. We answer several questions on
the equilibria of this process in any social network or in social networks that
correspond to restricted types of graphs.
  We show that a Nash-equilibrium may not exist, and that it is even
NP-complete to decide whether one exists or not. This holds even if the social
network is a complete graph or a bounded degree graph. We further show that
this existence problem is W[1]-hard w.r.t. the treewidth of the social network.
Besides these hardness results, we demonstrate that an equilibrium always
exists whatever the preferences of the voters iff the social network is a tree.
We design a dynamic programming procedure to determine some desirable
equilibria (e.g., minimizing the dissatisfaction of the voters) in polynomial
time for tree social networks. Lastly, we study the convergence of delegation
dynamics. Unfortunately, when an equilibrium exists, we show that a best
response dynamics may not converge, even if the social network is a path or a
complete graph.

2
The categories of this paper are: math
15
The categories of this paper are: nucl-ex
9
The categories of this paper are: nlin
3
The categories of this paper are: physics
32
The categories of this paper are: atom-ph
14
The categories of this paper are: math-ph
18
The categories of this paper are: econ
7
The categories of this paper are: hep-th
30
The categories of this paper are: q-alg
26
The categories of this paper are: bayes-an
17
The categories of this paper are: q-fin
34
The categories of this paper are: chem-ph
27
The categories of this paper are: comp-gas
35
The categories of this paper are: mtrl-th
37
The categories of this paper are: supr-con
21
The categories of this paper are: adap-org