Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Bribery in multiple-adversary path-disruption games is hard for the second level of the polynomial hierarchy
Marple A., Rey A., Rothe J.  AAMAS 2014 (Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems, Paris, France, May 5-9, 2014)1375-1376.2014.Type:Proceedings
Date Reviewed: Jun 25 2015

Nondeterministic polynomial time (NP) and NP-completeness are by now widely familiar notions within the general computer science (CS) community. Every CS undergraduate knows many examples of NP-complete problems. In contrast, most computer science professors, if stopped on the street, could not name even a single, complete problem for the next level of the polynomial hierarchy, . ( is the class of languages that can be accepted by an NP machine allowed access to a unit-cost satisfiability subroutine.)

This state of affairs is unfortunate since pinpointing what class a problem is complete for is one central way that the flavor of the problem is revealed and its complexity understood. For example, at their core, NP-complete problems are about polynomially bounded ∃ quantification, and at their core, problems are about a polynomially bounded ∃ ∀ quantifier sequence. Although proving problems complete for levels of the polynomial hierarchy beyond NP (and coNP, the class of languages whose complements are in NP) is indeed often more difficult than proving problems complete for NP (and coNP), it might surprise most people to know that more than 80 natural problems have been classified as complete for higher levels of the polynomial hierarchy (see the compendium [1]).

This paper studies the problem of bribery in multiple-adversary path-disruption games. Very loosely put, this problem involves evaluating whether there exists a bribing action (the buying up of a number of priced nodes in a graph) with at most a certain cost such that one has precluded every possible coalition not involving the bribed nodes from appropriately disrupting the existence of paths between various source-target node pairs. A 2011 paper by two of this paper’s authors implied that this problem was NP-hard and also noted that it belongs to [2]. The interesting paper under review removes this uncertainty about the exact complexity classification of this problem by establishing that the problem is many-one polynomial-time complete for .

Reviewer:  Lane A. Hemaspaandra Review #: CR143556 (1509-0816)
1) Schaefer, M.; Umans, C. Completeness in the polynomial-timehierarchy: part I: a compendium. SIGACT News 33, 3(2002), 32–49. See also the updated version: http://ovid.cs.depaul.edu/documents/phcom.ps.
2) Ray, A.; Rothe, J. Bribery in path-disruption games. In Proc. of the 2nd Int. Conf. on Algorithmic Decision Theory (Piscataway, NJ). Springer-Verlag, 2011, 247–261.
Bookmark and Share
  Reviewer Selected
 
 
Multiagent Systems (I.2.11 ... )
 
 
Economics (J.4 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Multiagent Systems": Date
Engineering intelligent hybrid multi-agent systems
Khosla R., Dillon T. (ed), Kluwer Academic Publishers, Norwell, MA, 1998. Type: Book (9780792399827)
Aug 1 1998
Linguistic geometry: from search to construction
Stilman B., Kluwer Academic Publishers, Norwell, MA, 2000.  395, Type: Book (9780792377382)
Jan 1 2001
 Transactional agents: towards a robust multi-agent system
Nagi K., Springer-Verlag New York, Inc., New York, NY, 2002.  205, Type: Book (9783540430469)
Apr 13 2004
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy