[{"id":18318,"title":"Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence","permalink":"https:\/\/bschool.nus.edu.sg\/biz-events\/event\/budget-pacing-in-repeated-auctions-regret-and-efficiency-without-convergence\/","category":"Seminars and talks","event_dept":{"value":"analytics-operations","label":"Analytics & Operations"},"event_sec_dept":false,"event_details":{"event_start_date":"4 August 2023","event_end_date":"4 August 2023","event_start_time":"10:00 am","event_end_time":"11:30 am","event_dress_code":"NA"},"event_loc":{"eve_address_selection":"1","eve_location_1":{"eve_org":"NUS Business School","eve_build":"Mochtar Riady Building","eve_room":"BIZ1-0202","eve_add":"15 Kent Ridge Drive","eve_count":"Singapore","eve_copos":"119245","eve_map_url":"https:\/\/goo.gl\/maps\/Q1kyjwxHNE22"},"eve_location_2":{"eve_org":"Shaw Foundation Alumni House","eve_build":"","eve_room":"Clove and Lemongrass Room Level 2","eve_add":"11 Kent Ridge Drive","eve_count":"Singapore","eve_copos":119244,"eve_map_url":"https:\/\/goo.gl\/maps\/docgThkDWFxKdb9c7"},"eve_location_3":{"eve_org":"Hon Sui Sen Memorial Library Auditorium","eve_build":"","eve_room":"","eve_add":"1 Hon Sui Sen Drive","eve_count":"Singapore","eve_copos":117588,"eve_map_url":"https:\/\/goo.gl\/maps\/NJjWK4RMpC92"},"eve_location_4":{"eve_org":"NUSS Kent Ridge Guild House","eve_build":"","eve_room":"Dalvey Room","eve_add":"9 Kent Ridge Drive","eve_count":"Singapore","eve_copos":119241,"eve_map_url":"https:\/\/goo.gl\/maps\/nXn2Luh96pH2"},"eve_location_5":{"eve_org":"Institute of Data Science","eve_build":"Innovation 4.0","eve_room":"1-3","eve_add":"3 Research Link","eve_count":"Singapore","eve_copos":117602,"eve_map_url":"https:\/\/goo.gl\/maps\/i1xocvvDh27QUXem7"},"eve_location_6":{"eve_org":"","eve_build":"","eve_room":"","eve_add":"","eve_count":"","eve_copos":"","eve_map_url":""},"eve_location_7":""},"event_introduction":"","event_short_intro":"","event_topic":null,"event_banner":false,"event_external_url":"","event_registration_details":{"event_registration_form":false,"event_registration_message":"","event_registration_deadline":null,"eve_registration_url":"","event_form":"","event_registration_ack":""},"event_speaker":[{"event_speaker_name":"Bar Light","event_speaker_designation":"Assistant Professor","event_speaker_affiliation":"Tel Aviv University's School of Mathematics","event_speaker_picture":false,"event_speaker_url":"","event_speaker_introduction":"Bar Light is an assistant professor in the Department of Statistics and Operations Research in Tel Aviv University’s School of Mathematics. Bar was previously a Postdoctoral Researcher at Microsoft Research focusing on market design and designing ad-auctions. Bar obtained a PhD in Operations Research from Stanford university. His research mainly focuses on market design for platforms, the analysis of large markets and systems, and dynamic optimization.<\/p>\n"}],"event_agenda":false,"event_photo_gallery":false,"event_presentations":false,"event_custom_heading":[{"event_custom_title":"Abstract","event_custom_details":"
We study the aggregate welfare and individual regret guarantees of dynamic\u00a0pacing\u00a0algorithms in the context of repeated auctions with\u00a0budgets. Such algorithms are commonly used as bidding agents in Internet advertising platforms. We show that when agents simultaneously apply a natural form of gradient-based\u00a0pacing, the liquid welfare obtained over the course of the learning dynamics is at least half the optimal expected liquid welfare obtainable by any allocation rule. Crucially, this result holds without requiring convergence of the dynamics, allowing us to circumvent known complexity-theoretic obstacles of finding equilibria. This result is also robust to the correlation structure between agent valuations and holds for any core auction, a broad class of auctions that includes first-price, second-price, and generalized second-price auctions. For individual guarantees, we further show such\u00a0pacing\u00a0algorithms enjoy dynamic regret bounds for individual value maximization, with respect to the sequence of\u00a0budget-pacing\u00a0bids, for any auction satisfying a monotone bang-for-buck property.<\/p>\n"}],"event_enquiry_details":{"event_enq_full_name":"","event_enq_department":"","event_enq_email":"","event_enq_telephone":"","event_enq_website":""}}]