Improved Truthful Mechanisms for Subadditive Combinatorial Auctions

This research paper discusses strategies to maximize welfare in combinatorial auctions. It explores mechanisms for handling strategic bidders with private valuations, aiming to design truthful and optimal welfare mechanisms while considering polytime constraints. The study presents advancements in achieving universally truthful mechanisms for subadditive bidders, breaking the logarithmic barrier in approximations.

• Mechanisms
• Combinatorial Auctions
• Truthful
• Subadditive
• Polytime

swartout_z Follow

Uploaded on Oct 02, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. IMPROVED TRUTHFUL MECHANISMS FOR SUBADDITIVE COMBINATORIAL AUCTIONS: BREAKING THE LOGARITHMIC BARRIER Jan 10th, 2021 SAHIL SINGLA INSTITUTE FOR ADVANCED STUDY AND PRINCETON UNIVERSITY JOINT WITH SEPEHR ASSADI AND THOMAS KESSELHEIM

2. COMBINATORIAL AUCTIONS: WELFARE MAXIMIZATION m indivisible non-identical items: {1,2, ,m} n bidders with privatecombinatorial valuations vi:2[m] 0 Goal: Allocate items S1,S2, ,Sn to maximize Welfare = ivi(Si) Examples of Bidder Valuations: m items n bidders 2

3. PURELY ALGORITHMIC QUESTION Suppose valuations ? given, can we maximize welfare in polytime? Easy for additive, otherwise how are valuations given? Value Oracle: query vi(S) Greedy gives 2 approx for submodular a) Lehmann- Lehmann- Nisan 06 b) Demand Oracle: (can simulate value oracle) Tight 2 approx for subadditive bidders e e 1 approx for XOS Feige 06 m items HOWTO HANDLE STRATEGIC BIDDERS? n bidders 3

4. TRUTHFUL COMBINATORIAL AUCTIONS m indivisible non-identical items: {1,2, ,m} nstrategic bidders with private valuations: vi:2[m] 0 Randomized truthful mechanism that given valuations ?: Returns allocations S1, ,Sn and payments p1, ,pn Goal: Maximize welfare: ivi(Si) Bidders maximize utilityviSi pi No incentive to lie m items Vickrey-Clarke-Groves Mechanism Generalizes 2nd-price Auction Truthful and optimal welfare, but not polytime n bidders ANY TRUTHFULAND POLYTIME MECHANISMTHAT APPROXIMATES WELFARE? 4

5. WHAT IS KNOWN? ValueOracle: (m (1)) Dobzinski-Vondrak 12 Demand Oracle for Submodular: O(log2 m) approx. O(log m loglog m) approx. O(log m) approx. O( log m) approx. O( loglog m3)approx. Dobzinski-Nisan-Schapira 05 Dobzinski 07 Krysta-Vocking 12 SUBADDITIVE Dobzinski 16 CAN WE GET ?(?) APPROX? Assadi-S 19 THM [Assadi-Kesselheim-S 21]: FOR SUBADDITIVE BIDDERS, A POLYTIME UNIVERSALLY TRUTHFUL MECHANISMWITH O( loglog m3) approx Remark: For Submodular/XOS valuations we get O( loglog m2) approx. 5

6. OUTLINE INTRODUCTION: TRUTHFUL COMBINATORIAL AUCTIONS POSTED-PRICE MECHANISMS OUR BINARY-SEARCH MECHANISM 6

7. FIXED-PRICE AUCTIONS Fixed-Price Auction (FPA) ??????? = ??????? + ??????? Set fixed prices ? 0 Bidders arrive in adversarial order and select best subset of remaining items: argmaxS Remaining{viS j Sp(j)} Truthful since ? fixed and Polytime due to Demand Oracle m For single-item auction, FPA with p = 2ndmax{vi} + gives optimal welfare DO PRICES ALWAYS EXIST WITH HIGH WELFARE? LEMMA: Exist prices ? s.t. FPA gives 2 approx for Submod/XOS O loglog m approx for Subadd Folklore Dutting, Kesselheim, Lucier 20 HOW TO LEARN SUCH PRICES? 7

8. WARM-UP: SINGLE ITEM WELFARE MAXIMIZATION Offline Algorithm: Run 2nd-price auction Online Algorithm: Secretary-problem based mechanism 1. 2. 3. Randomly partition bidders into N0 and N1 Ignore bidders N0 but ask them their values Set price p = max No incentive to lie N0 N1 i N0vi. Run FPA on N1 Gives 4-approx: With probability , both 2nd-highest bidder in N0 and highest bidder in N1 HOW TO SELL MULTIPLE ITEMS? 8

9. WARM-UP: O ???? APPROX FOR MULTIPLE ITEMS With constant probability, run 2nd price auction on the entire bundle. Otherwise, 1. Randomly partition bidders into N0 and N1 Ignore bidders N0 but ask them their valuations Gives estimate of OPT by concentration (2nd price auction handles corner cases) 2. N0 N1 OPT 2m,OPT 3. Optimal prices are in 1 After exponential bucketing, guess prices? w.p. HOW TO HANDLE SUBADDITIVE VALUES? log m 4. Run FPA with prices ? on N1 CHALLENGES: 1. All prices NOT correctly guessed 2. We only get (log m) approx FOR SUBMOD/XOS, O loglog m3APPROX: 1. Prices already robust 2. Learn prices in rounds Assadi-S 19 9

10. FPA FOR SUBADDITIVE VALUES } be optimal allocation Let {Si ) LEMMA [Dutting-Kesselheim-Lucier 20]: For any bidder i, there exist prices ?(Si and a distribution over 2Si such that for any sold items T Si , 1 viSi ES Si SviS T ?(S) + ? T E[Utilityi] Rev(T) = O(loglog m) for subadd = O(1) for submodular Take-Aways: 1. Exist prices s.t. either bidder i has a large utility or items already sold 2. Prices not robust: We lose additively for incorrectly priced items (in p(T)) 10

11. OUTLINE INTRODUCTION: TRUTHFUL COMBINATORIAL AUCTIONS POSTED-PRICE MECHANISMS OUR BINARY-SEARCH MECHANISM 11

12. OUR BINARY-SEARCH MECHANISM loglog m Assume OPT = m is given. Since all item prices in 1, ,m , defineBin Bj= [2j 1,2j) Binary search on prices 1. Randomly partition bidders into rounds: N1,N2, ,N +1 B1,B2,B3,B4,B5,B6,B7,B8 2. We do + 1 FPAs in rounds, and one of them is randomly the final allocation B5,B6,B7,B8 B1,B2,B3,B4 B3,B4 B5,B6 3. In round i (tree level), offer items to Ni at binary search prices ? B7,B8 B1,B2 B1 B3 B2 B4 B5 B7 B6 B8 Take-Away: Use FPAs as proxy to learn prices EACHITEMHASITSOWNPATH 12

13. = O(loglogm) for subadditive = O(loglogm) MAIN LEMMA LEMMA [Assadi-Kesselheim-S 21]: FORANYBIDDERi, Crucially use bidders arrive in random rounds 1 ) ) E Utilityi+ Rev(Si 2 + 12vi(Si Take-Away: Either bidder ihas a large utility or these items sold at a good price COROLLARY: FOR SUBADDITIVE VALUATIONS, WEGETO( loglog m3) approx PROOF: Summing over all bidders i, n n 1 ) } partitions all m items Recall{Si E Utilityi+ Rev(Si 2 + 12 viSi i=1 i=1 Total Welfare OPT 13

14. = O(loglogm) for subadditive = O(loglogm) MAIN LEMMA LEMMA [Assadi-Kesselheim-S 21]: FORANYBIDDERi, Crucially use bidders arrive in random rounds 1 ) ) E Utilityi+ Rev(Si 2 + 12vi(Si PROOF IDEA: Condition on rounds in which bidders except i arrive. Consider path of any item in Si 1. Item correctly priced at leaf: Bidder i could arrive in last round and buy this item 2. Item lost because sold earlier at a higher price: We already get large Rev(Si 3. Item lost because not sold even at a lower price: Bidder i could arrive in this round and buy this item . We are in one of 3 cases: ) Take-Away: Suffices to give i chance of picking any item in Si Finally, combine with Dutting, Kesselheim, Lucier 20 14

15. CONCLUSION Universally Truthful Mechanism: O loglog m3 approx. for subadd and O loglog m2 approx. for submod/XOS Secretary problem based Posted-price mechanisms Binary search using Fixed Price Auctions to update prices Open Problems: Can we get O(1) approx, even for submod bidders? Can we get o( m) approx deterministically, even for submod bidders? Do there exist FPA prices that give O(1) approx for subadd bidders? THANK YOU 15

16. FURTHER SLIDES 16

17. FPA FOR SUBADDITIVE VALUES } be optimal allocation Let {Si ) LEMMA [Dutting-Kesselheim-Lucier 20]: For any bidder i, there exist prices ?(Si and a distribution over 2Si such that for any sold items T Si , 1 viSi ES Si SviS T ?(S) + ? T = O(loglog m) for subadd = O(1) for submodular E[Utilityi] Rev(T) Takeaways: 1. Exist prices s.t. either bidder i has a large utility or items already sold 2. Prices not robust: We lose additively for incorrectly priced items (in p(T)) COROLLARY: Exist prices ? s.t. FPA gives O loglog m approx for subadditive bidders } partitions all m items, use above lemma to set item prices Proof Idea: Since {Si 17

18. PROVING THE FOLKLORE LEMMA LEMMA [Folklore]: IFAN ALLOCATION S1, ,SnHAS SUPPORTING PRICES? THEN FPA WITH? = ?HASWELFARE iviSi = iq Si. Welfare = Revenue + Utility Idea: iviSi = ip Si + i(viSi p Si) S1, ,Sn partitions [m] Let A be items eventually sold: Revenue= q A = iq(Si A) Utility of i is viSi A q Si A q Si A q Si A= q Si A Total Welfare iq(Si A) + iq Si A = iq(Si) Q.E.D. 18

19. BINARY SEARCH FOR ITEM PRICES Binary search on prices Recall OPT = m. DefineBin Bj= [2j 1,2j) height = For level i, subdivide Niinto 2pieces Run 2 FPAs Items priced at lowest bin s price B1,B2,B3,B4,B5,B6,B7,B8 B5,B6,B7,B8 B1,B2,B3,B4 B3,B4 B5,B6 B7,B8 B1,B2 At level i + 1, move items to Subtree of their highest sold bin B1 B3 B2 B4 B5 B7 B6 B8 EACHITEMHASITSOWN PATH 19