-
作者：Benade, Gerdus; Halpern, Daniel; Psomas, Alexandros
作者单位：Boston University; Harvard University; Purdue University System; Purdue University
摘要：We consider the fundamental problem of fairly and efficiently allocating T indivisible items among n agents with additive preferences. Items become available over a sequence of rounds, and every item must be allocated immediately and irrevocably before the next one arrives. Previous work shows that when the agents' valuations for the items are drawn from known distributions, it is possible (under mild assumptions) to find allocations that are envy-free with high probability and Pareto efficien...
-
作者：Lin, Yifan; Wang, Yuhao; Zhou, Enlu
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：This article may be used only for the purposes of research, teaching, and/or private study. Commercial use or systematic downloading (by robots or other automatic processes) is prohibited without explicit Publisher approval, unless otherwise noted. For more information, contact permissions@informs.org. The Publisher does not warrant or guarantee the article's accuracy, completeness, merchantability, fitness inclusion of an advertisement in this article, neither constitutes nor implies a guaran...
-
作者：Aid, Rene; Basei, Matteo; Ferrarid, Giorgio
作者单位：Universite PSL; Universite Paris-Dauphine; Institut Polytechnique de Paris; ENSTA Paris; University of Bielefeld
摘要：We consider a mean-field model of firms competing a` la Cournot on a commodity market, where the commodity price is given in terms of a power inverse demand function of the industry-aggregate production. Investment is irreversible and production capacity depreciates at a constant rate. Production is subject to Gaussian productivity shocks, whereas large nonanticipated macroeconomic events driven by a two-state continuous-time Markov chain can change the volatility of the shocks, as well as the...
-
作者：Spiers, Sandy; Bui, Hoa T.; Loxton, Ryan
摘要：The Euclidean max-sum diversity problem becomes substantially more difficult as the number of coordinates increases despite the number of decision variables not changing. In this paper, we overcome this complexity by constructing a new set of locations whose squared Euclidean distances equal that of the original. Using squared distances allows the objective function to be decomposed into the sum of pairwise distances within each coordinate. A partition set of the coordinates is then used to en...
-
作者：Heston, Steven L.; Hu, Bo
作者单位：University System of Maryland; University of Maryland College Park; George Mason University
摘要：A paradoxical conclusion arises in a series of game-theoretic models: the limit equilibria retain frictional qualities even as frictions seemingly vanish. This originates in textbook models, such as the differential game by Fershtman and Kamien [Fershtman C, Kamien MI (1987) Dynamic duopolistic competition with sticky prices. Econometrica 55(5):1151-1164] on duopolistic competition with sticky prices. We show that this paradox is an artifact of the type of limit restricted by continuous-time m...
-
作者：Simchi-Levi, David; Sun, Rui; Wang, Xinshang
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Shanghai Jiao Tong University
摘要：We study in this paper an online matching problem where a central platform needs to match a number of limited resources to different groups of users that arrive sequentially over time. The reward of each matching option depends on both the type of resource and the time period the user arrives. The matching rewards are assumed to be unknown but drawn from probability distributions that are known a priori. The platform then needs to learn the true rewards online based on real-time observations o...
-
作者：Wang, Tie; Gao, Rui; Xie, Yao
作者单位：The Chinese University of Hong Kong, Shenzhen; University of Texas System; University of Texas Austin; University System of Georgia; Georgia Institute of Technology
摘要：We study distributionally robust optimization with Sinkhorn distance: a variant of Wasserstein distance based on entropic regularization. We derive a convex programming dual reformulation for general nominal distributions, transport costs, and loss functions. To solve the dual reformulation, we develop a stochastic mirror descent algorithm with biased subgradient estimators and derive its computational complexity guarantees. Finally, we provide numerical examples using synthetic and real data ...
-
作者：Balkanski, Eric; Garimidi, Pranav; Gkatzelis, Vasilis; Schoepflin, Daniel; Tan, Xizhi
作者单位：Columbia University; Drexel University; Rutgers University System; Rutgers University New Brunswick
摘要：We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategy-proof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer while eliciting each seller's true cost for providing their service. Our main result in this paper is a novel method for designing budget-feasible auctions, lead...
-
作者：Ota, Matheus J.; Fukasawa, Ricardo
作者单位：University of Waterloo
摘要：The vehicle routing problem with stochastic demands (VRPSD) generalizes the classic vehicle routing problem by considering customer demands as random variables. Similar to other vehicle routing variants, state-of-the-art algorithms for the VRPSD are often based on set-partitioning formulations, which require efficient routines for the associated pricing problems. However, all of these set partitioning-based approaches have strong assumptions on the correlation between the demands of random var...
-
作者：Han, Yanjun; Weissman, Tsachy; Zhou, Zhengyuan
作者单位：New York University; New York University; Stanford University; New York University
摘要：We study online learning in repeated first-price auctions where a bidder, only observing the winning bid at the end of each auction, learns to adaptively bid to maximize the cumulative payoff. To achieve this goal, the bidder faces censored feedback: If the bidder wins the bid, then the bidder is not able to observe the highest bid of the other bidders, which we assume is i.i.d. drawn from an unknown distribution. In this paper, we develop the first learning algorithm that achieves a near-opti...
