{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T15:32:37Z","timestamp":1774107157517,"version":"3.50.1"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p>We investigate opinion dynamics in a fully-connected system, consisting of n agents, where one of the opinions, called correct, represents a piece of information to disseminate.\n\nOne source agent initially holds the correct opinion and remains with this opinion throughout the execution. The goal of the remaining agents is to quickly agree on this correct opinion. At each round, one agent chosen uniformly at random is activated: unless it is the source, the agent pulls the opinions of l random agents and then updates its opinion according to some rule.\n\nWe consider a restricted setting, in which agents have no memory and they only revise their opinions on the basis of those of the agents they currently sample.\n\nThis setting encompasses very popular opinion dynamics, such as the voter model and best-of-k majority rules.\n\n\n\nQualitatively speaking, we show that lack of memory prevents efficient  convergence. Specifically, we prove that any dynamics requires Omega(n^2) expected time, even under a strong version of the model in which activated agents have complete access to the current configuration of the entire system, i.e., the case l=n. Conversely, we prove that the simple voter model (in which l=1) correctly solves the problem, while almost matching the aforementioned lower bound.\n\n\n\nThese results suggest that, in contrast to symmetric consensus problems (that do not involve a notion of correct opinion), fast convergence on the correct opinion using stochastic opinion dynamics may require the use of memory.<\/jats:p>","DOI":"10.24963\/ijcai.2023\/4","type":"proceedings-article","created":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:31:30Z","timestamp":1691742690000},"page":"29-37","source":"Crossref","is-referenced-by-count":4,"title":["On the Role of Memory in Robust Opinion Dynamics"],"prefix":"10.24963","author":[{"given":"Luca","family":"Becchetti","sequence":"first","affiliation":[{"name":"Sapienza University of Rome"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Clementi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \"Tor Vergata\""}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amos","family":"Korman","sequence":"additional","affiliation":[{"name":"CNRS"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Pasquale","sequence":"additional","affiliation":[{"name":"University of Rome Tor Vergata"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Trevisan","sequence":"additional","affiliation":[{"name":"Bocconi University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robin","family":"Vacus","sequence":"additional","affiliation":[{"name":"IRIF, CNRS"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"name":"Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}","theme":"Artificial Intelligence","location":"Macau, SAR China","acronym":"IJCAI-2023","number":"32","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2023,8,19]]},"end":{"date-parts":[[2023,8,25]]}},"container-title":["Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:31:45Z","timestamp":1691742705000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2023\/4"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2023\/4","relation":{},"subject":[],"published":{"date-parts":[[2023,8]]}}}