Quadratic Scaling Constraints in Proximity Tracing Networks

40 concepts24 papers2 proposals

Imagine a crowded room where individuals want to exchange digital contact information using a smartphone app. If only half of the people in the room have the app installed, what is the probability that any given encounter between two people will be successfully logged?

Intuition might suggest 50%, but the actual probability is 25%.

This simple mathematical reality lies at the heart of why peer-to-peer digital contact tracing (DCT) systems struggle to succeed. As explored by Pahwa et al. in Contact Tracing: Holistic Solution Beyond Bluetooth, proximity-based detection systems require mutual adoption. For an encounter to be recorded, both the infected individual (the transmitter) and the exposed individual (the receiver) must be active users of the system. If either party lacks the app, the interaction vanishes from the digital record.

Consequently, if the adoption rate of a population is $p$, the probability of capturing a bilateral encounter scales as $p^2$. This is known as the quadratic adoption penalty, a network effect constraint that governs the efficacy of decentralized proximity networks.

The Mathematical Toll of Quadratic Scaling

The $p^2$ relationship creates a steep hurdle for public health interventions. In Automated Contact Tracing: a game of big numbers in the time of COVID-19, Paul et al. demonstrate how rapidly system utility degrades when adoption is voluntary and incomplete. If a campaign successfully enrolls 40% of a population, the app will capture a mere 16% of total transmission chains ($0.40 \times 0.40 = 0.16$), leaving 84% of exposures completely undetected.

Population Adoption (p)  --->  Encounter Coverage (p²)
[████░░░░░░] 40%               [█░░░░░░░░░] 16%
[██████░░░░] 60%               [███░░░░░░░] 36%
[████████░░] 80%               [██████░░░░] 64%

However, this mathematical constraint also implies that the utility of the network scales exponentially once adoption rises. As noted by Salathé et al. in Early evidence of effectiveness of digital contact tracing for SARS-CoV-2 in Switzerland, even modest linear increases in population uptake yield disproportionately large improvements in covered encounters.

This non-linear payoff was empirically validated by Wymant et al. in The epidemiological impact of the NHS COVID-19 app, where data showed that a 1% increase in user adoption could reduce overall case counts by 0.8% to 2.3%, illustrating the powerful compounding effect of high-density networks.

The Critical Mass Threshold and Efficacy Loops

Because of the quadratic penalty, peer-to-peer tracing networks suffer from a severe "cold-start" problem: the system provides almost zero utility to early adopters. Epidemiological frameworks published by Adans-Dester et al. in Can mHealth Technology Help Mitigate the Effects of the COVID-19 Pandemic? suggest that a system requires an adoption threshold of roughly 80% to suppress an epidemic independently. Other researchers, including Buchanan et al. in Review and Critical Analysis of Privacy-preserving Infection Tracking and Contact Tracing and Li et al. in What Makes People Install a COVID-19 Contact-Tracing App?, place the minimum critical mass for public health utility at 60%.

When adoption falls below this critical mass, it triggers a destructive psychological feedback loop. As documented by Montagni et al. in Health Care Students’ Knowledge of and Attitudes, Beliefs, and Practices Toward the French COVID-19 App, users frequently perceive the system as ineffective during its early stages because low initial uptake means few exposure alerts are generated. This perceived lack of practical value discourages new sign-ups, reinforcing low adoption and trapping the system below its functional threshold.

When voluntary participation stalls in this manner, the technological intervention fails to break transmission chains, forcing societies to rely on blunter, more economically damaging measures like broad lockdowns, as argued by Altmann et al. in Acceptability of app-based contact tracing for COVID-19: Cross-country survey evidence.

Breaking the Quadratic Constraint

To bypass the brutal mathematics of $p^2$, recent research focuses on architectural modifications that shift the system from quadratic to linear scaling.

Infrastructure-Based Tracing

Instead of tracking person-to-person interactions, networks can track person-to-infrastructure interactions. In Listening to bluetooth beacons for epidemic risk mitigation, Barthe et al. introduced PanCast, a system utilizing fixed Bluetooth beacons placed in physical locations. Because a single user's interaction with a static beacon can facilitate exposure notifications for anyone else visiting that space, the probability of capturing an encounter scales linearly ($p$) rather than quadratically ($p^2$). This allows the system to maintain high public health utility even when only a small fraction of the population utilizes the technology.

Passive Sensing

Another way to eliminate the adoption barrier is to remove the requirement for active user installation entirely. Trivedi et al. developed WiFiTrace: Network-based Contact Tracing for Infectious Diseases Using Passive WiFi Sensing, which leverages existing enterprise WiFi logs to passively reconstruct device trajectories. By operating entirely on the network side, it bypasses the voluntary opt-in hurdle, instantly achieving high network density within covered environments.

Asymmetric Tracing Protocols

To accommodate users who cannot or will not broadcast signals, Abtahi proposed DP-ACT: Decentralized Privacy-Preserving Asymmetric Digital Contact Tracing. This protocol allows "passive" users to participate simply by logging the IDs of active broadcasters they encounter. If a passive user tests positive, they can upload these recorded IDs, enabling the network to capture interaction data that traditional, symmetric peer-to-peer protocols would miss.

Linear-Value Features

To solve the cold-start problem for early adopters, the authors of PACT: Privacy-Sensitive Protocols And Mechanisms for Mobile Contact Tracing, led by Chan et al., suggested decoupling user utility from network density. By incorporating one-way, location-specific public health broadcasts into proximity apps, the system provides immediate, linear value to users (e.g., area risk updates) even when overall peer-to-peer adoption rates are low. This immediate utility incentivizes early adoption, helping the network cross the critical mass threshold needed for quadratic tracing to become effective.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_quadratic_adoption_scaling_ad5cd680,
  title = {quadratic adoption scaling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-adoption-scaling/rdr_ad5cd680efec4766b137c6f8d0b472a2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_quadratic_adoption_scaling_ad5cd680_v1,
  title = {quadratic adoption scaling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-adoption-scaling/rdr_ad5cd680efec4766b137c6f8d0b472a2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake