Prize Collecting Multiagent Orienteering: Price of Anarchy Bounds and Solution Methods

Timothy Murray, Jugal Garg, Rakesh Nagi

Research output: Contribution to journalArticlepeer-review

Abstract

We propose and address a new variation of the team orienteering problem (TOP) in which all members of the team are independent self-interested agents. The prize-collecting nature emanates from the fact that the prize available at a node of the traversal graph can be collected only by a single visiting agent. The problem is motivated by situations in which team members (agents) must accomplish tasks toward a common goal but are unable to communicate, such as a fleet of surveillance drones operating in a communication denied area or with remote pilots operating independently. We explore three policies for minimizing the amount of inefficiency these self-interested agents can bring into the situation. We analyze these policies in a game-theoretic framework and show upper bounds on the Price of Anarchy (PoA) ranging from ≈1.582 to unbounded depending on the policy, network type, and the number of players k. This is done by extending well-known PoA bounds for valid utility systems to a leader-follower setting. The PoA also depends on the behavior of the agents, which could not have goodwill toward other agents. In many cases, we are able to provide examples that establish the tightness of the bounds. Finally, solution methods are provided for each of these policies. Numerical results computed by these solution methods are then presented and compared with the optimal centrally coordinated solutions.

Original languageEnglish (US)
JournalIEEE Transactions on Automation Science and Engineering
DOIs
StateAccepted/In press - 2020

Keywords

  • Computational modeling
  • Delays
  • Drones
  • Game theory
  • Games
  • multiagent systems
  • Price of Anarchy (PoA)
  • prize collection.
  • Routing
  • Surveillance
  • Task analysis

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Prize Collecting Multiagent Orienteering: Price of Anarchy Bounds and Solution Methods'. Together they form a unique fingerprint.

Cite this