IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v288y2021i3p1036-1052.html
   My bibliography  Save this article

A polynomial-time method to compute all Nash equilibria solutions of a general two-person inspection game

Author

Listed:
  • Deutsch, Yael

Abstract

We consider a two-person nonzero-sum simultaneous inspection game that takes place at multiple sites. The inspector has a limited inspection resource. She needs to decide which sites to inspect, and with how much effort, while adhering also to local restrictions on the permitted inspections levels at the sites. The inspectee has several employees who work on his behalf. He needs to decide how to distribute them across the sites, and how they should act there. Computation of Nash equilibria is challenging for this sort of games. Still, we develop a linear-time algorithm that determines all Nash equilibria solutions of the game, and provide explicit (easily computable) expressions for all possible Nash equilibria. We then derive some managerial insights by applying the algorithm to several examples, and examining the Nash equilibria, including an outcome that an increase in the inspection resource may induce the inspectee to cooperate more at sites without increasing the inspection levels at them.

Suggested Citation

  • Deutsch, Yael, 2021. "A polynomial-time method to compute all Nash equilibria solutions of a general two-person inspection game," European Journal of Operational Research, Elsevier, vol. 288(3), pages 1036-1052.
  • Handle: RePEc:eee:ejores:v:288:y:2021:i:3:p:1036-1052
    DOI: 10.1016/j.ejor.2020.06.032
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720305750
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2020.06.032?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. D. W. Blackett, 1958. "Pure strategy solutions of blotto games," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 5(2), pages 107-109, June.
    2. Britta Hoyer & Kris De Jaegher, 2016. "Strategic Network Disruption and Defense," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 18(5), pages 802-830, October.
    3. Bernhard von Stengel, 2016. "Recursive Inspection Games," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 935-952, August.
    4. Reyniers, Diane J. & Tapiero, Charles S., 1995. "Contract design and the control of quality in a conflictual environment," European Journal of Operational Research, Elsevier, vol. 82(2), pages 373-382, April.
    5. Brian Roberson & Dmitriy Kvasov, 2012. "The non-constant-sum Colonel Blotto game," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 51(2), pages 397-433, October.
    6. Vassili Kolokoltsov, 2017. "The Evolutionary Game of Pressure (or Interference), Resistance and Collaboration," Mathematics of Operations Research, INFORMS, vol. 42(4), pages 915-944, November.
    7. Powell, Robert, 2007. "Allocating Defensive Resources with Private Information about Vulnerability," American Political Science Review, Cambridge University Press, vol. 101(4), pages 799-809, November.
    8. Martin Shubik & Robert James Weber, 1981. "Systems defense games: Colonel blotto, command and control," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 28(2), pages 281-287, June.
    9. Avenhaus, Rudolf & Canty, Morton & Marc Kilgour, D. & von Stengel, Bernhard & Zamir, Shmuel, 1996. "Inspection games in arms control," European Journal of Operational Research, Elsevier, vol. 90(3), pages 383-394, May.
    10. Deutsch, Yael & Golany, Boaz & Rothblum, Uriel G., 2011. "Determining all Nash equilibria in a (bi-linear) inspection game," European Journal of Operational Research, Elsevier, vol. 215(2), pages 422-430, December.
    11. Sanjeev Goyal & Adrien Vigier, 2014. "Attack, Defence, and Contagion in Networks," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 81(4), pages 1518-1542.
    12. Stamatios Katsikas & Vassili Kolokoltsov & Wei Yang, 2016. "Evolutionary Inspection and Corruption Games," Games, MDPI, vol. 7(4), pages 1-25, October.
    13. Yael Deutsch & Boaz Golany, 2016. "Multiple agents finitely repeated inspection game with dismissals," Annals of Operations Research, Springer, vol. 237(1), pages 7-26, February.
    14. Marlin U. Thomas & Yair Nisgav, 1976. "An infiltration game with time dependent payoff," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 23(2), pages 297-302, June.
    15. Deutsch, Yael & Goldberg, Noam & Perlman, Yael, 2019. "Incorporating monitoring technology and on-site inspections into an n-person inspection game," European Journal of Operational Research, Elsevier, vol. 274(2), pages 627-637.
    16. Hohzaki, Ryusuke, 2007. "An inspection game with multiple inspectees," European Journal of Operational Research, Elsevier, vol. 178(3), pages 894-906, May.
    17. Avenhaus, Rudolf & Canty, Morton John, 2005. "Playing for time: A sequential inspection game," European Journal of Operational Research, Elsevier, vol. 167(2), pages 475-492, December.
    18. Garrec, Tristan, 2019. "Continuous patrolling and hiding games," European Journal of Operational Research, Elsevier, vol. 277(1), pages 42-51.
    19. Steve Alpern & Thomas Lidbetter, 2013. "Mining Coal or Finding Terrorists: The Expanding Search Paradigm," Operations Research, INFORMS, vol. 61(2), pages 265-279, April.
    20. Powell, Robert, 2009. "Sequential, nonzero-sum "Blotto": Allocating defensive resources prior to attack," Games and Economic Behavior, Elsevier, vol. 67(2), pages 611-615, November.
    21. Russell Golman & Scott Page, 2009. "General Blotto: games of allocative strategic mismatch," Public Choice, Springer, vol. 138(3), pages 279-299, March.
    22. V. J. Baston & F. A. Bostock, 1991. "A generalized inspection game," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(2), pages 171-182, April.
    23. Michael Maschler, 1966. "A price leadership method for solving the inspector's non‐constant‐sum game," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 13(1), pages 11-33, March.
    24. John Canty, Morton & Rothenstein, Daniel & Avenhaus, Rudolf, 2001. "Timely inspection and deterrence," European Journal of Operational Research, Elsevier, vol. 131(1), pages 208-223, May.
    25. repec:oup:restud:v:81:y:2014:i:4:p:1518-1542. is not listed on IDEAS
    26. Toke S. Aidt, 2003. "Economic analysis of corruption: a survey," Economic Journal, Royal Economic Society, vol. 113(491), pages 632-652, November.
    27. Brian Roberson, 2006. "The Colonel Blotto game," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 29(1), pages 1-24, September.
    28. Arvind K. Jain, 2001. "Corruption: A Review," Journal of Economic Surveys, Wiley Blackwell, vol. 15(1), pages 71-121, February.
    29. Dziubiński, Marcin & Goyal, Sanjeev, 2013. "Network design and defence," Games and Economic Behavior, Elsevier, vol. 79(C), pages 30-43.
    30. Osorio, Antonio, 2013. "The lottery Blotto game," Economics Letters, Elsevier, vol. 120(2), pages 164-166.
    31. Yael Deutsch & Boaz Golany & Noam Goldberg & Uriel G. Rothblum, 2013. "Inspection games with local and global allocation bounds," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(2), pages 125-140, March.
    32. Yael Deutsch & Boaz Golany, 2018. "The effect of risk aversion on the outcomes of inspection games," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 69(5), pages 645-660, May.
    33. Yael Deutsch & Boaz Golany, 2016. "Multiple agents finitely repeated inspection game with dismissals," Annals of Operations Research, Springer, vol. 237(1), pages 7-26, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Johnston, Iain G., 2022. "Optimal strategies in the fighting fantasy gaming system: Influencing stochastic dynamics by gambling with limited resource," European Journal of Operational Research, Elsevier, vol. 302(3), pages 1272-1281.
    2. Mahajan, Aseem & Pongou, Roland & Tondji, Jean-Baptiste, 2023. "Supermajority politics: Equilibrium range, policy diversity, utilitarian welfare, and political compromise," European Journal of Operational Research, Elsevier, vol. 307(2), pages 963-974.
    3. Cao, Yiyin & Dang, Chuangyin & Xiao, Zhongdong, 2022. "A differentiable path-following method to compute subgame perfect equilibria in stationary strategies in robust stochastic games and its applications," European Journal of Operational Research, Elsevier, vol. 298(3), pages 1032-1050.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Deutsch, Yael & Goldberg, Noam & Perlman, Yael, 2019. "Incorporating monitoring technology and on-site inspections into an n-person inspection game," European Journal of Operational Research, Elsevier, vol. 274(2), pages 627-637.
    2. Dan Kovenock & Brian Roberson, 2018. "The Optimal Defense Of Networks Of Targets," Economic Inquiry, Western Economic Association International, vol. 56(4), pages 2195-2211, October.
    3. Ederlina Ganatuin‐Nocon & Tyrone Ang, 2020. "Revisiting inspection game and inspector leadership through reaction networks," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(6), pages 438-452, September.
    4. Stamatios Katsikas & Vassili Kolokoltsov & Wei Yang, 2016. "Evolutionary Inspection and Corruption Games," Games, MDPI, vol. 7(4), pages 1-25, October.
    5. Subhasish M Chowdhury & Dan Kovenock & David Rojo Arjona & Nathaniel T Wilcox, 2021. "Focality and Asymmetry in Multi-Battle Contests," The Economic Journal, Royal Economic Society, vol. 131(636), pages 1593-1619.
    6. Guzmán, Cristóbal & Riffo, Javiera & Telha, Claudio & Van Vyve, Mathieu, 2022. "A sequential Stackelberg game for dynamic inspection problems," European Journal of Operational Research, Elsevier, vol. 302(2), pages 727-739.
    7. Dan J. Kovenock & Brian Roberson, 2015. "The Optimal Defense of Network Connectivity," CESifo Working Paper Series 5653, CESifo.
    8. Dan Kovenock & Brian Roberson & Roman M. Sheremeta, 2019. "The attack and defense of weakest-link networks," Public Choice, Springer, vol. 179(3), pages 175-194, June.
    9. Nakao, Keisuke, 2017. "Denial vs. Punishment: Strategies Shape War, but War Itself Affects Strategies," MPRA Paper 81418, University Library of Munich, Germany.
    10. Boix-Adserà, Enric & Edelman, Benjamin L. & Jayanti, Siddhartha, 2021. "The multiplayer Colonel Blotto game," Games and Economic Behavior, Elsevier, vol. 129(C), pages 15-31.
    11. Subhasish Chowdhury & Dan Kovenock & Roman Sheremeta, 2013. "An experimental investigation of Colonel Blotto games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 52(3), pages 833-861, April.
    12. Duffy, John & Matros, Alexander, 2017. "Stochastic asymmetric Blotto games: An experimental study," Journal of Economic Behavior & Organization, Elsevier, vol. 139(C), pages 88-105.
    13. Scott Macdonell & Nick Mastronardi, 2015. "Waging simple wars: a complete characterization of two-battlefield Blotto equilibria," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 58(1), pages 183-216, January.
    14. Fandel, G. & Trockel, J., 2013. "Avoiding non-optimal management decisions by applying a three-person inspection game," European Journal of Operational Research, Elsevier, vol. 226(1), pages 85-93.
    15. Guzman, Cristobal & Riffo, Javiera & Telha, Claudio & Van Vyve, Mathieu, 2021. "A Sequential Stackelberg Game for Dynamic Inspection Problems," LIDAM Discussion Papers CORE 2021036, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    16. Antoine Pietri, 2017. "Les modèles de « rivalité coercitive » dans l’analyse économique des conflits," Revue d'économie politique, Dalloz, vol. 127(3), pages 307-352.
    17. Enric Boix-Adser`a & Benjamin L. Edelman & Siddhartha Jayanti, 2020. "The Multiplayer Colonel Blotto Game," Papers 2002.05240, arXiv.org, revised May 2021.
    18. Hunt, Kyle & Zhuang, Jun, 2024. "A review of attacker-defender games: Current state and paths forward," European Journal of Operational Research, Elsevier, vol. 313(2), pages 401-417.
    19. Dong, Xiaoqing & Li, Chaolin & Li, Ji & Wang, Jia & Huang, Wantao, 2010. "A game-theoretic analysis of implementation of cleaner production policies in the Chinese electroplating industry," Resources, Conservation & Recycling, Elsevier, vol. 54(12), pages 1442-1448.
    20. Yael Deutsch & Boaz Golany, 2019. "Securing Gates of a Protected Area: A Hybrid Game and Queueing Theory Modeling Approach," Decision Analysis, INFORMS, vol. 16(1), pages 31-45, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:288:y:2021:i:3:p:1036-1052. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.