Predictability and Fairness in Social Sensing

Ramen Ghosh, Jakub Marecek, Wynita M. Griggs, Matheus Souza, Robert N. ShortenIEEE Internet of Things Journal 2020 · DOI · OpenReview

Abstract

We consider the design of distributed algorithms that govern the manner in which agents contribute to a social sensing platform. Specifically, we are interested in situations where fairness among the agents contributing to the platform is needed. A notable example are platforms operated by public bodies, where fairness is a legal requirement. The design of such distributed systems is challenging due to the fact that we wish to simultaneously realise an efficient social sensing platform, but also deliver a predefined quality of service to the agents (for example, a fair opportunity to contribute to the platform). In this paper, we introduce iterated function systems (IFS) as a tool for the design and analysis of systems of this kind. We show how the IFS framework can be used to realise systems that deliver a predictable quality of service to agents, can be used to underpin contracts governing the interaction of agents with the social sensing platform, and which are efficient. To illustrate our design via a use case, we consider a large, high-density network of participating parked vehicles. When awoken by an administrative centre, this network proceeds to search for moving missing entities of interest using RFID-based techniques. We regulate which vehicles are actively searching for the moving entity of interest at any point in time. In doing so, we seek to equalise vehicular energy consumption across the network. This is illustrated through simulations of a search for a missing Alzheimer's patient in Melbourne, Australia. Experimental results are presented to illustrate the efficacy of our system and the predictability of access of agents to the platform independent of initial conditions.

Introduction: The Fairness-Efficiency Trade-off

Social sensing, or crowdsourcing, leverages distributed networks of agents—typically citizens and their mobile devices—to collect real-time data about the physical world. Applications range from monitoring air quality and traffic flow to identifying available parking. Traditionally, the primary design objective for these platforms has been efficiency: maximizing data collection while minimizing operational costs.

However, this focus often neglects critical aspects of fairness and predictability. If a platform consistently queries the same subset of "optimal" agents, those individuals suffer disproportionate battery drain and privacy loss, while others are excluded from potential incentives. For platforms operated by public entities, "statistical parity"—treating all participants equally—is often a legal mandate. The challenge lies in designing distributed algorithms that regulate agent participation to meet global sensing goals while guaranteeing that, in the long run, every agent’s workload remains predictable and fair.

Methodology: Iterated Function Systems and Feedback Control

To address these challenges, we move beyond simple heuristic assignments, modeling the sensing platform as a sophisticated feedback control loop. Our primary analytical tool is the Iterated Function System (IFS) with state-dependent probabilities.

The feedback control loop architecture used to regulate agent participation.

Ergodicity as a Guarantee of Fairness

The core of our approach is proving the ergodicity of the system. In this context, ergodicity implies that the system eventually reaches a stable statistical state where initial conditions no longer influence long-term outcomes. If the system is ergodic and agents are symmetric, the long-run average participation of every agent will converge to the same value, ensuring statistical parity.

As shown in the control loop above, a central authority broadcasts a control signal ($\pi$). Individual agents (such as parked cars) utilize this signal alongside local environmental data (e.g., neighbor density) to probabilistically decide whether to activate their sensors. This "neighbor effect" allows clusters of agents to take turns, significantly preserving battery life across the network without creating coverage gaps.

Robustness and Predictability

Real-world populations are dynamic. Our framework includes a stability analysis (Theorem 2) proving that small deviations in the environment or probabilistic models do not collapse the system's long-term fairness. This predictability is a prerequisite for Service Level Agreements (SLAs); for a participant to enter a contract with a platform, they must have a reliable expectation of their future workload.

Application: Searching for Missing Persons in Melbourne

To evaluate the framework, we simulated a high-stakes social sensing scenario: searching for a missing Alzheimer’s patient in Melbourne, Australia.

Conceptual diagram of the social sensing use case involving parked vehicles and RFID technology.

Simulation Setup

  • Map Data: Boundary maps and road networks were imported from OpenStreetMap.
  • Agent Population: We utilized a real-world dataset from the City of Melbourne containing 24,067 on-street parking spaces to populate the simulation with potential sensing agents (parked cars equipped with RFID readers).
  • Mobility Modeling: We used SUMO (Simulation of Urban MObility) to model the movement of the missing person through the city using a "striping" pedestrian model.

Experimental Results

The algorithm was tasked with regulating the number of active sensors to a target of 7,200 vehicles (approximately 30% of the available network).

  • Regulation and Efficiency: The system reached the target activation density almost immediately. By activating only a fraction of the network at any given time, the system maintained high search efficacy while preventing rapid battery depletion.
  • Search Performance: The average detection time for the missing person was 5.30 minutes, with a 94% success rate within a 30-minute window.
  • Convergence: Experimental data confirmed "weak convergence" of the control signal and agent participation. This validates that the system reaches its fair, predictable state regardless of how many agents were initially active.

Conclusion and Future Directions

While the IFS framework successfully demonstrates predictable fairness, several avenues for future research remain. Our current RFID sensing model is idealized and does not account for environmental interference like water or physical obstructions. Furthermore, while this study focused on stationary agents (parked cars), applying these proofs to moving agents (such as active ride-share drivers) would introduce complex time-varying dynamics. Finally, future work could explore "$\epsilon$-fairness," allowing for controlled, minor discrepancies between agents to potentially unlock even higher levels of platform efficiency.

Summary updated

Abstract

We consider the design of distributed algorithms that govern the manner in which agents contribute to a social sensing platform. Specifically, we are interested in situations, where fairness among the agents contributing to the platform is needed. A notable example is the platforms operated by public bodies, where fairness is a legal requirement. The design of such distributed systems is challenging due to the fact that we wish to simultaneously realize an efficient social sensing platform but also deliver a predefined quality of service to the agents (for example, a fair opportunity to contribute to the platform). In this article, we introduce iterated function systems (IFSs) as a tool for the design and analysis of systems of this kind. We show how the IFS framework can be used to realize systems that deliver a predictable quality of service to agents, can be used to underpin contracts governing the interaction of agents with the social sensing platform, and which are efficient. To illustrate our design via a use case, we consider a large, high-density network of participating parked vehicles. When awoken by an administrative center, this network proceeds to search for moving missing entities of interest using RFID-based techniques. We regulate which vehicles are actively searching for the moving entity of interest at any point in time. In doing so, we seek to equalize vehicular energy consumption across the network. This is illustrated through simulations of a search for a missing Alzheimer’s patient in Melbourne, Australia. The experimental results are presented to illustrate the efficacy of our system and the predictability of access of agents to the platform independent of initial conditions.
BibTeX
@article{ghosh2020predictability,
  author = {Ramen Ghosh and Jakub Marecek and Wynita M. Griggs and Matheus Souza and Robert N. Shorten},
  title = {{Predictability and Fairness in Social Sensing}},
  journal = {IEEE Internet of Things Journal},
  year = {2020},
  doi = {10.1109/jiot.2021.3085368},
}
Figure