Introduction

DELIMITATION OF THE SAMPLE

The sample was decided a priori based on the amount of data in literary history and economic history. 19 areas were included:

-2000 BCE -500 BCE: Egypt (from Ancient Egyptian) and Mesopotamia (from Sumerian and Akkadian).

-500 BCE -500 CE: Eastern Mediterranean (from Ancient Greek), Western Mediterranean (from Latin), India (from Sanskrit and Tamil), Central Asia (from Persian), China (from Chinese) -500 CE -1800 CE: England (from English), France (from French), Germany (from German), Italy (from Italian), Spain (from Castilian), Low Countries (from Dutch), Ireland (from Irish), Wales (from Welsh), Iceland and Norway (from Old Norse), Russian (from East Slavic), Japan (from Japanese), Arabic world (from Arabic), India (from Sanskrit, Tamil and Urdu), Central Asia (from Persian), China (from Chinese)

In order to have comprehensive series, we then completed the series with additional literary traditions when needed (Persian in Early Modern India, Latin in Early Medieval France, etc.). This method is common practice in cultural history. For instance, the authors of the Handbook of Spanish Literature write: 'As "Spain" did not exist as a political entity in the Middle Ages, we will have to understand the term "medieval Spanish literature" to be merely a useful shorthand for something like "the literature written in the medieval period in that geographical area corresponding, roughly, to the borders of the present-day Spanish state.' (Gies, 2004). Such a definition means that a survey of Spanish literature will include 'a number of languages and literary traditions we identify today with names like Latin, Occitan, Catalan, Galician-Portuguese, and Aragonese, in addition to the Arabic, Hebrew, and Castilian.' (Gies, 2004).

TEMPORAL AND SPATIAL LEVEL OF ANALYSIS

The temporal and spatial level of analysis were decided based on the availability of economic data. Before the 19 th c., it is impossible to go below the national level for most countries. The only exception is the Roman Empire where some estimates allow for distinguishing between the Western part and the Eastern part of the Empire, which corresponds to our Latin and Greek areas.

To limit bias in data analysis, we use standard historical periods whenever possible, deferring to Wikipedia to label each period. In particular, we use the same temporal division for all European countries: Early Medieval period (500 -1000), Central Medieval period (1000 -1300), Late Medieval period (1300 -1500) and Early Modern period (1500 -1800). These temporal division do not always match the evolution of economic development. However, they allow for limiting the degrees of freedom in the analysis. In the end, the combination of the 19 geographical areas and their standard historical periods leads to 77 cases of observation.

PRESENTATION OF THE SURVEY

The survey is organized by geographic areas (e.g. Greece, England, etc.), and within one geographical area by historical periods, with the earlier periods first.

Comparison within the same area (e.g. Archaic Greece and Hellenistic Greece) are thus naturally presented in the relevant section (e.g. Greece). The survey thus starts with the most ancient traditions (e.g. Ancient Egypt, Mesopotamia) and ends with the most recent (e.g. (Iceland and Norway, Russia).

In each case, the survey proceeds as follow: Takashima, 2019;Baten, & Van Zanden, 2008;Butel, 2012;Keene, 1999;Morris, 2013;Morton, 1997;Pan, 2015;Suzuki, 2010;Yokota-Murakami, & Yokota, 1998 Increase

Ancient Egypt (2000 BCE -300 BCE)

To the best of our knowledge, there is no systematic study of the diachronic evolution of romantic love in Ancient Egypt outside of literary history.

Mesopotamia (2000 BCE -550 BCE)

To the best of our knowledge, there is no systematic study of the diachronic evolution of romantic love in Mesopotamia outside of literary history.

Greek world (800 BCE -1800 CE)

To the best of our knowledge, there is no systematic study of the diachronic evolution of romantic love in Ancient Greece outside of literary history. Studies of romantic love do not differentiate one period from the other. There are works on the evolution of marriage or sex in Ancient Greece (Cantarella, 2002;Harper, 2013;P. Veyne, 1992). However, they do not specifically discuss romantic feeling.

Cantarella, E. (2002). Bisexuality in the ancient world. Yale University Press. Harper, K. ( 2013). From shame to sin. Harvard University Press. Veyne, P. (1992). A history of private life : From pagan Rome to Byzantium. Belknap.

Indian world (800 BC -1800 CE)

To the best of our knowledge, there is no systematic study of the diachronic evolution of romantic love in India outside of literary history.

Persian world (500 BCE -1800 CE)

To the best of our knowledge, there is no systematic study of the diachronic evolution of romantic love in the Persian World outside of literary history.

6. Latin world (300 BCE -500 CE)

FROM THE LATE REPUBLIC TO THE EARLY EMPIRE

A range of cues indeed suggests that love became a more important value between the late Republic and the early empire: tomb inscriptions celebrating conjugal happiness, letters from exile lamenting the absence of the loved spouse (from Cicero, Ovid, Pliny), debates in the senate revealing the emotional bounds between spouses in aristocratic circles, philosophical treatises emphasizing the role of love in marriage (Plutarch's Conjugal Precepts, Musonius Rufus), biographies of exemplary women, etc. The evolution is visible notably in collection of anecdotes (such as Valerius Maximus's collection of stories of outstanding conjugal affection) or in collection of biographies (such as Plutarch's Parallel lives): in both cases, manifestations of love are rare before the 1st c. BCE and are of a different character, stressing duty rather than sentiment (Dixon, 1992). In the same way, idealized scenes of marriage became increasingly common on the senatorial sarcophagi in the imperial era. Whereas the more ancient sarcophagi focused almost exclusively on the military accomplishments of senators, later sarcophagi display more domestic and private scenes, emphasizing family and children (Ewald, 2003;Norena, 2007). The evolution is also visible in moral philosophy. 'Where Aristotle saw relations between husband and wife as hierarchical and less intense than those between parents and children (Nichomachean Ethics, 8.12) (…), Musonius Rufus's chapters on marriage (fragments 13a-14) stress the complementary qualities and responsibilities of husband and wife and the special quality of married love' (Dixon, 1992). Finally, the study of thousands of inscription suggests a change in values: epithets depicting a loving/beloved wife (amantissima, dulcissima) and a faithful and chaste wife (fidelissima, castissima, pudicissima) are appear rather late in the Roman material and statistically more frequent in the 3rd c. than in the 1st. c. (Jeppesen-Wigelsworth, 2010). To sum up, the cultural evolution of love in fictions seems to parallel the cultural evolution of love in others cultural domains.

FROM PRE-TANG DYNASTIES AND TANG DYNASTY

Although love stories have been central in the study of the cultural evolution of romantic love in China, a few works have considered additional materials such as biographies, anecdotes, epitaphs, poetry or judiciary texts. These works demonstrate a clear increase in the cultural importance of romantic love from the Tang dynasty onward that parallels the evolution depicted in the above sections on literary narratives.

The Tang dynasty first saw the emergence of a new 'culture of romance' to use Stephen Owen's famous label (Owen, 1995(Owen, , 1996)). In this new culture, officials were not celebrated only as filial sons or righteous civil servants, as in earlier times, but also as devoted lovers.

'Prior to the ninth century, the identity of men and women were generally defined by family lineage, social status or moral character. Those deemed praiseworthy were then esteemed as members of the elite, or as upright officials, filial sons or virtuous wives, and kind mothers. During the ninth century, however, men and women began to be judged by the quality of their romantic sentiments.' (Yue, 2012)

Literati started to write about their romantic associations with courtesans in their youth, gifted poets wrote of themselves as participants in romantic affairs, and funerary inscriptions, despite their very conservative character, start evoking romantic feelings toward the deceased as well as the quality of the his or her emotional life. In the same way, the celebration of the love between the Emperor Xuanzong of Tang (685 -762) and his concubine Yang Guifei in the "Ballad of Eternal Sorrow" (Changhen ge) and its companion work, "An Account of the 'Ballad of Eternal Sorrow'" (Changhen ge zhuan) hen Hong demonstrates the increasing value of love defining people, including political leaders (Luo, 2015). There is thus an agreement between literary history and cultural history.

FROM THE TANG DYNASTY AND THE SONG DYNASTY

The cultural importance of romantic love also increased between the Tang and the Song, although scholarship is more limited. This increase is notably visible through women's private poetry (Bossler, 2011), literary biographies of courtesans (Bossler, 2011), as well as through funerary texts concerning women who start celebrating not only their fidelity, but also their emotional commitment to their lover (through voluntary seclusion, illness, even suicide) (Bossler, 2011(Bossler, , 2013)).

FROM THE SONG DYNASTY AND THE MING DYNASTY

Under the Ming dynasty, love became a central value, in particular in marriage. For instance, Katherine Carlitz notes the striking emphasis by male epitaph writers in late Ming times on conjugal affection between husbands and wives (Carlitz, 2011). The ethical discourse on love started also to evolve. While the traditional Confucian ethics granted more value to the link between father and son, and between parents of the same clan, Ming intellectuals granted an increasing importance to the attachment between spouses. The renowned iconoclast Li Zhi (1527-1602), for example, write that 'Husband and wife comprise the beginnings of human life. Only after there has been a husband-wife relation can there be a father-son relation (…) Should the relationship between husband and wife be proper, then all the relations among the myriad of living things and nonliving matter will also be proper.' (cited in Lee, 2006) Also, the old orthodox Confucianism proscribed overt manifestations of conjugal attachment and commended suicidal women (in defense of their chastity) in terms evocative of heroism (lie) rather than sentimentalism (qing). Ming intellectuals challenged the Confucian ideology and granted priority of sentiment over heroism, obedience and duty (see Lee, 2006 for a review). This movement culminated in Feng Menlong's famous collection of stories untitled The Anatomy of Love (Lee, 2006;Pan, 2015a, Wang, 1994). Carlitz, K. (2011). Lovers, Talkers, Monsters, and Good Women : Competing Images in Mid-Ming Epitaphs and Fiction. Beyond Exemplar Tales: Women's Biography in Chinese History, 175-92. Lee, H. (2006). Revolution of the heart : A genealogy of love in China, 1900-1950. Stanford University Press. Pan, L. (2015). When True Love Came to China. Hong Kong University Press. Wang, R. G. (1994). The cult of Qing: Romanticism in the late Ming period and in the novel Jiao Hong ji. Ming Studies, 1994(1), 12-55.

FROM THE MING DYNASTY AND THE QING DYNASTY

The rise of romantic love continued during the Qing dynasty (Lee, 2006;Pan, 2015a;Paul, 1993). This is notably visible in women's writing of love poetry which served as a major means of communication in expressing affection and offering mutual emotional support between husband and wives, and probably 'helped spur the development of conjugal love and companionate marriages within the gentry class' (Paul, 1993). There is thus an agreement between literary history and cultural history. Lee, H. (2006). Revolution of the heart : A genealogy of love in China, 1900-1950. Stanford University Press. Pan, L. (2015). When True Love Came to China. Hong Kong University Press.

EARLY MODERN CHINA COMPARED TO EARLY MODERN EUROPE

Several works have compared the relative importance of love in China and Europe at the time when China came into contact with the European literature in the end of the 19 th . They show that when Chinese and Europeans started to read each other's literature, they were strike by how limited the importance of love was in the Chinese culture (Lee, 2006;Pan, 2015a). A good example of this cultural dynamic is the case of the French novel La dame aux camélias which was one of the first European novels translated into Chinese. First published in 1848, the novel deals with the conflict between true love and social respectability. Armand Duval, the male character, wages a double-front battle against his bourgeois father who wants a respectable marriage and against his aristocratic milieux who regards women first and foresmost as sexual conquest. The story celebrates constancy, disinterestedness, reciprocity, spiritual communion, and selfless sacri¤ce on the othes against money, social rites, standards of distinction, intrigues, hierarchies, and calculation.

La dame aux camélias instantly claimed a devoted and broad readership base, captivating readers with its portray of modern love and inspiring local versions. For instance, Xu Zhenya , the author of the bestseller of the period, Jade Pear Spirit (1912), styled himself as the 'Dumas of the Orient,' recognizing his debt to the French novel. As historian Lynn Pan notes: 'no character in any Chinese novel would have avowed love so much.' Here are some examples: 'I love you as I never believed I could love anybody,' (Margerite) 'We love each other! What does the rest matter?' (Armand) '...no man has ever loved you as I do.' (Armand) 'Let's be clear about this: are you really in love with me?' (Armand) 'This love of ours, my dearest Armand, is no ordinary love. You love me as though I'd never belonged to anyone else . . .' (Marguerite) Although 18 th c. works such as Dream of the Red Chamber share some similar features as La Dame aux Camélias (the confessional mode, the forging of new gender relations, and the heroism of renunciation), many Chinese readers recognized that Dumas makes the love between Armand Duval and Marguerite Gautier noble and self-sacrificing, 'raising it to a loftier plane than any Chinese would have done before their exposure to Western fiction' (Pan, 2015a, p. 94). Even today, as the Chinese writer Eileen Chang write: 'we Chinese don't much love, and even our love stories don't often tell of love' (Pan, 2015a, p. 7) These remarks on the difference between European and Chinese literary traditions match observations by cultural historians of love. For instance, Arthur Waley, the great orientalist and Bloomsbury figure, opposed the importance of love in Europe to the importance of friendship in China: 'It has been the habit of Europe to idealize love at the expense of friendship and so to place too heavy a burden on the relation of man and woman. The Chinese erred in the opposite direction, regarding their wives and concubines simply as instruments of procreation. For sympathy and intellectual companionship they looked only to their friends.' (Pan, 2015a, p. 7) Another example is the invention of new words to describe the emotions found in European novels. For Zhang Xichen (1889Xichen ( -1969)), the Chinese language had no word to the English 'love' which is the reasons so many readers did not understand that the English 'love' did not mean 'lust'. A considerable amount of magazine articles were devoted to explain the signification of 'love' and to coin new Chinese words aiqing and qingai (Pan, 2015a).

Finally, the gap between Europe and China regarding love was also visible in politic. To the May Fourth generation 1915-1921 fighting against traditional Confucian values, the absence of love in Chinese marriages was one of the clearest signs that the Chinese culture was backward and that a revolution was needed. The battle for the right to love of "free love" was seen as a battle between tradition and modernity, love and kinship ties, East and West, feudalism and enlightenment, hypocrisy and authenticity, old and young (Lee, 2006).

To conclude, there is an agreement between observations in literary history and cultural history regarding the relative importance of romantic love in early Modern Europe and Early Modern China. Lee, H. (2006). Revolution of the heart : A genealogy of love in China, 1900-1950. Stanford University Press. Pan, L. (2015). When True Love Came to China. Hong Kong University Press.

Arab World (400 -1800)

During the classical period (9 th c. -11 th c.), more than twenty works on the theory of romantic love appeared from both the Islamic East and the Islamic West (Giffen, 1972). The most comprehensive works deal with the nature of love, Arabic terms for love, its causes, its varieties, the experiences that accompany it, the protocol to be observed by the lover (the exchange of letters, tokens, poems and so on). The very existence of this literature testifies the cultural importance of love during the classical period. It is difficult though to compare this material with earlier and later periods for philosophical and scholarly reflections are lacking in these periods. Hence, the surge in the reflections on love could a be consequences of an increase in all kinds of theoretical reflections. Legal or artistic materials would be more decisive. However, to the best of our knowledge, no scholarly work has been dedicated to the study of love outside the literary and philosophical domains. Giffen, L. A. (1972). Theory of profane love among the Arabs : The development of the genre. University of London Press.

9 -14 Western Europe: England, France, Germany, Italy, Low Countries and Spain (500 -1800) Coontz, S. (2006). Marriage, a history : How love conquered marriage. Penguin. Daumas, M. (1996). La tendresse amoureuse aux XVIe-XVIIe siècles. Perrin. Daumas, M. (2004). Le mariage amoureux : Histoire du lien conjugal sous l'Ancien Régime. Armand Colin. [START_REF] Macfarlane | [END_REF]. Marriage and love in England : Modes of reproduction 1300-1840. [START_REF] Stone | Quantitative series are limited. Yet, Figure 5 shows the importance of several issues in conjugal life according to religious manuals of marriage in Early Modern France[END_REF]. The family sex and marriage : In England 1500-1800.

Wales (500 -1800)

To the best of our knowledge, there is no systematic study of the diachronic evolution of romantic love in Wales outside of literary history.

16. Japan (700 -1800)

EARLY MODERN JAPAN COMPARED TO EARLY MODERN EUROPE

As for China, there is no scholarly study of the evolution of love in Japan. However, just as for China, a few works have studied the period during which Japan entered into contact with the 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7

When, How, ect.

Health, procreation

Moderation, restraint

Faithfulness Marital love Grace

  Bossler, B. (2011). Fantasies of Fidelity : Loyal Courtesans to Faithful Wives. Beyond Exemplar Tales: Women's Biography in Chinese History, 158-74. Bossler, B. (2013). Courtesans, concubines, and the cult of female fidelity. Harvard University Press.

Table 1 : Relative importance of romantic love by area and by period Periods References Evolution Least developed Most developed

 1

	• Economic Development across periods (when possible Living Standards and Human
	Development indicators were added)
	• Evolution of love in cultural history
	Results
			Dixon, 1992; Ewald, 2003;	Increase
	Late Republic (Latin)	Early Empire (Latin)	Jeppesen-Wigelsworth, 2010;
			Norena, 2007
	Early Medieval Europe	Central Medieval Europe	de La Roncière, 2009; Duby, 1981,	Increase
			1988; Joye, Santinelli, & Bührer-
			Thierry, 2013; Reddy, 2012;
			Rougemont, 1939; Schnell, &
			Schield, 1998; Stone, 2011
	Late Medieval Europe	Early Modern Europe	de La Roncière, 2009; Duby, 1981;	Increase
			Duby, 1988; Reddy, 2012;
			Rougemont, 1939; Schnell, &
			Shields 1998; Stone, 2011
	Early Medieval Norway	Central Medieval Noway	Ariès, 1982; Coontz, 2006; Daumas,	Increase
			1996; Daumas, 2004; Macfarlane,
			1986; Stone, 1977
	Medieval Russia	Medieval Europe	Levin, 2018; Sobol, 2011	Increase
	Medieval Russia	Early Modern Russia	Sobol, 2011	Increase
	Early Modern Russia	Early Modern Europe	Sobol, 2011	Increase
	Pre-Tang Dynasties	Tang Dynasty	Luo, 2015; Owen, 1995, 1996; Yue,	Increase
			2012
	Tang Dynasty	Song Dynasty	Bossler, 2011	Increase
	Song Dynasty	Ming Dynasty	Carlitz, 2011; Lee, 2006; Pan, 2015	Increase
	Ming Dynasty	Qing Dynasty	Lee, 2006; Pan, 2015	Increase
	19 th c. China	19 th c. W. Europe	Lee, 2006; Pan, 2015	Increase
	19 th c. Japan	19 th c. W. Europe	Bassino, Broadberry, Fukao, Gupta,

Table 1 : Relative importance of romantic love by period (predicted and observed)

 1

	Periods
			Prediction	Observations
	Least developed	Most developed
	Late Republic	Early Empire	Increase	Increase

  The Portrayal of Roman Wives in Literature and Inscriptions [PhD Thesis].

	University of Calgary.
	Norena, C. F. (2007). Hadrian's chastity. Phoenix, 296-317.
	7. China (300 CE -1800 CE)

Dixon, S. (1992). The Roman Family. JHU Press. Ewald, B. C. (2003). Sarcophagi and senators : The social history of Roman funerary art and its limits-Verlag Philipp von Zabern, Mainz am Rhein 2001). Pp. 146, pls. 24. ISBN 3-8053-2696-3. Journal of Roman Archaeology, 16, 561-571. Jeppesen-Wigelsworth, A. D. (2010).

Table 2 : Relative importance of romantic love by area and by period (predicted and observed) Periods

 2

	Prediction	Observations

Table 3 : Relative importance of romantic love by area and by period (predicted and observed)

 3

	Periods				Agreement with the
	Least developed	Most developed	Prediction	Observations	narrative literature
	191 Early Middle Ages	Central Middle Ages	Increase	Increase	Yes
	192 Late Middle Ages Early modern period	Increase	Increase	Yes

Proportion of French treaties on marriage discussing love in marriage in the 16th (grey) and 17th (black) centuries (Daumas, 2004).

Ariès, P. (1982)

. Le mariage indissoluble.

Communications, 35(1),[123][124][125][126][127][128][129][130][131][132][133][134][135][136][137]

Table 4 : Relative importance of romantic love by area and by period (predicted and observed)

 4

	Periods				Agreement with the
	Least developed	Most developed	Prediction	Observations	narrative literature
	19 th c. Japan	19 th c. W. Europe	Europe > Japan	Europe > Japan	Yes
	19 th c. China	19 th c. Japan	Japan > China	Japan > China	Yes

European culture at the end of the 19 th c., a few decades before China. And, as for China, there is an agreement between literary history and cultural history.

In literary history, the consensus is that Japanese literature was less romantic than its European counterpart, and that romantic love is a foreign notion. For instance, historian of Japanese literature Donald Keene writes: 'Romantic love, probably the most familiar theme in Western literature, was celebrated for the first time by Japanese poets in the 1880s.' (Keene, 1999, p. 24). In the same way, the poet and essayist Kitamura Tōkoku (1868-94) thought that 'the kind of love portrayed by Plato, Dante and Byron' was absent in Japan and that men of letters of the period (the Edo) preceding his own (the Meiji) had no 'other means to express romantic sentiments than to describe carnal lust.' (Yokota-Murakami & Yokota, 1998, p. 87).

This contrast between Japan and Europe regarding romantic love has a parallel in cultural history for the consensus in history of Japanese mentalities is that romantic love up until the 19 th c. was less developed than in the West (Butel, 2012;Morton, 1997;Pan, 2015;Suzuki, 2010;Yokota-Murakami & Yokota, 1998). 'In Japan, love as the West understood it was thought to be something Japanese people had not known before it entered their country with Christianity' (Pan, 2015, p. 114).

Japanese historians Yokota-Murakami and Yokota explains further how alien to the malefemale relationship romantic love was: "If the premodern regime of Japanese male sexuality, which mostly encompassed prostitution, entailed condescending patronage on the part of a man and humble servitude on that of a woman, love as friendship required mutual respect. Concern for love and respect had, apparently, never been concurrently expressed in premodern Japanese texts. (…) Only through reading European literature did a connotation of "respect" arise within the significative system of "love" of Japanese literati. Such a male-female relationship was in complete contradiction to the hierarchical gender structure and the hedonistic masculine sexuality of premodern Edo upper-and middle-class society. The semi-feudal (male) system of passion depended on the division between prostitutes (yujo) as objects of love, and housewives (or, literally, "ordinary women", jionna) as domestic servants and agents of reproduction." (Yokota-Murakami & Yokota, 1998, p. 87).

Kuriyagawa Hakuson, author of a best-seller treaty on love Modern Views of Love (1921) notes that:

'The Japanese language utterly lacks words comparable to the English word "love," and as for the statements "I love you," or "Je t'aime," there is no way whatsoever of rendering them into Japanese. The Japanese language is entirely incapable of expressing the sort of feeling contained in these statements . . . And the reason the vocabulary is lacking is that the thought which such vocabulary might express is not there. ' (cited in Pan, 2015, p. 114) A new term, rabu, had to be coined for talking about 'love'. Here is what Tōkoku wrote to a friend about this new concept: 'Our love [rabu] stands outside sexual passion, we love in our hearts, we love in our hopes: in contrast to the sexual love of others, we possess a much stronger love. Even though we are not yet one body, I feel as if we are already together. We will build an impregnable fortress of love where no enemies will frighten us.' (Morton, 1997, p. 84) As Yokota-Murakami & Yokota note: "The fact that "love" had to be first called rabu, the neared phonetic equivalent in Japanese for "love", and that it was subsequently necessary to invent a completely new signifier, strongly suggest that the signified of "love" was, at least to the eyes of Japanese literari, in no way similar to the related concepts in the Japanese vocabulary." (Yokota-Murakami & Yokota, 1998, p. 87) In the late 1880s and 1890s, another new term, ren'ai, was popularized and accepted as the Japanese translation of the English (and European) concept of love (Yokota-Murakami & Yokota, 1998, p. 42). This concept was popularized in particular by a manifesto 'Disillusioned Poets and Women,' that Tōkoku published in 1892. The text was the first in Japan to idealize ren'ai as the most important aspect of human existence. The opening words of the text are famous: 'Love is the key to life's secrets. Love exists first, then human life. If one takes away love, what is left of the meaning of life?' (Suzuki, 2010, p. 9). Iwamoto Yoshiharu, one of the first writers to use ren'ai in the sense of Western romantic love wrote in 1890 in the review of a Japanese translation of a Balzac novel: 'Japanese men love (ren'ai-suru) very superficially. They don't love (ai-suru) from deep within their soul' (Yokota-Murakami & Yokota, 1998, p. 87).

It is worth noting that, in this process of cultural transmission, Japan was ahead of China. Despite a much longer history of contact with West and despite the long isolation of Japan until 1868, it is the more affluent and dynamic Japan that started to catch-up with the West in terms of the evolution of love (on the advance of Japan in 1900, see Bassino et al., 2019;Baten & Van Zanden, 2008;Morris, 2013). The translation of European novels started earlier in Japan (many Chinese translations were in fact retranslation from Japanese translations). The coining of new words, in particular news words related to love appeared earlier, started also earlier in Japan (the Chinese term lian'ai is actually inspired by the Japanse ren'ai) It is also in Japan that the first theories of love appeared, such as in Modern views of love, published in Japan in 1922 and translated in Chinese a year later (Pan, 2015). These observations fit well with the idea that love became more important earlier in Japan than in China, in line with the affluence hypothesis.

To conclude, there is an agreement between observations in literary history and cultural history regarding the relative importance of romantic love in early Modern Europe and Early Modern Japan.

Ireland (700 -1800)

To the best of our knowledge, there is no systematic study of the diachronic evolution of romantic love in Ireland outside of literary history.

18. Old Norse world (800 -1800)

FROM EARLY MEDIEVAL NORWAY TO CENTRAL MEDIEVAL NORWAY

In Strategies of passion, Bjørn Bandlien studied the importance of romantic love during the medieval period, using not only the narative literature but also skaldic poems, runic inscriptions, legal decisions, canon law and clerical historiography. He demonstrates that there is a clear evolution from the Early Medieval period where love was 'caught up in a discourse on honour' and 'still a force of chaos' to the Central Medieval period (especially after 1250) where 'love was no longer a sign of weakness, but a symbol of his good nature' (Bandlien, 2005). There is thus an agreement between literary history and cultural history regarding the relative importance of romantic love in Norway.

Bandlien, B. (2005). Strategies of passion :

Love and marriage in medieval Iceland and Norway (Vol. 6). Brepols Pub.

19. East Slavic world (1100 -1800)

MEDIEVAL RUSSIA COMPARED TO MEDIEVAL EUROPE

Historians have noted that the attitude of medieval Russian culture regarding romantic love were extremely negative. As Eve Levin writes in Sex and Society in the World of the Orthodox Slavs 900-1700, the attitude of the Orthodox Church to love was even more negative than its Western counterpart (Levin, 2018). Unlike Western Christian writers, Eastern Christian considered sexual relationships of any kind as a manifestation of fallen nature', and 'sexual desire and love were viewed as antithetical emotions, even within the domain of Christian marriage' (Levin, 2018). In her comparison between medieval Western European, Levin writes that the medieval Slavs:

'denied that love, an emotion of generosity and devotion, could be connected to sexual desire. The medieval Slavs could scarcely conceive that sexual activity might be more fulfilling physically or emotionally with one partner than with another.'

Levin concludes:

'The idea of romantic love, which became dominant in Western literature and ultimately in legal and popular conceptions of marriage, remained unfamiliar in the East. (…) Medieval Slavic brides and grooms did not expect to receive emotional support from their spouses, much less from their in-laws. Men expected strongest their strongest relationships to be with their natal family, particularly parents and brothers, and from familial connections.' (Levin, 2018)

The negative attitude toward love is also visible in the 17 th The Tale of Savva Grudtsyn. In this narrative fiction, love play an important role. However, the origins of love are, characteristically, the devil's intervention, and love is essentially depicted as a dangerous and disturbing activity (Sobol, 2011). As a traditional Russian proverb says: 'If blind love fixes itself into someone's heart, it will either cripple him or blind him' (Sobol, 2011).

What is also interesting is that cultural contact with the West did not impact Russian culture until the economic take-off of the 17 th c.

'despite centuries of political interaction between the Slavic Orthodox and Roman Catholic states, key Western concepts of sexuality, such as Augustine's conjugal debt and the idea of courtly love, remained unknown in the East until the middle of the seventeenth century.' (Levin, 2018)

To conclude, there is an agreement between observations in literary history and cultural history regarding the relative importance of romantic love in Medieval Europe and Medieval Russia.

Levin Despite its enormous popular success, Trediakovsky was accused of corrupting the Russian youth.

'Once again, underlying his contemporaries' indignation is the idea that passionate love as a psychological and even physiological phenomenon had not existed in Russia before it was introduced from the outside, through cultural institutions and literary texts.' (Sobol, 2011) This clearly reveals that the conception of love has been changing between the medieval and the early modern period, both in literature and in cultural values.

EARLY MODERN RUSSIA COMPARED TO MEDIEVAL EUROPE

Early modern Russians were well aware that romantic love was much highly regarded in the West than in their own country. One of the earliest private journals in Russian culture, Prince Kurakin's The Life of the Prince Boris Ivanovich Kurakin, Which He Himself Wrote, records the following amourous episode from the author's travel in Europe:

'And during my stay there I was inamorat with a chitadinka (citydweller), famous for her beauty, her name was signora Francesca Rota, whom I had for a medresa (mistress) for my entire stay. And I was so inamaroto (sic) that I could not spend even an hour without her who kostet (cost) me 1000 chervonnys during those two months. And I partet with great lament and sorrow, and even now that amor cannot leave my heart and, I believe, will not. I took her persona in my memoria and promised to come back to her again. ' (cited in Sobol, 2011) As Valeria Sobol writes:

'It can hardly escape the readers' attention that every word related to the prince's love experience is Italian, sometimes transliterated, sometimes not: 'inamorat,' with its broken version 'inamorato', 'medresa' and significantly 'amor'. Obviously, the 'translation' of Western love vocabulary presented a linguistic as well as a cultural, difficulty for the author.' (Sobol, 2011)

A few decades later, though, in Mikhail Danilov's Diary (1771), a very similar situation is described without any difficulty: the Russian language now have the adequate vocabulary to describe romantic love, from strast' (passion) to liubimyi predmet (the object of love). There is thus an agreement between literary history and cultural history regarding the relative importance of romantic love in Early Modern Europe and Early Modern Russia.

Sobol, V. (2011). Febris erotica : Lovesickness in the Russian literary imagination. University of Washington Press.


Amos Korman

Robin Vacus

Distributed Alignment Processes with Samples of Group Average * †

This paper studies a stochastic alignment problem assuming that agents can sense the general tendency of the system. More specifically, we consider n agents, each being associated with a real number. In each round, each agent receives a noisy measurement of the system's average value and then updates its value. This value is then perturbed by random drift. We assume that both noise and drift are Gaussian. We prove that a distributed weighted-average algorithm optimally minimizes the deviation of each agent from the average value, and for every round. Interestingly, this optimality holds even in the centralized setting, where a master agent can gather all the agents' measurements and instruct a move to each one. We find this result surprising since it can be shown that the set of measurements obtained by all agents contains strictly more information about the deviation of Agent i from the average value, than the information contained in the measurements obtained by Agent i alone. Although this information is relevant for Agent i, it is not processed by it when running a weighted-average algorithm. Finally, we also analyze the drift of the center of mass and show that no distributed algorithm can achieve drift that is as small as the one that can be achieved by the best centralized algorithm.

1 Introduction

Background and Motivation

Reaching agreement, or approximate agreement, is fundamental to many distributed systems, including: computer networks, mobile sensor systems, animal groups, and neural networks [START_REF] Craig | Flocks, herds and schools: A distributed behavioral model[END_REF][START_REF] Andrew | Many wrongs: the advantage of group navigation[END_REF][START_REF] Vicsek | Collective motion[END_REF]. In the natural world, one fascinating example occurs during cooperative transport in ants, in which a group of ants join forces to carry a large or heavy food load [START_REF] Gelblum | Ant groups optimally amplify the effect of transiently informed individuals[END_REF][START_REF] Gelblum | Emergent oscillations assist obstacle negotiation during ant cooperative transport[END_REF]. While carrying the load, improved consensus on the direction of forces applied by the ants amounts to faster movement of the carried load, since less forces are canceling each other. Another beautiful example concerns flocking birds (or, e.g., schooling fish) that manage to maintain a cohesive direction of movement by constantly aligning their directions of flights [START_REF] Vicsek | Collective motion[END_REF]. In these contexts, as well as in multiple other contexts, such as during clock synchronization [START_REF] Sivrikaya | Time synchronization in sensor networks: a survey[END_REF][START_REF] Sundararaman | Clock synchronization for wireless sensor networks: a survey[END_REF], the space in which the process occurs is continuous, measurements are noisy and the output needs to be maintained over time, while being subject to drift.

In several contexts, distributed consensus algorithms can be designed by letting each agent repeatedly execute the following two steps.

1. obtain an estimate regarding the average "opinion" of other agents in the system.

2. shift the "opinion" by a certain extent towards the estimated average. The first step assumes that agents are somehow able to sense the general behavior of the system. Such an ability may be quite limited in many contexts, but not in all. We shall soon provide several examples for scenarios in which agents are able to measure global parameters of the system, either directly, or indirectly.

However, before we list these examples, we would like to stress that the current paper is not concerned with the mechanism behind implementing such samples, and instead focuses on optimizing the second step, corresponding to the shifts that should be made after obtaining such samples.

Examples of global parameter samplings

We next provide several examples for settings in which agents can sample global parameters. The emphasis is on examples from the biological world. We classify these examples into three categories.

• Using an external entity as a relay of information. In several contexts, agents may use an external entity (or a "leader" agent) to gather information from agents, compute a certain function of it (e.g., the average value), and then communicate this information to all others. Indirectly, this happens, for example, during the process of cooperative transport, in which agents physically carry a large or heavy object, as mentioned above. In this process the carried object itself serves as a medium entity through which the global tendency of the group could be sensed by each carrying agent. In the context of ants, for example, the authors of [START_REF] Gelblum | Ant groups optimally amplify the effect of transiently informed individuals[END_REF][START_REF] Gelblum | Emergent oscillations assist obstacle negotiation during ant cooperative transport[END_REF][START_REF] Korman | Sequential decision-making in ants and implications to the evidence accumulation decision model[END_REF][START_REF] Helen | Cooperative transport in ants: a review of proximate mechanisms[END_REF] assumed that each ant uses the carried object to sense the sum of the forces exerted by all carrying ants. After measuring this sum (which represents the velocity vector of the carried object), each ant decides whether, and by how much, it should align its force to this measurement. Cooperative transport following a similar approach was also studied in the context of robotics, see, e.g., [START_REF] Berman | Study of group food retrieval by ants as a model for multi-robot collective transport strategies[END_REF][START_REF] Wang | Multi-robot manipulation without communication[END_REF]. Other natural examples include the behavior of a swarm of flying midges [START_REF] Gorbonos | Long-range acoustic interactions in insect swarms: an adaptive gravity model[END_REF], and during firefly synchronization [START_REF] Guerraoui | Byzantine fireflies[END_REF]. In such swarms, each midge (respectively, firefly) is affected by the acoustic (respectively, visual) field produced by all others. In these examples, the environment plays the role of relaying global information to agent.

• Broadcast in clique networks. Obtaining measurements of the whole system is also relevant for relatively packed systems, so that the communication is essentially being broadcasted over a clique. In the natural world, the clique abstraction can find relevance in small flocks of birds, or in other small animal groups [START_REF] Conradt | Consensus decision making in animals[END_REF][START_REF] Tamm | Bird orientation: single homing pigeons compared with small flocks[END_REF].

• Well-mixed populations. The assumption that agents sense global parameters of the system also finds relevance in highly mobile systems. In particular, when the population is well-mixed, the pattern of communication may be captured by a random process, in which the set of neighbors is constantly being replaced by agents chosen uniformly at random. In such cases, sensing the current set of neighbors can serve as a fresh random sample of the global population. This perspective has recently been adopted by multiple works in theoretical computer science (although in contrast to this paper, the typical assumption in these works is that the set of opinions is discrete), see, e.g., [START_REF] Becchetti | Consensus dynamics: An overview[END_REF][START_REF] Becchetti | Simple dynamics for plurality consensus[END_REF][START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits[END_REF][START_REF] Doerr | Stabilizing consensus with the power of two choices[END_REF][START_REF] Ofer Feinerman | Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication[END_REF][START_REF] Ghaffari | Nearly-tight analysis for 2-choice and 3-majority consensus dynamics[END_REF]. For example, in Majority Dynamics, each agent pulls the opinions of a few random agents, and changes its opinion to the majority opinion among these samples [START_REF] Becchetti | Consensus dynamics: An overview[END_REF][START_REF] Becchetti | Simple dynamics for plurality consensus[END_REF][START_REF] Doerr | Stabilizing consensus with the power of two choices[END_REF][START_REF] Ghaffari | Nearly-tight analysis for 2-choice and 3-majority consensus dynamics[END_REF]. As such, these protocols can be viewed as being composed of two parts: (1) obtain a noisy sample of the majority opinion in the population based on the opinions of the pulled agents, and (2) align to this majority.

Informally, the alignment problem we study, considers a group of n agents positioned on the real line, aiming to be located as close as possible to one another. We stress that the setting on the line does not necessarily aim to capture the physical locations of the agents, which may actually be scattered in arbitrary domains (e.g., two or three dimensional Euclidean spaces). Instead, the positions on the line aim to capture the "opinions" of the agents, which, in this preliminary work, are restricted to a one dimensional space. For example, in view of general alignment problems, such as flocking, the position of an agent aims to model its direction. When flocks of birds fly, the altitude axis often remains stable, and hence the flight could be viewed as two-dimensional, implying that the direction could be represented as one-dimensional. A similar observation holds in many contexts of two-dimensional navigation, for example, during cooperative transport by ants. In view of clock-synchronization [START_REF] Sivrikaya | Time synchronization in sensor networks: a survey[END_REF][START_REF] Sundararaman | Clock synchronization for wireless sensor networks: a survey[END_REF] or firefly synchronization [START_REF] Guerraoui | Byzantine fireflies[END_REF], the position of an agent models its clock (i.e., time), which again can be viewed as a one-dimensional space1 .

Initially, agents' positions are sampled from a Gaussian distribution around 0. Execution proceeds in discrete rounds, where in each round, each agent receives a noisy measurement of its current deviation from the average position of others. Then, governed by the rules of its algorithm, each agent performs a move to re-adjust its position. Subsequently, before the next round begins, the position of each agent is perturbed following random drift. The drift component may model unreliability due to external conditions (e.g., perturbation of direction by wind), or the inability of an agent to precisely adjust itself as it wishes. Both noises in measurements and random drifts are governed by Gaussian distributions. We are mostly interested in the following questions:

• Which re-adjustment rule should agents adopt if their goal is to minimize expected distance of each agent from the average position?

• Could further communication between agents (e.g., by sharing measurements) help?

• Which protocols minimize the drift of the center of mass? Importantly, we assume that agents are unaware of the actual value of their current positions, and of the realizations of the random drifts, and instead, must base their movement decisions only on noisy measurements of relative positions. This lack of global "sense of orientation" prevents the implementation of the trivial distributed protocol in which all agents simply move to a predetermined point, say 0.

One trivial algorithm is the "fully responsive" protocol, where in each round, each agent moves all the way to its current measurement of the average position of others. When drift is large compared to measurement noise, and the number of agents is large, this protocol can become highly efficient. However, when measurement noise is non-negligible compared to the drift, it is expected that incorporating past measurements could enhance the cohesion, even though drift may have changed the configuration considerably.

Perhaps the simplest class of algorithms that take such past information into account are weightedaverage algorithms. By weighing the current position against the measured position in a non-trivial way, such algorithms can potentially exploit the fact that the current position implicitly encodes information from past measurements. Indeed, in a centralized setting, when a single agent aims to estimate a fixed target relying on noisy Gaussian measurements, a weighted-average algorithm is known to be optimal, in the sense that it minimizes the expected distance between the agent and the target [START_REF] Brian | Optimal filtering[END_REF]. However, here the setting is more complex since it is distributed, and the objective goal is to estimate (and get closer to) the average position, which is a function of the agents decisions.

The alignment problem

We consider n agents located on the real line R. Let I = {1, . . . , n} be the set of agents. We denote by θ (t) i ∈ R the position of Agent i at round t, where initially, the position of each agent is chosen independently according to a normal distribution around 0, with variance σ 2 0 , that is, for each Agent i, θ

∼ N 0, σ 2 0 . As mentioned, we assume that an agent is unaware of the actual value of its current position.

Execution proceeds in discrete rounds. At round t, each agent i receives a noisy measurement of the deviation from the current average position of all other agents. Specifically, denote the average of the positions of all agents except i by: θ

(t) -i = 1 n-1 j∈I\i θ (t) i . Let θ (t) i = θ (t) -i -θ (t) i
denote the stretch of Agent i. At any round t, for every i ∈ I, a noisy measurement of the stretch of Agent i is sampled:

Y (t) i = θ (t) i + N (t) m,i , (1)
where

N (t)
m,i ∼ N (0, σ 2 m ). In response, Agent i makes a move dθ (t) i and may update its memory state (if it has any). Finally, the position of Agent i at the next round is obtained by adding a drift:

θ (t+1) i = θ (t) i + dθ (t) i + N (t) d,i , (2)
where .

N (t) d,i ∼ N (0, σ 2
Note that the cost depends on the algorithm used by i and on the algorithms used by others. As these algorithms will be clear from the context, we omit mentioning them in notations.

Definition 2 (Optimality). We say that an algorithm is optimal if, for every i ∈ I and every round t, no algorithm can achieve a strictly smaller cost C (t) i . Note that the definition refers to a very strong notion of optimality -it implies that if Algorithm A is optimal, then for any given round t and for any given Agent i, no algorithm B can achieve better performances for Agent i at round t than the performances guaranteed by A, regardless of what B did in previous rounds. Definition 3 (Weighted-average algorithms). A weighted-average algorithm is a distributed algorithm that is characterized by a responsiveness parameter ρ (t) for each round t, indicating the weight given to the measurement at that round. Formally, an agent i following the weighted-average algorithm W(ρ (t) ) at round t, sets dθ

(t) i = ρ (t) Y (t) i . (3)
Full communication (or centralized) model. When executing a weighted-average algorithm, an agent bases its decisions solely on its own measurements. A main question we ask is whether, and if so to what extent, can performances be improved if agents could communicate with each other to share their measurements.

In order to study the impact of communication, we compare the performances of the best weighted-average algorithm to the performances of the best algorithm in the full-communication model, where agents are free to share their measurements with all other agents at no cost. In the case that agents have identities, this setting is essentially equivalent to the following centralized setting: Consider a master agent that is external to the system. The master agent receives, at any round t, the stretch measurements of all agents, i.e., the collection {Y (t) j } j∈I , where these measurements are noisy in the same manner as described in Eq. ( 1). Analyzing these measurements at round t, the master agent then instructs each agent i to move by a quantity dθ (t) i . After moving, the agents are subject to drift, as described in Eq. [START_REF] Becchetti | Consensus dynamics: An overview[END_REF]. Note that the master agent is unable to "see" the positions of the agents, and its information regarding their locations is based only on the measurements it gathers from the agents, and on the movements it instructs. The goal of the master agent is to minimize the maximal cost of an agent, (where the maximum is over the agents), per round. In particular, an algorithm is said to be optimal in the centralized setting if it satisfies Definition 2, (where optimality is with respect to all algorithms in the centralized setting).

Our results

We prove that a distributed weighted-average algorithm, termed W ⋆ , optimally minimizes the expected stretch of all agents at all rounds, in the strong sense of Definition 2. The optimality of this weighted-average algorithm holds even in the centralized (full-communication) model. We find this result surprising since it can be shown that the measurements made by Agent i contain strictly less information about the agent's relative position to the average position than the information contained in the collection of all measurements {Y (t) j } j∈I . Indeed, although the {Y (t) j } j∈I measurements are not centered around the stretch θ (t) i of Agent i, they still contain useful information about the stretch of Agent i. For example, it can be shown that

- j∈I\i Y (t) j = θ (t) i - n j∈I\i N (t) m,j , (4)
thus representing an additional "fresh" estimation of θ (t)

i . Hence, the measurements obtained by Agent i are not sufficient statistics with respect to all measurements, when aiming to estimate the stretch of Agent i. 2 Another natural cost measure is the deviation from the average position of all agents (including the agent), i.e., C

(t) i ′ := E(| 1 n j∈I θ (t) j -θ (t) i |). These two measures are effectively equivalent. Indeed, C (t) i ′ = n-1 n C (t)
i , thus an algorithm minimizing one measure will also minimize the other.

Therefore, at a first glance, it may appear that in the centralized setting the stretch of agents could potentially be reduced by letting the master agent process all measurements. Nevertheless, when operating under W ⋆ , Agent i processes merely its own measurements, and still its stretch is minimized, as it could best be minimized by utilizing all measurements. The reason why this happens, is that other agents manage to fully process the information not processed by Agent i in a way that also benefits Agent i, by shifting the center of mass towards it.

Finally, we also analyze the drift of the center of mass and show that no distributed algorithm can achieve as small of a drift as can be achieved by the best centralized algorithm. In light of this, we also show that the drift associated with W ⋆ incurs a relatively small overhead over the best possible drift in the centralized setting.

Intuition: The case of Two Agents in One round.

In order to obtain preliminary understanding, let us first examine the case of two agents operating in a single round, and compare the situation between the centralized and the distributed setting. This simple example is informative since it already demonstrates the aforementioned surprising phenomenon.

To really limit this example to "one round", we assume that the initial distribution of the stretches has a very large variance (formally, σ 2 0 ≫ σ 2 m ). Therefore, we can put aside the Bayesian conflict between the a priory knowledge about the stretches, and the information contained in the new measurement -and only work with the latter.

When considering two agents, the stretch θ i of Agent i ∈ {1, 2} is simply its relative distance to the other agent. Assume that their positions are initially set to θ 1 = 0 and θ 2 = 1, so that θ 1 = +1 and θ 2 = -1. Assume further that the respective measurement noises are N m,1 = 0.1 and N m,2 = 0.2. In this case, the measurements of the stretches are:

Y 1 = θ 1 + N m,1 = +1.1 Y 2 = θ 2 + N m,2 = -0.8. (5)
Centralized setting. Here, a central entity gathers both measurements Y 1 and Y 2 , and, based on these measurements, instructs each agent of its move. Since we assumed that the initial distribution of the stretches has a very large variance compared to σ 2 m , the most accurate estimates of the relative stretches between the agents depends only on the measurements

θ1 cent = 1 2 (Y 1 -Y 2 ) = +1.9 2 = +0.95 θ2 cent = 1 2 (Y 2 -Y 1 ) = -1.9 2 = -0.95. (6)
Recall that the goal of the central entity is to minimize the absolute stretch between the agents. Note that for this purpose, it has a degree of freedom, since, once it moves each of them, shifting both by the same amount would not change their stretch. However, if the central entity also wishes to minimize the drift of the center of mass, then it should instruct the agents to move towards the estimated center, shifting them by θi /2 towards each-other. (This type of algorithm will later be called "meet at the center".) Specifically, the instructed moves would be dθ

1 cent = 1 2 θ1 cent = +0.475 and dθ 2 cent = 1 2 θ2 cent = -0.475. By definition,
the new positions of the agents (before drift applies) would be:

θ ′ 1 cent = θ 1 + dθ 1 cent = 0.475 θ ′ 2 cent = θ 2 + dθ 2 cent = 0.525 so θ ′ 1 cent = +0.05, θ ′ 2 cent = -0.05. (7)
As can be seen, the center of mass is unchanged. In fact, this is no coincidence and would be the case for any measurement noises (before drift takes place). Distributed setting. In the distributed setting, an agent must base its estimate of the stretch on its measurement alone. In this case, we have:

θ1 dist = Y 1 = +1.1, θ2 dist = Y 2 = -0.8.
Of course, the quality of these estimates is less than in the centralized setting (compare with Eq. ( 6)).

Once again, in attempting to "meet at the center", the best that the agents can do is to go half way to their respective estimate of the location of the other agent. That is, dθ

1 dist = 1 2 θ1 dist = 1 2 • Y 1 = +0.55 and dθ 2 dist = 1 2 θ2 dist = 1 2 • Y 2 = -0.4.
By definition, their new locations (before drift applies) would be:

θ ′ 1 dist = θ 1 + dθ 1 dist = 0.55 θ ′ 2 dist = θ 2 + dθ 2 dist = 0.6 , yielding    θ ′ 1 dist = +0.05 θ ′ 2 dist = -0.05.
Evidently, in contrast to the centralized case (Eq. ( 7)), here the center of mass moved as a result of the agents movements. Importantly, however, the relative positions of the agents (and therefore, their costs) are identical to the ones obtained in the centralized protocol. Again, this is no coincidence, and holds for any measurement noises. The reason is, that the two locations of the agents in the distributed setting differ by the same shift, compared to their location in the centralized setting. Indeed, we have:

θ ′ 1 dist -θ ′ 1 cent = dθ 1 dist -dθ 1 cent = 1 4 (Y 1 + Y 2 ) θ ′ 2 dist -θ ′ 2 cent = dθ 2 dist -dθ 2 cent = 1 4 (Y 1 + Y 2 ).
This shift, i.e., 1 4 (Y 1 + Y 2 ), represents the "mistake" made by distributed agents in attempting to meet at the center, compared with the centralized algorithm. However, since both agents in the distributed setting are shifted by the same quantity compared to their respective positions in the centralized setting, their relative stretch remains the same in both settings. A main challenge of this paper is to show that this phenomenon holds also in the multi-round scenario, and with arbitrary number of agents. Weighted-average algorithms with fixed responsiveness. As a warm-up towards understanding multiround scenarios with multiple agents, we first investigate weighted-average algorithms in which all agents have the same responsiveness ρ, that furthermore remains fixed throughout the execution (see Eq. ( 3)). The proofs of both Theorems 1 and 2 below are given in Section 2.

Theorem 1. Assume that all agents execute W(ρ), for a fixed 0 ≤ ρ ≤ 1. Then for every i ∈ I and every t ∈ N, the stretch θ (t) i is normally distributed, and

lim t→+∞ Var θ (t) i = n n-1 (ρ 2 σ 2 m + σ 2 d ) 1 -(1 -n n-1 ρ) 2 ,
with the convention that lim t→+∞ Var(θ

(t) i ) = +∞ if the denominator 1 -(1 -n n-1 ρ) 2 = 0.
If all agents run W(ρ), then Agent i's cost at steady state is captured by Var(ρ) := lim t→+∞ Var θ (t) i .

Indeed, for every i, since θ

(t) i is normally distributed, lim t→+∞ E θ (t) i = 2
π Var(ρ). The minimal value of this is achieved when taking argmin ρ Var(ρ) as the responsiveness parameter.

Theorem 2. The weighted-average algorithm that optimizes group variance among all weighted-average algorithms W(ρ) (that use the same responsiveness parameter ρ at all rounds) is W(ρ ⋆ ), where

ρ ⋆ = σ d 4σ 2 m + n n-1 σ d 2 -n n-1 σ 2 d 2σ 2 m . ( 8
)
When n is large, Eq. ( 8) becomes ρ ⋆ ≈

σ d √ 4σ 2 m +σ 2 d -σ 2 d 2σ 2 m
. Note that the role played by the measurement noise is very different than the role played by the drift. For example, if

σ m ≫ σ d , then ρ ⋆ ≈ 0. However, if σ m ≪ σ d then ρ ⋆ ≈ 1. Interestingly, if σ m = σ d then ρ ⋆ ≈ √ 5-1
2 , which is highly related to the golden ratio. Moreover, for large n, the minimal Var(ρ) is

Var(ρ ⋆ ) = 1 2 σ d 4σ 2 m + σ 2 d + σ d . (9)
Note that when the measurements are perfect, i.e., σ m = 0, we have Var(ρ ⋆ ) = σ 2 d , which is the best achievable value that an agent can hope for, since no algorithm can overcome the drift-noise.

The impact of communication. Our next goal is to understand whether, and if so, to what extent, can performances be improved if further communication between agents is allowed. For this purpose, we compare the performances of W(ρ ⋆ ) to the performances of the best algorithm in the centralized (full-communication) setting.

A natural candidate for an optimal algorithm in the centralized setting is the "meet at the center" algorithm. This algorithm first obtains, for each agent, the best possible estimate of the distance from the agent's position to the average position θ , based on all measurements, and then instructs the agent to move by this quantity (towards the estimated average position). However, it is not immediate to figure out the distances to the average position, and furthermore, quantify the performances of this algorithm. To this end, we make use of the Kalman filter tool [START_REF] Brian | Optimal filtering[END_REF], by adapting it to our setting. Solving the Kalman filter system associated with the centralized version of our alignment problem, we obtain an estimate of the relative distance of each agent i from the average position (based on all measurements). To describe these estimates we first define the following. Definition 4 (Uncertainty). We inductively define the sequence (α t ) ∞ t=0 . Let α 0 = nσ 2 0 /(n -1), and for every t, let

α t+1 = σ 2 m α t n n-1 α t + σ 2 m + n n-1 σ 2 d . (10)
The value of α t aims to represent the variance of the (random) error made when estimating the stretch of the agents at round t. When thinking of n as very large, the formula for α t+1 is reminiscent of the resistance formula in electrical circuits, where we add in parallel to the current resistor with resistance α t a resistor with resistance σ 2 m (standing for the measurement noise), and another resistor in a series, with resistance σ 2 d (standing for the drift).

⋆ ≈ 0, and the agent should not take the measurement into account. At each round t, the Kalman filter returns an estimate of the relative distance of each agent i from the average position, which turns out to be

ρ (t) ⋆ n-1 n Y (t) i -1 n j∈I\i Y (t) j .
As guaranteed by the properties of the Kalman filter, these estimates minimize the expected sum of squareerrors, which can be translated to our desired measure of minimizing the agents' costs. The "Meet-at-thecenter" algorithm is given by Algorithm 1 below, and the following theorem stating its optimality is proved in Section 3.5.

Theorem 3. Meet-at-the-center is optimal in the centralized setting.

Note that in the centralized setting, once we have an optimal algorithm A, we can derive another optimal algorithm B by simply shifting all agents, at each round t, by a fixed quantity λ t . Indeed, such shifts do not influence the relative positions between the agents. Conversely, we show in Appendix D.1 that all (optimal) deterministic algorithms in the centralized setting are shifts of one another (note that the shifts λ t are not necessarily the same for all rounds t).

As it happens, another solution that follows from the Kalman filter estimations can be described as a distributed weighted-average algorithm (see Algorithm 2). As such, this algorithm, henceforth called W ⋆ , also yields optimal stretches. The proof of the following theorem is given in Section 3.6.

Algorithm 1: Meet-at-the-center foreach round t do

Consider all measurements at round t, {Y

(t) j | 1 ≤ j ≤ n} ; foreach agent i do Set dθ (t) i = ρ (t) ⋆ n-1 n Y (t) i -1 n j =i Y (t) j ; /* Output an estimate of θ -θ i */ end end Algorithm 2: Algorithm W ⋆ foreach round t do
Consider all measurements at round t, {Y

(t) j | 1 ≤ j ≤ n} ; foreach agent i do Set dθ (t) i = ρ (t) ⋆ Y (t) i ; end end Theorem 4. Algorithm W ⋆ = W(ρ (t)
⋆ ) is optimal in the centralized setting. Since both Meet-at-the-center and W ⋆ are optimal deterministic algorithms they must be shifts of one another. Indeed, as validated in [START_REF] Korman | Distributed Alignment Processes with Samples of Group Average[END_REF] (Appendix D.2), by adding the shift

λ t = 1 n ρ (t) ⋆ i∈I Y (t) i
to the agents in Meet-at-the-center we obtain Algorithm W ⋆ .

Note that in contrast to W(ρ ⋆ ), Algorithm W ⋆ uses a different responsiveness ρ

⋆ at each round t. We next argue that the sequences (α t ) and (ρ (t) ⋆ ) converge. Not surprisingly, at the limit, we recover the optimal responsiveness as stated in Theorem 2. Due to lack of space the proof of the following claim is deferred to Appendix B.2 of [START_REF] Korman | Distributed Alignment Processes with Samples of Group Average[END_REF].

Claim 1. The sequence α t converges to

α ∞ := 1 2 σ d 4σ 2 m + n n-1 σ d 2 + n n-1 σ 2 d .
Moreover, lim t→+∞ ρ

(t) ⋆ = ρ ⋆ .
Drift of the center of mass. In this section we analyze the drift of the center of mass. Essentially, we show that with respect to this drift (and in contrast to the measure of stretch as used in Definition 1), there is a gap between the centralized and the distributed settings. Specifically, we first show that Meet-at-the-center is "drift-optimal", in sense that it achieves the best possible drift among all algorithms in the centralized setting. In contrast, we prove that there is no distributed algorithm that can achieve as small of a drift as the one obtained by the "meet at the center" algorithm. Consistent with this result, Algorithm W ⋆ is not "drift-optimal", yet we show that the overhead it incurs in terms of this drift is relatively small, especially when n is large compared to t or when σ m is small compared to σ d .

Let us now describe these results in more detail. Denote ∆ t = θ (t)θ (0) . By definition (Eq. ( 2)), for a given algorithm, the center of mass changes in round t as follows:

θ (t+1) -θ (t) = 1 n i∈I dθ (t) i + N (t) d,i . (11)
The drift of the center of mass after t rounds is therefore

∆ t = 1 n t s=0 i∈I dθ (s) i + N (s) d,i .
Let us define inherent-drift as ∆ inh i . With these notations, we have:

∆ t = ∆ rel t + ∆ inh t . (12)
Due to lack of space, the proof of the following lemma appears in Appendix E of [START_REF] Korman | Distributed Alignment Processes with Samples of Group Average[END_REF].

Lemma 1. For every protocol and for every round t, ∆ inh t and ∆ rel t are independent. A direct consequence of Lemma 1 is that

E ∆ 2 t = E ∆ rel t 2 + Var ∆ inh t ≥ Var(∆ inh t ), (13)
justifying the choice of the term "inherent". Since Var(∆ inh t ) = Var Proof. When the agents follow Algorithm Meet-at-the-center, for every t ∈ N

1 n i∈I dθ (t) i = 1 n i∈I ρ (t) ⋆   n-1 n Y (t) i -1 n j∈I\i Y (t) j   = ρ (t) ⋆ n n-1 n i∈I Y (t) i -1 n i∈I (n -1) • Y (t) i = 0.
Hence, by definition, ∆ rel t = 0 and by Eq. ( 13), the drift of the center of mass in round t is limited to ∆ inh t , which concludes the proof of Theorem 6.

Next, we analyze the drift of W ⋆ . Theorem 7. When Algorithm W ⋆ is used, the drift of the center of mass satisfies

E ∆ 2 t = t+1 n σ 2 d + 1 n t s=0 ρ (s) ⋆ 2 σ 2 m .
Proof. Under Algorithm W ⋆ , we have for every t ∈ N

1 n i∈I dθ (t) i = 1 n i∈I ρ (t) ⋆ θ (t) i + N (t) m,i = 1 n i∈I ρ (t) ⋆ N (t) m,i ,
where the last equality is by Lemma 2. Using Eq. ( 13), and summing over the rounds s = 0, . . . , t, we conclude the proof of Theorem 7.

Note that since ρ (s)

⋆ ≤ 1, the overhead incurred by Algorithm W ⋆ is at most t+1 n σ 2 m . Finally, we argue that the sub-optimality of Algorithm W ⋆ (in terms of the drift of the center of mass) is not coincidental. The proof of the following claim is deferred to Appendix D.2.

Claim 2.

No algorithm in the distributed setting can be simultaneously optimal (Definition 2) and driftoptimal (Definition 6).

Related works

The Kalman filter algorithm is a prolific tool commonly used in control theory and statistics, with numerous technological applications [START_REF] Brian | Optimal filtering[END_REF]. In this paper, we used the Kalman filter to investigate the centralized setting, where all relative measurements are gathered at one master agent that processes them and instructs agents how to move. Fusing relative measurements of multiple agents is often referred to in the literature as distributed Kalman filter, see surveys in [START_REF] Cao | An overview of recent progress in the study of distributed multi-agent coordination[END_REF][START_REF] Olfati-Saber | Distributed kalman filtering for sensor networks[END_REF][START_REF] Ren | A survey of consensus problems in multi-agent coordination[END_REF]. However, there, the typical setting is that each agent invokes a separate Kalman filter to process its measurements, and then the resulted outputs are integrated using communication. Moreover, works in that domain often assume that observations are attained by static observers (i.e., the agents are residing on a fixed underlying graph) and that the measured target is external to the system. In contrast, here we consider a self-organizing system, with mobile agents that measure a target (average position) that is a function of their positions. Closer works to our setting where a group of mobile agents aim to gather together are [START_REF] Huang | Coordination and consensus of networked agents with noisy measurements: stochastic algorithms and asymptotic behavior[END_REF][START_REF] Tang | Continuous-time stochastic consensus: Stochastic approximation and kalmanbucy filtering based protocols[END_REF]. However, among the several differences with our paper, these papers assume that there is no drift and that agents communicate their absolute position, rather than their relative position.

Similarly to our findings, the authors of [START_REF] Korman | Confidence sharing: An economic strategy for efficient information flows in animal groups[END_REF] also emphasize the effectiveness of performing a weightedaverage between the opinion of the individual and the sample it receives. However, we find this result less surprising under their model, which features one-to-one communications and no drift.

Another related self-organization problem is clock synchronization, where the goal is to maintain a common notion of time in the absence of a global time source. The main difficulty is handling the fact that clocks count time at slightly different rates and that messages arrive with some delays. Variants of this problem were studied in wireless network contexts, mostly by control theoreticians [START_REF] Simeone | Distributed synchronization in wireless networks[END_REF][START_REF] Sivrikaya | Time synchronization in sensor networks: a survey[END_REF][START_REF] Sundararaman | Clock synchronization for wireless sensor networks: a survey[END_REF]. A common technique uses oscillating models [START_REF] Hong | A scalable synchronization protocol for large scale sensor networks and its applications[END_REF][START_REF] Mirollo | Synchronization of pulse-coupled biological oscillators[END_REF].

Warm-up proofs

The goal of this section is to prove Theorems 1 and 2. These theorems assume all agents execute a weightedaverage algorithm with the same responsiveness parameter ρ, that furthermore remains fixed throughout the execution (see Eq. ( 3)). The proofs of all intermediate results can be found in Appendix B. We start with the following observation.

Lemma 2. For any integer t, and whatever the positions of the agents, we have i∈I θ

(t) i = 0.
Next, we compute how the stretch θ (t) i of Agent i changes when all agents perform weighted-average moves with constant responsiveness parameter ρ. Lemma 3. Assume that all agents execute W(ρ), for some

0 ≤ ρ ≤ 1. Let E (t) j = ρN (t) m,j + N (t)
d,j . Then for every i ∈ I and every t ∈ N,

θ (t+1) i = 1 -n n-1 ρ θ (t) i + 1 n-1 j∈I\i E (t) j -E (t)
i .

Now we can prove that the stretch of each agent is normally distributed at every round, and compute its variance.

Lemma 4. Assume that all agents execute W(ρ), for some 0 ≤ ρ ≤ 1. Then, for every i ∈ I and every t ∈ N, the stretch θ

(t) i is normally distributed, E θ (t) i = 0, and Var θ (t+1) i = (1 -nρ n-1 ) 2 • Var θ (t) i + n(ρ 2 σ 2 m + σ 2 d ) n -1 .
Before proving Theorem 1, we need a small technical result. Proof. (of Theorem 1.) First, apply Lemma 4. Hence, by Claim 3, Var θ (t) i converges to the limit as stated. Note that the variance is infinite if either (1) the responsiveness is equal to 0, in which case the drift adds up endlessly, or (2) the responsiveness is equal to 1 and n = 2, in which case the agents "swap" at each round, producing the same result. This completes the proof of Theorem 1.

Proof. (of Theorem 2.) Consider the function

Var(ρ) = n n-1 (ρ 2 σ 2 m + σ 2 d ) 1 -(1 -n n-1 ρ) 2 = ρ 2 σ 2 m + σ 2 d 2ρ -n n-1 ρ 2 .
Note that this function evaluates to +∞ when ρ = 0, or when ρ = 1 and n = 2. Computing its derivative yields:

Var ′ (ρ) = 2ρσ 2 m 2ρ -n n-1 ρ 2 -(ρ 2 σ 2 m + σ 2 d ) 2 -2 n n-1 ρ 2ρ -n n-1 ρ 2 2 .
Hence, Var ′ (ρ) = 0 if and only if:

ρ 2 σ 2 m 2 -n n-1 ρ -(ρ 2 σ 2 m + σ 2 d ) 1 -n n-1 ρ = 0 ⇐⇒ ρ 2 σ 2 m -σ 2 d 1 -n n-1 ρ = 0.
This equation has a unique solution in the interval [0, 1], which is ρ =

σ d 4σ 2 m + n n-1 σ d 2 - n n-1 σ 2 d 2σ 2 m
. Checking that this is a minimum concludes the proof.

Solving the alignment problem

We denote N (µ, Σ) the multivariate normal distribution with mean vector µ ∈ R n and co-variance matrix Σ ∈ R n×n , and by I the identity matrix. Letting 1 be the matrix whose all coefficients are equal to 1, we denote M(a, b) = b1 + (ab)I, the matrix having diagonal coefficients equal to a, and other coefficients equal to b.

Rephrasing the alignment problem as a linear filtering problem

The goal of this section is to write Eqs. ( 1) and ( 2) in a matrical form. Let θ (t) , dθ (t) , Y (t) , N

m , and

N (t) d
denote the vectors (indexed by the set of agents) corresponding to each variable. (E.g., θ (t) = (θ

(t) 1 , . . . , θ (t)
n ), and similarly for the other vectors.)

Measurement rule Recall that, as stated in Eq. ( 1), the measurement of Agent i at time t is given by Y

(t) i = θ (t) i + N (t)
m,i . We simply rewrite this equation as:

Y (t) = θ (t) + N (t) m , (14)
where, by definition, N

m ∼ N 0, σ 2 m I .

Update rule

We recall the update equation of the stretch, which follows from Eq. (2) (see also Eq. ( 29)):

θ (t+1) i = θ (t) i -dθ (t) i -N (t) d,i + θ (t+1) -i -θ (t) -i = θ (t) i -dθ (t) i -N (t) d,i + 1 n-1 j∈I\i dθ (t) j + N (t) d,j . (15)
We define the matrix

M n = M -1, 1 n-1 . Let Ñ (t) d = M n N (t)
d . With these definitions and Eq. ( 15), we write Eq. (2) in the following vector notation:

θ (t+1) = θ (t) + M n dθ (t) + Ñ (t) d . (16)
By definition, N

d ∼ N 0, σ 2 d I , so by Claim 4, Ñ (t) d ∼ N (0, Q) where Q = σ 2 d • M n IM ⊤ n = σ 2 d M 2 n . (t)

Applying the Kalman filter

We use the Kalman filter as a tool for analysis purposes of the process. We stress, however, that the Kalman filter is not actually applied by any agent. We denote by θt the estimate of θ (t) produced by the Kalman filter after the measurements at round t were obtained (Eq. ( 14)) and before the update of round t occurs (Eq. ( 16)). Let P t denote the error co-variance matrix associated with this estimate. Specifically, P t = E (θ (t) -θt )(θ (t) -θt ) ⊤ . We add the superscript "-" to these notations (for example P - t ), to denote the same quantities before the measurement obtained at round t.

So, in a sense, round t can be divided into the following four consecutive time steps: (a) the filter produces an estimation θt of θ (t) , (b) a new measurement vector Y (t) of θ (t) is obtained, (c) the filter produces an estimation θt of θ (t) given the new measurement, and (d) θ (t) is updated to θ (t+1) . Recall that at round 0, i.e., at the initialization stage, the agents are normally distributed around 0. For technical reasons, we define the Kalman filter estimate at round 0 to be zero, that is, θ-0 = 0.

Measurement update

In order to produce (c), the filter incorporates the measurement in (b) to the estimation in (a). Specifically, the filter computes the "Kalman gain":

K t = P - t P - t + σ 2 m I -1 . (17)
Then, it produces the following estimate, as required in (c):

θt = θ- t + K t Y (t) -θ- t . (18)
The new error co-variance matrix can then be written as:

P t = (I -K t ) P - t . (19)
Time update The estimation for (a) for the following round is then given by:

θ- t+1 = θt + M n dθ (t) . (20)
Finally, the new error co-variance matrix that is used in the Kalman gain corresponding to round t + 1 (Eq. ( 17)) is:

P - t+1 = P t + σ 2 d • M 2 n . (21)

Optimality

Definition 7. A history H t is a realization of all measurements and all moves up to time (t -1).

The following is a well-known result, see e.g., [START_REF] Brian | Optimal filtering[END_REF].

Theorem 8. For every round t, every history H t and every vector

x ∈ R n , i∈I E (θ (t) i -θ- t,i ) 2 | H t ≤ i∈I E (θ (t) i -x i ) 2 | H t .
In particular, for every round t, every history H t , every i ≤ n and every scalar x ∈ R, E (θ

(t) i -θ- t,i ) 2 | H t ≤ E (θ (t) i -x) 2 | H t .
Definition 8. We say that an algorithm for the alignment problem is Kalman-perfect if it always produces a sequence of moves (dθ (t) ) t≥0 , such that for every integer t ≥ 1, θt = 0. The proof of the following result is provided in Appendix A. Proposition 1. If there exists a Kalman-perfect algorithm for the alignment problem, then this algorithm is optimal in the centralized setting (in the sense of Definition 2). Moreover, any other optimal (deterministic) algorithm is Kalman-perfect.

Kalman gain and the error co-variance matrix

Recall the sequences (α t ) t≥0 and (ρ (t) ⋆ ) t≥0 introduced in Definitions 4 and 5. This section is dedicated to proving the following lemma, which provides a formula for the error co-variance matrix associated with the estimate θt , as well as for the Kalman gain.

Lemma 5. For every integer t, P - t = M α t , -αt n-1 = -α t M n , and

K t = - n-1 n αtMn n n-1 σ 2 m +αt = -ρ (t) ⋆ M n .
Proof. We prove the first part of the claim by induction, and prove that for every round t, the second part of the claim (regarding K t ) follows from the first part (regarding P - t ). By Claim 4 (see Appendix C),

P - 0 = σ 2 0 M 2 n . By Claim 5 (see Appendix C), M 2 n = M n n-1 , -n (n-1) 2 = -n n-1 M n .
Therefore, P - 0 = -n n-1 σ 2 0 M n , and so the first part of the claim holds at round 0 since α 0 = n n-1 σ 2 0 . Now, let us assume that the first part of the claim holds for some t ∈ N. It follows that

P - t + σ 2 m I = M α t + σ 2 m , -αt n-1
. By Claim 6 (see Appendix C), since σ m > 0, we have

P - t + σ 2 m I -1 = M α t + σ 2 m -(n -2) • αt n-1 , αt n-1 α t + σ 2 m + αt n-1 α t + σ 2 m -(n -1) • αt n-1 = M αt n-1 + σ 2 m , αt n-1 σ 2 m n n-1 α t + σ 2 m .
By Claim 5 again, we can compute the "Kalman gain":

K t = P - t P - t + σ 2 m I -1 = 1 σ 2 m n n-1 α t + σ 2 m • M α 2 t n-1 + σ 2 m α t - (n-1)•α 2 t (n-1) 2 , -α 2 t (n-1) 2 - σ 2 m αt n-1 + α 2 t n-1 -(n -2) • α 2 t (n-1) 2 = M σ 2 m α t , -σ 2 m αt n-1 σ 2 m n n-1 α t + σ 2 m = -α t M n n n-1 α t + σ 2 m ,
This proves that the second part of the claim holds at round t. Next, we compute the error co-variance matrix after the measurement:

P t = (I -K t ) • P - t = M αt n-1 + σ 2 m , αt n-1 n n-1 α t + σ 2 m • P - t = 1 n n-1 α t + σ 2 m • M α 2 t n-1 + σ 2 m α t -(n -1) • α 2 t (n-1) 2 , - α 2 t (n-1) 2 - σ 2 m αt n-1 + α 2 t n-1 -(n -2) • α 2 t (n-1) 2 = M σ 2 m α t , -σ 2 m αt n-1 n n-1 α t + σ 2 m = - n-1 n σ 2 m α t α t + n-1 n σ 2 m M n .
Eventually, we compute the error co-variance matrix at round t + 1, before the measurement:

P - t+1 = P t + σ 2 d M 2 n = P t -n n-1 σ 2 d M n .
Plugging in the expression of P t , we get

P - t+1 = - n-1 n σ 2 m α t α t + n-1 n σ 2 m M n -n n-1 σ 2 d M n = - n-1 n σ 2 m α t n-1 n σ 2 m + α t + n n-1 σ 2 d M n = -α t+1 M n ,
which concludes the induction proof.

Meet-at-the-center

The goal of this section is to prove Theorem 3 stating that Algorithm Meet-at-the-center is optimal in the centralized setting (in the sense of Definition 2). The choice of the name comes from the fact that this algorithm minimizes the drift of the center of mass (see Theorem 6).

Proof. (of Theorem 3.) By Proposition 1, it is sufficient to prove that Algorithm Meet-at-the-center is Kalman-perfect, that is, that for every integer t ≥ 1, the Kalman filter associated with the moves it produces gives the estimate θt = 0. For this purpose, assume that all agents run Algorithm Meet-at-the-center. We prove by induction that for every integer t ≥ 0, the Kalman filter produces the estimate θt = 0. This holds at t = 0 since we assumed that the Kalman filter estimates 0 at round 0, i.e., θ-0 = 0. Next, let us assume that θt = 0 for some integer t ≥ 0. We have by definition, θ-

t+1 = θt + M n dθ (t) , (22)
and θt = θ-

t + K t Y (t) -θ- t = K t Y (t) , (23)
where the second equality in Eq. ( 23) is by the induction hypothesis. By Lemma 5,

K t = -ρ (t)
⋆ M n . Note that, by definition of Algorithm Meet-at-the-center,

dθ (t) = -n-1 n ρ (t) ⋆ M n Y (t) = n-1 n θt .
Finally, by the equations above, we rewrite Eq. ( 22) as:

θ- t+1 = I + n-1 n M n θt = I + n-1 n M n K t Y (t) = -M n + n-1 n M 2 n ρ (t) ⋆ Y (t) .
Since M 2 n = -n n-1 M n , we have θ-t+1 = 0. This concludes the induction, and completes the proof of the theorem.

Algorithm W ⋆ is optimal in the centralized setting

The goal of this section is to prove Theorem 4. The proof follows the same line of arguments as the proof of Theorem 3.

Proof. (of Theorem 4) Our goal is to prove that Algorithm W ⋆ is Kalman-perfect, that is, for every integer t ≥ 1, the Kalman filter associated with the moves produced by Algorithm W ⋆ gives the estimate θt = 0. This would conclude the proof of the theorem, by Proposition 1.

For this purpose, assume that all agents run Algorithm W ⋆ . We prove by induction that for every integer t ≥ 0, the Kalman filter produces the estimate θt = 0. The base case, where t = 0, holds since we assumed that the Kalman filter estimates zero at round zero, i.e., θ-0 = 0. Next, let us assume that θt = 0 for some integer t ≥ 0, and consider t + 1. We have by definition, θ-

t+1 = θt + M n dθ (t) , (24)
and θt = θ-

t + K t Y (t) -θ- t = K t Y (t) , (25)
where the second equality in Eq. ( 25) is by induction hypothesis. By Lemma 5,

K t = -ρ (t)
⋆ M n . Hence, Eq. ( 24) rewrites θ-

t+1 = M n -ρ (t)
⋆ Y (t) + dθ (t) .

Finally, by the definition of W ⋆ , we have

dθ (t) = ρ (t)
⋆ Y (t) , so θ-t+1 = 0, concluding the induction step.

Discussion and Future Work

We introduced the distributed alignment problem, aiming to study basic algorithmic aspects that govern approximate agreement processes in unreliable stochastic environments, while relying on measurements of the overall group tendency. We proposed a weighted-average algorithm, termed W ⋆ , and proved that it achieves optimal stretches, that is, it minimizes the expected distance of each agent from the center of mass of others, at each round. In fact, the optimality of W ⋆ holds also in the full-communication (or centralized) model, where communication of internal states is unrestricted. Algorithm W ⋆ is based on having a different responsiveness parameter that is applied by each agent at each round. We also find the optimal weightedaverage algorithm among the ones that use the same responsiveness at all times. In contrast to W ⋆ that minimizes the expected stretch at every round separately, this algorithm becomes optimal only at steadystate.

In our setting, the cost of an individual is defined as its expected distance from the average position of other agents. Minimizing this quantity is equivalent to minimizing the expected distance from the average position of all agents (see Footnote 2). Another interesting measure is the expected diameter of the group, defined as the maximal distance between any two agents, at steady state. It would not come as a surprise if Algorithm W ⋆ would turn out to be optimal also with respect to this measure, however, analyzing its expected diameter would require handling further dependencies between agents, and therefore remains for future work.

It would also be interesting to see how our work could be extended to scenarios in which each agent can observe a subset of randomly chosen agents at each round. As mentioned in the introduction, averaging the values of the agents in such a subset can serve as a noisy sample of average value in the population. However, in contrast to our model, the noise in this sample is not fixed, and depends on the distribution of values in the population and on the size of the sampled subset. In many cases, one can expect that sampling a subset containing a logarithmic number of agents could suffice to obtain a relatively good sample of the population. We find this encouraging towards generalizing our work to such scenarios.

A Proof of Proposition 1

Proposition 1 is a direct consequence of the following result. Lemma 6. Fix i ∈ I and an integer t ≥ 1, and consider a history H t such that the Kalman filter produces θt,i = 0 on H t . Let dϑ (t-1) be an alternative move for the agents at round (t -1), and consider history H ′ t obtained from H t by replacing dθ (t-1) by dϑ (t-1) . Then,

E θ (t) i 2 | H ′ t ≥ E θ (t) i 2 | H t .
Proof. Let c be the ith coordinate of the vector M n (dθ (t)dϑ (t) ). By Eq. ( 2), c is the difference between the position of Agent i in the beginning of round t if it moves by dθ (t) instead of moving by dϑ (t) (conditioning on having the same drift at the end of round t -1). In other words,

E θ (t) i 2 | H ′ t = E (θ (t) i -c) 2 | H t . (26)
By Theorem 8,

E (θ (t) i -c) 2 | H t ≥ E (θ (t) i -θt,i ) 2 | H t . (27)
By assumption, θt,i = 0, so

E (θ (t) i -θt,i ) 2 | H t = E θ (t) i 2 | H t . (28)
Combining Eqs. ( 26), ( 27) and ( 28) establishes the result.

B More Results on Weighted-Average Algorithms

Proof. (of Lemma 2.)

i∈I θ (t) i = i∈I θ (t) -i -θ (t) i = 1 n-1 i∈I j∈I\i θ (t) i - i∈I θ (t) i = 1 n-1 • (n -1) i∈I θ (t) i - i∈I θ (t) i = 0.
Proof. (of Lemma 3.) Agent i's stretch at round t + 1 is:

θ (t+1) i = θ (t+1) -i -θ (t+1) i = θ (t+1) -i -(θ (t) i + dθ (t) i + N (t) d,i ) = θ (t+1) -i -θ (t) -i + θ (t) -i -θ (t) i -dθ (t) i -N (t) d,i = θ (t+1) -i -θ (t) -i + θ (t) i -dθ (t) i -N (t) d,i , (29)
where the first equality is by definition, and the second equality is a consequence of (2). Let us break down the first term:

θ (t+1) -i -θ (t) -i = 1 n-1 j∈I\i dθ (t) j + N (t) d,j = 1 n-1 j∈I\i ρ θ (t) j + N (t) m,j + N (t) d,j ,
where the second equality is because dθ

(t) j = ρY (t) j = ρ θ (t) j + N (t) m,j . By Lemma 2, j∈I\i θ (t) j = -θ (t)
i , so we can rewrite the last equation as

θ (t+1) -i -θ (t) -i = -ρ n-1 θ (t) i + 1 n-1 j∈I\i ρN (t) m,j + N (t) d,j = -ρ n-1 θ (t) i + 1 n-1 j∈I\i E (t) j . (30)
Plugging Eq. ( 30) into Eq. ( 29) gives

θ (t+1) i = 1 -ρ n-1 θ (t) i + 1 n-1 j∈I\i E (t) j -dθ (t) i -N (t) d,i . (31)
By assumption, dθ

(t) i = ρY (t) i = ρ θ (t) i + N (t)
m,i . Plugging this expression into Eq. ( 31) gives the result.

Proof. (of Lemma 4.) We prove that the stretch is normally distributed with mean 0 by induction on t. By construction, for every i, θ (0) i is normally distributed with mean 0. Let us assume that θ (t) i is normally distributed with mean 0 for some round t, and consider round t + 1. Recall that Lemma 3 gives

θ (t+1) i = 1 -n n-1 ρ θ (t) i + 1 n-1 j∈I\i E (t) j -E (t) i . (32)
Since by definition, for every j, E (t) j is normally distributed around 0, and by induction θ D Additional claims about optimal algorithms D.1 All optimal algorithms are shifts of one another

In this section, we characterize all optimal (deterministic) algorithms for the alignment problem in the centralized setting. We show that each of these algorithms can be obtained from W ⋆ , by shifting all the agents by the same quantity λ t .

Theorem 9. A deterministic algorithm is optimal in the centralized setting if and only if for every round t, there exists λ t such that for every i ∈ I, dθ

(t) i = ρ (t) ⋆ Y (t) i + λ t .
Proof. We have already established that Algorithm W ⋆ is Kalman-perfect. Therefore, by Proposition 1, any other deterministic algorithm is optimal in the centralized setting if and only if it is Kalman-perfect. In other words, it is optimal if and only if it produces a sequence of moves such that for every round t, the Kalman-filter estimator operating on the corresponding process yields θ-t+1 = 0 ⇐⇒ θt + M n dθ (t) = 0 ⇐⇒ K t Y (t) + M n dθ (t) = 0 ⇐⇒ -ρ

(t) ⋆ M n Y (t) + M n dθ (t) = 0 ⇐⇒ M n -ρ (t) ⋆ Y (t) + dθ (t) = 0 ⇐⇒ -ρ (t)
⋆ Y (t) + dθ (t) ∈ ker(M n ).

Writing 1 to denote the vector whose coefficients are all equal to 1, we observe that 1 ∈ ker(M n ). Since rank(M n ) = n -1, dim(ker(M n )) = 1, so for every round t, ρ

(t) ⋆ Y (t) + dθ (t) ∈ ker(M n ) ⇐⇒ ∃λ t ∈ R, -ρ (t) ⋆ Y (t) + dθ (t) = λ t • 1 ⇐⇒ ∃λ t ∈ R, dθ (t) = λ t • 1 + ρ (t)
⋆ Y (t) .

D.2 Proof of Claim 2

Let A be an optimal algorithm. Again, we denote the variables involved in the execution of A by

MatC

, which is equal to λ t (the second term is 0 following the definition of Algorithm 1).

Therefore, ∆ rel By Eq. ( 13), we conclude that, among optimal algorithm, "meet at the center" is the only one minimizing ∆ t for every t. Note that it is not implementable in the distributed setting, because it requires for each agent to know all measurements. This concludes the proof of Claim 2.

Claim 3 .

 3 Let a, b ≥ 0. Consider the sequence {u n } ∞ n=0 defined by letting u 0 ∈ R and for every integer n, u n+1 = au n + b. If a < 1, then {u n } ∞ n=0 converges and lim n→+∞ u n = b/(1a). If a = 1, and b > 0, then lim n→+∞ u n = +∞.

Claim 5 .Claim 6 .

 56 distributed around 0. This concludes the induction. Noting that Var(E (t) j ) = ρ 2 σ 2 m + σ 2 d and taking the variance in Eq. (32) concludes the proof. Proof. (of Claim 3.) First, consider the case that a < 1. Let λ = b/(a -1). Consider the sequence defined by v n = u n + λ. We have v n+1 = u n+1 + λ = au n + b + λ = au n + (a -1)λ + λ = au n + aλ = a(u n + λ) = av n . Since |a| < 1, lim v n = 0, and so lim u n = -λ = b/(1a). Now, if a = 1, then we have for every n ∈ N, u n = u 0 + nb. If b > 0 then lim u n = +∞. C Useful linear algebra claims Claim 4. If X ∼ N (µ, Σ), then for every c ∈ R n and B ∈ R n×n , c + BX ∼ N c + Bµ, BΣB ⊤ .Claim 4 above is well-known, and Claim 5 below follows from a straightforward matrix multiplication. For every a, b, a′ , b ′ ∈ R, M(a, b)M(a ′ , b ′ ) = M(aa ′ + (n -1)bb ′ , ab ′ + a ′ b + (n -2)bb ′ ). For every a, b ∈ R such that a = b and a = -(n -1)b, the matrix M(a, b) is invertible, and M(a, b) -1 = M(a+(n-2)b,-b) (a-b)(a+(n-1)b) .Proof. Note that 1 2 = n1. Let A = M(a, b). We haveA 2 = (b1 + (ab)I) 2 = b 2 1 2 + 2b(ab)1 + (ab) 2 I = (nb + 2(ab))(b1) + (ab) 2 I = (2a + (n -2)b)(b1 + (ab)I) -(nb + 2(ab))(ab)I + (ab) 2 I = (2a + (n -2)b)A + (ab)((ab)nb -2(ab))I = (2a + (n-2)b)A -(ab)(a + (n -1)b)I. Hence A(A -(2a + (n -2)b)I) = -(ab)(a + (n -1)b)I, from which we conclude the proof of Claim 6.

  s . If A is different than Algorithm 1, we can define t 0 := min{t ∈ N, E λ 2 t > 0} < +∞, and have

  Definition 1 (Cost). The cost of Agent i at a given time t is the absolute value of its expected stretch at that time 2 , i.e., C

	(t) i := E θ	(t) i
	d ). All random perturbations (N	(t) m,i ) i∈I and (N	(t) d,i ) i∈I are mutually independent,
	and σ m , σ d > 0.

  [•] A . We have shown in Appendix D.1 that all optimal algorithms are shifts of one another, i.e., for all t we can find a random variable λ t s.t. for all i, dθ

			(t) i	A	= dθ	(t) i	MatC	+ λ t . It implies that 1 n	i∈I dθ	(t) i	A	=
	λ t + 1 n	i∈I dθ	(t) i

Depending on the application, the actual domain may be bounded, or periodic. For example, when modeling directions, the domain is [-π, π] and when modeling clock synchronization, the domain may be [0, T ] for some phase duration T . Since we are interested in the cases where agents are more or less aligned, approximating an interval domain with the real line is not expected to reduce the generality of our results.

Acknowledgment The authors thank Yongcan Cao for a helpful discussion regarding related works on distributed Kalman filter, as well as anonymous reviewers whose critical comments helped improve the presentation of the paper significantly.

† This work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No 648032).