-
作者：Bogomolnaia, Anna; Moulin, Herve
作者单位：University of Glasgow; Centre National de la Recherche Scientifique (CNRS)
摘要：We must assign n agents to m posts subject to negative congestion; what assignment is fair and efficient? If congestion is anonymous (each agent adds one unit), it is always possible to assign each agent to one of the agent's top n out of the n x m feasible allocations. This ordinal interpretation of ex ante fairness can be adjusted if congestion is weighted (agent-specific). An assignment is competitive if I don't want to move to an empty post or to an occupied one at its current congestion l...
-
作者：Li, Zanyu; Bao, Chenglong
作者单位：Tsinghua University; Tsinghua University; Yanqi Lake Beijing Institute of Mathematical Sciences & Applications
摘要：Anderson mixing (AM) method is a popular approach for accelerating fixedpoint iterations by leveraging historical information from previous steps. In this paper, we introduce the Riemannian Anderson mixing (RAM) method, an extension of AM to Riemannian manifolds, and analyze its local linear convergence under reasonable assumptions. Unlike other extrapolation-based algorithms on Riemannian manifolds, RAM does not require computing the inverse retraction or inverse exponential mapping and has a...
-
作者：Djehiche, Boualem; Dumitrescu, Roxana
作者单位：Royal Institute of Technology; Institut Polytechnique de Paris; Ecole Polytechnique; ENSAE Paris
摘要：We introduce a zero-sum game problem of mean-field type as an extension of the classical zero-sum Dynkin game problem to the case where the payoff processes might depend on the value of the game and its probability law. We establish sufficient conditions under which such a game admits a value and a saddle point. Furthermore, we provide a characterization of the value of the game in terms of a specific class of doubly reflected backward stochastic differential equations of mean-field type, for ...
-
作者：Cohen, Asaf; Zell, Ethan
作者单位：University of Michigan System; University of Michigan
摘要：Mean field games (MFGs) model equilibria in games with a continuum of weakly interacting players as limiting systems of symmetric n-player games. We consider the finiteprove that any solution to the MFG system gives rise to a (C/ ffififfi state, infinite-horizon problem with ergodic cost. Assuming Markovian strategies, we first Vn)-Nash equilibrium in the n-player game. We follow this result by proving the same is true for the strategy profile derived from the master equation. We conclude the ...
-
作者：Khanh, Pham Duy; Khoa, Vu Vinh Huy; Mordukhovich, Boris S.; Phat, Vo Thanh
作者单位：Wayne State University; University of North Dakota Grand Forks
摘要：The paper is devoted to a systematic study and characterizations of notions of local maximal monotonicity and their strong counterparts for set-valued operators that appear in variational analysis, optimization, and their applications. We obtain novel resolvent characterizations of these notions together with efficient conditions for their preservation under summation in broad infinite-dimensional settings. Further characterizations of these notions are derived by using generalized differentia...
-
作者：Sentenac, Flore; Noiry, Nathan; Lerasle, Matthieu; Perchet, Vianney; Menard, Laurent
作者单位：IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom Paris; Institut Polytechnique de Paris; ENSAE Paris; Institut Polytechnique de Paris; ENSAE Paris
摘要：We investigate online maximum cardinality matching, a central problem in ad allocation. In this problem, users are revealed sequentially, and each new user can be paired with any previously unmatched campaign that it is compatible with. Despite the limited theoretical guarantees, the greedy algorithm, which matches incoming users with any available campaign, exhibits outstanding performance in practice. Some theoretical support for this practical success has been established in specific classe...
-
作者：Ahn, Dohyun; Zheng, Lewen
作者单位：Chinese University of Hong Kong
摘要：We consider the problem of estimating the expectation over a convex polyhedron specified by a set of linear inequalities. This problem encompasses a multitude of financial applications, including systemic risk quantification, exotic option pricing, and portfolio management. We particularly focus on the case where the target event is rare, which corresponds to extreme systemic failures, deep out-of-the-money options, and high target returns in the aforementioned applications, respectively. This...
-
作者：Hu, Xiaomeng; Klep, Igor; Nie, Tiawang
作者单位：University of California System; University of California San Diego; University of Ljubljana; University of Primorska
摘要：This paper studies Positivstellensatze and moment problems for sets K that are given by universal quantifiers. Let Q be the closed set of universal quantifiers. Fix a finite nonnegative Borel measure whose support is Q and assume it satisfies the multivariate Carleman condition. First, we prove a Positivstellensatz with universal quantifiers: if a polynomialf is positive on K, then f belongs to the associated quadratic module, under the archimedeanness assumption. Second, we prove some necessa...
-
作者：Kruk, Lukasz
作者单位：Maria Curie-Sklodowska University
摘要：A single-server queue with renewal arrivals and generally distributed independent and identically distributed service times is considered. Customers are served using the longest job first (LJF) scheduling algorithm with first in, first out being used as a tiebreaking rule. We introduce a fluid model for the evolution of a measure-valued state descriptor of this queue, and we investigate its properties. We also prove a fluid limit theorem justifying our fluid model as the first order approximat...
-
作者：Faenza, Yuri; He, Chengyue; Sethuraman, Jay
作者单位：Columbia University
摘要：Scarf's algorithm gives a pivoting procedure to find a special vertex-a dominating vertex-in a down-monotone polytope. This paper studies the behavior of Scarf's algorithm when employed to find stable matchings in bipartite graphs. First, it proves that Scarf's algorithm can be implemented to run in polynomial time, showing the first positive result on its runtime in significant settings. Second, it shows an infinite family of instances where, no matter the pivoting rule and runtime, Scarf's a...
