Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Effective deadlock resolution with self-interested partially-rational agents

  • Published:
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

Abstract

This paper pertains to distributed deadlock resolution in settings populated with self-interested bounded-rational autonomous agents. In particular it reports the results of extensive experimentation with 66 agents, each using a deadlock resolution strategy developed and maintained throughout the experiment by a different human decision maker. While from the game-theoretic perspective a simple equilibrium-based solution can be engineered for the problem, it is shown that such a solution fails to hold with bounded-rational agents, even when its principles are thoroughly explained to the individuals that maintain the agents’ strategies. Instead, we show that the system converges to a steady-state, in which the agents use a rich set of different strategies, varying in their performance, as each of them has a different belief regarding its ability to improve, based on the behaviors of the others. To improve system performance, we develop and implement a restructuring heuristic that changes the input each agent receives, as a means of affecting the agents’ decisions to better align with the desired solution. The restructured deadlock presented to each agent is based on former deadlocks it had experienced. Our experiments demonstrate the effectiveness of the restructuring heuristic in facilitating a new steady-state in which the system as a whole substantially improves its performance. The efficiency of the method, in terms of the size of the set of former experiences required for effectively restructuring the agents’ input, is demonstrated through a comparison with a neural network implementation of input restructuring, showing a substantial advantage to the restructuring heuristic.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Abreu, D., Rubinstein, A.: The structure of nash equilibrium in repeated games with finite automata. Econometrica 56(6), 1259–1281 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  2. Agrawal, R., Carey, M., Mcvoy, L.: The performance of alternative strategies for dealing with deadlocks in database management systems. IEEE Trans. Softw. Eng. 13(12), 1348–1363 (1987)

    Article  Google Scholar 

  3. Auer, P., Bianchi, N., Fischer, P.: Finite-time analysis of the multiarmed bandit problem. Mach. Learn. 47(2–3), 235–256 (2002)

    Article  MATH  Google Scholar 

  4. Azaria, A., Rabinovich, Z., Kraus, S., Goldman, C.: Strategic information disclosure to people with multiple alternatives. In: proceedings of AAAI, pp. 594–600 (2011)

  5. Azoulay-Schwartz, R., Kraus, S., Wilkenfeld, J.: Exploitation vs. exploration: choosing a supplier in an environment of incomplete information. Int. J. Decis. Support. Syst. Electron. Commer. 38(1), 1–18 (2004)

    Article  Google Scholar 

  6. Bensalem, S., Fernandez, J., Havelund, K.: Confirmation of deadlock potentials detected by runtime analysis. In: proceedings of PADTAD, pp. 41–50 (2006)

  7. Bo, P., Frechette, G.: The evolution of cooperation in infinitely repeated games: Experimental evidence. Am. Econ. Rev. 101(1), 411–429 (2011)

    Article  Google Scholar 

  8. Chalamish, M., Sarne, D., Kraus, S.: Programming agents as a means of capturing self-strategy. In: proceedings of AAMAS, pp. 1161–1168 (2008)

  9. Chalamish, M., Sarne, D., Lin, R.: Enhancing parking simulations using peer-designed agents. IEEE Trans. Intell. Transp. Syst. 13(4), 1–7 (2012)

    Article  Google Scholar 

  10. Chandy, K., Misra, J., Haas, L.: Distributed deadlock detection. ACM Trans. Comput. Syst. 1(2), 144–156 (1983)

    Article  Google Scholar 

  11. Chavez, A., Kasbah, P. Maes.: An agent marketplace for buying and selling goods In: proceedings of PAAM, pp. 75–90 (1996)

  12. Coffman, E., Elphick, M., Shoshani, A.: System deadlocks. ACM Comput. Surv. 3(2), 67–78 (1971)

    Article  MATH  Google Scholar 

  13. Cybeko, G.: Approximations by superpositions of sigmoidal functions. Math. Control Signals Syst. 5(4), 455–455 (1992)

    Article  Google Scholar 

  14. Cysneiros, L., Yu, E.: Requirements engineering for large-scale multi-agent systems. In: Proceedings of Software Engineering for Large-Scale Multi-Agent Systems, pp. 39–56 (2002)

  15. Duffy, J., Hopkins, E.: Learning, information and sorting in market entry games: Theory and evidence. ESE Discussion Papers 78. University of Edinburgh (2004)

  16. Elmalech, A., Sarne, D.: Evaluating the applicability of peer-designed agents in mechanisms evaluation. In: Proceedings of IAT (2012)

  17. Elmaliach, Y., Kaminka, G.: Robust multi-robot formations under human supervision and control. J. Phys. Agents 2(1), 31 (2008)

    Google Scholar 

  18. Endriss, U.: Monotonic concession protocols for multilateral negotiation. In: Proceedings of AAMAS, pp. 392–399 (2006)

  19. Erez, I., Roth, A.: Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria. Am. Econ. Rev. 88(4), 848–881 (1998)

    Google Scholar 

  20. Ferrari, S.: Smooth function approximation using neural networks. IEEE Trans. Neural Netw. 16(1), 24–38 (2005)

    Article  Google Scholar 

  21. Gasser, M., Goldstein, A., Kaufman, C., Lampson, B.: The digital distributed system security architecture. In: Proceedings of National Computer Security Conference, 305–319 (1989)

  22. Gmytrasiewicz, P., Durfee, E.: Rational coordination in multi-agent environments. J. Auton. Agents. Multi-Agent Syst. 2(4), 319–350 (2000)

    Article  Google Scholar 

  23. Grosz, B., Kraus, S., Talman, S., Stossel, B., Havlin, M.: The influence of social dependencies on decision-making: Initial investigations with a new game. In: proceedings of AAMAS, pp. 780–787 (2004)

  24. Hadad, M., Kraus, S., Hartman, I. B.-A., Rosenfeld, A.: Group planning with time constraints. Ann. Math. Artif. Intell., 1–49 (2013)

  25. Hajaj, C., Hazon, N., Sarne, D., Elmalech, A.: Search more, disclose less. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence (2013)

  26. Hazon, N., Lin, R., Kraus, S.: How to Change a Group’s Collective Decision? In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI’13, pp 198–205. AAAI Press (2013)

  27. Hirayama, K., Toyoda, J.: Forming coalitions for breaking deadlocks. In: proceedings of AAAI, pp. 155–162 (1995)

  28. Hornick, M., Zdonik, S.: A shared, segmented memory system for an object-oriented database. ACM Trans. Inf. Syst. 5(1), 70–95 (1987)

    Article  Google Scholar 

  29. http://neuroph.sourceforge.net

  30. Isloor, S., Marsland, T.: The deadlock problem: An overview. IEEE Comput. 13(9), 58–78 (1980)

    Article  Google Scholar 

  31. Iyengar, S.: The Art of Choosing. Twelve (2010)

  32. Jager, M., Nebel, B.: Decentralized collision avoidance, deadlock detection, and deadlock resolution for multiple mobile robots. In: proceedings of IEEE Intelligent Robots and Systems, pp. 1213–1219 (2001)

  33. Kahneman, D., Tversky, A.: Choices, Values, and Frames. Cambridge University Press (2000)

  34. Kaveh, N., Emmerich, W.: Deadlock detection in distributed object systems. In: proceedings of ACM SIGSOFT Symposium on the Foundations of Software Engineering, pp. 44–51 (2001)

  35. Kshemkalyani, A., Singhal, M.: Efficient detection and resolution of generalized distributed deadlocks. IEEE Trans. Softw. Eng. 20(1), 43–54 (1994)

    Article  Google Scholar 

  36. Lee, S.: Fast, centralized detection and resolution of distributed deadlocks in the generalized model. IEEE Trans. Softw. Eng. 30(9), 561–573 (2004)

    Article  Google Scholar 

  37. Li, P., Agrawal, K., Buhler, J., Chamberlain, R., Lancaster, J.: Deadlock-avoidance for streaming applications with split-join structure: Two case studies. In: proceedings of IEEE Application-specific Systems Architectures and Processors, pp. 333–336 (2010)

  38. Lin, R., Kraus, S., Oshrat, Y., Gal, Y.: Facilitating the evaluation of automated negotiators using peer designed agents. In: proceedings of AAAI, pp. 817–822 (2010)

  39. Mailath, G.: Do people play nash equilibrium? lessons from evolutionary game theory. J. Econ. Lit. 36(3), 1347–1374 (1998)

    Google Scholar 

  40. Manisterski, E., Lin, R., Kraus, S.: Understanding how people design trading agents over time. In: proceedings of AAMAS, pp. 1593–1596 (2008)

  41. Mitchell, D., Merritt, M.: Distributed algorithm for deadlock detection and resolution. In: proceedings of ACM Symposium on Principles of Distributed Computing, pp. 282–284 (1984)

  42. Mohan, C., Lindsay, B., Obermarck, R.: Transaction management in the r* distributed database management system. ACM Trans. Database Syst. 11(4), 378–396 (1986)

    Article  Google Scholar 

  43. Narendra, K.: Adaptive control using neural networks and approximate models. IEEE Trans. Neural Netw. 8(3), 475–485 (1997)

    Article  Google Scholar 

  44. Nguyen, T., Roos, M., Rothe, J.: A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation. Ann. Math. Artif. Intell., 1–26 (2013)

  45. Parameswaran, M., Rui, H., Sayin, S.: A game theoretic model and empirical analysis of spammer strategies. In: proceedings of Collaboration, Electronic Messaging, AntiAbuse and Spam (2010)

  46. Rabin, M.: Psychology and economics. J. Econ. Lit. 36(1), 11–46 (1998)

    MathSciNet  Google Scholar 

  47. Roesler, M., Burkhard, W.: Resolution of deadlocks in object-oriented distributed systems. IEEE Trans. Comput. 38(8), 1212–1224 (1989)

    Article  Google Scholar 

  48. Rosenfeld, A., Kraus, S.: Modeling agents through bounded rationality theories. In: proceedings of IJCAI, pp. 264–271 (2009)

  49. Rosenfeld, A., Kraus, S.: Modeling agents based on aspiration adaptation theory. J. Auton. Agents. Multi-Agent Syst. 24(2), 221–254 (2012)

    Article  Google Scholar 

  50. Sarne, D., Elmalech, A., Grosz, B., Geva, M.: Less is more: Restructuring decisions to improve agent search. In: proceedings of AAMAS, pp. 431–438 (2011)

  51. Selvaraj, S., Ramasamy, R.: An efficient detection and resolution of generalized deadlocks in distributed systems. Int. J. Comput. Appl. 1(1), 1–7 (2010)

    Article  Google Scholar 

  52. Silberschatz, A., Gagne, G., Galvin, P., 8th edn: Operating System Concepts. Wiley (2008)

  53. Simon, A.: Theories of bounded rationality. In: McGuire, C. B., Radner, R. (eds.) Decision and Organization. Amsterdam, North Holland (1972)

    Google Scholar 

  54. Sofy, N., Sarne, D.: On the failure of game theoretic approach for distributed deadlock resolution. In: Proceedings of AAMAS, pp. 1445–1446 (2012)

  55. Srinivasan, S., Rajaram, R.: A decentralized deadlock detection and resolution algorithm for generalized model in distributed systems. Distrib. Parallel Databases 29(4), 261–276 (2011)

    Article  MathSciNet  Google Scholar 

  56. Stirling, W., Goodrich, M., Packard, D.: Satisficing equilibria: a non-classical theory of games and decisions. J. Auton. Agents. Multi-Agent Sys. 5(3), 305–328 (2002)

    Article  MathSciNet  Google Scholar 

  57. Sujit, P., Sinha, A., Ghose, D.: Multiple uav task allocation using negotiation. In: proceedings of AAMAS, pp. 471–478 (2006)

  58. Thaler, R., Sunstein, C.: Nudge: Improving decisions about Health, Wealth, and Happiness. Yale University Press (2008)

  59. Tversky, A., Kahneman, D.: The framing of decisions and the psychology of choice. Sci. 211(4481), 453–458 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  60. Vermorel, J., Mohri, M.: Multi-armed bandit algorithms and empirical evaluation. In: proceedings of European Conference on Machine Learning, pp. 437–448 (2005)

  61. Werbos, P.: Backpropagation through time: what it does and how to do it. Proc. IEEE 78(10), 1550–1560 (1990)

    Article  Google Scholar 

  62. Weyns, D., Boucke, N., Holvoet, T.: A field-based versus a protocol-based approach for adaptive task assignment. J. Auton. Agents. Multi-Agent Sys. 17(2), 288–319 (2008)

    Article  Google Scholar 

  63. Wijngaards, N., Overeinder, B., Steen, M. V., Brazier, F.: Supporting internet-scale multi-agent systems. Data Knowl. Eng. 41, 229–245 (2002)

    Article  MATH  Google Scholar 

  64. Wright, J., Brown, K.: Beyond equilibrium: Predicting human behavior in normal-form games. In: proceedings of AAAI, pp. 901–907 (2010)

  65. Yu, E.: Evolving and messaging decision-making agents. In: proceedings of AGENTS, pp. 449–456 (2001)

Download references

Author information

Authors and Affiliations

  1. Bar-Ilan University, Ramat-Gan, 52900, Israel

    Nadav Sofy & David Sarne

Authors
  1. Nadav Sofy
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David Sarne
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to David Sarne.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sofy, N., Sarne, D. Effective deadlock resolution with self-interested partially-rational agents. Ann Math Artif Intell 72, 225–266 (2014). https://doi.org/10.1007/s10472-014-9422-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10472-014-9422-x

Keywords

Search

Navigation