講座題目：
1. Beyond Classical Fisher Markets: Non-convexity and Uncertainty
2. A 1.643-approximation algorithm for the vertex cover problem
主講嘉賓：1.葉蔭宇 2.韓喬明
時間：2023年12月29日（星期五）下午14:00—17:00
地點：菠菜网最新平台网116東方廳
歡迎感興趣的師生參加聆聽！
菠菜担保平台官网
2023年12月25日
主講嘉賓簡介
葉蔭宇（Yinyu Ye）現任斯坦福大學管理科學與工程系及計算數學工程研究院李國鼎講座教授。他的主要研究領域包括連續和離散優化、數據科學及應用、數字算法設計及分析、算法博弈及市場均衡、運籌及管理科學等。他是内點優化算法、錐規劃模型、分布式魯棒優化、在線線性規劃和學習、強化學習和馬可夫過程算法分析等領域的開創者之一。他多次獲得各大科學獎項，包括：2009年約翰·馮·諾依曼理論獎、2012年國際數學規劃大會(ISMP)Tseng Lectureship獎（每三年一次）、2014年美國應用數學學會優化獎（每三年一次）等。根據谷歌學術統計，葉蔭宇教授的論文和著作被引用超過55000次。
韓喬明，南京工業大學教授，主要從事優化理論算法及應用研究，對圖的剖分問題、點覆蓋問題、報童問題以及投資組合等有深入的研究，發表學術論文二十餘篇，其中國際頂尖運籌學期刊《Operations Research》兩篇、《Mathematical Programming 》一篇。主持、參與六項國家自然科學基金的研究工作。
講座主要内容
1. The Fisher market is one of the most fundamental models for resource allocation. However, classical Fisher markets (i) only consider two types of constraints, i.e., budgets of individual buyers and capacities of goods, and (ii) involve a complete information setting wherein buyers' utilities are known, and all the transactions happen in a static market. In this talk, we present generalizations of classical Fisher markets to settings when agents have additional linear constraints and when buyers arrive at the market sequentially with utilities and budgets that are not known a priori to the market designer. We first show that the addition of linear constraints introduces non-convexities into Fisher markets as the equilibrium price set may be non-convex, and computing equilibria is, in general, PPAD-hard. Yet, to set equilibrium prices, we introduce a budget-adjusted social optimization problem (BA-SOP), whose optimal dual variables correspond to the equilibrium prices. Next, we extend the above-mentioned distributed implementation to the online setting when agents arrive sequentially at the market with privately known utility and budget parameters drawn i.i.d. from some distribution. In this setting, we study the performance limitations of static pricing approaches, which set the same prices for all users, and develop two adaptive pricing algorithms, one with knowledge of the distribution and another that solely relies on past observations of user consumption, i.e., revealed preference feedback, with improved performance guarantees.
2. We present an algorithm for the vertex cover problem by combining the LP relaxation and the random edge-reductions. The algorithm has the expected approximation ratio of 23/14=1.643.
當前位置: