In many applications, a physical phenomenon can be sensed by collecting data collaboratively [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, e.g.] , either from humans directly or from devices acting on their behalf. This is variously known as (spatial) crowdsourcing [2] , (mobile) crowd sensing [13] , or social sensing [14, 15] . Often, crowdsourcing is associated with situations, where there is a payment made to the participants. Instead, we focus on situations, where sensing is provided without any payment per query made, such as in disaster response, disease outbreaks, and the search for missing entities, which we refer to as social sensing.
We develop a framework for reasoning about fairness in social sensing in the sense of guaranteeing that the number of queries per participant will be equalised among comparable participants, in expectation, even when the population of participants varies over time. A prerequisite for fairness is predictability, in the sense of guaranteeing that the expected number of queries per participant is independent of the initial state. We develop a meta-algorithm for social sensing in such a time-varying setting, for which we prove such guarantees, by reasoning about the existence of a unique invariant measure for a related stochastic system.
As a motivating application, consider the situation when a material object, pet, or even a loved one goes missing. Considering that objects, pets and even people go missing every day, there are methods and systems to facilitate the location of missing entities. For example, applications on our computers allow us to track missing or stolen smartphones. Pets can be microchipped or equipped with "smart" collars. Medical jewellery and community support networks exist to aid people with needs who wander, including Alzheimer's patients [16] . The emergence of the Internet of Things (IoT) allows for the automation of the search and therewith, improved response times. For instance, in the context of IoT, the vehicles that we drive are becoming connected to each other, to the infrastructure, as well as to the internet [3, 6] . With expanding on-board sensor complements, computing, and communication abilities, parked cars no longer need to be idle, to be of no service to us during the extended periods when they are not being driven. Recently [6, 17, 18] , the use of networks of parked vehicles in dense urban areas has been suggested for the detection and localisation of moving, missing entities using RFID technology.
The RFID-based system, described in [6, 17, 18] and illustrated in Fig. 1 , was envisioned as follows. Each participating parked vehicle has an RFID reader and antenna on board, and is able to communicate with an administrative centre. The missing entity is presumed to be carrying an RFID passive tag via some means, e.g., a wrist band. Passive RFID tags do not require a local power source, beyond the field created by the RFID reader, and thus need not contain batteries. When an entity is missing, an alarm is raised with the administrative centre. For example, the entity's carer or owner places a phone call with the police. Once the alarm has been raised, the administrative centre prompts the RFID-based application on board the parked vehicles participating in the service. The RFID technology enables those vehicles to attempt to locate the missing entity, and to inform the administrative centre when the missing entity is found, i.e., when the RFID equipment on board a parked vehicle detects and processes the presence of the unique RFID passive tag carried by the missing entity. The information sent to the administrative centre might include a time stamp, a GPS location of the parked vehicle, and the unique RFID passive tag ID carried by the missing entity that was detected by the equipment on Figure 1 . An illustration of the RFID-based system, following [1] . (Some sub-images obtained from Openclipart [19, 20] .) board the parked vehicle. Once detected, the administrative centre is then able to invoke a procedure aimed at making contact with the missing entity. For example, police are able to go to the location at which the entity was detected in order to refine the localisation and determine whether the entity needs assistance, and if required, aid the entity on its way home. See [6, 17, 18] for further details. The work presented in [18] was simulation-based. The system was demonstrated through a use case scenario of a missing Alzheimer's patient in innercity of Melbourne, Australia. System parameters were varied, including: (i) the percentage of parking spaces on the map of Melbourne that were inhabited by vehicles participating in the service; (ii) the polling rate of the RFID equipment on board the participating parked vehicles; and (iii) the RFID equipment's detection range. Results were presented from thousands of simulations and consisted of: (a) average times that it took for the network of participating parked vehicles to detect the moving pedestrian; (b) population standard deviations from these average detection times; and (c) the number of times that the system failed to detect the pedestrian within a thirty-minute time frame. An interesting (albeit expected) observation that the results revealed was one of redundancy, in that the average detection times, and particularly the "failed to detect" totals, followed curves resembling the exponential. That is, the average detection times and "failed to detect" results remained relatively constant until a "threshold" participation percentage was reached. When numbers of parking spaces inhabited by searching vehicles fell below this threshold, detection times, and especially the "failed to detect" totals, increased sharply. Clearly, a key question is: How can we distribute the searching agents to quickly locate the moving, missing entity, while also reducing redundancy in the system? There are a number of ways in which this problem can be approached, but one should keep in mind that the best search strategy can be formulated as the restless bandit problem, whose approximation to any non-trivial factor is complete for polynomial-space Turing machines [21] , i.e., provably intractable. We hence propose to focus on fairness among participating vehicles in terms of energy consumption.
Technically, we consider a feedback loop wherein the administrative centre broadcasts a signal to all agents capable of participating in social sensing. The agents respond to the signal, and thereby alter the state of the system. The administrative center observes a filtered aggregate state of the system, and the process repeats. In the example of an urban centre with the aim of regulating the number of cars looking for a missing, moving entity efficiently, the administrative center may be the municipality or police force. Probabilistic models of each vehicle switching on or off their RFID readers are associated with the numbers of neighbours that are also capable of participating, obtained by sending out a "ping" and observing the responses. The agent uses the broadcast signal from the administration centre, together with the relevant probability model deduced by the number of his or her neighbours, to "flip a coin" and determine whether to "Switch On" their RFID reader over the next time interval. This process is repeated every time interval.
A preliminary version of this paper has appeared in [1] , which focused on the motivating application and presented an initial version of Algorithm 2, specific to the motivating application. Meanwhile, the work presented in this current paper expands upon [1] significantly, as follows:
• we present a framework for reasoning about predictability and fairness of regulating task distribution in social sensing; • we develop conditions that ensure predictability and fairness both, even when there are small deviations in the probabilistic models over time; • we expand upon the motivating application of searching for a missing person with illustrations from simulations from Melbourne, Australia. The new simulations corroborate our analysis: using Algorithm 2, "Switching On" or "Off" of the RFID readers per participant over time is, indeed, independent of the initial state and does exhibit weak convergence.
The paper is structured as follows: In the next section, we provide an overview of related work both in Social Sensing and Control Theory. Next, we formalise the problem and present our meta-algorithm. In Section V-B, we demonstrate the feedback regulation in action by revisiting the use case of a missing Alzheimer's patient in inner-city Melbourne, Australia. Finally, conclusions and future work are presented in Section VI.
Some researchers may be prefer to consider the applied Algorithm 2, before considering the abstract Algorithm 1, and the associated guarantees of Section IV.
There is an extensive literature on social sensing, as surveyed in [14, 15] . Much of the early work has been empirical and exploratory in nature [5] . More recently, however, rigorous analyses appear. [7] consider credibility estimation and [22] set the study in context. [23] proposed different likelihood-based inference algorithms (EM and Fisher scoring) that achieve estimation performance bounds in terms of Fisher information asymptotically. [10] combined both efforts in a time-sensitive setting. A number of studies [24, 25, 26, 27, 28, 12] analysed privacy in this context, as surveyed in [29] : [24] consider kanonymity and [25, 26, 28] consider differential privacy, for instance. Excellent recent surveys include [29, 30, 14, 15] .
More broadly, one should also mention related work on the interface of social sensing and control theory, which elucidates certain mathematical features of the problem. Most of the theory discussed in this section is presented in [31, 32] , who have introduced an abstract framework, blending practical aspects of intelligent transportation systems, smart cities, and techniques from classical control theory. Let us consider a resource allocation problem in discrete time. In particular, consider the closed-loop system as depicted in Fig. 2 , which comprises a (typically large) number of agents, a controller, and a filter. The controller, C , broadcasts a signal π(k) at time k ∈ N; the N ∈ N agents S 1 , . . . , S N amend their use of a shared resource in response. The use x i (k) of the resource by agent i at time k is modelled as a random variable, as there is an inherent randomness in the reaction of each agent to the broadcast signal. The main design task is to regulate the aggregate resource utilisation
which is also a random variable. In this setting, the controller usually does not have access to either x i or y, but only to an estimateŷ of y, which is the output of a filter F . In addition to achieving regulation, the controller should also ensure that the agents have a sense of fairness and predictability. In controltheoretic terms, this can be cast as a particular flavour of ergodicity of the closed-loop system dynamics, known as the existence of a unique invariant measure [31, 32] . This completely removes effects of initial conditions on the long run. Overall, in the aforementioned references, the authors state the following conditions for unique ergodicity of the closed-loop with linear controllers and filters.
Theorem 1 ( [31] ). Consider the feedback system depicted in Fig. 2 , for some given finite-dimensional linear systems C and F . Assume that each agent i ∈ {1, . . . , N } has state x i (k) governed by the following affine stochastic difference equation:
where the affine mapping w ij is chosen at each step of time according to a Dini-continuous probability function p ij (x i (k), π(k)), out of
where A i is a Schur matrix and for all i, π(k),
, π(k)) = 1. In addition,suppose that there exist scalars δ i > 0 such that p ij (x i , π) ≥ δ i > 0; that is, the probabilities are bounded away from zero. Then, for every stable linear controller C and every stable linear filter F , the feedback loop converges in distribution to a unique invariant measure.
Remark 2. Dini's condition on the probabilities may, obviously, be replaced by simpler, more conservative assumptions, such as Lipschitz or Hölder conditions [33] .
This theoretical framework will be exploited and extended in the sequel to devise our fair and predictable social sensing solution. For now, there are some key aspects on this framework and specifically on the previous theorem that should be pointed out and discussed. Note first that the agents' dynamic behaviour may seem rather limited, but it suffices for several smart cities applications, such as the ones with 'on-off' participants; the reader may see [32] for extensions to the nonlinear case. Note also that the main design task in the linear setting described above is to devise two stable linear time-invariant systems (a filter and a controller) so that the closed-loop dynamics is stable. This ensures ergodicity and, thus, fairness. Finally, it is important to point out that all probabilities involved in the dynamic response of the agents with respect to the broadcast signal must be bounded away from zero. The lack of this assumption can yield non-ergodic stochastic processes, as some agents may monopolise allocated resources.
As stated in the introduction, our aim in this paper is to regulate task distribution of social sensing, which assures predictability and fairness. Our solution is embedded in the feedback-control framework presented in the previous section.
While we define predictability formally later in this section, it requires that for each agent, there exists a limit of the long-run average of the agent's state, and that this limit is independent of the agent's initial state. Fairness, consequently, requires that this limit coincides for all agents. Notice that the definition of a state can differ across the agents, or can remain the same, for all agents. A simple example of the definition uniform across the agents may be the probability of activation in each period. An example of the definition varying across the agents may be a combination of the number of agents in that particular agent's vicinity in the given period, combined with the probability of activation of that particular agent in the given period.
In our application, agent i represents a parked car whose state x i (k) at time k is in the set {0, 1}; these variables model whether agent i allows for the search (x i (k) = 1) or not (x i (k) = 0). Further, we assume that, at each time instant k, agent i has a probability p i1 of being on and a probability p i0 of being off at the following time step. Both probabilities depend on the broadcast control signal π; that is,
and, thus,
since both events are complementary. These probabilities may depend on the number of neighbouring vehicles. Indeed, clusters of cars can cooperate and take turns to cover one area, whereas a sole car on a street must be almost always on. In particular, we consider three kinds of responses to the broadcast signal π, depending on whether a car has few (f f ), some/medium (f s ), or many (f m ) neighbours, as depicted in Fig. 4 . Notice that these probabilities must satisfy the conditions of Theorem 1.
Remark 3. Note that Theorem 1 addresses a more general dynamic model for the agents than the one we consider here. Indeed, for our case, we can take A i = 0 and define b i0 = 0 and b i1 = 1 for all i.
To formalise our definitions, consider a controller that regulates the number of simultaneously active agents around a pre-specified number r using the broadcast signal π, which affects the agents behaviour towards turning on or off. Broadly speaking, if the error signal e = r−ŷ is large, then we expect a large value of π; their probabilities of turning on must be tuned so that large values of π induce more agents to turn active. The contrary effect should hold if e = r −ŷ gets negative; that is, π should get negative and this should induce more agents to turn off. The response of agent i to the broadcast signal π, namely its probabilities p i1 and p i0 , also plays a key role in the design. In addition to their explicit dependence on π, as discussed previously, these probabilities also depend on each agent's surroundings. With this notation, one can define: Definition 4 (Predictability). Whenever, for each agent i, there is an agent-specific constant r i such that the following limit exists:
i.e., a long-run average of agents' states independent of the initial state x i (0), we say the system is predictable.
Next, fairness in the sense of statistical parity [34] , requires the limits of (31) coincide for all agents i: Definition 5 (Fairness). Whenever there exists a finite constant r such that:
for all agents i, we say the system is fair.
Notice that this notion of fairness is rather strict. One may equally well consider simpler notions of fairness, perhaps summing over only a certain coordinates of the multivariate state variable, or considering a fixed numerical threshold: Definition 6 (ǫ-fairness). Based on (6) and (7), we define predictability and fairness vectors for some r ∈ R as follows:
and for some small ǫ > 0 and any vector norm · in R n , we say that the system is ǫ-
Note that this definition does not imply the existence of a protocol which can ensure ǫ-fairness of the system. This is because, however large the values of ǫ, however fast the protocol used for conveying agent's long-term usage converges, a scenario can be created to violate the ǫ-fairness condition by instantly introducing a sufficiently large number of usage in the agent's population, Hence, a violation of ǫ fairness condition only serves as a guideline for triggering max − min fairness and predictability computation. Thus, using ǫ-fairness criteria, we avoid being too keen or too idle in computing fairness and predictability.
While in some smart cities applications one may assume that the population probabilistic models is time-invariant, most social sensing problems have a time-varying nature and this can be challenging from a theoretical perspective. For instance, in our application, the number of parked cars and each agents' surroundings may change from time to time. In such time-varying setting, the efficient task-allocation (e.g., search efficiency in our application) becomes computationally intractable [35] when the probabilistic models are allowed to vary arbitrarily, as in approximation to any non-trivial factor is complete for polynomial-space Turing machines [21] . Hence, any scheme assuring efficiency is computationally complex, independent of whether P equals NP, and in turn, predictability and fairness are as much as we can hope for. Second, the analysis of predictability and fairness becomes rather nontrivial.
We address these complications with tools from stochastic analysis and control. Both predictability and fairness are satisfied can be defined in terms of properties of an associated stochastic model, which is known as iterated function system (cf. Definition 7 in the next section). When the probabilistic model does not change over time, predictability is assured by the exists of a unique invariant measure (cf. Definition 9 in the next section). When we cannot rely on the probabilities and the transformations in the iterated function system being invariant over time, or perfectly known to us, there are still at least two options. Either we can consider the notion of piece-wise stationary measures [36] for a time-varying iterated function system [36] , or we can consider perturbation analysis, also known as sensitivity analysis. There, it is of interest to know whether a perturbation in the states causes a large difference in the behavior of the corresponding stochastic process. In our classes of contractive transformations, we show that small perturbations in the states or probabilities do not cause large changes in the behavior, in terms of the long-run average state. This means that we can use linear or other approximations without changing the invariant measures too much.
Data: Number of agents N ; initial state x i (0) ∈ X for each agent i; a set of possible behaviours {w τ } τ valid for any agent, to be chosen with agent-and state-dependent probability; number t of time steps between perturbations; time horizon t ≤ T of time steps; a bound δ on the rate of the environment-driven change per t time steps. Initialise counters s ← 0, h ← 0, where (s, h) considered lexicographically captures time ; Central authority broadcasts arbitrary signal π(0), such as 0 ;
.; Agent i selects response function w σ , where σ is chosen according to to the probabilities
i.e., according to (4); end Central authority observes filtered aggregate statê y(st + h), where the filter F is possibly not known a priori ; Central authority computes the error e(st + h) ; Central authority broadcasts signal π(st + h) computed using some controller C and increments h to h + 1; end The environment perturbs the state of agents such that |x i ((s + 1)t) − x i (st + h)| ≤ δ and increments s to s + 1. end Algorithm 1: An algorithm schema for social sensing with fairness guarantees
To address predictability and fairness in social sensing rigorously, we present a result which is applicable for a class of stochastic phenomena which can be modelled as iterated function systems, generalising (3).
Let us define the class of systems we consider formally:
Definition 7 (Iterated function system [37, 38] ). Let X ⊆ R n be closed, and let ρ be a metric on X such that (X , ρ) is a complete metric space. Let {w i } N i=1 be transformations on X and {p i (x)} N i=1 be probability functions defined on Borel sigma-algebra B(X ), such that,
The pair of sequences (w 1 (x), w 2 (x), . . . , w N (x); p 1 (x), p 2 (x), . . . , p N (x)) (10)
is called an iterated function system (IFS).
Informally, the corresponding discrete-time Markov process on X evolves as follows: Choose an initial point x 0 ∈ X . Select an integer from the set [1, N ] := {1, 2, . . . , N } in such a way that the probability of choosing σ is p σ (x 0 ), σ ∈ [1, N ]. When the number σ 0 is drawn, define
Having x 1 , we select σ 1 according to the distribution
and we define
and so on.
Let us denote ν n for n = 0, 1, 2, . . . , the distribution of x n , i.e, ν n (A ) = P(x n ∈ A ) for some A ∈ B(X ).
The above procedure can be formalized for a given x ∈ X and a Borel subset A ∈ B(X ), we may easily show that the transition operator for the given IFS is of the form:
ν(x, A) is the transition probability from x to A . where 1 A denotes the characteristic function of S A:
Definition 8 (Markov operator [39] ). Closely connected with this transition probability is the Markov operator, denoted by P , defined on the space of all real or complex valued Borel measurable maps f on X as:
Definition 9 (Invariant probability measure [33, 39] ). If a Markov chain {X n } moves with transitional probability (12), then it is of great interest to know the existence of an invariant probability measure for the chain, i.e, existence of a probability measure ν ⋆ ∈ M (X ), for which:
In our analytic approach we consider the dual of Markov operator P defined in (13), 
Definition 10 (Total-variation (TV) distance; Proposition 4.2 in [40] ). Let µ and ν be any two probability measure on X and B(X ) be a sigma-algebra on X , then
If X is finite, one can show the above expression is equivalent to the following:
We finish this preliminary section of mathematical definitions and set up by defining an useful metric on the space of probability measure on X , due to Kantorovich and Rubinstein [41, 42, 43] , also known as Wasserstein-1 distance.
Definition 11 (Wasserstein-1 distance; Remark 6.5, p. 95 in [43] ). Let W 1 denote the space of all Lipschitz maps with Lipschitz constant 1, i.e
For ν 1 , ν 2 ∈ M (X ), Wasserstein-1 distance between these two probability measure is denoted by d 1 (ν 1 , ν 2 ) and is given by:
Theorem 12. Let P * 1 be the Markov operator [39] of an iterated function system (w i , p i ) with invariant measure ν * 1 , and let, P * 2 be the Markov operator of the perturbed iterated function system (w ′ i , p ′ i ) with invariant measure ν * 2 , then we have the following estimates of distance between their invariant measure in Wasserstein-1 distance, which we denote by d 1 , as follows:
where σ 0 , σ 1 , σ 2 , . . . are i.i.d discrete-random-variable taking values in {1, 2, . . . , N }, β is a bound for the real-valued continuous function w ∈ C b (X , R), η is the bound on the perturbation in probabilities in total-variation distance [40, p-48, Proposition 4.2], r ∈ (0, 1) and for some r ′ we have w(x) − w(y) ≤ r ′ x − y for almost all x, y ∈ X .
The proof is included in the Appendix.
Let X be a closed subset of R n . We are given a finite set of bounded Lipschitz transformations:
and a countable family of N -tuple probability functions
where the variable s denotes a discrete time-scale, for each fixed s ∈ N, and for all i ∈ [1, N ], p s i : X → [0, 1] and for any fixed s ∈ N,
We now introduce a time-varying stochastic situation as follows: let s denote a discrete time-scale, between s = 1 and s = 2, a certain number say k = 1, 2, . . . , t iteration is performed for the system (2) with a tuple of probability function {(p 1 1 (x), p 1 2 (x), . . . , p 1 N (x))} and after such number of iteration we change the probability-tuple and we perform the iteration again, for a general s, time-varying situation (2) becomes (21), we use this vector as the chance of selecting a transformation
This is done by considering the probabilities as bins, σ 1 1 , with length p 1 i (x 1 (0)). Placing these bins end to end on [0, 1] will fill the interval as a consequence of (22) . We then choose a random number q ∈ [0, 1] and the bin containing q corresponds to the probability function we choose. The starting point of the next iteration is 0)) is calculated and consequently a new probability vector p 1 (x 1 (1)) must be calculated. See Algorithm 1 for the general schema. For time steps t between s and s + 1, the conditional distribution of the future depends only on the current state. For the time steps between s and s + 1, the process defined the realization equation as in (23) is clearly Markovian. Let C b (X ) denote the set of real-valued bounded continuous functions on X , for any s, one can define a linear map P s on C b (X , R):
This operator characterizes the Markov chain. Clearly from the fact that P s maps C b (X ) into itself, which is known as P s is a Feller map or it satisfies Feller property . Markov chains with the Feller property are sometimes called Feller chains. We will mainly be interested in the problem of uniqueness or nonuniqueness of invariant probability measures. A probability measure ν on X is called invariant for the operator P s if
Denoting dual of the map P s as follows:
with the requirement
then (25) is reduced as: a ν ⋆ ∈ M (X ) is invariant if and only if
Such a dual map P ⋆ s well defined by the Riesz representation theorem.
In the following, we would like to show the existence of an invariant measure (Theorem 14) and its uniqueness (Theorem 15). In Theorem 14, we need:
Definition 13 (Uniformly tight measure; Definition 8.6.1 in [44] ). An arbitrary M ⊆ M (X ) is called uniformly tight if ∀ǫ > 0 there exists a compact subset K ⊆ X such that
It can be shown that on a compact metric space, any family of probability measures is uniformly tight Theorem 8.6.2 in [44] and intuitively, for any other space, probability measures accumulate on compact subsets of the underlying space. We use a result due to Prokhorov [45] which says, if {ν n } ∞ n=1 ∈ M (X ) be uniformly tight sequence, then there exists a sub-sequence {ν n k } ∞ k=1 of {ν n } ∞ n=1 and a ν ∈ M (X ) such that ν n k → ν weakly. Now, with this in mind we establish existence of invariant measures of the Markov process described in equation (23) . Let B(X ) denote the Borel sigma-algebra on X . For any Borel set A ∈ B(X ) we define m-step transitional probability functions, which are probability measure for each fixed x ∈ X and measurable function of x for each fixed A ∈ B(X ), as follows:
Theorem 14. Let for each s, P s be defined as in (24) . If there exists x ∈ X , for which the sequence of transitional probability measures {ν m s (x, ·)} m≥0 is uniformly tight, then there exists an invariant probability measure for P ⋆ s . As before, the proof is in the Appendix. Next, notice that any two trajectories get arbitrarily close to each other, eventually:
Theorem 15. Consider two trajectories (realizations) of the Markov chain in (23) starting from any two different initial conditions x s (0) and y s (0). Then trajectories couple in the sense of (1.2) in Hairer [46] .
Once again the proof is included in the Appendix. Thus, we obtain a unique ergodic measure, which assures predictability and, in turn, allows for fairness: Corollary 16. Consider an extension of Theorem 1 towards the time-varying stochastic setting, as modelled by Markov chain (23) . Conditions of Theorem 14 assure predictability, i.e., for each agent i, there being a constant r i such that
Proof: This follows from the existence of a existence of a ergodic measure (Theorem 14), its uniqueness (Theorem 15), and from Theorem 2 of Elton [47] .
The results presented in Theorem 15 and in Corollary 16 ensure that, under the mild assumptions of Theorems 1 and 14, the participants' trajectories still couple for different initial conditions; that is, predictability still holds. As stated before, such property is important in practical social sensing problems 1 , as the central authority thus ensures a predictable task allocation.
Notice that while predictability is highly desirable in many situations, fairness in the sense of statistical parity [34] is a much stricter notion, which does apply under stricter conditions:
Corollary 17. Consider an extension of Theorem 1 towards the time-varying stochastic setting, as modelled by Markov chain (23) . Conditions of Theorem 14 and the uniform initial state, i.e., the existence of a constant c such that x i (0) = c for all agents i, assure fairness, i.e., the existence of a constant r such that
for all agents i.
Proof: This follows from the Markov property of (23). The question as to whether generalisations of fairness, such as ǫ-fairness of Definition 6, allow for less strict conditions on the initial state, are most intriguing.
We are now able to showcase the application of our abstract algorithmic schema (cf. Algorithm 1) in the context of searching for missing entities utilising a network of parked cars. Algorithm 2 specialises Algorithm 1 as follows: abstract agents are specialised to cars, the state is composed of internal states of the cars (x i ) and the numbers of cars parked in their vicinity (N i ), as well as the possible states of the controller (C ) and filter (F ). The abstract sets of state-to-state functions w of Algorithm 1 are replaced with three possible behaviours f f , f s , f m of the cars, corresponding to few, some, and many cars parked in their vicinity. The abstract agent-and statedependent probability p i (x i (t)) = (p i 1 (x i (t)), . . . , p i N (x i (t))) of choosing a particular abstract w at time t is specialised to an agent-and state-dependent probability (p i f (t), p i s (t), p i m (t)) of the three possible behaviours. Finally, k is a counter of the samples drawn using any of the three-vectors, since the most recent signal broadcast. Another counter h counts the number of signals broadcast, since the most recent perturbation. perturbation of the states. Finally, s is the counter of the perturbations. Time is hence captured by a triple (s, h, k), considered lexicographically.
To demonstrate the performance of our algorithm, we employed Simulation of Urban MObility (SUMO) Version 1.2.0. SUMO [48] is an open-source, microscopic traffic simulation package primarily being developed at the Institute of Transportation Systems at the German Aerospace Centre (DLR). SUMO is designed to handle large networks, and comes with a "remote control" interface, TraCI (short for Traffic Control Interface) [49] , which allows one to adapt the simulation and to control singular vehicles and pedestrians on the fly. Our goal was to simulate a pedestrian walking about in an urban scenario, and to regulate the number of parked vehicles actively searching for the pedestrian in an energyand coverage-efficient manner using our algorithm.
The region considered for our simulations consisted of the City of Melbourne municipality, with boundary map obtained from [50] ; cf. Fig. 3 . A dataset containing spatial polygons representing the on-street parking bays across the city was obtained from [51]. A total of 24,067 on-street parking spaces were imported onto our SUMO network as polygons from this dataset. To generate random walks for the pedestrian, we utilised the TraCI function traci.simulation.findIntermodalRoute. In particular, at the commencement of each walk, a random origin and destination lane were selected from the list of all possible lanes on the network for which pedestrians were permitted on, and these origin and destination links were then provided as input to the TraCI function which generated the route. The maximum walking speed for the pedestrian Data: Number of agents N ; initial state x i (0) ∈ X for each agent i; a set of possible behaviours {f f , f s , f m } valid for any agent, based on the few, some, or many cars in the vicinity; number t of time steps between perturbations; time horizon t ≤ T of time steps; a bound δ on the rate of change of the number N i of cars parked in the vicinity of car i, within t time steps. Result: Missing entity location or fail alert. Car i "tosses a coin" and updates state
Car i scans for missing entity using RFID ; if the missing entity is located then Car i returns position of the missing entity to the requester of the search ; end end end Central authority observes filtered aggregate statê y(st + h), where the filter F is possibly not known a priori ; Central authority computes the error e(st + h) ; Central authority broadcasts signal π(st + h) computed using some controller C and increments h to h + 1; end The environment perturbs the numbers N i , i.e., the numbers of cars parked in the vicinity, such that |N i ((s + 1)t) − N i (st + h)| ≤ δ and increments s to s + 1. end The cars have failed to locate the entity within the time horizon ;
Return an alert to the requester of the search; Algorithm 2: A specialisation of Algorithm 1 for the search for a missing entitity. was set at SUMO's default of 1.39m/s. We used SUMO's striping pedestrian model [52] as the model for how the person otherwise interacted with the map.
Another parameter in our experiment was the proportion of parking spaces in each simulation that would have cars parked in them that were capable of participating in the search. We elected for each parking space (out of the 24,067 total parking spaces) to have a 50% chance of being inhabited by a vehicle capable of participating in the search. Thus, at the beginning of each simulation, a "coin" was flipped for each of the 24,067 parking spaces. The result of this "coin flip" was compared to the fifty percent value, to determine whether that parking space would be inhabited by a parked vehicle capable of participating in the search or not, over that particular simulation. Parking space assignments for vehicles then remained constant for the duration of a simulation, and parked, participating vehicles were "Switched On" or "Switched Off" according to Algorithm 2. At the beginning of each search, the proportion of participating vehicles that were initially "Switched On" was set at 30%. We chose our target number r of "Switched On" vehicles to be 7,200.
For our probability models, we employed the use of logistic functions which are illustrated in Fig. 4 . We placed a circle with a radius of twenty metres around each parked vehicle capable of participating in the search, and let the number of other parked vehicles (capable of participating in the search, and) residing within this circle, equate to the number of neighbours that the vehicle at the centre of the circle had. For simplicity, we assume thatŷ = y (that is, the filter F provides a perfect estimate for the resource consumption) 2 . We also consider a simple controller model given by the difference equation
for all k ∈ N, in which α, β, κ ∈ R. This model includes, as particular cases, classical lead, lag and PI controller structures [53, 54] . For this particular example, we let α = −4.01, β = 0.99 and κ = 0.1 in (32). We set each vehicle's RFID polling rate (i.e. the frequency at which a car's RFID system is sampling at when the vehicle is "Switched On") as "Always On", meaning that once "Switched On", a vehicle is always polling as opposed to doing periodic, timed reads. We set a circular RFID field around each car with a radius of six metres. Moreover, we assumed that once a pedestrian entered this field, and if the vehicle was "Switched On", then the pedestrian would be detected. In other words, in this paper, we neglect some of the more complicated phenomena typically associated with RFID, such as the effects of tag placement, antenna orientation, cable length, reader settings, and environmental factors such as the existence of water or other radio waves [55] .
For each simulation, then, our goal was to set the person down on a random edge, and have them walk until either: (i) they were detected by a parked vehicle that was "Switched On" and thus actively searching at the same time as when the pedestrian was passing by; or (ii) thirty minutes had transpired Logistic functions used to model the possible behaviours {f f , fs, fm} in Algorithm 2. and no detection event had occurred. We permitted thirty minutes to lapse before a "fail-to-detect" event was recorded, keeping in mind that quickly finding a missing and potentially stressed person, and returning them to their home, for instance, is ideal. All simulations had time-step updates of 1s, while our control signals were sent only every 20s. For our test case scenario, 100 simulations were performed in total.
To gather some preliminary data, we first permitted a small sample of ten simulations to run for a full thirty minutes, with no pedestrian placement yet. From these simulations, Fig. 5 demonstrates that regulation of the system, such that approximately 7,200 parked vehicles were "Switched On" at any point in time, was achieved quite rapidly. Specifically, the blue line in the figure indicates the mean number of vehicles "Switched On' versus time (from the ten sample simulations); while the red shaded area indicates one sample standard deviation each side of the mean. Fig. 6 illustrates the evolution of the mean control signal π over time. (Again, the red shaded area indicates one sample standard deviation each side of the mean.) Notice that π could then be used in association with Fig. 4 , along with the known number of neighbours that a vehicle had, to determine the probability of that vehicle being "Switched On" over the next appropriate time interval.
Next, we performed our simulations proper, where a pedestrian was inserted onto the map at the beginning of each simulation, and the emulations ran until either: (i) the pedestrian was detected by a parked vehicle that was "Switched On" and thus actively searching at the same time as when the pedestrian was passing by; or (ii) thirty minutes had lapsed and no detection event had occurred. The data collected from our experiment comprised of: (i) the average time taken (in minutes) until detection of the missing entity occurred (provided that the detection occurred within thirty minutes from the beginning of an emulation, else a fail result was recorded); and (ii) the total number of times that fail results were recorded over the entirety of the experiment. To reiterate, 100 simulations in total were conducted over the course of our experiment. The results were as follows: (a) Average Detection Time = 5.30 minutes; and (b) Failed to Detect = 6 times out of 100 simulations. In other words, the pedestrian was not detected, within a thirty minute time frame, 6% of the time. For the other 94 cases, the pedestrian was detected, on average, in approximately five minutes.
We have considered the notion of predictability and a notion of fairness in time-varying probabilistic models of social sensing. A number of theoretical questions arise: what other conditions assure fairness in the sense of statistical parity? What other notions of parity could there be? We believe these could spur a considerable interest across both Social Sensing and Control Theory.
In our application, we have considered dynamic parking, which requires such time-varying probabilistic models. We envisage a number of ways forward in regard to improving our experimental setup, including performing more simulations, in further cities worldwide.
There could also be a number of other applications. For instance, during the current COVID19 pandemic, many governments considered the participation in a tracing scheme that would be sufficient to contain a contagion, and the option of invading privacy of individuals in a sensing scheme. Should such a measure be applied, our notion of fairness may also be worth considering.
In the following, we present proofs of three key results: We refer to the main body of the text for the full statement of all theorems.
Proof of Theorem 12: Let C b (X ) denote the set of realvalued bounded continuous functions on X , for any s, one can define a linear map P s on C b (X , R):
This operator characterizes the Markov chain. Clearly from the fact that P maps C b (X ) into itself, which is known as P is a Feller map or it satisfies Feller property. Let M (X ) denote the set of Borel probability measures on X . Denoting dual of the map P as follows:
with the requirement X wd(P ⋆ ν) = X (P w)dν.
Such a dual map P ⋆ well defined by the Riesz representation theorem. Now we show that P ⋆ is contraction in the Wasserstein-1 i.e., in d 1 metric with some contraction factor r ∈ (0, 1). For any two ν 1 , ν 2 ∈ M (X ), we have:
Now a useful consequence of the above derived fact is: d 1 (ν * 1 , ν * 2 ) =d 1 (P * 1 ν * 1 , P * 2 ν * 2 ) ≤d 1 (P * 1 ν * 1 , P * 1 ν * 2 ) + d 1 (P * 1 ν * 2 , P * 2 ν * 2 ) ≤rd 1 (ν * 1 , ν * 2 ) + d 1 (P 1 ν * 2 , P 2 ν * 2 )