På senare tid har problemet med att utforma dynamiska mekanismer i flera steg visat sig vara både teoretiskt utmanande och praktiskt taget viktigt. I detta dokument anser vi att problemet med att utforma intäkter är optimal dynamisk mekanism för en miljö där en auktionsförrättare säljer en uppsättning varor till en köpare i flera steg. I varje steg kan det finnas flera objekt till salu, men varje objekt kan bara visas i ett steg. Typen av köpare i varje steg är således en flerdimensionell vektor som kännetecknar köparens värdering av objekten i det skedet och antas vara oberoende i det skedet. Jämfört med den en-shot multi-dimensionella intäktsmaximering, design optimal dynamiska mekanismer för denna inställning medför ytterligare svårigheter i att mekanismer kan nu grena på olika insikter om tidigare slumpmässiga händelser och säkra extra intäkter. Vi föreslår i synnerhet en ny typ av mekanismer som kallas bankkontomekanismer. Ungefär en bankkontomekanism skiljer sig inte från någon stegvis individuell mekanism förutom en förstärkt struktur som kallas bankkonto, ett reellt tal för varje nod som sammanfattar historien hittills. Denna struktur gör det möjligt för auktionsförrättaren att lagra underskott eller överskott av köparnytta från varje enskild mekanism och även ut på lång sikt. Även om denna enkelhet möjliggör ett enkelt genomförande i praktiken, visar det sig att det också är tillräckligt för att garantera optimala intäkter. Vi fastställer först att de optimala intäkterna från alla dynamiska mekanismer i denna miljö kan uppnås genom en bankkontomekanism, och vi tillhandahåller en enkel karakterisering av uppsättningen av incitament kompatibla och i efterhand individuellt rationella bankkontomekanismer. Baserat på dessa karakteriseringar undersöker vi sedan problemet med att hitta de (ungefär) optimala bankkontomekanismerna. Vi visar att det finns en enkel, randomiserad bankkontomekanism som approximerar optimala intäkter upp till en konstant faktor. Vårt resultat är allmänt och kan tillgodose tidigare approximativa resultat i end-shot multi-dimensionell mekanism design. Baserat på den tidigare mekanismen visar vi vidare att det finns en deterministisk bankkontomekanism som också uppnår en approximation av konstanta faktorer. Slutligen anser vi att problemet med att beräkna optimala mekanismer när typutrymmet är diskret och tillhandahåller ett FPTAS via linjär och dynamisk programmering.
Mirrokni m.fl. REF-studiens intäktsmaximering för bankkontomekanismer som är föremål för en IR-restriktion i efterhand.
Optimal dynamic mechanisms with ex-post IR via bank accounts
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}