3期

最新文章

• Rockafellian Relaxation and Stochastic Optimization Under Perturbations AI翻译
  作者：Royset, Johannes O.; Chen, Louis L.; Eckstrand, Eric
  作者单位：University of Southern California; United States Department of Defense; United States Navy; Naval Postgraduate School
  摘要：In practice, optimization models are often prone to unavoidable inaccuracies because of dubious assumptions and corrupted data. Traditionally, this placed special emphasis on risk-based and robust formulations, and their focus on conservative decisions. We develop, in contrast, an optimistic framework based on Rockafellian relaxations in which optimization is conducted not only over the original decision space but also jointly with a choice of model perturbation. The framework enables us to ad...
• Envy-Free Division of Multilayered Cakes AI翻译
  作者：Igarashi, Ayumi; Meunier, Frederic
  作者单位：University of Tokyo; Institut Polytechnique de Paris; Ecole des Ponts ParisTech
  摘要：Dividing a multilayered cake under nonoverlapping constraints captures several scenarios (e.g., allocating multiple facilities over time where each agent can utilize at most one facility simultaneously). We establish the existence of an envy-free multi-division that is nonoverlapping and contiguous within each layer when the number of agents is a prime power, solving partially an open question by Hosseini et al. [Hosseini H, Igarashi A, Searns A (2020) Fair division of time: Multi-layered cake...
• Risk-Averse Markov Decision Processes Through a Distributional Lens AI翻译
  作者：Cheng, Ziteng; Jaimungal, Stian
  作者单位：University of Toronto
  摘要：By adopting a distributional viewpoint on law-invariant convex risk measures, we construct dynamic risk measures (DRMs) at the distributional level. We then apply these DRMs to investigate Markov decision processes, incorporating latent costs, random actions, and weakly continuous transition kernels. Furthermore, the proposed DRMs allow risk aversion to change dynamically. Under mild assumptions, we derive a dynamic programming principle and show the existence of an optimal policy in both fini...
• Compact Extended Formulations for Low-Rank Functions with Indicator Variables AI翻译
  作者：Han, Shaoning; Gomez, Andres
  作者单位：National University of Singapore; University of Southern California
  摘要：We study the mixed-integer epigraph of a special class of convex functions with nonconvex indicator constraints, which are often used to impose logical constraints on the support of the solutions. The class of functions we consider are defined as compositions of low-dimensional nonlinear functions with affine functions. Extended formulations describing the convex hull of such sets can easily be constructed via disjunctive programming although a direct application of this method often yields pr...
• Large Independent Sets in Recursive Markov Random Graphs AI翻译
  作者：Gupte, Akshay; Zhu, Yiran
  作者单位：University of Edinburgh; Heriot Watt University; University of Edinburgh
  摘要：Computing the maximum size of an independent set in a graph is a famously hard combinatorial problem that has been well studied for various classes of graphs. When it comes to random graphs, the classic Erdos-Renyi-Gilbert random graph G(n,p) has been analyzed and shown to have the largest independent sets of size Theta(logn) with high probability (w.h.p.) This classic model does not capture any dependency structure between edges that can appear in real-world networks. We define random graphs ...
• The Core of Housing Markets from an Agent's Perspective: Is It Worth Sprucing up Your Home? AI翻译
  作者：Schlotter, Ildiko; Biro, Peter; Fleinera, Tamas
  作者单位：HUN-REN; HUN-REN Centre for Economic & Regional Studies; Budapest University of Technology & Economics; Corvinus University Budapest
  摘要：We study housing markets as introduced by Shapley and Scarf. We investigate the computational complexity of various questions regarding the situation of an agent a in a housing market H: we show that it is NP-hard to find an allocation in the core of H in which (i) a receives a certain house, (ii) a does not receive a certain house, or (iii) a receives a house other than a's own. We prove that the core of housing markets respects improvement in the following sense: given an allocation in the c...
• Analysis of a Class of Minimization Problems Lacking Lower Semicontinuity AI翻译
  作者：Han, Shaoning; Cui, Ying; Pang, Jong-Shi
  作者单位：National University of Singapore; University of California System; University of California Berkeley; University of Southern California
  摘要：The minimization of nonlower semicontinuous functions is a difficult topic that has been minimally studied. Among such functions is a Heaviside composite function that is the composition of a Heaviside function with a possibly nonsmooth multivariate function. Unifying a statistical estimation problem with hierarchical selection of variables and a sample average approximation of composite chance constrained stochastic programs, a Heaviside composite optimization problem is one whose objective a...
• Order Independence in Sequential, Issue-by-Issue Voting AI翻译
  作者：Gershkov, Alex; Moldovanu, Benny; Shi, Xianwen
  作者单位：Hebrew University of Jerusalem; University of Surrey; University of Bonn; Tel Aviv University; University of Toronto
  摘要：We study when the voting outcome is independent of the order of issues put up for vote in a spatial multidimensional voting model. Agents equipped with norm-based preferences that use a norm to measure the distance from their ideal policy vote sequentially and issue by issue via simple majority. If the underlying norm is generated by an inner product-such as the Euclidean norm-then the voting outcome is order independent if and only if the issues are orthogonal. If the underlying norm is a gen...
• Dual Solutions in Convex Stochastic Optimization AI翻译
  作者：Pennanen, Teemu; Perkkioe, Ari-Pekka
  作者单位：University of London; King's College London; University of Munich
  摘要：This paper studies duality and optimality conditions for general convex stochastic optimization problems. The main result gives sufficient conditions for the absence of a duality gap and the existence of dual solutions in a locally convex space of random variables. It implies, in particular, the necessity of scenario-wise optimality conditions that are behind many fundamental results in operations research, stochastic optimal control, and financial mathematics. Our analysis builds on the theor...
• Robust Online Selection with Uncertain Offer Acceptance AI翻译
  作者：Perez-Salazar, Sebastian; Singh, Mohit; Toriello, Alejandro
  作者单位：Rice University; University System of Georgia; Georgia Institute of Technology
  摘要：Online advertising has motivated interest in online selection problems. Displaying ads to the right users benefits both the platform (e.g., via pay-per-click) and the advertisers (by increasing their reach). In practice, not all users click on displayed ads, while the platform's algorithm may miss the users most disposed to do so. This mismatch decreases the platform's revenue and the advertiser's chances to reach the right customers. With this motivation, we propose a secretary problem where ...