Date(s) : 05/03/2024 iCal
11 h 00 min - 12 h 00 min
In majority voting dynamics, a group of n agents in a social network are asked for their preferred candidate in a future election between two possible choices. At each time step, a new poll is taken, and each agent adjusts their vote according to the majority opinion of their network neighbors. After T time steps, the candidate with the majority of votes is the leading contender in the election.
In general, it is very hard to predict who will be the leading candidate after a large number of time-steps.
In this work, we study the cost of local certification for predicting the leading candidate after a certain number of time-steps, which we call electionpred. We show that in graphs with sub-exponential growth electionpred admits a proof labeling scheme of size O(log n). We also find non-trivial upper bounds for graphs with a bounded degree, in which the size of the certificates are sub-linear in n.
Furthermore, we explore lower bounds for the unrestricted case, showing that locally checkable proofs for Election-Prediction on arbitrary n-node graphs have certificates on Ω(n) bits.
Finally, we show that our upper bounds are tight even for graphs of polynomial growth.
Emplacement
Site Sud, Luminy, TPR2, Amphithéâtre Herbrand 130-134 (1er étage)
Catégories