讲座题目：

    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

地点：新时代赌城543003cc116东方厅

欢迎感兴趣的师生参加聆听！

新时代赌城543003cc

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.