Vi visar att varje genomförbar mekanism, Bayesian, multi-item multi-bitder mekanism för oberoende, additiv budgivare kan genomföras som en mekanism som: a) fördelar varje post oberoende av de andra posterna; b) för fördelningen av varje post använder den en strikt beställning av alla budgivares typer; och fördelar posten med hjälp av en fördelning över hierarkiska mekanismer som stryker denna beställning till en icke-strikt beställning, och ger posten enhetligt slumpmässigt till de budgivare vars rapporterade typer dominerar alla andra rapporterade typer enligt den icke-striktade beställningen. I kombination med cyklisk monotonitet ger våra resultat en karakterisering av genomförbara Bayesian Incitament Kompatibla mekanismer i denna miljö. Vår karakterisering möjliggörs av ett nytt, konstruktivt bevis på Border's theorem [Bor91], och en ny generalisering av detta teorem till oberoende (men inte nödvändigtvis identiskt distribuerade) budgivare, vilket förbättrar resultaten av [Bor07, CKM11]. För en enda post och oberoende budgivare, visar vi att varje möjlig reducerad form auktion kan genomföras som en distribution över hierarkiska mekanismer som är förenliga med samma strikta beställning av alla budgivares typer, som varje mekanism till stöd för distribution strykjärn till en icke-strikt beställning. Vi ger också en polynom-tidsalgoritm för att bestämma genomförbarheten av en reducerad form auktion, eller tillhandahålla en separation hyperplane från uppsättningen möjliga reducerade former. För att slutföra bilden ger vi polynom-tidsalgoritmer till †
I synnerhet resultaten av Cai et al. REF innebär att varje första ordningens interimistiska regel effektivt kan implementeras som en distribution över virtuella värde maximerare.
An algorithmic characterization of multi-dimensional mechanisms
{'venue': "STOC '12", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}