Affiliations: Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel. E-mail: {igor.rochlin,david.sarne}@gmail.com | Department of Electrical Engineering, Columbia University, New York, NY, USA. E-mail: [email protected]
Note: [] Corresponding author.
Abstract: Motivated by applications in Dynamic Spectrum Access Networks, we focus on a system in which a few agents are engaged in a costly individual exploration process where each agent's benefit is determined according to the minimum obtained value. Such an exploration pattern is applicable to many systems, including shipment and travel planning. This paper formally introduces and analyzes a sequential variant of the general model. According to that variant, only a single agent engages in exploration at any given time, and when an agent initiates its exploration, it has complete information about the minimum value obtained by the other agents so far. We prove that the exploration strategy of each agent, according to the equilibrium of the resulting Stackelberg game, is reservation-value based, and show how the reservation values can be calculated. We also analyze the agents' expected-benefit maximizing exploration strategies when they are fully cooperative (i.e., when they aim to maximize the expected joint benefit). The equilibrium strategies and the expected benefit of each agent are illustrated using a synthetic homogeneous environment, thereby demonstrating the properties of this new exploration scheme and the benefits of cooperation.
Keywords: Multi-agent exploration, multilateral search, cooperation, dynamic spectrum access networks, game theory
