-
作者：Wang, Xinshang; Van-Anh Truong
作者单位：Columbia University
摘要：We study a fundamental model of resource allocation in which a finite amount of service capacity must be allocated to a stream of jobs of different priorities arriving randomly over time. Jobs incur costs and may also cancel while waiting for service. To increase the rate of service, overtime capacity can be used at a cost. This model has application in healthcare scheduling, server applications, make-to-order manufacturing systems, general service systems, and green computing. We present an o...
-
作者：Ho-Nguyen, Nam; Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University
摘要：Robust optimization (RO) has emerged as one of the leading paradigms to efficiently model parameter uncertainty. The recent connections between RO and problems in statistics and machine learning domains demand for solving RO problems in ever larger scales. However, the traditional approaches for solving RO formulations based on building and solving robust counterparts or the iterative approaches utilizing nominal feasibility oracles can be prohibitively expensive and thus significantly hinder ...
-
作者：Bayati, Mohsen; Montanari, Andrea; Saberi, Amin
作者单位：Stanford University; Stanford University; Stanford University; Stanford University; Stanford University; Stanford University
摘要：Random graph generation is an important tool for studying large complex networks. Despite abundance of random graph models, constructing models with application-driven constraints is poorly understood. To advance state-of-the-art in this area, we focus on random graphs without short cycles as a stylized family of graphs, and we propose the RandGraph algorithm for randomly generating them. For any constant k, when m = O(n(1+1/[2k(k+3)])), RandGraph generates an asymptotically uniform random gra...
-
作者：Gianfreda, Angelica; Bunn, Derek
作者单位：University of London; London Business School; Free University of Bozen-Bolzano; University of London; London Business School
摘要：The wide range of models needed to support the various short-term operations for electricity generation demonstrates the importance of accurate specifications for the uncertainty in market prices. This is becoming increasingly challenging, since hourly price densities for electricity exhibit a variety of shapes, with their characteristic features changing substantially within the day and evolving over time. Furthermore, the influx of renewable power, wind, and solar, in particular, has made th...
-
作者：Acemoglu, Daron; Makhdoumi, Ali; Malekian, Azarakhsh; Ozdaglar, Asuman
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); University of Toronto
摘要：To systematically study the implications of additional information about routes provided to certain users (e.g., via GPS-based route guidance systems), we introduce a new class of congestion games in which users have differing information sets about the available edges and can only use routes consisting of edges in their information set. After defining the notion of an information-constrained wardrop equilibrium (ICWE) for this class of congestion games and studying its basic properties, we tu...
-
作者：Luo, Yuan; Shah, Nihar B.; Huang, Jianwei; Walrand, Jean
作者单位：Imperial College London; Chinese University of Hong Kong; Chinese University of Hong Kong; University of California System; University of California Berkeley
摘要：We consider a problem of prediction based on opinions elicited from heterogeneous rational agents with private information. Making an accurate prediction with a minimal cost requires a joint design of the incentive mechanism and the prediction algorithm. To elicit heterogeneous agents' private information and incentivize agents with different capabilities to act in the principal's best interest, we design an optimal joint incentive mechanism and prediction algorithm called COPE (COst and Predi...
-
作者：Russo, Daniel; Van Roy, Benjamin
作者单位：Columbia University; Stanford University
摘要：We propose information-directed sampling-a new approach to online optimization problems in which a decision maker must balance between exploration and exploitation while learning from partial feedback. Each action is sampled in a manner that minimizes the ratio between squared expected single-period regret and a measure of information gain: the mutual information between the optimal action and the next observation. We establish an expected regret bound for information-directed sampling that ap...
-
作者：Bakshi, Nitin; Pinker, Edieal
作者单位：Utah System of Higher Education; University of Utah; Yale University
摘要：Public warnings have the potential to mitigate the threat from terrorism: the public is alerted, and in response, the terrorist may defer his attack. Paradoxically, warnings can be a victim of their own success. The absence of an attack may be misconstrued by the warning recipients as a false alarm, leading to warning fatigue and a dampened response to future warnings-also referred to as the cry-wolf effect. To capture this phenomenon and examine its implications, we model the interaction betw...
-
作者：Ding, Yichuan; Ge, Dongdong; He, Simai; Ryan, Christopher Thomas
作者单位：University of British Columbia; Shanghai University of Finance & Economics; University of Chicago
摘要：We propose a novel methodology to study kidney exchange. Using a random graph model of kidney exchange, we propose a nonasymptotic approach to quantifying the effectiveness of transplant chains in reducing the number of unmatched highly sensitized patients. Our approach is based on a two-phase random walk procedure where random walks are used to allocate chains, followed by allocation in cycles. The benefit of random walks is that they preserve the probabilistic structure of residual graphs, g...
-
作者：Scarsini, Marco; Schroder, Marc; Tomala, Tristan
作者单位：Luiss Guido Carli University; RWTH Aachen University; Hautes Etudes Commerciales (HEC) Paris
摘要：We propose a model of discrete time dynamic congestion games with atomic players and a single source-destination pair. The latencies of edges are composed of free-flow transit times and possible queuing time due to capacity constraints. We give a precise description of the dynamics induced by the individual strategies of players and of the corresponding costs, either when the traffic is controlled by a planner, or when players act selfishly. In parallel networks, optimal and equilibrium behavi...
