En sekvens av färska studier visar att även i den enkla inställningen av en enda säljare och en enda köpare med additiv, oberoende värderingar över m poster, intäktsmaximering mekanismen är oöverkomligt komplex. Detta problem har behandlats med hjälp av två huvudstrategier: • Tillnärmning: det bästa av två enkla mekanismer (sälj varje post separat, eller sälja alla objekt som ett paket) ger 1/6 av de optimala intäkterna [1]. • Ökad konkurrens: att driva den enkla VCG-mekanismen med ytterligare m köpare utvinner åtminstone de optimala intäkterna på den ursprungliga marknaden [17]. Båda tillvägagångssätten har dock allvarliga nackdelar: Å ena sidan är det knappast acceptabelt att förlora 83 % av intäkterna i någon tillämpning. Å andra sidan kan det vara oöverkomligt att locka ett linjärt antal nya köpare. Vi visar att genom att kombinera de två tillvägagångssätten kan man uppnå det bästa av båda världarna. Specifikt, för varje konstant ε man kan få en (1 - ε ) bråkdel av den optimala intäkterna genom att köra enkla mekanismer - antingen sälja varje post separat eller sälja alla objekt som ett enda paket - med betydligt färre ytterligare köpare: logaritmiska, konstant, eller inte ens någon i vissa fall.
Feldman m.fl. REF bevisar att försäljningen separat till ( ln( / ) / ) ytterligare köpare överstiger en (1 - ) andel av den optimala intäkterna (utan ytterligare köpare).
99% Revenue via Enhanced Competition
{'venue': "EC '18", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}