Discrete Incremental Voting on Expanders
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916400988160000 |
|---|---|
| author | Cooper, Colin Radzik, Tomasz Shiraga, Takeharu |
| author_facet | Cooper, Colin Radzik, Tomasz Shiraga, Takeharu |
| contents | Pull voting is a random process in which vertices of a connected graph have initial opinions chosen from a set of $k$ distinct opinions, and at each step a random vertex alters its opinion to that of a randomly chosen neighbour. If the system reaches a state where each vertex holds the same opinion, then this opinion will persist forthwith.
In general the opinions are regarded as incommensurate, whereas in this paper we consider a type of pull voting suitable for integer opinions such as $\{1,2,\ldots,k\}$ which can be compared on a linear scale; for example, 1 ('disagree strongly'), 2 ('disagree'), $\ldots,$ 5 ('agree strongly'). On observing the opinion of a random neighbour, a vertex updates its opinion by a discrete change towards the value of the neighbour's opinion, if different.
Discrete incremental voting is a pull voting process which mimics this behaviour. At each step a random vertex alters its opinion towards that of a randomly chosen neighbour; increasing its opinion by $+1$ if the opinion of the chosen neighbour is larger, or decreasing its opinion by $-1$, if the opinion of the neighbour is smaller. If initially there are only two adjacent integer opinions, for example $\{0,1\}$, incremental voting coincides with pull voting, but if initially there are more than two opinions this is not the case.
For an $n$-vertex graph $G=(V,E)$, let $λ$ be the absolute second eigenvalue of the transition matrix $P$ of a simple random walk on $G$. Let the initial opinions of the vertices be chosen from $\{1,2,\ldots,k\}$. Let $c=\sum_{v \in V} π_v X_v$, where $X_v$ is the initial opinion of vertex $v$, and $π_v$ is the stationary distribution of the vertex. Then provided $λk=o(1)$ and $k=o(n/\log n)$, with high probability the final opinion is the initial weighted average $c$ suitably rounded to $\lfloor c \rfloor$ or $\lceil c\rceil$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_12615 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Discrete Incremental Voting on Expanders Cooper, Colin Radzik, Tomasz Shiraga, Takeharu Discrete Mathematics Pull voting is a random process in which vertices of a connected graph have initial opinions chosen from a set of $k$ distinct opinions, and at each step a random vertex alters its opinion to that of a randomly chosen neighbour. If the system reaches a state where each vertex holds the same opinion, then this opinion will persist forthwith. In general the opinions are regarded as incommensurate, whereas in this paper we consider a type of pull voting suitable for integer opinions such as $\{1,2,\ldots,k\}$ which can be compared on a linear scale; for example, 1 ('disagree strongly'), 2 ('disagree'), $\ldots,$ 5 ('agree strongly'). On observing the opinion of a random neighbour, a vertex updates its opinion by a discrete change towards the value of the neighbour's opinion, if different. Discrete incremental voting is a pull voting process which mimics this behaviour. At each step a random vertex alters its opinion towards that of a randomly chosen neighbour; increasing its opinion by $+1$ if the opinion of the chosen neighbour is larger, or decreasing its opinion by $-1$, if the opinion of the neighbour is smaller. If initially there are only two adjacent integer opinions, for example $\{0,1\}$, incremental voting coincides with pull voting, but if initially there are more than two opinions this is not the case. For an $n$-vertex graph $G=(V,E)$, let $λ$ be the absolute second eigenvalue of the transition matrix $P$ of a simple random walk on $G$. Let the initial opinions of the vertices be chosen from $\{1,2,\ldots,k\}$. Let $c=\sum_{v \in V} π_v X_v$, where $X_v$ is the initial opinion of vertex $v$, and $π_v$ is the stationary distribution of the vertex. Then provided $λk=o(1)$ and $k=o(n/\log n)$, with high probability the final opinion is the initial weighted average $c$ suitably rounded to $\lfloor c \rfloor$ or $\lceil c\rceil$. |
| title | Discrete Incremental Voting on Expanders |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2409.12615 |