Decentralized Network Interdiction Games

Abstract

This project established the theoretical and computational foundation for a new class of games, termed as the multi-interdictor network games(MINGs). Such games naturally arise in the context of various military and security applications in which multiple interdictors with differing objectives operating on a common network. Within the general class of MINGs, we proved existence of Nash equilibria for specific subclasses of such games, including the shortest-path and maximum-flow multi-interdictor network games, and developed scalable algorithms to compute such equilibria. In addition, we provided theoretical bounds on the worst-case efficiency loss of equilibria for the shortest-path games, with such loss caused by the lack of coordination among noncooperative interdictors, and prosed an empirical approach utilizing decentralized algorithms to study the average-case efficiency loss. Finally, we developed convergent decentralized algorithms based on the connection between the class of potential games (to which the MINGs belong) and optimization that will advance the computation of large-scale optimization problems.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 31, 2015
Accession Number
AD1009259

Entities

People

  • Andrew L. Liu
  • Nelson U. Uhan

Organizations

  • Purdue University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Science
  • Computations
  • Computer Programming
  • Efficiency
  • Electronic Mail
  • Game Theory
  • Industrial Engineering
  • Interdiction
  • Linear Programming
  • Mathematical Programming
  • Microarchitecture
  • Operating Systems
  • Operations Research
  • Optimization
  • Security
  • Systems Engineering

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Game Theory.
  • Neural Network Machine Learning.