I detta dokument överväger vi problemet med att utforma incitamentskompatibla auktioner för flera (homogena) enheter av en vara, när budgivare har privata värderingar och privata budgetbegränsningar. När endast värderingarna är privata och budgetarna är offentliga visar Dobzinski et al [8] att den adaptiva clinching-auktionen är den unika incitamentskompatibla auktionen för att uppnå Paretooptimalitet. De visar vidare att denna auktion inte är sanningsenlig med privata budgetar, så att det inte finns någon deterministisk Pareto-optimal auktion med privata budgetar. Vårt huvudsakliga bidrag är att visa följande Budget Monotonicitet egendom av denna auktion: När det bara finns en oändligt delbart god, kan en budgivare inte förbättra sin nytta genom att rapportera en budget mindre än sanningen. Detta innebär att den adaptive clinching auktionen är incitamentskompatibel när överrapportering av budgeten inte är möjlig (t.ex. när medel måste visas i förväg). Vi kan också göra rapportering större budgetar suboptimal med en liten randomiserad ändring av auktionen. I båda fallen gör detta den modifierade auktionen Pareto-optimal med privata budgetar. Vi visar också att fastigheten Budget Monotonicity inte innehar för att auktionera ut odelbara enheter av varan, vilket visar en skarp kontrast mellan de delbara och odelbara fallen. Egendomen Budget Monotonicitet innebär också andra förbättrade resultat i detta sammanhang. För intäktsmaximering förbättrar samma auktion det mest kända konkurrensförhållandet till följd av Abrams [1] med en faktor av 4, och asymptotiskt närmar sig resultatet av den optimala singelprisauktionen. Slutligen betraktar vi problemet med inkomstmaximering (eller social välfärd) i en Bayesisk miljö. Vi tillåter anbudsgivarna att ha offentliga storleksbegränsningar (på den mängd varor de är villiga att köpa) utöver privata budgetbegränsningar. Vi visar en enkel poly-time beräkningsbar 5.83- approximation till den optimala Bayesian * Korresponderande författare. † Stödd av Alfred P. Sloan Research Fellowship och av NSF bidrag IIS-0812113. Stöds av Alfred P. Sloan Research Fellowship, och av NSF genom en CAREER-utmärkelse och bidrag CNS-0540347. § Stöds av en James B. Duke Fellowship och NSF bidrag IIS-0812113. Incitamentskompatibel mekanism, som är genomförbar i dominerande strategier. Vår teknik behöver återigen förmågan att förhindra budgivare från att överrapportera budgetar via randomisering. Vi visar tillnärmningsresultatet genom att utforma ett avrundningssystem för en LP-avslappning av problemet, vilket kan vara av oberoende intresse.
Ref-dokumentet visade att i fallet med en oändligt delbar vara är den adaptiva clinching-auktionen förenlig med vissa antaganden.
Incentive compatible budget elicitation in multi-unit auctions
{'venue': "SODA '10", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Economics']}