Models and Algorithms for Crowds and Networks (16w5140)

Arriving in Oaxaca, Mexico Sunday, August 28 and departing Friday September 2, 2016


(University of Washington)

(École Polytechnique Fédérale de Lausanne)

(Harvard University)

(New York University)


By bringing together researchers from different yet synergistic fields we hope to share and improve state-of-the-art techniques, models and algorithms for networks both generally and motivated by crowdsourcing as an application area. Moreover, we hope to define the vision for the future by identifying the key problems and potential bottlenecks to overcome over the next few years.


Foundations: Network Models \& Algorithmic Game Theory

In order to reason about networks} (social, economic, biological, or technological), the complexity and scale are often prohibitively large. Abstracting the details away into a \emph{model} which still captures the salient aspects of the particular application is key. Network models have a long and rich history; originating with Erd\H os-R\'enyi, models have since evolved to capture salient aspects observed in reality. For example, preferential attachment graphs arose as a random graph model which has a power-law degree distribution as observed in the internet graph. While classic network models have homogeneous nodes, many new application areas require us to think about connectivity properties between different \emph{types of nodes; a network may, for example, combine crowd workers (humans) and artificial intelligence (computers) which aggregate their work. The connectivity properties within a type versus between types may not be the same. Filling this gap requires a three-pronged effort: \begin{description}
  • Identify nuanced properties of networks or sub-networks, such as degree distributions, clustering, betweenness, transitivity, and local dependence.
  • Develop generative models that capture these properties.
  • Test and verify hypothesis such as network robustness or rates of contagion on such models.
  • \end{description} Such an endeavour will require expertise from Social and Data Science, Statistics, Mathematics, and Computer Science.

    While networks form the underlying structure, in many settings the properties of a network also depend on the behavior of its individual components. For example, consider a network of roads where individuals choose which routes to take; both the topology and the individual choices affect congestion. Game theory} formulates models of rational behavior in environments where agents' decisions affect each other's outcomes in this manner. While traditional game theory considers a set of individuals who all interact with each other, recent work has focused on networked settings where interactions are local but effects are global. \emph{Algorithmic} game theory takes this a step further to ask in which ways can we design the rules of interaction, or change the properties of the underlying network, in order to achieve a more desirable outcome. The goal is to design systems in a way such that the \emph{selfish individual actions} result in \emph{global good. Applications which comprise of multiple parties with (often opposing) goals interacting across network topologies require a synthesis of network models with (algorithmic) game theory in novel ways.

    Application: Crowdsourcing \& Networks

    Crowdsourcing is a form of outsourcing where the job or task in question is posed to a large, often anonymous, crowd over the internet. Its popularity has arisen largely due to its ability to solve complex problems which require human intelligence; i.e., unstructured abstract questions which machine intelligence cannot (yet) tackle. However, while human intelligence is necessary, it must also be harnessed effectively:
    • The task description, input/output requirements, decomposition, or aggregation need to be designed well (Human-Computer Interaction).
    • One must first learn about the performance of the crowd under different conditions in order to use it efficiently (Machine Learning, AI and Statistics).
    • Fair payment methods and incentivizing worker performance is important in order to ensure accuracy or timeliness (Economics, Algorithmic Game Theory, Operations Research).
    Thus, a variety of skills are required to design effective crowdsourcing systems.

    More recently, the network properties of the underlying crowd and of the overall system have become increasingly relevant. For example, crowdsourcing is moving from its early individualistic model where a single worker or known group is given a task (big or small) to larger more collaborative environments which require workers to engage with each other on multiple levels. As tasks (e.g., forming emergency response teams) can be physical, the network properties, both in the virtual and physical world, play key roles. Since many tasks require privacy guarantees due to sensitive company information, ensuring no privacy violations relies crucially on having the correct network model of the worker base. Moreover, the components of a crowdsourcing system form a heterogeneous network (where a node may be a worker, a requester, a platform, an AI component, an advertiser, or an intermediary), requiring new network models as discussed above.

    Hence, a synthesis of algorithmic game theory and new networks models, along with insights from a variety of data-driven areas such as machine learning, statistics and artificial intelligence, are required to fully understand crowdsourcing and develop efficient crowdsourcing systems.


    In the last decades there has been a dramatic increase in connectivity among individuals and technology. However, a gap remains between emergent real-world networks and the knowledge we have built up. Heterogeneity in networks, especially when nodes act as selfish agents, have not been studied to a wide extent. Application areas such as crowdsourcing require a renewed look in this context. A meeting which brings together experts from areas such as computer science, economics, mathematics, information science and sociology who are keenly poised to tackle these problems could not be more timely. While there have been an increasing number of productive meetings on related topics, they have been structured for participants from only one or two communities.\footnote{e.g., EC Workshop on Social Computing and User Generated Content (2014, theoretical computer science and economics), NetSci (yearly since 2010, biology, sociology, ecology), Workshop on Complex Networks and their Applications (2007, mathematics and theoretical computer science), Foundations in Network Design Conference (yearly since 2007, computer science), Human Computation Workshop (yearly conference as of 2013, human-computer interaction, economics).} Given the high level of interest in the subject, a united effort and exchange between all communities would be extremely useful in setting a strong course for the future.


    Our proposed schedule would combine broad talks from experts in different areas along with talks on recent results. Since a primary objective of this workshop is to generate new collaboration across disciplines, we will allow for plenty of time in the schedule for informal discussions.


    The participant pool will contain an even mix of leaders/experts, junior researchers/faculty and outstanding post-docs/students aiming to work in this area. We will also try to ensure ample participation by female scientists both at the senior and junior level. Two of our co-organizers are female, and our participant list is more than 40\