I’ve listened to enough of Professor Ye’s talks that my Apple Photos automatically organizes pictures of his slides into a “memory” album (by recognizing Prof Ye of course). Interestingly delightful — I always learn so much from them!
Professor Ye: Slay.
Another refreshing piece of research on applying OR to game theory:
The Implicit Barrier of Utility Maximization: An Interior-Point Approach for Market Equilibria
Chuwen Zhang, Chang He, Bo Jiang, Yinyu Ye | ArXiv link
ABSTRACT We study the computation of equilibria in exchange markets with divisible goods and players endowed with heterogeneous utilities. In this paper, we revisit the polynomial-time interior-point strategies that update \emph{only} the prices, mirroring the tâtonnement process. The key ingredient is the \emph{implicit barrier} inherent in the utility maximization: the utility turns unbounded when the goods are almost free of charge. Focusing on a ubiquitous class of utilities, we formalize this observation into Scaled Lipschitz Continuity for utility maximization from both the primal and dual perspectives. A companion result suggests that no additional effort is required for computing high-order derivatives; all the necessary information is readily available when collecting the best responses. To tackle the Newton systems, we present an explicitly invertible approximation of the Hessian operator with high probability guarantees, and a scaling matrix that minimizes the condition number of the linear system. Building on these tools, we design two inexact interior-point methods. One such method has O(ln(1/{\epsilon})) complexity rate. Under mild conditions, the other method achieves a non-asymptotic superlinear convergence rate. Extensions and preliminary experiments are presented.
Takeaway: Interior-point methods can be viewed as a kind of “decentralized 2ⁿᵈ-order tâtonnement process” for equilibrium computation. For more details on the setup and computational complexity, check out the paper :)