-
作者：Deza, Anna; Hall, Georgina
作者单位：INSEAD Business School
摘要：We introduce the notion of t-sum of squares (sos) submodularity, which is a hierarchy, indexed by t, of sufficient algebraic conditions for certifying submodularity of set functions. We show that, for fixed t, each level of the hierarchy can be verified via a semidefinite program of size polynomial in n, the size of the ground set of the set function. This is particularly relevant given existing results by Crama around testing whether a set function is submodular. We derive several equivalent ...
-
作者：Abdallah, Tarek; Reed, Josh
作者单位：Northwestern University; New York University
摘要：We study the single-item dynamic pricing problem in three separate asymptotic regimes characterized by their ratio of inventory to market size. We first consider the case of customer item valuations following an exponential distribution, for which we derive a sharp characterization of the boundaries between each of the regimes. We then proceed to the case of customer item valuations following a general distribution. In this case, we derive for each regime approximations to the optimal value fu...
-
作者：Golz, Paul; Peters, Dominik; Procaccia, Ariel D.
作者单位：University of California System; University of California Berkeley; Cornell University; Centre National de la Recherche Scientifique (CNRS); Harvard University
摘要：Apportionment is the problem of distributing h indivisible seats across states in proportion to the states' populations. In the context of the U.S. House of Representatives, this problem has a rich history and is a prime example of interactions between mathematical analysis and political practice. Grimmett suggests to apportion seats in a randomized way such that each state receives exactly its proportional share qi of seats in expectation (ex ante proportionality) and receives either left per...
-
作者：Udwani, Rajan
作者单位：University of California System; University of California Berkeley
摘要：We generalize the problem of online submodular welfare maximization to incorporate various stochastic elements that have gained significant attention in recent years. We show that a nonadaptive Greedy algorithm, which is oblivious to the realization of these stochastic elements, achieves the best possible competitive ratio among all polynomial-time algorithms, including adaptive ones, unless NP = RP. This result holds even when the objective function is not submodular but instead satisfies the...
-
作者：Xie, Jun; Wang, Qianni; Li, Jiayang; Nie, Yu (Marco)
作者单位：Southwest Jiaotong University; Northwestern University; University of Hong Kong
摘要：The continuous bi-criteria traffic assignment (C-BiTA) problem aims to find the distribution of agents with heterogeneous preferences in a network. The agents can be seen as playing a congestion game, and their payoff is a linear combination of time and toll accumulated over the selected path. We rediscover a formulation that enables the development of a novel and highly efficient algorithm. The novelty of the algorithm lies in a decomposition scheme and a special potential function. Together,...
-
作者：Jasin, Stefanus; Liu, Sheng; Zhao, Jinglong
作者单位：University of Michigan System; University of Michigan; University of Toronto; Boston University
摘要：We study the inventory allocation problem for an online retailer with multiple warehouses and geographically dispersed demand. The retailer fulfills customer orders using a greedy policy (i.e., ship from the cheapest available warehouse) and determines inventory allocation using the widely adopted hindsight or stochastic programming approach. Although this approach is popular in both academia and practice, its limitations remain poorly understood. We show that the hindsight solution coincides ...
-
作者：Correa, Jose; Cristi, Andres; Dutting, Paul; Hajiaghayi, Mohammad; Olkowski, Jan; Schewiore, Kevin
作者单位：Universidad de Chile; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Alphabet Inc.; Google Incorporated; University System of Maryland; University of Maryland College Park; University of Cologne; University of Southern Denmark
摘要：In this work, we initiate the study of buy-and-sell prophet inequalities. We start by considering what is arguably the most fundamental setting. In this setting, the online algorithm observes a sequence of prices one after the other. At each time step, the online algorithm can decide to buy and pay the current price if it does not hold the item already, or it can decide to sell and collect the current price as a reward if it holds the item. We identify settings in which a constant-factor buy-a...
-
作者：Li, Shukai; Shi, Cong; Mehrotra, Sanjay
作者单位：New York University; NYU Shanghai; University of Miami; Northwestern University
摘要：We consider price competition among multiple sellers over a selling horizon of T periods. In each period, sellers simultaneously set prices and subsequently observe their own demand realizations, which are unobservable to competitors. The realized demand of each seller depends on the prices of all sellers and follows a private, unknown linear model. We propose a least-squares estimation and then gradient optimization (LEGO) policy, which does not require sellers to share demand information or ...
-
作者：Zhou, Ziyan; Wang, Tong; Zhang, Tingwei
作者单位：Shanghai Jiao Tong University; City University of Hong Kong; The Chinese University of Hong Kong, Shenzhen
摘要：Stockout-based substitution creates complex stochastic dynamics in inventory systems even in highly symmetric settings. We study a joint assortment and inventory allocation problem in which a firm allocates a fixed total inventory of m units across n perfectly substitutable product types (e.g., colors or designs). Customers are indifferent among available types and arrive sequentially, each purchasing one unit chosen uniformly at random from the nonempty types. The sales process terminates whe...
-
作者：Murthy, Yashaswini; Moharrami, Mehrdad; Srikant, Rayadurgam
作者单位：California Institute of Technology; University of Iowa; University of Illinois System; University of Illinois Urbana-Champaign
摘要：Modified policy iteration (MPI) is a dynamic programming algorithm that combines elements of policy iteration and value iteration. The convergence of MPI is wellstudied in the context of discounted and average-cost Markov decision processes (MDPs). In this work, we consider the exponential cost risk-sensitive MDP formulation, which is known to provide some robustness to model parameters. Although policy iteration and value iteration are well-studied in the context of risk-sensitive MDPs, MPI i...
