Mekanismedesign - Mechanism design
Mekanismedesign er et felt inden for økonomi og spilteori, der tager en mål-første tilgang til at designe økonomiske mekanismer eller incitamenter mod de ønskede mål i strategiske indstillinger , hvor spillerne handler rationelt . Fordi det starter i slutningen af spillet og derefter går baglæns, kaldes det også omvendt spilteori . Det har brede applikationer, fra økonomi og politik inden for områder som markedsdesign , auktionsteori og social valgteori til netværkssystemer (internet interdomæne-routing, sponsorerede søgeauktioner).
Mekanismedesign studerer løsningskoncepter til en klasse af private informationsspil. Leonid Hurwicz forklarer, at 'i et designproblem er målfunktionen den vigtigste "givne", mens mekanismen er den ukendte. Derfor er designproblemet det "omvendte" af traditionel økonomisk teori, som typisk er afsat til analysen af udførelsen af en given mekanisme. ' Så to karakteristiske træk ved disse spil er:
- at en spil "designer" vælger spilstrukturen i stedet for at arve en
- at designeren er interesseret i spillets resultat
2007 nobelpris i økonomi blev tildelt Leonid Hurwicz , Eric Maskin og Roger Myerson "for at have lagt grundlaget for mekanisme design teori".
Intuition
I en interessant klasse af Bayesian-spil , vil en spiller, kaldet "hovedstol", gerne betingelse af hans opførsel på information, der er kendt af andre spillere. For eksempel vil rektor gerne vide den sande kvalitet af en brugt bil, som en sælger kaster op. Han kan ikke lære noget ved blot at spørge sælgeren, for det er i sælgerens interesse at fordreje sandheden. Imidlertid har hovedmanden i mekanismedesign en fordel: Han kan designe et spil, hvis regler kan påvirke andre til at handle som han ønsker.
Uden teori om mekanismedesign ville rektorens problem være vanskeligt at løse. Han bliver nødt til at overveje alle de mulige spil og vælge den, der bedst påvirker andre spillers taktik. Derudover skulle rektoren drage konklusioner fra agenter, der måske lyver for ham. Takket være mekanismedesign og især afsløringsprincippet behøver hovedmanden kun at overveje spil, hvor agenter sandfærdigt rapporterer deres private oplysninger.
Fundamenter
Mekanisme
Et spil med mekanismedesign er et spil med privat information, hvor en af agenterne, kaldet rektor, vælger udbetalingsstrukturen. Efter Harsanyi ( 1967 ) modtager agenterne hemmelige "beskeder" fra naturen, der indeholder information, der er relevant for udbetalinger. For eksempel kan en besked indeholde oplysninger om deres præferencer eller kvaliteten af en vare til salg. Vi kalder disse oplysninger agentens "type" (normalt bemærket og følgelig typen af rum ). Agenter rapporterer derefter en type til hovedmanden (normalt bemærket med en hat ), der kan være en strategisk løgn. Efter rapporten betales rektor og agenter i henhold til den udbetalingsstruktur, som rektor valgte.
Tidspunktet for spillet er:
- Hovedmanden forpligter sig til en mekanisme, der giver et resultat som en funktion af rapporteret type
- Agenterne rapporterer, muligvis uærligt, en typeprofil
- Mekanismen udføres (agenter modtager resultat )
For at forstå, hvem der får hvad, er det almindeligt at opdele resultatet i en varetildeling og en pengeoverførsel, hvor det står for en allokering af varer, der er leveret eller modtaget som en funktion af typen, og står for en monetær overførsel som en funktion af type.
Som et benchmark definerer designeren ofte, hvad der ville ske under fuld information. Definer en social valgfunktion, der kortlægger (ægte) typeprofilen direkte til tildelingen af varer modtaget eller gengivet,
I modsætning hertil kortlægger en mekanisme den rapporterede typeprofil til et resultat (igen både en varetildeling og en pengeoverførsel )
Åbenbaringsprincip
En foreslået mekanisme udgør et Bayesisk spil (et spil med privat information), og hvis det er velopdragen, har spillet en Bayesisk Nash-ligevægt . Ved ligevægt vælger agenter deres rapporter strategisk som en funktion af typen
Det er vanskeligt at løse for Bayesianske ligevægte i en sådan indstilling, fordi det involverer løsning af agenters bedste responsstrategier og for den bedste slutning fra en mulig strategisk løgn. Takket være et vidtrækkende resultat kaldet afsløringsprincippet, uanset hvilken mekanisme en designer kan begrænse opmærksomheden til ligevægte, hvor agenter sandfærdigt rapporterer typen. De vigtigste åbenbaring hedder: "at hver Bayesian Nash ligevægt der svarer et Bayesian spil med den samme ligevægt resultat, men hvor spillerne sandfærdigt rapportere type."
Dette er yderst nyttigt. Princippet tillader en at løse en Bayesisk ligevægt ved at antage, at alle spillere sandt rapporterer type (underlagt en incitamentskompatibilitetsbegrænsning ). I et slag eliminerer det behovet for at overveje enten strategisk adfærd eller løgn.
Dens bevis er ret direkte. Antag et Bayesisk spil, hvor agentens strategi og udbetaling er funktioner af sin type, og hvad andre gør ,. Per definition agent i' s ligevægt strategi er Nash i forventet nytte:
Du skal blot definere en mekanisme, der ville få agenter til at vælge den samme ligevægt. Den nemmeste at definere er, at mekanismen forpligter sig til at spille agenternes ligevægtstrategier for dem.
Under en sådan mekanisme finder agenterne det naturligvis optimalt at afsløre typen, da mekanismen spiller de strategier, de alligevel fandt optimale. Vælg formelt sådan, at
Implementeringsevne
Designeren af en mekanisme håber generelt enten
- at designe en mekanisme, der "implementerer" en social valgfunktion
- at finde den mekanisme, der maksimerer et værdikriterium (f.eks. fortjeneste)
At implementere en social valgfunktion er at finde en overførselsfunktion, der motiverer agenter til at vælge . Formelt, hvis ligevægtsstrategiprofilen under mekanismen kortlægges til den samme varetildeling som en social valgfunktion,
vi siger, at mekanismen implementerer den sociale valgfunktion.
Takket være åbenbaringsprincippet kan designeren normalt finde en overførselsfunktion til at implementere et socialt valg ved at løse et tilknyttet sandhedsfortællingsspil. Hvis agenter finder det optimalt at sandfærdig rapportere typen,
Vi siger, at en sådan mekanisme sandfærdigt kan implementeres (eller bare "implementeres"). Opgaven er derefter at løse en sandt implementerbar og tilregne denne overføringsfunktion til det originale spil. En allokering kan sandfærdigt implementeres, hvis der findes en overførselsfunktion sådan
hvilket også kaldes begrænsningen af incitamentkompatibilitet (IC).
I applikationer er IC-tilstanden nøglen til at beskrive formen på enhver nyttig måde. Under visse betingelser kan det endda isolere overførselsfunktionen analytisk. Derudover tilføjes en deltagelsesbegrænsning ( individuel rationalitet ) undertiden, hvis agenter har mulighed for ikke at spille.
Nødvendighed
Overvej en indstilling, hvor alle agenter har en typekontingent hjælpefunktion . Overvej også en varetildeling, der er vektorvurderet og størrelse (som tillader antal varer), og antag, at den er stykkevis kontinuerlig med hensyn til dens argumenter.
Funktionen kan kun implementeres, hvis
når og og x er kontinuerlig kl . Dette er en nødvendig betingelse og er afledt af første- og andenordensbetingelser for agentens optimeringsproblem under forudsætning af sandhed.
Dens betydning kan forstås i to stykker. Det første stykke siger, at agentens marginale substitutionsrate (MRS) stiger som en funktion af typen,
Kort sagt, agenter vil ikke fortælle sandheden, hvis mekanismen ikke giver højere agenttyper en bedre aftale. Ellers vil højere typer, der står over for enhver mekanisme, der straffer høje typer for rapportering, lyve og erklære, at de er lavere typer, hvilket krænker IC-begrænsningen med sandhed. Det andet stykke er en monotonicitet, der venter på at ske,
hvilket for at være positivt betyder, at højere typer skal gives mere af det gode.
Der er potentiale for, at de to stykker kan interagere. Hvis kontrakten for nogle typer tilbyder mindre mængde til højere typer , er det muligt, at mekanismen kan kompensere ved at give højere typer rabat. Men en sådan kontrakt eksisterer allerede for agenter af lav type, så denne løsning er patologisk. En sådan løsning opstår undertiden i processen med at løse en mekanisme. I disse tilfælde skal det " stryges ". I et miljø med flere gode er det også muligt for designeren at belønne agenten med mere af en vare til erstatning for mindre af en anden (f.eks. Smør til margarine ). Flere gode mekanismer er et løbende problem i teorien om mekanismedesign.
Tilstrækkelighed
Mekanismepapirer antager normalt to antagelser for at sikre implementerbarhed:
Dette er kendt under flere navne: den enkeltkrydsende tilstand , sorteringsbetingelsen og tilstanden Spence – Mirrlees. Det betyder, at nyttefunktionen har en sådan form, at agentens MRS øges i type.
Dette er en teknisk betingelse, der begrænser væksten i MRS.
Disse antagelser er tilstrækkelige til at give, at ethvert monotont kan implementeres (der findes en , der kan implementere det). Derudover er single-crossing-tilstanden i en enkelt god indstilling tilstrækkelig til at give, at kun en monoton er implementerbar, så designeren kan begrænse sin søgning til en monoton .
Fremhævede resultater
Teorem for indtægtsækvivalens
Vickrey ( 1961 ) giver et berømt resultat, at ethvert medlem af en stor auktionsklasse forsikrer sælgeren om den samme forventede indtægt, og at den forventede indtægt er det bedste, sælgeren kan gøre. Dette er tilfældet, hvis
- Køberne har identiske værdiansættelsesfunktioner (som kan være en funktion af typen)
- Købertyperne distribueres uafhængigt
- Købertyperne er trukket fra en kontinuerlig distribution
- Typefordelingen bærer den monotone farehastighedsegenskab
- Mekanismen sælger varen til køberen med den højeste værdiansættelse
Den sidste betingelse er afgørende for sætningen. En implikation er, at for at sælgeren skal opnå højere indtægter, skal han tage en chance for at give varen til en agent med en lavere værdiansættelse. Normalt betyder det, at han skal risikere ikke at sælge varen overhovedet.
Vickrey – Clarke – Groves mekanismer
Auktionsmodellen Vickrey (1961) blev senere udvidet af Clarke ( 1971 ) og Groves til at behandle et offentligt valgproblem, hvor omkostningerne til et offentligt projekt bæres af alle agenter, f.eks. Om de skal bygge en kommunal bro. Den resulterende "Vickrey – Clarke – Groves" -mekanisme kan motivere agenter til at vælge den socialt effektive allokering af det offentlige gode, selvom agenter har privat kendte værdiansættelser. Med andre ord kan det løse " tragedien i det fælles " - under visse betingelser, især kvasilinær nytte, eller hvis budgetbalance ikke er påkrævet.
Overvej en indstilling, hvor antallet af agenter har quasilinear nytte med private værdiansættelser, hvor valutaen værdiansættes lineært. VCG-designeren designer en incitamentkompatibel (dermed sandfærdig implementerbar) mekanisme til at opnå den ægte typeprofil, hvorfra designeren implementerer den socialt optimale tildeling
VCG-mekanismens kløgtighed er den måde, den motiverer sandfærdig åbenbaring. Det eliminerer incitamenter til misrapportering ved at straffe enhver agent for omkostningerne ved den forvrængning, han forårsager. Blandt de rapporter, agenten kan komme med, tillader VCG-mekanismen en "null" -rapport, der siger, at han er ligeglad med det offentlige gode og kun bekymrer sig om pengeoverførslen. Dette fjerner agenten effektivt fra spillet. Hvis en agent vælger at rapportere en type, opkræver VCG-mekanismen agenten et gebyr, hvis hans rapport er afgørende , dvs. hvis hans rapport ændrer den optimale tildeling x for at skade andre agenter. Betalingen beregnes
der opsummerer forvrængningen i de andre agenters (og ikke hans egen) forsyningsselskaber forårsaget af rapportering af en agent.
Gibbard – Satterthwaite sætning
Gibbard ( 1973 ) og Satterthwaite ( 1975 ) giver et umulighedsresultat, der i sin ånd svarer til Arrow's umulighedssætning . For en meget generel klasse af spil kan kun "diktatoriske" sociale valgfunktioner implementeres.
En social valgfunktion f () er diktatorisk, hvis en agent altid modtager sin mest foretrukne varetildeling,
Teoremet siger, at enhver sandfærdig socialt valgfunktion under generelle forhold skal være diktatorisk, hvis
- X er endelig og indeholder mindst tre elementer
- Præferencer er rationelle
Myerson – Satterthwaite sætning
Myerson og Satterthwaite ( 1983 ) viser, at der ikke er nogen effektiv måde for to parter at handle med en vare, når de hver især har hemmelige og sandsynligt varierende værdiansættelser for det uden risiko for at tvinge en part til at handle med tab. Det er blandt de mest bemærkelsesværdige negative resultater inden for økonomi - et slags negativt spejl over for de grundlæggende sætninger i velfærdsøkonomi .
Eksempler
Prisdiskrimination
Mirrlees ( 1971 ) introducerer en indstilling, hvor overføringsfunktionen t () er let at løse for. På grund af dets relevans og sporbarhed er det et almindeligt miljø i litteraturen. Overvej en enkelt god indstilling for en enkelt agent, hvor agenten har quasilinear-værktøj med en ukendt type-parameter
og hvor hovedmanden har en forudgående CDF over agentens type . Hovedmanden kan producere varer til en konveks marginalkostnad c ( x ) og ønsker at maksimere det forventede overskud fra transaktionen
underlagt IC- og IR-betingelser
Hovedmanden her er en monopolist, der prøver at indstille en fortjenstmaksimerende prisordning, hvor den ikke kan identificere kundetypen. Et almindeligt eksempel er et flyselskabs prisfastsættelse for forretningsrejsende, fritidsrejsende og studerende. På grund af IR-tilstanden skal den give hver type en god nok aftale til at inducere deltagelse. På grund af IC-tilstanden skal den give hver type en god nok aftale, at typen foretrækker sin aftale frem for enhver anden.
Et trick givet af Mirrlees (1971) er at bruge konvolutt sætningen til at fjerne overførselsfunktionen fra forventningen om at blive maksimeret,
Integrering,
hvor er en indeks type. Udskiftning af incitamentkompatibel i maksimum,
efter en integration af dele. Denne funktion kan maksimeres punktvist.
Fordi det allerede er incitamentkompatibelt, kan designeren droppe IC-begrænsningen. Hvis hjælpefunktionen opfylder tilstanden Spence – Mirrlees, findes der en monoton funktion. IR-begrænsningen kan kontrolleres i ligevægt, og gebyrplanen hæves eller sænkes i overensstemmelse hermed. Bemærk desuden tilstedeværelsen af en faresats i udtrykket. Hvis typefordelingen bærer den monotone fare-forhold-egenskab, er FOC tilstrækkelig til at løse t (). Hvis ikke, er det nødvendigt at kontrollere, om monotonicitetsbegrænsningen (se tilstrækkelighed ovenfor) er opfyldt overalt langs fordelings- og gebyrplanerne. Hvis ikke, skal designeren bruge Myerson-strygning.
Myerson stryger
I nogle applikationer kan designeren muligvis løse de første ordres betingelser for pris- og tildelingsplaner, men alligevel finder de ikke monotone. For eksempel i quasilinear-indstilling sker dette ofte, når fare-forholdet i sig selv ikke er monoton. Under tilstanden Spence – Mirrlees skal den optimale pris og tildelingsplaner være ensformige, så designeren skal fjerne ethvert interval, hvor tidsplanen ændrer retning, ved at flade den ud.
Intuitivt hvad der foregår er designeren finder det optimalt at bunch bestemte typer sammen og give dem den samme kontrakt. Normalt motiverer designeren højere typer til at adskille sig ved at give dem en bedre aftale. Hvis der ikke er tilstrækkeligt få højere typer på margenen, finder designeren det ikke værd at give lavere typer en koncession (kaldet deres informationsleje ) for at opkræve højere typer en typespecifik kontrakt.
Overvej en monopolforvalter, der sælger til agenter med quasilinear-værktøj, eksemplet ovenfor. Antag, at tildelingsplanen, der opfylder de første ordres betingelser, har en enkelt indvendig top ved og et enkelt indvendigt trug ved , illustreret til højre.
- Efter Myerson (1981) flad det ved at vælge tilfredsstillende
- Hvis det ikke-monotoniske område af grænser op til kanten af typeområdet , skal du blot indstille den passende funktion (eller begge dele) til grænsetypen . Hvis der er flere regioner, se en lærebog for en iterativ procedure. det kan være, at mere end et trug skal stryges sammen.
Bevis
Beviset bruger teorien om optimal kontrol. Den overvejer sæt af intervaller i det ikke-monotone område, som det kan flade tidsplanen over. Derefter skriver han en Hamilton for at opnå de nødvendige betingelser for en inden for intervallerne
- der tilfredsstiller monotonicitet
- hvor monotonicitetsbegrænsningen ikke er bindende for grænserne for intervallet
Betingelse to sikrer, at det tilfredsstillende optimale kontrolproblem genopretter forbindelsen til tidsplanen i det oprindelige problem ved intervalgrænserne (ingen spring). Enhver, der opfylder de nødvendige betingelser, skal være flad, fordi den skal være monoton og alligevel genoprette forbindelse ved grænserne.
Som før maksimerer rektorens forventede udbytte, men denne gang underlagt monotonicitetsbegrænsningen
og brug en Hamilton til at gøre det med skyggepris
hvor er en tilstandsvariabel og kontrol. Som sædvanlig i optimal kontrol skal costate evolution ligningen tilfredsstille
Udnyt betingelse 2 og bemærk, at monotonicitetsbegrænsningen ikke er bindende ved grænserne for intervallet,
hvilket betyder, at den costate variable tilstand kan integreres og også er lig med 0
Den gennemsnitlige forvrængning af hovedstolens overskud skal være 0. For at udjævne tidsplanen skal du finde en sådan, at dens omvendte billede kortlægges til et interval, der opfylder ovenstående tilstand.
Se også
Bemærkninger
Referencer
- Clarke, Edward H. (1971). "Priser i flere dele af offentlige varer" (PDF) . Offentligt valg . 11 (1): 17–33. doi : 10.1007 / BF01726210 . JSTOR 30022651 . S2CID 154860771 .
- Gibbard, Allan (1973). "Manipulation af afstemningsordninger: Et generelt resultat" (PDF) . Econometrica . 41 (4): 587–601. doi : 10.2307 / 1914083 . JSTOR 1914083 .
- Groves, Theodore (1973). "Incitamenter i hold" (PDF) . Econometrica . 41 (4): 617-631. doi : 10.2307 / 1914085 . JSTOR 1914085 .
- Harsanyi, John C. (1967). "Spil med ufuldstændig information spillet af" Bayesian "-spillere, I-III. Del I. Grundmodellen". Ledelsesvidenskab . 14 (3): 159–182. doi : 10.1287 / mnsc.14.3.159 . JSTOR 2628393 .
- Mirrlees, JA (1971). "En udforskning i teorien om optimal indkomstbeskatning" (PDF) . Gennemgang af økonomiske studier . 38 (2): 175–208. doi : 10.2307 / 2296779 . JSTOR 2296779 . Arkiveret fra originalen (PDF) den 10.05.2017 . Hentet 12.08.2016 .
- Myerson, Roger B .; Satterthwaite, Mark A. (1983). "Effektive mekanismer til bilateral handel" (PDF) . Journal of Economic Theory . 29 (2): 265-281. doi : 10.1016 / 0022-0531 (83) 90048-0 . HDL : 10419/220829 .
- Satterthwaite, Mark Allen (1975). "Strategisikkerhed og Arrow's conditions: Eksistens- og korrespondancesætninger for afstemningsprocedurer og sociale velfærdsfunktioner". Journal of Economic Theory . 10 (2): 187-217. CiteSeerX 10.1.1.471.9842 . doi : 10.1016 / 0022-0531 (75) 90050-2 .
- Vickrey, William (1961). "Modspekulation, auktioner og konkurrencedygtige forseglede bud" (PDF) . Journal of Finance . 16 (1): 8–37. doi : 10.1111 / j.1540-6261.1961.tb02789.x .
Yderligere læsning
- Kapitel 7 i Fudenberg, Drew; Tirole, Jean (1991), Game Theory , Boston: MIT Press , ISBN 978-0-262-06141-4. En standardtekst til gradueret spilteori.
- Kapitel 23 i Mas-Colell ; Whinston; Green (1995), Microeconomic Theory , Oxford: Oxford University Press , ISBN 978-0-19-507340-9. En standardtekst til kandidat-mikroøkonomi.
- Milgrom, Paul (2004), Putting Auction Theory to Work , New York: Cambridge University Press , ISBN 978-0-521-55184-7. Anvendelser af mekanismernes designprincipper i forbindelse med auktioner.
- Noam Nisan . En Google tech-tale om mekanismedesign.
- Legros, Patrick; Cantillon, Estelle (2007). "Hvad er mekanismedesign, og hvorfor betyder det noget for beslutningstagning?" . Center for økonomisk politisk forskning .
- Roger B. Myerson (2008). "Mekanismedesign", The New Palgrave Dictionary of Economics Online, Abstract.
- Diamantaras, Dimitrios (2009), En værktøjskasse til økonomisk design , New York: Palgrave Macmillan , ISBN 978-0-230-61060-6. En kandidattekst specifikt fokuseret på mekanismedesign.
eksterne links
- Eric Maskin " Nobelprisforedrag " leveret den 8. december 2007 på Aula Magna , Stockholms universitet.