"Crowd algorithms often assume workers are inexperienced and thus fail to adapt as workers in the crowd learn a task. These assumptions fundamentally limit the types of tasks that systems based on such algorithms can handle. This paper explores how the crowd learns and remembers over time in the context of human computation, and how more realistic assumptions of worker experience may be used when designing new systems. We first demonstrate that the crowd can recall information over time and discuss possible implications of crowd memory in the design of crowd algorithms. We then explore crowd learning during a continuous control task. Recent systems are able to disguise dynamic groups of workers as crowd agents to support continuous tasks, but have not yet considered how such agents are able to learn over time. We show, using a real-time gaming setting, that crowd agents can learn over time, and `remember' by passing strategies from one generation of workers to the next, despite high turnover rates in the workers comprising them. We conclude with a discussion of future research directions for crowd memory and learning."

"This paper gives an introduction to the problem of mapping simple polygons with autonomous agents. We focus on minimalistic agents that move from vertex to vertex along straight lines inside a polygon, using their sensors to gather local observations at each vertex. Our attention revolves around the question whether a given configuration of sensors and movement capabilities of the agents allows them to capture enough data in order to draw conclusions regarding the global layout of the polygon. In particular, we study the problem of reconstructing the visibility graph of a simple polygon by an agent moving either inside or on the boundary of the polygon. Our aim is to provide insight about the algorithmic challenges faced by an agent trying to map a polygon. We present an overview of techniques for solving this problem with agents that are equipped with simple sensorial capabilities. We illustrate these techniques on examples with sensors that mea- sure angles between lines of sight or identify the previous location. We give an overview over related problems in combinatorial geometry as well as graph exploration."

"In this paper, we study the consensus problem of multiple agents on a kind of famous graph, Peterson graph. It is an undirected graph with 10 vertices and 15 edges. Each agent randomly walks on this graph and communicates with each other if and only if they coincide on a node at the same time. We conduct numerical study on the consensus problem in this framework and show that global consensus can be achieved."

"We introduce the concept of attainable sets of payoffs in two-player repeated games with vector payoffs. A set of payoff vectors is called {em attainable} if player 1 can ensure that there is a finite horizon $T$ such that after time $T$ the distance between the set and the cumulative payoff is arbitrarily small, regardless of what strategy player 2 is using. This paper focuses on the case where the attainable set consists of one payoff vector. In this case the vector is called an attainable vector. We study properties of the set of attainable vectors, and characterize when a specific vector is attainable and when every vector is attainable."

"This paper develops generalizations of empowerment to continuous states. Empowerment is a recently introduced information-theoretic quantity motivated by hypotheses about the efficiency of the sensorimotor loop in biological organisms, but also from considerations stemming from curiosity-driven learning. Empowemerment measures, for agent-environment systems with stochastic transitions, how much influence an agent has on its environment, but only that influence that can be sensed by the agent sensors. It is an information-theoretic generalization of joint controllability (influence on environment) and observability (measurement by sensors) of the environment by the agent, both controllability and observability being usually defined in control theory as the dimensionality of the control/observation spaces.…"

"In evaluating prediction markets (and other crowd-prediction mechanisms), investigators have repeatedly observed a so-called "wisdom of crowds" effect, which roughly says that the average of participants performs much better than the average participant. The market price---an average or at least aggregate of traders' beliefs---offers a better estimate than most any individual trader's opinion. In this paper, we ask a stronger question: how does the market price compare to the best trader's belief, not just the average trader. We measure the market's worst-case log regret, a notion common in machine learning theory. To arrive at a meaningful answer, we need to assume something about how traders behave. We suppose that every trader optimizes according to the Kelly criteria, a strategy that provably maximizes the compound growth of wealth over an (infinite) sequence of market interactions. We show several consequences.…"

"In this paper we define what we call an affinity system, which is a set of individuals, each with a vector characterizing its preference for all other individuals in the set. The preference of a member can be given either by a ranking of all members or by a weighted vector that defines the degrees of its affinity to others. Affinity systems are useful for modeling social systems as well as general data sets, as social interactions are often determined by affinities among the members. We also define a natural notion of (potentially overlapping) communities in an affinity system, in which the members of a given community collectively prefer each other to anyone else outside the community. Thus these communities are "self-determined" or "self-certified" by the affinity system. We provide a tight polynomial bound on the number of self-determined communities as a function of the robustness of the community. Moreover, we present a polynomial-time algorithm for enumerating these communities, as well as a local algorithm with a strong stochastic performance guarantee that can find a community in time nearly linear in the of size the community.…"

"We introduce the optimal obstacle placement with disambiguations problem wherein the goal is to place true obstacles in an environment cluttered with false obstacles so as to maximize the total traversal length of a navigating agent (NAVA). Prior to the traversal, NAVA is given location information and probabilistic estimates of each disk-shaped hindrance (hereinafter referred to as disk) being a true obstacle. The NAVA can disambiguate a disk's status only when situated on its boundary. There exists an obstacle placing agent (OPA) that locates obstacles prior to NAVA's traversal. The goal of OPA is to place true obstacles in between the clutter in such a way that NAVA's traversal length is maximized in a game-theoretic sense.…"

"In a recent paper, we analyzed the self-assembly of a complex cooperation network. The network was shown to approach a state, where every agent invests the same amount of resources. Nevertheless, highly-connected agents arise that extract extra-ordinarily high payoffs while contributing comparably little to any of their cooperations. Here, we investigate a variant of the model, in which highly-connected agents have access to additional resources. We study analytically and numerically whether these resources are invested in existing collaborations, leading to a fairer load distribution, or in establishing new collaborations, leading to an even less fair distribution of loads and payoffs."

A community of agents is subject to a stream of messages, which are represented as points on a plane of issues. Messages are sent by media and by agents themselves. Messages from media shape the public opinion. They are unbiased, i.e. positive and negative opinions on a given issue appear with equal frequencies. In our previous work, the only criterion to receive a message by an agent is if the distance between this message and the ones received earlier does not exceed the given value of the tolerance parameter. Here we introduce a possibility to address a message to a given neighbour. We show that this option reduces the unanimity effect, what improves the collective performance.

We propose a nonlinear voter model to study the emergence of global consensus in opinion dynamics. In our model, agent $i$ agrees with one of binary opinions with the probability that is a power function of the number of agents holding this opinion among agent $i$ and its nearest neighbors, where an adjustable parameter $alpha$ controls the effect of herd behavior on consensus. We find that there exists an optimal value of $alpha$ leading to the fastest consensus for lattices, random graphs, small-world networks and scale-free networks. Qualitative insights are obtained by examining the spatiotemporal evolution of the opinion clusters.

This article analyses a game where players sequentially choose either to become insiders and pick one of finitely many locations or to remain outsiders. They will only become insiders if a minimum distance to the next player can be assured; their secondary objective is to maximize the minimal distance to other players. This is illustrated by considering the strategic behavior of men choosing from a set of urinals in a public lavatory. However, besides very similar situations (e.g. settling of residents in a newly developed area, the selection of food patches by foraging animals, choosing seats in waiting rooms or lines in a swimming pool), the game might also relevant to the problem of placing billboards attempting to catch the attention of passers-by or similar economic situations. In the non-cooperative equilibrium, all insiders behave as if they cooperated with each other and minimized the total number of insiders. It is shown that strategic behavior leads to an equilibrium with substantial under utilization of available locations. Increasing the number of locations tends to decrease utilization. The removal of some locations which leads to gaps can not only increase relative utilization but even absolute maximum capacity.

"We propose distributed algorithms to automatically deploy a team of mobile robots to partition and provide coverage of a non-convex environment. To handle arbitrary non-convex environments, we represent them as graphs. Our partitioning and coverage algorithm requires only short-range, unreliable pairwise "gossip" communication. The algorithm has two components: (1) a motion protocol to ensure that neighboring robots communicate at least sporadically, and (2) a pairwise partitioning rule to update territory ownership when two robots communicate. By studying an appropriate dynamical system on the space of partitions of the graph vertices, we prove that territory ownership converges to a pairwise-optimal partition in finite time. This new equilibrium set represents improved performance over common Lloyd-type algorithms. Additionally, we detail how our algorithm scales well for large teams in large environments and how the computation can run in anytime with limited resources. Finally, we report on large-scale simulations in complex environments and hardware experiments using the Player/Stage robot control system."

"This work is devoted to communication approaches, which spread information in robot swarms. These mechanisms are useful for large-scale systems and also for such cases when a limited communication equipment does not allow routing of information packages. We focus on two approaches such as virtual fields and epidemic algorithms, discuss several aspects of hardware implementation and demonstrate experiments performed with microrobots "Jasmine"."

"We have developed a Nagel-Schreckenberg cellular automata model for describing of vehicular traffic flow at a single intersection. A set of traffic lights operating in fixed-time scheme controls the traffic flow. Open boundary condition is applied to the streets each of which conduct a uni-directional flow. Streets are single-lane and cars can turn upon reaching to the intersection with prescribed probabilities. Extensive Monte Carlo simulations are carried out to find the model flow characteristics. In particular, we investigate the flows dependence on the signalisation parameters, turning probabilities and input rates. It is shown that for each set of parameters, there exist a plateau region inside which the total outflow from the intersection remains almost constant. We also compute total waiting time of vehicles per cycle behind red lights for various control parameters."

"We consider the problem of locating a black hole in synchronous anonymous networks using finite state agents. A black hole is a harmful node in the network that destroys any agent visiting that node without leaving any trace. The objective is to locate the black hole without destroying too many agents. This is difficult to achieve when the agents are initially scattered in the network and are unaware of the location of each other. Previous studies for black hole search used more powerful models where the agents had non-constant memory, were labelled with distinct identifiers and could either write messages on the nodes of the network or mark the edges of the network. In contrast, we solve the problem using a small team of finite-state agents each carrying a constant number of identical tokens that could be placed on the nodes of the network. Thus, all resources used in our algorithms are independent of the network size. We restrict our attention to oriented torus networks and first show that no finite team of finite state agents can solve the problem in such networks, when the tokens are not movable. In case the agents are equipped with movable tokens, we determine lower bounds on the number of agents and tokens required for solving the problem in torus networks of arbitrary size. Further, we present a deterministic solution to the black hole search problem for oriented torus networks, using the minimum number of agents and tokens."