Vi studerar kombinatoriska auktioner där varje vara säljs separat men samtidigt via en andra prisauktion. Vi frågar om det är möjligt att effektivt beräkna i detta spel en ren Nash jämvikt med social välfärd nära den optimala. Vi visar att när anbudsgivarnas värderingar är submodulära är det i många intressanta miljöer (t.ex. konstant antal budgivare, budgettillförordnade budgivare) att beräkna jämvikt med god välfärd i huvudsak lika enkelt som att beräkna, helt ignorera incitamentsproblem, en tilldelning med god välfärd. Å andra sidan, för subadditiva värderingar, visar vi att beräkning en jämvikt kräver exponentiell kommunikation. Slutligen för XOS (även känt som XOS). Delvis subadditiva) värderingar, visar vi att om det finns en effektiv algoritm som finner en jämvikt, måste den använda tekniker som skiljer sig mycket från våra nuvarande.
Dobzinski m.fl. REF, till exempel, visade att för subadditiva värderingar beräkning en ren Nash jämvikt kräver exponentiell kommunikation.
On the Complexity of Computing an Equilibrium in Combinatorial Auctions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}