💰 quantitative finance

Markets are competitive if and only if P != NP

Dit paper bewijst dat markten alleen concurrerend kunnen zijn als P niet gelijk is aan NP, omdat gelijkheid tussen deze complexiteitsklassen het voor bedrijven mogelijk maakt om collusie efficiënt te handhaven, wat leidt tot het fundamentele dilemma dat markten ofwel informatief efficiënt ofwel concurrerend kunnen zijn, maar niet beide.

Oorspronkelijke auteurs: Philip Z. Maymin

Gepubliceerd 2026-02-25

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Philip Z. Maymin

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Grote Rekenkracht-Dilemma: Waarom Concurrentie Afhangt van een Wiskundig Raadsel

Stel je voor dat de economie een enorm, chaotisch bordspel is. In dit spel spelen honderden bedrijven met elkaar. Normaal gesproken denken we dat concurrentie (dat bedrijven elkaar de prijs afhandigen) wordt bewaakt door wetten, toezichthouders en de angst om betrapt te worden.

Maar deze paper, geschreven door Philip Maymin, zegt iets verrassends: Concurrentie bestaat alleen omdat computers (en mensen) niet slim genoeg zijn om samenzweringen perfect te detecteren.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen.

1. Het Grote Wiskundige Raadsel: P vs. NP

Om het verhaal te begrijpen, moeten we eerst kijken naar een beroemd raadsel in de wiskunde: P vs. NP.

P zijn problemen die een computer snel kan oplossen (zoals een simpele som).
NP zijn problemen die een computer snel kan controleren als het antwoord al bekend is, maar die extreem langzaam op te lossen zijn als je het antwoord zelf moet vinden.

De meeste wiskundigen geloven dat P niet gelijk is aan NP. Dat betekent: er zijn problemen die zo complex zijn dat ze praktisch onoplosbaar zijn voor onze huidige computers.

2. Het Spel: Samenzwering vs. Concurrentie

Stel je voor dat twee of meer bedrijven een geheime afspraak maken om de prijzen hoog te houden (collusie). Dit is goed voor hun winst, maar slecht voor jou als consument.
Om deze afspraak vol te houden, moeten ze drie dingen doen:

De afspraak maken: "Wat is de perfecte prijs voor elk product?"
De controle: "Heeft de ander de afspraak gebroken, of was de prijsverlaging gewoon omdat de vraag zakte?"
De straf: "Als de ander de afspraak breekt, hoe straffen we hem zo hard dat hij er spijt van krijgt?"

De ontdekking van de paper:

Als P = NP (als computers alles perfect kunnen oplossen), kunnen bedrijven deze drie stappen in een flits uitvoeren. Ze kunnen perfect controleren of iemand bedriegt en direct straffen. Resultaat: Samenzwering is perfect en concurrentie verdwijnt.
Als P ≠ NP (zoals we nu denken), is het probleem van het controleren ("Was die prijsverlaging opzet of toeval?") zo complex dat het onoplosbaar is voor computers. Er is te veel ruis en te veel variatie in de markt.
- De Analogie: Stel je voor dat je probeert te horen of iemand in een drukke, stormachtige zee een fluisterend woord heeft gezegd. Als de storm (de markt) te hard waait en het water te onrustig is, kun je het niet horen. Omdat bedrijven dit niet kunnen horen, durven ze niet te straffen. Als je niet kunt straffen, durven ze niet te samenzweren. Resultaat: Ze blijven concurreren.

3. De "Onmogelijke Driehoek"

De paper combineert dit met een eerdere theorie (Maymin, 2011) die zegt: "Om dat prijzen perfect alle informatie weerspiegelen (efficiëntie), moet P = NP zijn."

Dit leidt tot een gruwelijke waarheid, de Efficiëntie-Concurrentie Onmogelijkheid:
Je kunt niet alles hebben. Je kunt kiezen uit:

Perfecte Informatie (Efficiëntie): Prijzen zijn perfect en snel, maar bedrijven werken samen en maken hoge winsten.
Concurrentie: Prijzen zijn laag en eerlijk, maar de markt is "dom" en niet perfect efficiënt.
Beide? Nee. Dat is wiskundig onmogelijk.

4. Wat doet Kunstmatige Intelligentie (AI)?

Hier wordt het spannend. AI (zoals grote taalmodellen en algoritmes) maakt computers steeds slimmer. Het duwt ons langzaam richting de wereld waar P = NP lijkt te zijn voor deze specifieke problemen.

Vroeger: Mensen waren te dom om te zien of een concurrent de prijs verlaagde door een storm of door verraad. Dus bleef de concurrentie bestaan.
Nu: AI kan miljoenen data-punten per seconde analyseren. Het kan het "ruis" in de storm filteren en zien: "Ah, die prijsverlaging was geen toeval, het was bedrog!"
Het gevolg: Zodra AI slim genoeg wordt, kunnen bedrijven perfect samenwerken zonder ooit een woord te hoeven spreken. Ze "leren" samenwerken. Dit is wat we nu zien in de praktijk: algoritmes die automatisch hogere prijzen vinden, zonder dat er een menselijke samenzwering is.

5. De "Transparantie Valstrik"

Normaal denken we: "Hoe transparanter de markt, hoe eerlijker."
De paper zegt: Nee!
Als je alles heel transparant maakt (iedereen ziet elke prijs en elke transactie direct), maak je het voor AI makkelijker om te zien of iemand bedriegt.

De Vergelijking: Als je in een donkere kamer zit, is het moeilijk om te zien wie er een kaars dooft. Maar als je de lichten aan doet (transparantie), ziet iedereen het direct. Voor AI is "licht" eigenlijk een hulpmiddel om samenzwering te perfectioneren.

6. Wat betekent dit voor de toekomst?

De auteur stelt dat we onze wetten moeten aanpassen.

Oude wetten: Kijken naar "bewijs van samenzwering" (bellen, e-mails, afspraken).
Nieuwe realiteit: Samenzwering gebeurt nu door rekenkracht. Er is geen gesprek nodig, alleen maar slimme software.

De oplossing?
Misschien moeten we de markt juist moeilijker maken. Net zoals cryptografen systemen ontwerpen die zo complex zijn dat hackers ze niet kunnen kraken, moeten we markten ontwerpen die zo complex zijn dat AI niet kan samenzweren.

Meer productvariatie.
Meer willekeur in de vraag.
Minder transparantie (of tenminste, meer "ruis").

Conclusie

Concurrentie is geen natuurlijk gegeven. Het is een bijproduct van onze beperkingen. We concurreren omdat we niet slim genoeg zijn om samen te werken.
Nu AI die beperkingen wegneemt, dreigt de concurrentie te verdwijnen. De paper waarschuwt dat we een keuze moeten maken: willen we een super-efficiënte markt waar AI alles regelt (en prijzen hoog zijn), of houden we een markt waar we "dom" genoeg blijven om te concurreren?

Het is een waarschuwing dat we, naarmate onze technologie groeit, misschien onze vrijheid en lage prijzen verliezen, tenzij we slimme nieuwe regels bedenken.

Titel: Markten zijn concurrentieel dan en slechts dan als P ≠ NP

Auteur: Philip Z. Maymin (Fairfield University)
Doelgroep: Theoretische Economie / Computatiewetenschap

1. Het Kernprobleem

Het artikel adresseert een fundamentele vraag in de economie: wat handhaaft concurrentie in markten? De traditionele economische theorie wijst op institutionele factoren zoals antitrustwetgeving, toezicht en lage toetredingsdrempels. Maymin stelt echter dat de echte oorzaak computatiebeperkingen zijn.

De centrale stelling is dat concurrentie slechts kan bestaan omdat bedrijven de rekenkracht missen om collusie (prijsafspraken) duurzaam te handhaven. Het paper onderzoekt de relatie tussen de complexiteitstheorie (de P vs. NP vraag) en de marktstructuur. Specifiek wordt onderzocht of de mogelijkheid om afwijkingen van een collusieovereenkomst te detecteren en te straffen, afhankelijk is van de rekenkracht van de marktpartijen.

2. Methodologie en Model

Maymin bouwt een formeel model op dat een herhaald spel (repeated game) tussen $N$ bedrijven over $T$ periodes beschrijft, met stochastische vraag die onderhevig is aan schokken uit een combinatorisch rijke ruimte.

De Modelaannames:

Productruimte: Bedrijven verkopen unieke producten in een combinatorische ruimte.
Vraagstructuur: De vraag hangt af van een onwaarneembare vraagtoestand ( $\theta$ ) en ruis ( $\epsilon$ ).
Informatie: Bedrijven observeren alleen prijzen en kwantiteiten, niet de onderliggende vraagtoestand.
Aanneming 6 (Instance Hardness): Voor de specifieke markten die in de praktijk voorkomen, is het probleem van het detecteren van collusie "hard" (NP-hard) op de instances die natuurlijk ontstaan. Dit betekent dat het onderscheid maken tussen een prijsverlaging door een concurrent (afwijking) en een prijsverlaging door een vraagshock computationeel onmogelijk is binnen polynomiale tijd.

De Drie Computatieproblemen van Collusie:
Om collusie te handhaven, moeten bedrijven drie problemen oplossen:

Collusie Strategie Probleem (CSP): Het berekenen van het prijsvector dat de gezamenlijke winst maximaliseert.
Collusie Detectie Probleem (CDP): Het bepalen, op basis van waargenomen data, of een bedrijf heeft afgeweken van de afspraak of slechts gereageerd op een vraagshock.
Optimale Straf Probleem (OPP): Het berekenen van de strafstrategie die afwijken onrendabel maakt.

Maymin bewijst dat CSP, CDP en OPP allemaal NP-hard zijn voor algemene marktspellen. In tegenstelling hiermee is het Concurrentiële Best Response Probleem (CBR) (het vinden van de optimale prijs gegeven de prijzen van concurrenten) oplosbaar in polynomiale tijd ( $P$ ).

3. Belangrijkste Resultaten en Theorema's

Theorema 1-3 (Complexiteit):
De drie componenten van collusie (plannen, monitoren, straffen) zijn computationeel onhaalbaar (NP-hard) voor algemene markten.

Theorema 5 (Hoofdresultaat):

Als P = NP: Bedrijven kunnen alle drie de problemen efficiënt oplossen. Collusie wordt een duurzaam evenwicht (Perfect Public Equilibrium) dat de concurrentie overtreft. Punishment threats zijn geloofwaardig omdat afwijkingen direct gedetecteerd kunnen worden.
Als P ≠ NP: (Wat algemeen wordt aangenomen) Voor markten die voldoen aan de "Instance Hardness" conditie, is het detecteren van afwijkingen computationeel onmogelijk. Punishment threats zijn niet-geloofwaardig omdat bedrijven kunnen afwijken zonder ontdekt te worden. Het gevolg is dat bedrijven rationeel afwijken naar de concurrentiële best response, en de markt convergeert naar het competitieve evenwicht (marginaalkostprijzen).

Corollarium 7: Het Onmogelijkheidsresultaat (Efficiency-Competition Impossibility)
Dit is de meest fundamentele conclusie, die een koppeling maakt met eerdere werk van Maymin (2011):

Informatieve Efficiëntie (prijzen reflecteren alle informatie) vereist P = NP.
Concurrentie (prijzen convergeren naar marginaalkosten) vereist P ≠ NP.
Conclusie: Een markt kan ofwel informatief efficiënt zijn, ofwel concurrentieel, maar niet beide.

Corollarium 8: Het Transparantieparadox
Meer transparantie (lagere ruis in data) verkleint de "ambiguïteitsset" van mogelijke vraagtoestanden. Dit maakt het Collusie Detectie Probleem (CDP) makkelijker op te lossen. Conventioneel wordt transparantie gezien als pro-concurrentieel, maar dit paper toont aan dat transparantie de computatiekosten voor het detecteren van collusie verlaagt, waardoor collusie juist makkelijker vol te houden is.

4. De Overgang naar AI en Regimeverschuivingen

Het paper introduceert een dynamisch perspectief waarbij AI-systemen de rekenkracht van bedrijven geleidelijk vergroten. Dit leidt tot drie regimes (zie Figuur 1 in het paper):

Concurrentieel Regime: Rekenkracht is te laag om CDP op te lossen. Concurrentie heerst.
Instabiel Regime: Deels oplosbaar. Collusie is onstabiel en leidt tot prijsstrijd.
Collusie Regime: Rekenkracht is hoog genoeg (benadert P=NP voor deze problemen) om CDP op te lossen. AI-agenten leren autonoom collusie en handhaven deze zonder expliciete communicatie.

Dit verklaart empirische bevindingen (zoals Calvano et al., 2020; Fish et al., 2024) waar algoritmes tot supra-concurrentiële prijzen convergeren zonder menselijke instructie.

5. Bijdragen en Implicaties

Theoretische Bijdrage:

Het biedt een wiskundige onderbouwing voor "tacit collusion" (stilzwijgende collusie) die niet gebaseerd is op intentie of communicatie, maar op computatiecapaciteit.
Het koppelt de P vs. NP vraag direct aan economische welvaart en marktstructuur.
Het lost het "Grossman-Stiglitz paradox" op door te tonen dat de voorwaarden voor efficiëntie en concurrentie logisch incompatibel zijn.

Beleid en Antitrust (Computational Antitrust):
De huidige antitrustwetgeving focust op het bewijzen van "intentie" of "communicatie" (conspire). Maymin stelt dat dit onvoldoende is in een AI-tijdperk.

Nieuwe aanpak: Regulators moeten "marktcomplexiteit" zien als een beleidsvariabele.
Strategie: Om concurrentie te behouden in een wereld met krachtige AI, moeten markten complexer worden gemaakt (meer productdifferentiatie, meer ruis, asynchrone prijzen) zodat het CDP computationeel onhaalbaar blijft voor bedrijven.
Dilemma: Er is een "Regulatory Trilemma": je kunt niet tegelijkertijd hebben: (1) Efficiëntie, (2) Concurrentie, en (3) Volledige AI-integratie. Je moet er twee kiezen.

6. Conclusie

Maymin concludeert dat concurrentie geen natuurlijk wet is, maar een gevolg van onze computationele beperkingen. Zodra AI deze beperkingen opheft (en de effectieve grens naar P=NP verschuift), zal concurrentie verdwijnen en plaatsmaken voor collusie. De enige manier om concurrentie te behouden in een wereld van onbeperkte rekenkracht, is door markten te ontwerpen die computationeel moeilijk zijn om te manipuleren, vergelijkbaar met hoe cryptografen systemen ontwerpen die moeilijk te kraken zijn.