Vi studerar mekanismer för utilitariska kombinatoriska fördelningsproblem, där agenter inte antas vara ensinnade. Denna klass av problem inkluderar kombinatoriska auktioner, flerenhetsauktioner, osplitterbara flödesproblem, och andra. Vi fokuserar på problemet med att utforma mekanismer som ungefär optimerar social välfärd vid varje Bayes-Nash jämvikt (BNE), som är standardbegreppet för jämvikt i miljöer av ofullständig information. För en bred klass av giriga approximationsalgoritmer ger vi en allmän minskning av svart-box till deterministiska mekanismer med nästan ingen förlust till approximationsförhållandet vid någon BNE. Vi anser också att det speciella fallet Nash equilibria i full information spel, där vi får skärpta resultat. Detta lösningskoncept är nära relaterat till det välstuderade priset på anarki. Dessutom, för en rik underklass av tilldelningsproblem, är ren Nash Equilibria garanterat att existera för våra mekanismer. För många problem, de approximativa faktorer vi får i jämvikt förbättra på de mest kända resultaten för deterministiska sanningsenliga mekanismer. I synnerhet uppvisar vi en enkel deterministisk mekanism för allmänna kombinatoriska auktioner som får en O ( ε m) approximation vid varje
Lucier och Borodin REF studerar Bayesian priset för anarki för giriga kombinatoriska auktioner.
Price of anarchy for greedy auctions
{'venue': "SODA '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}