SEARCHING FOR SOMEONE
From the “Small World Experiment” to the “Red Balloon Challenge,” and beyond
Our ability to search social networks for people and information is fundamental to our success. We use our personal connections to look for new job opportunities, to seek advice about what products to buy, to match with romantic partners, to find a good physician, to identify business partners, and so on.
Despite living in a world populated by seven billion people, we are able to navigate our contacts efficiently, only needing a handful of personal introductions before finding the answer to our question, or the person we are seeking. How does this come to be? In folk culture, the answer to this question is that we live in a “small world.” The catch-phrase was coined in 1929 by the visionary author Frigyes Karinthy in his Chain-Links essay, where these ideas are put forward for the first time.
Let me put it this way: Planet Earth has never been as tiny as it is now. It shrunk — relatively speaking of course — due to the quickening pulse of both physical and verbal communication. We never talked about the fact that anyone on Earth, at my or anyone’s will, can now learn in just a few minutes what I think or do, and what I want or what I would like to do. Now we live in fairyland. The only slightly disappointing thing about this land is that it is smaller than the real world has ever been. — Frigyes Karinthy, Chain-Links, 1929
Then, it was just a dystopian idea reflecting the anxiety of living in an increasingly more connected world. But there was no empirical evidence that this was actually the case, and it took almost 30 years to find any.
Six Degrees of Separation
In 1967, legendary psychologist Stanley Milgram conducted a ground-breaking experiment to test this “small world” hypothesis. He started with random individuals in the U.S. midwest, and asked them to send packages to people in Boston, Massachusetts, whose address was not given. They must contribute to this “search” only by sending the package to individuals known on a first-name basis. Milgram expected that successful searches (if any!) would require hundreds of individuals along the chain from the initial sender to the final recipient.
Surprisingly, however, Milgram found that the average path length was somewhere between five point five and six individuals, which made social search look astonishingly efficient. Although the experiment raised some methodological criticisms, its findings were profound. However, what it did not answer is why social networks have such short paths in the first place. The answer was not obvious. In fact, there were reasons to suspect that short paths were just a myth: social networks are very cliquish. Your friends’ friends are likely to also be your friends, and thus most social paths are short and circular. This “cliquishness” suggests that our search through the social network can easily get “trapped” within our close social community, making social search highly inefficient.
Architectures for Social Search
Again, it took a long time — more than 40 years — before this riddle was solved. In a 1998 seminal paper in Nature, Duncan Watts & Steven Strogatz came up with an elegant mathematical model to explain the existence of these short paths. They started from a social network that is very cliquish, i.e., most of your friends are also friends of one another. In this model, the world is “large” since the social distance among individuals is very long. However, if we take only a tiny fraction of these connections (say one out of every hundred links), and rewire them to random individuals in the network, that same world suddenly becomes “small.” These random connections allow individuals to jump to faraway communities very quickly — using them as social network highways — thus reducing average path length in a dramatic fashion.
While this theoretical insight suggests that social networks are searchable due to the existence of short paths, it does not yet say much about the “procedure” that people use to find these paths. There is no reason, a priori, that we should know how to find these short chains, especially since there are many chains, and no individuals have knowledge of the network structure beyond their immediate communities. People do not know how the friends of their friends are connected among themselves, and therefore it is not obvious that they would have a good way of navigating their social network while searching.
Soon after Watts and Strogatz came up with this model at Cornell University, a computer scientist across campus, Jon Kleinberg, set out to investigate whether such “small world” networks are searchable. In a landmark Nature article, “Navigation in a Small World,” published in 200o, he showed that social search is easy without global knowledge of the network, but only for a very specific value of the probability of long-range connectivity (i.e., the probability that we know somebody far removed from us, socially, in the social network). With the advent of a publicly available social media dataset such as LiveJournal, David Liben-Nowell and colleagues showed that real-world social networks do indeed have these particular long-range ties. It appears the social architecture of the world we inhabit is remarkably fine-tuned for searchability.
Network Incentives
Circa 2005, scientists had established that the world is indeed small, that it became small thanks to a tiny number of random connections, and that people can collectively find such connections with ease. Efficient Network search was possible. The remaining question at the time was: why would people participate in such search tasks? What would motivate an individual to help another by passing the baton to another person?
Indeed, when Duncan Watts, then at Columbia University, set out to replicate Milgram’s experiment in the Internet age — i.e., using email instead of snail mail — he found that most recruitment chains died out. At some point during the search, individuals would not pass the search token to anybody else. This happened despite the cost being minuscule: all it takes is a single click to forward the email! Watts found that financial incentives were the instrument missing: insufficient incentives resulted in a very large drop-out rate from the search experiments. If we are to truly harness the power of our small world network, we need to provide the right incentives. This was indeed a network-level, game theoretic problem: how do you persuade individuals to convince other individuals, and so on, to help search and to do so efficiently?
It turns out the question is quite difficult to answer. Jon Kleinberg, again, this time with long-term collaborator Prabhakar Raghavan found a solution for it: a sophisticated technique, “Query Incentive Networks,” which provided a powerful way of exchanging favors in a social networks. Individuals interested in recruiting other individuals for an ongoing social search would set the terms of the “favor exchange” for their recruited friends: “If you help me with the search, I give you X.” This is how networks usually work: they do so by the fact that people expect some sort of payoff when helping out. Query Incentive Networks compute a value for X that keeps the recruitment chain growing until the elusive information or individual is found by the network.
The problem with these incentives is that, for them to promote efficient search, everyone needs to persuade more than two individuals to enlist in the search. Unfortunately, it is well known that network recruitment has a “reproductive number” (the average number of people an individual can recruit) smaller than two . In fact, this number is often close to one. Thus, in the real world, these contracts rarely suffice to find what the crowd is looking for. Realistic reproductive numbers make individuals greedy and their offers not generous enough, causing social search to falter. It seems that we need to overcome an additional hurdle: until we have the right way to structure financial incentives for search, search will be too inefficient.
Crowdsourcing Annus Mirabilis
As in many other situations in life, it takes humans to be under pressure to innovate and solve problems otherwise thought unsolvable. And nothing put so much pressure on “social search” scientists than the now-famous DARPA Network Challenge. A $40,000 challenge award would be granted to the first team to submit the locations of 10 moored, eight-foot, red weather balloons at 10 previously undisclosed fixed locations in the continental United States. The balloons were to be placed in readily accessible locations visible from nearby roads. The balloons were deployed at 10:00 AM Eastern Time on December 5, 2009 and scheduled to be taken down at 5:00 PM. DARPA selected the date of the competition to commemorate the 40th anniversary of the Internet. Around 8,000 teams around the world competed in this quest.
Our team at the MIT Media Lab designed a modification of Query Incentive Networks, where the offers were upside down. Instead of the recruiter making an offer to the recruit, it would be the other way around: the recruit would offer a split of the reward back to the recruiter, upon the information being found — the anti-pyramid scheme. We called these offers “split-contracts.” This modification provided a massive advantage to our team over our competitors, landing us the prize, and capturing worldwide attention, including Stephen Colbert’s.
It took us, however, three more years to figure out why these split-contracts provided a competitive advantage over Query Incentive Networks. But after quite a few theorems, we got it: split-contracts allowed Query Incentive Networks to work for branching factors below two — people did not need to recruit at least two friends anymore — which made these incentives usable in the real world. With this, the “split-contracts” became a powerful tool for time-critical social mobilization.
These contracts were quite effective and they were used frequently around the early 2010s. For instance, we used it again to win the Tag Challenge, a transcontinental version of the DARPA Network Challenge, where five simulated jewel thieves where hiding in five different European and North American cities. Participants were able to recruit others in a targeted manner, leading to remarkable convergence towards the target cities. Similarly, they proved to be effective in hybrid versions of social search, such as the Langley Castle Challenge, where some individuals of interest to be found were hiding in the physical world, and others had only a cybernetic presence online. By then, it seemed that social search was pretty much figured out. This collective way of solving problems was even featured on an IBM commercial, as split-contracts have become a part of folk culture.
The Monster at the End of the Crowdsourcing Dream
Just when the split-contracts seemed like the ultimate social search and crowdsourcing strategy, we took a brutal defeat in the DARPA Shredder Challenge, arguably the most difficult task ever posed to time-critical social mobilization. Participants in this challenge had to recruit thousands of people to assemble five puzzles of extreme difficulty, totalling around 10,000 pieces. Every puzzle was a shredded document that had to be reconstructed, with an increasing level of sophistication for the shredding, oiling, and blurring of the pieces.
We used split-contracts again to recruit over 3,500 participants from all over the world to work on the puzzles around the clock — via an online virtual assembly board. However, upon completion of the first three puzzles, we were subjected to a series of sabotage attacks that shattered, scrambled, and completely disrupted the puzzles the participants were working on. Eventually, these attacks not only halted collective progress, but resulted in an exodus of our discouraged crowd workers, deeply frightened about the idea of future attacks.
There was very little that our team, or the crowd itself, could do to avert these attacks. We were victims of the very strength of crowdsourcing: its openness to participation. Split-contracts, and crowdsourcing in general, were designed to be open to massive influxes of participants coming in, recruiting others, etc: the more the merrier. Unfortunately, sabotage, misinformation, and evildoing were far from the minds of scientists working on ways to increase the productivity of crowdsourcing. At the time, this was also true for Wikipedia, which was also being plagued by vandalism. It seemed that evil was definitely present across our recruitment trees, lurking in the nameless crowd.
The Tragedy of the Crowdsourcers
Some recent efforts have been made to try and disincentivize sabotage. If verification is also rewarded along the recruitment tree, then the individuals who recruited the saboteurs would have a clear incentive to verify, halt, and punish the saboteurs. This theoretical solution is yet to be tested in practice, and it is conjectured that a coalition of saboteurs, where saboteurs recruit other saboteurs pretending to “vet” them, would make recursive verification futile.
If we are to believe in theory, theory does not shed a promising light on reducing sabotage in social search. We recently proposed the “Crowdsourcing Dilemma.” In it, we perform a game-theoretic analysis of the fundamental tradeoff between the potential for increased productivity of social search and the possibility of being set back by malicious behavior, including misinformation. Our results show that, in competitive scenarios, such as those with multiple social searches competing for the same information, malicious behavior is the norm, not an anomaly — a result contrary to conventional wisdom. Even worse: counterintuitively, making sabotage more costly does not deter saboteurs, but leads all the competing teams to a less desirable outcome, with more aggression, and less efficient collective search for talent.
These empirical and theoretical findings have cautionary implications for the future of social search, and crowdsourcing in general. Social search is surprisingly efficient, cheap, easy to implement, and functional across multiple applications. But there are also surprises in the amount of evildoing that the social searchers will stumble upon while recruiting. As we get deeper and deeper into the recruitment tree, we stumble upon that evil force lurking in the dark side of the network.
Evil mutates and regenerates in the crowd in new forms impossible to anticipate by the designers or participants themselves. Crowdsourcing and its enemies will always be engaged in an co-evolutionary arms race.
Talent is there to be searched and recruited. But so are evil and malice. Ultimately, crowdsourcing experts need to figure out how to recruit more of the former, while deterring more of the later. We might be living on a small world, but the cost and fragility of navigating it could harm any potential strategy to leverage the power of social networks.
Search and the City
The way we search for people gives away a lot of information about us. Another legendary scientist, Mark Granovetter, famously hypothesized (and notoriously got rejected for publication upon submission) that the more social ties you have, the more access you have to find opportunities and increase your socioeconomic standing. However, not only does the number of ties matter, the degree to which you balance your social search efforts equally among them also matters. By comparing this diversity in communications with measures of poverty, scientists have confirmed this relationship. In other words, people who can more readily access knowledge, information, and opportunities for jobs from diverse communities within the population are able to leverage this privileged position in their social networks and convert that advantage into material wealth.
Most of these searches happen in cities, arguably the largest human-built megastructures. This may also be why cities seem fine-tuned for social search: we migrate to them to be able to find like-minded people in a more efficient fashion. Earlier experimental results by Watts et al. suggested that searching for a person becomes easier once the search is happening within the city limits. To put it differently, the fact that cities make the world small is precisely why people move to cities.
In fact, Marta Gonzalez’s laboratory at MIT uncovered that urban networks consist of highly homophilious communities, i.e., “birds of a feather flock together.” This structure explains why people are able to successfully route in experiments like Milgram’s, Watts’, or the Tag Challenge, relying heavily on correctly identifying the community of the target. Gonzalez and colleagues regard these results as suggesting that among many possible network configurations, humans have favored networks where a message can reach anyone even if delivered using knowledge about which community the individual belongs to. This is a remarkable example of a self-organized structure that allows a small group of individuals to solve a complex problem by cooperating to take advantage of collective knowledge.
We might think that humans are the only species to have evolved to display incredible ingenuity in engineering complex macroscopic social networks with these characteristics. However, work by Iain Couzin’s and Gene Stanley’s laboratories shows that many species are as well versed in searching as humans are. Studying multiple species, ranging from insects to fish, they found that the best foraging strategy (e.g., search for food or shelter) combines not only small-scale exploitation of resources (which will eventually become depleted, leaving the hypothetical forager dangerously dependent on a single site) but also occasionally “jumps” a-la Grannoveter to explore new pastures. This ability to access random parts of the foraging space echoes the random rewiring of human small-world networks modeled by Watts and Strogatz in their seminal paper, hinting at the fact that search is a fundamental feature that is universal across nature.
Small New World
It may seem that even when searches for people or physical things are not occurring directly, social networks are constantly abuzz with small-scale searches generating social capital, or reconfiguring themselves to increase searchability. The ability to efficiently traverse networks is important and has real consequences, even at a macroeconomic perspective, and in the case of species, for collective survival.
This pervasiveness of constant search and reach, has, however, worried some. Fridges Karynthy himself was troubled by living in a world that was becoming way too searchable, way too connected:
Well, just like this gentleman, who stepped up to my table in the café where I am now writing. He walked up to me and interrupted my thoughts with some trifling, insignificant problem and made me forget what I was going to say. Why did he come here and disturb me? The first link: he doesn’t think much of people he finds scribbling. The second link: this world doesn’t value scribbling nearly as much as it used to just a quarter of a century ago. The famous worldviews and thoughts that marked the end of the 19th century are to no avail today. Now we disdain the intellect.
As Karinthy points out, the perfected ability to search has a dramatic impact on those being searched, eating away their attention. The world is looking for answers, and if they know we have them, how to get to us, and what to offer to us in return, they will keep coming to us for more, depleting our energy and attention.
Karinthy was thus not too far off when he pointed out that the world seemed to be getting smaller. In fact, modeling observations about the spread of disease, Seth Marvel et al. argue that the small-world effect is a relatively recent phenomenon, arising only in the last few hundred years: for most of mankind’s tenure on Earth, the social world was large, with most pairs of individuals connected by relatively long chains of acquaintances, if at all.
A morbid early example of how difficult it was to search until quite recently is the ill-fated Arctic explorers of the Jeanette, which left San Francisco in 1879 on a journey to the North Pole. Undertaking this journey at this time would be treacherous enough, with a high risk that they would not return. They wished to prove true the astonishing theory of German cartographer August Petermann that the North Pole contained warm water that could easily be traversed.
In the 1880s, without long-distance communication, the crew’s families would not expect to hear from them for years on end. If the crew perished, the families may never receive confirmation. So the families adopted a remarkable strategy; not knowing the ship’s whereabouts, they would pen letters which they passed to whaling ships and skiffs departing San Francisco to Alaska, Greenland, or Norway. The only instructions were to take the letters closer to their intended recipients based on their own information; whether that was rumors of landings at previous remote ports, or guesses based on the proposed routes and subsequent climactic shifts.
Alas, all but three members of the Jeanette’s crew perished before any of these missives reached them. However, in 1909 two American explorers, Peary and Henson, found in a remote hut in Greenland one of Emma de Long’s “letters to nowhere” addressed to her husband. Sadly any record of the remarkable routing of this letter over the previous 20 years remains a mystery.
Dreams of Vanishing
Is social search a problem that we should aim to solve? Moreover, is it an irreversible trend? Some groups of people, ranging from isolated groups of survivalists to centrally planned communist societies, have decided to have a simplified social setup. In these rather homogeneous environments, everyone is within reach as everyone knows what everyone is up to. The adoption of these social setups seems, however, limited at best.
In “How to Disappear,” “How to Disappear Completely and Never Be Found,” and “How to be Invisible,” the authors offer a guide for anyone who’s ever entertained the fantasy of disappearing — whether actually dropping out of sight or by eliminating the traceable evidence of their existence. Whereas the efficacy of the discussed techniques remains to be evaluated, there is no doubt that this is an underlying modern societal desire.
These days, we dream of vanishing as much as we do about finding somebody important for us.
But why? Perhaps we have all decided to live in a world where we cannot actually be perfectly searched, where we can hide and reinvent ourselves, try different personas, to create, to escape other people’s vigilance; ultimately running search interference from the rest of the world. In some ways, the reign of Facebook has come at a high price: the annihilation of the ‘avatar’ (unless one can see that there’s a parallel universe where an avatar is the only way to be: the darknet.)
Being searchable is a way of being closely connected to everyone else, which is conducive to contagion, group-think, and, most crucially, makes it hard for individuals to differentiate from each other. Evolutionarily, for better or worse, our brain makes us mimic others, and whether this copying of others ends up being part of the Wisdom of the Crowds, or the “stupidity of many,” it is highly sensitive to the scenario at hand.
Katabasis, or the myth of the hero that descends to the underworld and comes back stronger, is as old as time and pervasive across ancient cultures. Creative people seem to need to “get lost.” Grigori Perelman, Shinichi Mochizuki, and Bob Dylan all disappeared for a few years to reemerge later as more creative versions of themselves. Others like J. D. Salinger and Bobby Fisher also vanished, and never came back to the public sphere. If others cannot search and find us, we gain some slack, some room to escape from what we are known for by others. Searching for our true creative selves may rest on the difficulty of others finding us.
Special thanks to feedback from Iyad Rahwan, Victoriano Izquierdo, Alex Rutherford, Esteban Moro and Alex (Sandy) Pentland. Illustrated by Beatriz Travieso. Sponsored by the Data61 Unit at CSIRO.
