Increasing Threshold Search for Best-Valued Agents

David Sarne, Simon Shamoun, Eli RataAAAI 2010 · DOI

Abstract

In multi-agent systems, identifying the "best" agent—such as the lowest-cost contractor or the highest-performing sensor—often involves significant search costs. This paper introduces an "Increasing Threshold Search" strategy designed to minimize the expected total cost of discovery. By focusing on a distribution-independent "reservation probability," the authors provide a robust framework that consistently outperforms standard networking heuristics.

Introduction: The Search Cost Dilemma

Imagine a government agency seeking the most competitive bid from a vast pool of contractors. Evaluating every single bid is prohibitively expensive due to variable costs (time and resources spent per bid). Conversely, setting a threshold that is too restrictive might yield no results, wasting the fixed costs associated with initiating the search round.

This creates a fundamental trade-off between:

  1. Fixed Costs ($\alpha$): The overhead of re-issuing a call for bids or initiating a new search round.
  2. Variable Costs ($\beta$): The cost of processing each individual response within a given threshold.

The challenge lies in determining the optimal sequence of thresholds to minimize the total expected cost.

The Increasing Threshold Strategy

The core innovation of this research is the shift from physical thresholds (e.g., dollar amounts) to a mathematical abstraction: the reservation probability ($P$). This represents the probability that an agent's value falls within the current search extent.

The authors demonstrate that the optimal strategy involves an infinite sequence of increasing thresholds where each round targets the same marginal probability $P^*$. This $P^*$ is derived based on the fixed cost $\alpha$, the variable cost function $\beta$, and the total number of agents $N$.

Crucially, this optimal reservation probability is distribution-independent. Whether agent values follow a Gaussian, Uniform, or Power Law distribution, the optimal $P^*$ remains identical. The specific distribution is only required at the final step to map $P^*$ back to real-world threshold values using an inverse Cumulative Distribution Function (CDF).

Experimental Evaluation

The proposed method was evaluated against three common heuristics used in networking:

  • Two-Step Rule: A simple two-round process (one limited, one exhaustive).
  • Fixed-Step Rule: Increasing the threshold by a constant amount each round.
  • California Split Rule: Doubling the search extent in each successive round.
Comparison of the Optimal Increasing Threshold method against common heuristics across three cost settings (A, B, C).

As shown in the experimental results, the "Optimal Increasing Threshold" method consistently maintains a lower and more stable cost curve as the number of agents increases. In high-fixed-cost scenarios (Setting C), the gap between the optimal strategy and heuristics like the Fixed-Step rule becomes particularly pronounced, highlighting the method's efficiency in preventing "bidder explosion" in large populations.

Beyond finding the single "best" agent, this thresholding logic can enhance traditional "Economic Search" (where the goal is to find any agent that meets a "good enough" criteria). By using an iterative expanding search to prune the population first, the overall cost of sequential sampling can be significantly reduced.

Performance comparison between iterative expanding search and traditional economic sequential search for varying agent counts (N).

The data indicates that as the ratio of fixed to variable costs ($\alpha/\beta(1)$) increases, the iterative expanding search becomes increasingly advantageous over standard sequential methods, especially as the number of agents ($N$) grows.

Conclusion and Future Work

The Increasing Threshold Search provides a mathematically rigorous yet practical solution for cost-effective agent discovery. While the current model assumes known, independent, and identically distributed (I.I.D.) agent values, it sets a strong foundation for future work. Potential extensions include adapting the model for non-stationary distributions, correlated agent values, or competitive environments where multiple searchers vie for the same top-tier agents.

Summary updated

BibTeX
@inproceedings{sarne2010increasing,
  author = {David Sarne and Simon Shamoun and Eli Rata},
  title = {{Increasing Threshold Search for Best-Valued Agents}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7628},
}
Figure