Vi studerar priset på anarki (PoA) av samtidiga förstapris auktioner (FPA) för köpare med submodulära och subadditiva värderingar. De nuvarande bästa övre gränserna för Bayesian priset för anarki (BPoA) av dessa auktioner är e/(e − 1) [Syrgkanis och Tardos 2013] och 2 [Feldman et al. 2013], respektive. Vi erbjuder matchande nedre gränser för båda fallen även för fall av fullständig information och för blandade Nash equilibria via en explicit konstruktion. Vi presenterar ett alternativt bevis på den övre gränsen för e/e − 1) för FPAs med delvis subadditiva värderingar som avslöjar den värsta prisfördelningen, som används som ett byggsten för den matchande lägre bundet konstruktion. Vi generaliserar våra resultat till en allmän klass av objekt budauktioner som vi kallar budberoende auktioner (inklusive FPAs och all-pay auktioner) där vinnaren alltid är den högsta budgivaren och varje budgivares betalning beror endast på hans eget bud. Slutligen tillämpar vi våra tekniker på diskriminerande auktioner av flera enheter. Vi kompletterar resultaten från de Keijzer et al. [2013] för subadditiva värderingar genom att tillhandahålla en motsvarande nedre gräns på 2. För submodulära värderingar ger vi en lägre gräns på 1.109. För samma värderingsklass kunde vi återge den övre gränsen för e/e − 1) med vår icke-smooth-strategi. är att utforma en (sann) mekanism som fördelar objekten på ett effektivt sätt i jämvikten till exempel, så att det maximerar den sociala välfärden, vilket är summan av värderingarna av spelarna för de mottagna paketen. Även om det är välkänt att detta kan uppnås optimalt genom VCG-mekanismen [Vickrey 1961; Clarke 1971; Groves 1973], tyvärr kan detta ta exponentiell tid i m och n [Nisan och Ronen 1999 Ronen, 2000 ] (om inte P = NP). I praktiken används flera enkla icke-sanningsmekanismer. De mest anmärkningsvärda exemplen är generaliserade andraprisauktioner (GSP) som används av AdWords [Edelman et al. 2007; Varian 2007], samtidig stigande prisauktioner för trådlös spektrumtilldelning [Milgrom 2000] eller oberoende andraprisauktion (SPAs) på eBay. Dessutom begränsas köparnas uttryckskraft i dessa auktioner kraftigt av budspråket, så att de inte kan representera sina komplexa preferenser exakt. Mot bakgrund av de föregående upplysningarna, Christodoulou m.fl. [2008] föreslog en undersökning av enkla, icke-sanna auktioner med hjälp av priset på anarki (PoA) [Koutsoupias och Papadimitriou 1999] som ett mått på ineffektiviteten i sådanaauktioner. 1 1 I detta sammanhang definieras PoA som det värsta förhållandet mellan den optimala sociala välfärden och den sociala välfärd som erhålls i en (bayesisk) Nash-jämvikt. 2 Fraktionellt subadditiva värderingar är också kända som XOS-värderingar. För definitioner av dessa värderingsfunktioner hänvisar vi läsaren till Avsnitt 2.
Christodoulou m.fl. REF konstruerade snäva nedre gränser för förstaprisauktioner och visade ett snävt pris på anarki som är bundet till 2 för all pay-auktioner med subadditiva värderingar.
Tight Bounds for the Price of Anarchy of Simultaneous First-Price Auctions
{'venue': 'TEAC', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}