-
作者：Blanchet, Jose H.; Reiman, Martin I.; Shah, Virag; Wein, Lawrence M.; Wu, Linjia
作者单位：Stanford University; Columbia University; Stanford University
摘要：We consider a matching market where buyers and sellers arrive according to independent Poisson processes at the same rate and independently abandon the market if not matched after an exponential amount of time with the same mean. In this centralized market, the utility for the system manager from matching any buyer and any seller is a general random variable. We consider a sequence of systems indexed by n where the arrivals in the nth system are sped up by a factor of n. We analyze two familie...
-
作者：Chen, Qi (George); Beil, Damian R.; Duenyas, Izak
作者单位：University of London; London Business School; University of Michigan System; University of Michigan
摘要：A buyer seeking to outsource production may be able to find ways to reduce a potential supplier's cost, for example, by suggesting improvements to the supplier's proposed production methods. We study how a buyer could use such cost-reduction investigations by proposing a three-step supplier selection mechanism: First, each of several potential suppliers submits a price bid for a contract. Second, for each potential supplier, the buyer can exert an effort to see if the buyer can identify how th...
-
作者：Arieli, Itai; Babichenko, Yakov; Mueller-Frank, Manuel
作者单位：Technion Israel Institute of Technology; University of Navarra; IESE Business School
摘要：We analyze boundedly rational updating in a repeated interaction network model with binary actions and binary states. Agents form beliefs according to discretized DeGroot updating and apply a decision rule that assigns a (mixed) action to each belief. We first show that under weak assumptions, random decision rules are sufficient to achieve agreement in finite time in any strongly connected network. Ourmain result establishes that naive learning can be achieved in any large strongly connected ...
-
作者：Gur, Yonatan; Momeni, Ahmadreza; Wager, Stefan
作者单位：Stanford University; Stanford University
摘要：We study a nonparametric multiarmed bandit problem with stochastic covariates, where a key complexity driver is the smoothness of payoff functions with respect to covariates. Previous studies have focused on deriving minimax-optimal algorithms in cases where it is a priori known how smooth the payoff functions are. In practice, however, the smoothness of payoff functions is typically not known in advance, and misspecification of smoothness may severely deteriorate the performance of existing m...
-
作者：Borgs, Christian; Chayes, Jennifer T.; Shah, Devavrat; Yu, Christina Lee
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley; University of California System; University of California Berkeley; Cornell University
摘要：We consider sparse matrix estimation where the goal is to estimate an n-by-n matrix from noisy observations of a small subset of its entries. We analyze the estimation error of the popularly used collaborative filtering algorithm for the sparse regime. Specifically, we propose a novel iterative variant of the algorithm, adapted to handle the setting of sparse observations. We establish that as long as the number of entries observed at random scale logarithmically larger than linear in n, the e...
-
作者：He, Xue Dong; Strub, Moris S.
作者单位：Chinese University of Hong Kong; Southern University of Science & Technology; Southern University of Science & Technology
摘要：We study the implications of various models of partially endogenous reference point formation on optimal decision making in the context of portfolio optimization under loss aversion. Specifically, we first consider the partially endogenous model of De Giorgi and Post [Management Science (2011) 57(6):1094-1110], where the reference point is determined in equilibrium but contains an exogenous component. We find that optimal trading behavior is as if the reference point were completely exogenous ...
-
作者：Bonami, Pierre; Lodi, Andrea; Zarpellon, Giulia
作者单位：Universite de Montreal; Polytechnique Montreal; Vector Institute for Artificial Intelligence
摘要：With the aim of fully embedding learned predictions in the algorithmic design of a mixed-integer quadratic programming (MIQP) solver, we translate the algorithmic question of whether to linearize convex MIQPs into a classification task and use machine learning (ML) techniques to tackle it. We represent MIQPs and the linearization decision by careful target and feature engineering. Computational experiments and evaluation metrics are designed to further incorporate the optimization knowledge in...
-
作者：Shah, Devavrat; Xie, Qiaomin; Xu, Zhi
作者单位：Massachusetts Institute of Technology (MIT); University of Wisconsin System; University of Wisconsin Madison
摘要：In this work, we consider the popular tree-based search strategy within the framework of reinforcement learning, the Monte Carlo tree search (MCTS), in the context of the infinite-horizon discounted cost Markov decision process (MDP). Although MCTS is believed to provide an approximate value function for a given state with enough simulations, the claimed proof of this property is incomplete. This is because the variant of MCTS, the upper confidence bound for trees (UCT), analyzed in prior work...
-
作者：Shafiee, Mehrnoosh; Ghaderi, Javad
作者单位：Columbia University
摘要：Motivated bymodern parallel computing applications, we consider the problem of scheduling parallel-task jobs with heterogeneous resource requirements in a cluster of machines. Each job consists of a set of tasks that can be processed in parallel; however, the job is considered completed only when all its tasks finish their processing, which we refer to as the synchronization constraint. Furthermore, assignment of tasks to machines is subject to placement constraints, that is, each task can be ...
-
作者：Alpern, Steve; Bui, Thuy; Lidbetter, Thomas; Papadaki, Katerina
作者单位：University of Warwick; Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick; University of Virginia; University of London; London School Economics & Political Science
摘要：We study a patrolling game played on a network Q, considered as a metric space. The Attacker chooses a point of Q (not necessarily a node) to attack during a chosen time interval of fixed duration. The Patroller chooses a unit speed path on Q and intercepts the attack (and wins) if she visits the attacked point during the attack-time interval. This zero-sum game models the problem of protecting roads or pipelines from an adversarial attack. The payoff to the maximizing Patroller is the probabi...
