IDEAS home Printed from https://ideas.repec.org/p/ise/remwps/wp0772019.html
   My bibliography  Save this paper

Controlling Algorithmic Collusion: short review of the literature, undecidability, and alternative approaches

Author

Listed:
  • João E. Gata

Abstract

Algorithms have played an increasingly important role in economic activity, as they becoming faster and smarter.Together with the increasing use of ever larger data sets, they may lead to significant changes in the way markets work. These developments have been raising concerns not only over the rights to privacy and consumers’ autonomy, but also on competition. Infringements of antitrust laws involving the use of algorithms have occurred in the past. However, current concerns are of a different nature as they relate to the role algorithms can play as facilitators of collusive behavior in repeated games, and the role increasingly sophisticated algorithms can play as autonomous implementers of pricing strategies, learning to collude without any explicit instructions provided by humanagents. In particular, it is recognized that the use of ‘learning algorithms’ can facilitate tacit collusion and lead to an increased blurring of borders between tacit and explicit collusion. Several authors who have addressed the possibilities for achieving tacit collusion equilibrium outcomes by algorithms interacting autonomously, have also consideredsome form of ex-ante assessment and regulation over the type of algorithms used by firms. By using well-known resultsin the theory of computation, I showthat such option faces serious challenges to its effectivenessdue to undecidability results. Ex-post assessment may be constrained as well. Notwithstanding several challenges face by current software testing methodologies, competition law enforcement and policy have much to gain from an interdisciplinary collaboration with computer science and mathematics.

Suggested Citation

  • João E. Gata, 2019. "Controlling Algorithmic Collusion: short review of the literature, undecidability, and alternative approaches," Working Papers REM 2019/77, ISEG - Lisbon School of Economics and Management, REM, Universidade de Lisboa.
  • Handle: RePEc:ise:remwps:wp0772019
    as

    Download full text from publisher

    File URL: https://rem.rc.iseg.ulisboa.pt/wps/pdf/REM_WP_077_2019.pdf
    Download Restriction: no
    ---><---

    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. Ben-porath, Elchanan, 1990. "The complexity of computing a best response automaton in repeated games with mixed strategies," Games and Economic Behavior, Elsevier, vol. 2(1), pages 1-12, March.
    3. Joseph E Harrington, 2018. "Developing Competition Law For Collusion By Autonomous Artificial Agents," Journal of Competition Law and Economics, Oxford University Press, vol. 14(3), pages 331-363.
    4. John Conlisk, 1996. "Why Bounded Rationality?," Journal of Economic Literature, American Economic Association, vol. 34(2), pages 669-700, June.
    5. Joao Gata, "undated". "Infinite Regression in Strategic Decision Making: an application of Rice's Theorem," Discussion Papers 95/38, Department of Economics, University of York.
    6. Gilboa, Itzhak, 1988. "The complexity of computing best-response automata in repeated games," Journal of Economic Theory, Elsevier, vol. 45(2), pages 342-352, August.
    7. Ulrich Schwalbe, 2018. "Algorithms, Machine Learning, And Collusion," Journal of Competition Law and Economics, Oxford University Press, vol. 14(4), pages 568-607.
    8. 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.
    9. Rubinstein, Ariel, 1986. "Finite automata play the repeated prisoner's dilemma," Journal of Economic Theory, Elsevier, vol. 39(1), pages 83-96, June.
    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. Cho, In-Koo, 2005. "Introduction to learning and bounded rationality," Journal of Economic Theory, Elsevier, vol. 124(2), pages 127-128, October.
    2. Jesper Breinbjerg & Alexander Sebald & Lars Peter Østerdal, 2016. "Strategic behavior and social outcomes in a bottleneck queue: experimental evidence," Review of Economic Design, Springer;Society for Economic Design, vol. 20(3), pages 207-236, September.
    3. Sarin, Rajiv, 1999. "Simple play in the Prisoner's Dilemma," Journal of Economic Behavior & Organization, Elsevier, vol. 40(1), pages 105-113, September.
    4. Jehiel, Philippe, 2005. "Analogy-based expectation equilibrium," Journal of Economic Theory, Elsevier, vol. 123(2), pages 81-104, August.
    5. Dargaj, Jakub & Simonsen, Jakob Grue, 2023. "A complete characterization of infinitely repeated two-player games having computable strategies with no computable best response under limit-of-means payoff," Journal of Economic Theory, Elsevier, vol. 213(C).
    6. Hubie Chen, 2013. "Bounded rationality, strategy simplification, and equilibrium," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(3), pages 593-611, August.
    7. Mastrogiorgio, Antonio & Petracca, Enrico, 2016. "Embodying rationality," MPRA Paper 74658, University Library of Munich, Germany.
    8. Ying-Fang Kao & Ragupathy Venkatachalam, 2021. "Human and Machine Learning," Computational Economics, Springer;Society for Computational Economics, vol. 57(3), pages 889-909, March.
    9. Pedro Dal Bo & Guillaume R. Frochette, 2011. "The Evolution of Cooperation in Infinitely Repeated Games: Experimental Evidence," American Economic Review, American Economic Association, vol. 101(1), pages 411-429, February.
    10. Ehud Kalai, 1995. "Games," Discussion Papers 1141, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    11. Scott E. Page, 2008. "Uncertainty, Difficulty, and Complexity," Journal of Theoretical Politics, , vol. 20(2), pages 115-149, April.
    12. Joseph Y. Halpern, 2007. "Computer Science and Game Theory: A Brief Survey," Papers cs/0703148, arXiv.org.
    13. Oliveira, Fernando S., 2010. "Limitations of learning in automata-based systems," European Journal of Operational Research, Elsevier, vol. 203(3), pages 684-691, June.
    14. Juan Manuel Sánchez-Cartas & Alberto Tejero & Gonzalo León, 2021. "Algorithmic Pricing and Price Gouging. Consequences of High-Impact, Low Probability Events," Sustainability, MDPI, vol. 13(5), pages 1-14, February.
    15. Compte, Olivier & Postlewaite, Andrew, 2015. "Plausible cooperation," Games and Economic Behavior, Elsevier, vol. 91(C), pages 45-59.
    16. Christoph March, 2011. "Adaptive social learning," Working Papers halshs-00572528, HAL.
    17. Jakub Dargaj & Jakob Grue Simonsen, 2020. "A Complete Characterization of Infinitely Repeated Two-Player Games having Computable Strategies with no Computable Best Response under Limit-of-Means Payoff," Papers 2005.13921, arXiv.org, revised Jun 2020.
    18. Xie, Chi & Liu, Zugang, 2014. "On the stochastic network equilibrium with heterogeneous choice inertia," Transportation Research Part B: Methodological, Elsevier, vol. 66(C), pages 90-109.
    19. Troy Tassier, 2013. "Handbook of Research on Complexity, by J. Barkley Rosser, Jr. and Edward Elgar," Eastern Economic Journal, Palgrave Macmillan;Eastern Economic Association, vol. 39(1), pages 132-133.
    20. Pierre Garrouste, 2001. "Learning in economics: the Austrian insights," ICER Working Papers 25-2001, ICER - International Centre for Economic Research.

    More about this item

    Keywords

    Collusion; Antitrust; Algorithms; Finite Automaton; Turing Machine; Church-Turing Thesis; Halting Problem; Recursiveness; Undecidability.;
    All these keywords.

    JEL classification:

    • D43 - Microeconomics - - Market Structure, Pricing, and Design - - - Oligopoly and Other Forms of Market Imperfection
    • D83 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Search; Learning; Information and Knowledge; Communication; Belief; Unawareness
    • K21 - Law and Economics - - Regulation and Business Law - - - Antitrust Law
    • L41 - Industrial Organization - - Antitrust Issues and Policies - - - Monopolization; Horizontal Anticompetitive Practices

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:ise:remwps:wp0772019. 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: Sandra Araújo (email available below). General contact details of provider: https://rem.rc.iseg.ulisboa.pt/ .

    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.