Joint Search with Self-Interested Agents and the Failure

Abstract: This paper considers the problem of autonomous agents that need to pick one of several options, who are all rational but differ in their value, which is a priori uncertain and can be revealed for a cost. The agents thus need to weigh the benefits of revealing further values against the associated costs. The paper addresses the problem in its multi-agent joint form, such that not a single but rather a group of agents may benefit from the fruits of the search. The paper formally introduces and analyzes the joint search problem, when carried out fully distributedly, and determines the strategies to be used by the agents both when fully cooperative and when self-interested. The analysis is used to demonstrate that changes which can easily be proved to be beneficial with fully cooperative agents’ search (e.g., extension of the search horizon, increase in the number of cooperating agents) can actually degrade individual and overall expected utility in the self-interested case. The analysis both contributes to the advancement of joint search theories and offers important insights for system designers, enabling them to determine the mechanisms that should be included in the markets and systems they design.