Vi tillhandahåller en Polynom tid approximation Scheme för flerdimensionella enhet-efterfrågan prisproblem, när köparens värden är oberoende (men inte nödvändigtvis identiskt fördelade.) För alla > 0, vi får en (1+ )-faktor approximation till den optimala intäkterna i tid polynom, när värdena provtas från Monotone Hazard Rate (MHR) distributioner, kvasi-polynomial, när provtas från regelbundna distributioner, och polynomial i n poly(log r), när provtagning från allmänna distributioner stöds på en uppsättning [umin, rumin]. Vi tillhandahåller även ett additivt PTAS för alla avgränsade distributioner. Våra algoritmer är baserade på nya extrema värdeteorier för MHR och regelbundna distributioner, och tillämpar probabilistiska tekniker för att förstå de statistiska egenskaperna hos intäktsfördelningar, samt för att minska storleken på sökområdet för algoritmen. Som en biprodukt av våra tekniker skapar vi strukturella egenskaper hos optimala lösningar. Vi visar att för alla > 0, g(1/ ) skiljer priser tillräckligt för att uppnå en (1 + )-faktor approximation till den optimala intäkterna för MHR distributioner, där g(1/ ) är en kvasi-linjär funktion av 1/ som inte beror på antalet poster. På samma sätt räcker för alla > 0 och n > 0, g(1/ · log n) skilda priser för regelbundna distributioner, där n är antalet poster och g(·) är en polynomfunktion. Äntligen, på i.d. MHR fall, visar vi att så länge antalet objekt är en tillräckligt stor funktion av 1/, ett enda pris räcker för att uppnå en (1 + ) faktor approximation. Våra resultat innebär betydande framsteg mot den enda-bider fall av multidimensionell optimal mekanism design problem, efter Myersons berömda arbete med optimal mekanism design [Myerson 1981 ].
I synnerhet löser Cai och Daskalakis REF det flerdimensionella prisproblemet, under förhållanden där olika typer fördelas.
Extreme-Value Theorems for Optimal Multidimensional Pricing
{'venue': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'journal': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}