交叉科学研究院分享会

2025年6月22日（周日）；

上午 9 : 00 - 12 : 00

信息管理与工程学院102室

上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号

报告 ①

Tractable Robust Mechanism Design with General Concave Objectives

Abstract

There has been a growing interest in studying nonlinear objective functions in mechanism design due to its flexibility to capture real-world economic environments. However, much of the existing literature assumes that the buyer's valuation distribution is exactly known — a condition rarely met in practice. To bridge this gap, we study the robust mechanism design with general concave objective functions. The challenges encountered in analyzing these problems stem from their inherent nature as infinite-dimensional nonlinear optimization problems. We employ piecewise linear approximation as the building block of our analysis to address these challenges. As a result, we provide a detailed characterization of the optimal solution, which includes the properties of the optimal mechanism, the optimal support set, and the structure of objective function under the optimal mechanism. As a byproduct, we show that when the objective is a concave piecewise linear function, the dual of the robust mechanism design problem can be reduced to a minimax pricing problem, where the posted price emerges as the optimal solution. The latter problem itself is a classic economic problem and closely related to issues studied in the buyer-optimal pricing and personalized pricing literature. On the algorithmic side, we identify and transform the optimality conditions of the robust mechanism into a series of linear ordinary differential equations (ODEs) and derive semi-closed-form solutions, thereby reducing the originally infinite-dimensional problem to a finite-dimensional one. Based on that, we design an alternating iterative method to solve for the remaining unknown parameters. Finally, we summarize the proposed methods in a solution framework and validate its effectiveness by applying it to several robust nonlinear mechanism design problems in economics and operations management.

报告 ②

Abstract

Local search (LS) is an efficient method for solving combinatorial optimization problems such as MaxSAT and Pseudo Boolean Problems (PBO). However, due to a lack of reasoning power and global information, LS methods get stuck at local optima easily. In contrast to the LS, Systematic Search utilizes unit propagation and clause learning techniques with strong reasoning capabilities to avoid falling into local optima. Nevertheless, the complete search is generally time-consuming to obtain a global optimal solution. This work proposes a deep cooperation framework combining local search and unit propagation to address their inherent disadvantages. First, we design a mechanism to detect when LS gets stuck, and then a well-designed unit propagation procedure is called upon to help escape the local optima. To the best of our knowledge, we are the first to integrate unit propagation technique within LS to overcome local optima. Experiments based on a broad range of benchmarks from MaxSAT Evaluations, PBO competitions, the Mixed Integer Programming Library, and three real-life cases validate that our method significantly improves three state-of-the-art MaxSAT and PBO local search solvers.

报告 ③

Abstract

Recent advancements have been achieved in designing efficient algorithms for combinatorial optimization problems, such as Maximum Satisfiability (MaxSAT) and pseudo-Boolean optimization (PBO). Among various methodologies, conflict-driven clause learning (CDCL)-based algorithm is considered one of the most effective approaches. However, without additional guidance beyond the solution-improving constraint, CDCL-based algorithms often fail to produce high-quality solutions. To this end, we propose a novel CDCL-based solution-improving search method for PBO, {\em AssumeOPT}, designed to efficiently derive high-quality solutions. Specifically, we first introduce a hybrid assumption selection method to generate appropriate assumption, which integrates three distinct assumption heuristics by a well designed mechanism. Then, a phase selection strategy is proposed to delivery the first feasible solution. Experiments shows that our proposed algorithms outperforms the state-of-the-art CDCL-based solvers on all benchmarks and remains competitive to the-state-of-art local search solver, demonstrating efficiency of our strategy and the potential of CDCL-based algorithms to produce high-quality solution.