Vi studerar det klassiska matematiska ekonomiproblemet med Bayesian optimal mekanism design där en huvudsaklig syftar till att optimera förväntade intäkter vid tilldelning av resurser till egenintresserade agenter med preferenser från en känd distribution. I en enda parameter inställningar (dvs., där varje agents preferens ges av ett enda privat värde för att serveras och noll för inte serveras) är detta problem löst [20]. Tyvärr är dessa enskilda parameter optimala mekanismer opraktiska och sällan använda [1], och dessutom den underliggande ekonomiska teorin misslyckas med att generalisera till den viktiga, relevanta och olösta multidimensionella inställning (dvs., där varje agents preferens ges av flera värden för var och en av de flera tillgängliga tjänsterna) [25]. I motsats till teorin om optimala mekanismer utvecklar vi en teori om sekventiella postade prismekanismer, där agenter i följd erbjuds take-it-or-leave-it-priser. Vi bevisar att dessa mekanismer är ungefär optimala i endimensionella miljöer. Dessa post-prismekanismer undviker många av egenskaperna hos optimala mekanismer som gör det senare opraktiskt. Dessutom generaliserar dessa mekanismer naturligt till flerdimensionella inställningar där de ger de första kända approximationer till det svårfångade optimala flerdimensionella mekanismen design problem. I synnerhet löser vi flerdimensionella flerenhetsauktionsproblem och generaliseringar till matrisens genomförbarhetsbegränsningar. De konstanta approximationer vi får varierar från 1,5 till 8. För alla utom ett fall, våra postade prissekvenser kan beräknas i polynom tid. Detta arbete kan ses som en utvidgning och förbättring av den algoritmiska prissättningen av enagent [9] till att omfatta flera agenter där konstruktören har kombinatoriska genomförbarhetsbegränsningar som agenterna samtidigt kan erhålla varje tjänst.
För intäktsmaximering, REF presenterar flera sekventiella postade prissättningsmekanismer för olika inställningar med olika typer av matris genomförbarhet begränsningar.
Multi-parameter mechanism design and sequential posted pricing
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}