Management Science

We develop a model of many-to-one matching markets in which agents with multiunit demand aim to maximize a cardinal linear objective subject to multidimensional knapsack constraints. The choice functions of agents with multiunit demand are therefore not substitutable. As a result, pairwise stable matchings may not exist and even when they do, may be highly inefficient. We provide an algorithm that finds a group-stable matching that approximately satisfies all the multidimensional knapsack constraints. The novel ingredient in our algorithm is a combination of matching with contracts and Scarf’s Lemma. We show that the degree of the constraint violation under our algorithm is proportional to the sparsity of the constraint matrix. The algorithm, therefore, provides practical constraint violation bounds for applications in contexts, such as refugee resettlement, day care allocation, and college admissions with diversity requirements. Simulations using refugee resettlement data show that our approach produces outcomes that are not only more stable, but also more efficient than the outcomes of the Deferred Acceptance algorithm. Moreover, simulations suggest that in practice, constraint violations under our algorithm would be even smaller than the theoretical bounds.

This paper was accepted by Gabriel Weintraub, revenue management and market analytics.

Tài liệu hiện có, dựa trên lý thuyết tín hiệu, đề xuất rằng các cam kết hoàn tiền (MBGs) sẽ được các công ty chất lượng cao sử dụng, trong đó chất lượng cao được định nghĩa là khả năng trả lại sản phẩm thấp. Tuy nhiên, trong thế giới ngày nay, các cam kết hoàn tiền rất phổ biến trong số các nhà bán lẻ lớn, ngay cả khi khả năng trả lại sản phẩm dao động rất lớn giữa họ. Để hiểu hiện tượng này, chúng tôi khám phá một môi trường cạnh tranh giữa các nhà bán lẻ chất lượng cao và chất lượng thấp, nơi mà người tiêu dùng hoàn toàn được thông tin và không có rủi ro, và các nhà bán lẻ nhận ra giá trị thu hồi cho các sản phẩm đã được trả lại. Khi các cam kết hoàn tiền có lãi, dưới nhu cầu liên tục, đây là trạng thái cân bằng Nash cho cả hai nhà bán lẻ để cung cấp các cam kết hoàn tiền, và nhà bán lẻ chất lượng thấp đạt lợi nhuận trong khi nhà bán lẻ chất lượng cao mất lợi nhuận so với khi không cung cấp các cam kết hoàn tiền. Ngược lại, nếu nhu cầu không liên tục, các nhà bán lẻ có thể hoạt động độc quyền trên các phân khúc thị trường tương ứng của họ, cho phép cả hai nhà bán lẻ đều có lợi từ các cam kết hoàn tiền, mặc dù nhà bán lẻ chất lượng thấp vẫn thu được nhiều lợi ích hơn.

Bài báo này đã được chấp nhận bởi J. Miguel Villas-Boas, chuyên ngành marketing.

For fossil fuel power plants to be built in the future, carbon capture and storage (CCS) technologies offer the potential for significant reductions in carbon dioxide (CO₂) emissions. We examine the break-even value for CCS adoptions, that is, the critical value in the charge for CO₂ emissions that would justify investment in CCS capabilities. Our analysis takes explicitly into account that the supply of electricity at the wholesale level (generation) is organized competitively in some U.S. jurisdictions, whereas in others a regulated utility provides integrated generation and distribution services. For either market structure, we find that emissions charges near $30 per tonne of CO₂ would be the break-even value for adopting CCS capabilities at new coal-fired power plants. The corresponding break-even values for natural gas plants are substantially higher, near $60 per tonne. Our break-even estimates serve as a basis for projecting the change in electricity prices once carbon emissions become costly. CCS capabilities effectively put an upper bound on the increase in electricity prices resulting from carbon regulations, and we estimate this bound to be near 30% at the retail level for both coal and natural gas plants. In contrast to the competitive power supply scenario, however, these price increases materialize only gradually for a regulated utility. The delay in price adjustments reflects that for regulated firms the basis for setting product prices is historical cost, rather than current cost.

This paper was accepted by Gérard P. Cachon, accounting.

In this paper a branch-and-bound procedure is described for scheduling the activities of a project of the PERT/CPM variety subject to precedence and resource constraints where the objective is to minimize project duration. The procedure is based on a depth-first solution strategy in which nodes in the solution tree represent resource and precedence feasible partial schedules. Branches emanating from a parent node correspond to exhaustive and minimal combinations of activities, the delay of which resolves resource conflicts at each parent node. Precedence and resource-based bounds described in the paper are combined with new dominance pruning rules to rapidly fathom major portions of the solution tree. The procedure is programmed in the C language for use on both a mainframe and a personal computer. The procedure has been validated using a standard set of test problems with between 7 and 50 activities requiring up to three resource types each. Computational experience on a personal computer indicates that the procedure is 11.6 times faster than the most rapid solution procedure reported in the literature while requiring less computer storage. Moreover, problems requiring large amounts of computer time using existing approaches for solving this problem type are rapidly solved with our procedure using the dominance rules described, resulting in a significant reduction in the variability in solution times as well.

Many real-world situations involve queueing systems in which customers wait for service for a limited time only and leave the system if service has not begun within that time. This paper considers a multiserver queueing system with impatient customers, where the customers arrive according to a Poisson process and the service requirements have a general distribution. A simple and insightful solution is presented for the loss probability. The solution is exact for exponential services and is an excellent heuristic for general service times.

An algorithm is developed to rapidly compute approximations for all the standard steady-state performance measures in the basic call-center queueing model M/GI/s/r+GI, which has a Poisson arrival process, independent and identically distributed (IID) service times with a general distribution, s servers, r extra waiting spaces and IID customer abandonment times with a general distribution. Empirical studies of call centers indicate that the service-time and abandon-time distributions often are not nearly exponential, so that it is important to go beyond the Markovian M/M/s/r+M special case, but the general service-time and abandon-time distributions make the realistic model very difficult to analyze directly. The proposed algorithm is based on an approximation by an appropriate Markovian M/M/s/r+M(n) queueing model, where M(n) denotes state-dependent abandonment rates. After making an additional approximation, steady-state waiting-time distributions are characterized via their Laplace transforms. Then the approximate distributions are computed by numerically inverting the transforms. Simulation experiments show that the approximation is quite accurate. The overall algorithm can be applied to determine desired staffing levels, e.g., the minimum number of servers needed to guarantee that, first, the abandonment rate is below any specified target value and, second, that the conditional probability that an arriving customer will be served within a specified deadline, given that the customer eventually will be served, is at least a specified target value.

The single-server queueing system is studied where arrivals are rejected if their waiting plus service times would exceed a fixed amount K. Applications of this model include equipment repair facilities and buffered communication devices with constant discharge rate receiving messages from a high-speed data channel. A procedure for computing the equilibrium behavior is described for the case of random arrivals and arbitrary service time requirements. Detailed analytic results and graphs are given for the case of exponentially distributed service time requirements, including the server utilization, rejection probability, mean time in system, mean server busy period, and the mean and probability density function of the virtual waiting time.

This paper investigates the effect upon performance in a service system, such as a telephone call center, of giving waiting customers state information. In particular, the paper studies two M/M/s/r queueing models with balking and reneging. For simplicity, it is assumed that each customer is willing to wait a fixed time before beginning service. However, customers differ, so the delay tolerances for successive customers are random. In particular, it is assumed that the delay tolerance of each customer is zero with probability β, and is exponentially distributed with mean α⁻¹ conditional on the delay tolerance being positive. Let N be the number of customers found by an arrival. In Model 1, no state information is provided, so that if N ≥ s, the customer balks with probability β; if the customer enters the system, he reneges after an exponentially distributed time with mean α⁻¹ if he has not begun service by that time. In Model 2, if N = s + k ≥ s, then the customer is told the system state k and the remaining service times of all customers in the system, so that he balks with probability β + (1 − β)(1 − q_k), where q_k = P(T > S_k), T is exponentially distributed with mean α⁻¹, S_k is the sum of k + 1 independent exponential random variables each with mean (sμ)⁻¹, and μ⁻¹ is the mean service time. In Model 2, all reneging is replaced by balking. The number of customers in the system for Model 1 is shown to be larger than that for Model 2 in the likelihood-ratio stochastic ordering. Thus, customers are more likely to be blocked in Model 1 and are more likely to be served without waiting in Model 2. Algorithms are also developed for computing important performance measures in these, and more general, birth-and-death models.

We consider how two networked large-scale service systems that normally operate separately, such as call centers, can help each other when one encounters an unexpected overload and is unable to immediately increase its own staffing. Our proposed control activates serving some customers from the other system when a ratio of the two queue lengths (numbers of waiting customers) exceeds a threshold. Two thresholds, one for each direction of sharing, automatically detect the overload condition and prevent undesired sharing under normal loads. After a threshold has been exceeded, the control aims to keep the ratio of the two queue lengths at a specified value. To gain insight, we introduce an idealized stochastic model with two customer classes and two associated service pools containing large numbers of agents. To set the important queue-ratio parameters, we consider an approximating deterministic fluid model. We determine queue-ratio parameters that minimize convex costs for this fluid model. We perform simulation experiments to show that the control is effective for the original stochastic model. Indeed, the simulations show that the proposed queue-ratio control with thresholds outperforms the optimal fixed partition of the servers given known fixed arrival rates during the overload, even though the proposed control does not use information about the arrival rates.

In this paper we show that for a finite Markov decision process an average optimal policy can be found by solving only one linear programming problem. Also the relation between the set of feasible solutions of the linear program and the set of stationary policies is analyzed.