IDEAS home Printed from https://ideas.repec.org/a/wsi/acsxxx/v09y2006i04ns0219525906000884.html
   My bibliography  Save this article

Advances In Distributed Optimization Using Probability Collectives

Author

Listed:
  • DAVID H. WOLPERT

    (NASA Ames Research Center, Moffett Field, CA 94035, USA)

  • CHARLIE E. M. STRAUSS

    (Bioscience Division, Los Alamos National Laboratory, USA)

  • DEV RAJNARAYAN

    (Department of Aeronautics/Astronautics, Stanford University, Stanford, CA 94305, USA)

Abstract

Recent work has shown how information theory extends conventional full-rationality game theory to allow bounded rational agents. The associated mathematical framework can be used to solve distributed optimization and control problems. This is done by translating the distributed problem into an iterated game, where each agent's mixed strategy (i.e. its stochastically determined move) sets a different variable of the problem. So the expected value of the objective function of the distributed problem is determined by the joint probability distribution across the moves of the agents. The mixed strategies of the agents are updated from one game iteration to the next so as to converge on a joint distribution that optimizes that expected value of the objective function. Here, a set of new techniques for this updating is presented. These and older techniques are then extended to apply to uncountable move spaces. We also present an extension of the approach to include (in)equality constraints over the underlying variables. Another contribution is that we show how to extend the Monte Carlo version of the approach to cases where some agents have no Monte Carlo samples for some of their moves, and derive an "automatic annealing schedule".

Suggested Citation

  • David H. Wolpert & Charlie E. M. Strauss & Dev Rajnarayan, 2006. "Advances In Distributed Optimization Using Probability Collectives," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 9(04), pages 383-436.
    • Handle: RePEc:wsi:acsxxx:v:09:y:2006:i:04:n:s0219525906000884
    DOI: 10.1142/S0219525906000884
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S0219525906000884
    Download Restriction: Access to full text is restricted to subscribers
    File URL: https://libkey.io/10.1142/S0219525906000884?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. Fudenberg, Drew & Levine, David, 1998. "Learning in games," European Economic Review, Elsevier, vol. 42(3-5), pages 631-639, May.
    2. Drew Fudenberg & David K. Levine, 1998. "The Theory of Learning in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262061945, April.
    3. Drew Fudenberg & Jean Tirole, 1991. "Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262061414, April.
    Full references (including those not matched with items on IDEAS)

    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. Jehiel, Philippe, 2005. "Analogy-based expectation equilibrium," Journal of Economic Theory, Elsevier, vol. 123(2), pages 81-104, August.
    2. Federico Echenique & Aaron Edlin, 2001. "Mixed Equilibria in Games of Strategic Complements are Unstable," Levine's Working Paper Archive 563824000000000161, David K. Levine.
    3. Harri Ehtamo & Simo Heliövaara & Timo Korhonen & Simo Hostikka, 2010. "Game Theoretic Best-Response Dynamics For Evacuees' Exit Selection," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 13(01), pages 113-134.
    4. Oyarzun, Carlos & Sarin, Rajiv, 2013. "Learning and risk aversion," Journal of Economic Theory, Elsevier, vol. 148(1), pages 196-225.
    5. Mészáros, József, 2005. "A társadalombiztosítási nyugdíjrendszerek mint közjószágok [Social-insurance pension systems as public goods]," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(3), pages 275-288.
    6. David Ettinger & Philippe Jehiel, 2004. "Towards a Theory of Deception," Levine's Bibliography 122247000000000247, UCLA Department of Economics.
    7. Marden, Jason R. & Shamma, Jeff S., 2015. "Game Theory and Distributed Control****Supported AFOSR/MURI projects #FA9550-09-1-0538 and #FA9530-12-1-0359 and ONR projects #N00014-09-1-0751 and #N0014-12-1-0643," Handbook of Game Theory with Economic Applications,, Elsevier.
    8. Veller, Carl & Hayward, Laura K., 2016. "Finite-population evolution with rare mutations in asymmetric games," Journal of Economic Theory, Elsevier, vol. 162(C), pages 93-113.
    9. Battigalli, Pierpaolo & Dufwenberg, Martin, 2009. "Dynamic psychological games," Journal of Economic Theory, Elsevier, vol. 144(1), pages 1-35, January.
    10. Garcia, Alfredo & Reaume, Daniel & Smith, Robert L., 2000. "Fictitious play for finding system optimal routings in dynamic traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 34(2), pages 147-156, February.
    11. Echenique, Federico & Edlin, Aaron, 2004. "Mixed equilibria are unstable in games of strategic complements," Journal of Economic Theory, Elsevier, vol. 118(1), pages 61-79, September.
    12. Edward Cartwright, 2005. "On the Emergence of Social Conformity," Studies in Economics 0501, School of Economics, University of Kent.
    13. Drew Fudenberg & David K. Levine, 2016. "Whither Game Theory? Towards a Theory of Learning in Games," Journal of Economic Perspectives, American Economic Association, vol. 30(4), pages 151-170, Fall.
    14. Candogan, Ozan & Ozdaglar, Asuman & Parrilo, Pablo A., 2013. "Dynamics in near-potential games," Games and Economic Behavior, Elsevier, vol. 82(C), pages 66-90.
    15. Georgios Chasparis & Jeff Shamma, 2012. "Distributed Dynamic Reinforcement of Efficient Outcomes in Multiagent Coordination and Network Formation," Dynamic Games and Applications, Springer, vol. 2(1), pages 18-50, March.
    16. Alexander Smajgl, 2007. "Modelling evolving rules for the use of common-pool resources in an agent-based model," Interdisciplinary Description of Complex Systems - scientific journal, Croatian Interdisciplinary Society Provider Homepage: http://indecs.eu, vol. 5(2), pages 56-80.
    17. Larry Samuelson, 2016. "Game Theory in Economics and Beyond," Journal of Economic Perspectives, American Economic Association, vol. 30(4), pages 107-130, Fall.
    18. Kets, W., 2008. "Networks and learning in game theory," Other publications TiSEM 7713fce1-3131-498c-8c6f-3, Tilburg University, School of Economics and Management.
    19. Wolpert David & Leslie David S., 2012. "Information Theory and Observational Limitations in Decision Making," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 12(1), pages 1-43, January.
    20. Galbiati, Marco & Soramäki, Kimmo, 2011. "An agent-based model of payment systems," Journal of Economic Dynamics and Control, Elsevier, vol. 35(6), pages 859-875, June.

    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:wsi:acsxxx:v:09:y:2006:i:04:n:s0219525906000884. 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: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/acs/acs.shtml .

    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.