Increasing Threshold Search for Best-Valued Agents


  • David Sarne Bar-Ilan University
  • Simon Shamoun City University of New York
  • Eli Rata Bar Ilan University



Multiagent Systems, Sequential Decision Making, eCommerce


This paper investigates search techniques for multi-agent settings in which the most suitable agent, according to given criteria, needs to be found. In particular, it considers the case where the searching agent incurs a cost for learning the value of an agent and the goal is to minimize the expected overall cost of search by iteratively increasing the extent of search. This kind of search is applicable to various domains, including auctions, first responders, and sensor networks. Using an innovative transformation of the extents-based sequence to a probability-based one, the optimal sequence is proved to consist of either a single search iteration or an infinite sequence of increasing search extents. This leads to a simplified characterization of the the optimal search sequence from which it can be derived. This method is also highly useful for legacy economic-search applications, where all agents are considered suitable candidates and the goal is to optimize the search process as a whole. The effectiveness of the method for both best-valued search and economic search is demonstrated numerically using a synthetic environment.




How to Cite

Sarne, D., Shamoun, S., & Rata, E. (2010). Increasing Threshold Search for Best-Valued Agents. Proceedings of the AAAI Conference on Artificial Intelligence, 24(1), 848-853.



AAAI Technical Track: Multiagent Systems