Cow-path games : tactical strategies to search for scarce resources

[摘要] This thesis investigates search scenarios in which multiple mobile, self-interested agents, cows in our case, compete to capture targets. The problems considered in this thesis address search strategies that reflect (i) the need to efficiently search for targets given a prior on their location, and (ii) an awareness that the environment in which searching takes place contains other self-interested agents. Surprisingly, problems that feature these elements are largely under-represented in the literature. Granted, the scenarios of interest inherit the challenges and complexities of search theory and game theory alike. Undeterred, this thesis makes a contribution by considering competitive search problems that feature a modest number of agents and take place in simple environments. These restrictions permit an in-depth analysis of the decision-making involved, while preserving interesting options for strategic play. In studying these problems, we report a number of fundamental competitive search game results and, in so doing, begin to populate a toolbox of techniques and results useful for tackling more scenarios. The thesis begins by introducing a collection of problems that fit within the competitive search game framework. We use the example of taxi systems, in which drivers compete to find passengers and garner fares, as a motivational example throughout. Owing to connections with a well-known problem, called the Cow-Path Problem, the agents of interest, which could represent taxis or robots depending on the scenario, will be referred to as cows. To begin, we first consider a one-sided search problem in which a hungry cow, left to her own devices, tries to efficiently find a patch of clover located on a ring. Subsequently, we consider a game in which two cows, guided only by limited prior information, compete to capture a target. We begin by considering a version in which each cow can turn at most once and show this game admits an equilibrium. A dynamic-programming-based approach is then used to extend the result to games featuring at most a finite number of turns. Subsequent chapters consider games that add one or more elements to this basic construct. We consider games where one cow has additional information on the target;;s location, and games where targets arrive dynamically. For a number of these variants, we characterize equilibrium search strategies. In settings where this proves overly difficult, we characterize search strategies that provide performance within a known factor of the utility that would be achieved in an equilibrium. The thesis closes by highlighting the key ideas discussed and outlining directions of future research.

[发布机构] Massachusetts Institute of Technology