The Optimality of a Simple Market Mechanism

Strategic behavior in a finite market can cause inefficiency in the allocation, and market mechanisms differ in how successfully they limit this inefficiency. A method for ranking algorithms in computer science is adapted here to rank market mechanisms according to how quickly inefficiency diminishes as the size of the market increases. It is shown that trade at a single market–clearing price in the k–double auction is worst–case asymptotic optimal among all plausible mechanisms: evaluating mechanisms in their least favorable trading environments for each possible size of the market, the k–double auction is shown to force the worst–case inefficiency to zero at the fastest possible rate.     

On the Effects of Capacity Agent on Market Equilibrium

We consider a setting of two firms and one capacity agent. Each firm serves a primary market, and the capacity agent sustains a common market to draw demand for capacity from the external firms. The firms can partner with the capacity agent under her contract to serve the common market. When they use the common market mainly as an outlet for their unused capacities, the capacity agent will only specify a variable fee for each capacity unit deployed through her, and prefer to partner with one firm in most circumstances. When the firms adjust capacities to accommodate the businesses created by serving the common market, the capacity agent will specify a lump‐sum payment and a variable fee, and will be more likely to incentivize only one firm to partner with her, when the common market is sufficiently large or the demands in the common and primary markets are strongly correlated. She will always use a fixed fee to extract, while not necessarily all, the profit gains to the firms serving the common market, but will use a variable fee only when partnering with both firms. The key results are robust with respect to market configuration and contract type.     

On the Generic (Im)Possibility of Full Surplus Extraction in Mechanism Design

A number of studies, most notably Crémer and McLean (1985, 1988), have shown that in generic type spaces that admit a common prior and are of a fixed finite size, an uninformed seller can design mechanisms that extract all the surplus from privately informed bidders. We show that this result hinges on the nonconvexity of such a family of priors. When the ambient family of priors is convex, generic priors do not allow for full surplus extraction provided that for at least one prior in this family, players' beliefs about other players' types do not pin down the players' own preferences. In particular, full surplus extraction is generically impossible in finite type spaces with a common prior. Similarly, generic priors on the universal type space do not allow for full surplus extraction.     

The Effect of Competition on the Efficient–Responsive Choice

In determining their operations strategy, a firm chooses whether to be responsive or efficient. For firms competing in a market with uncertain demand and varying intensity of substitutability for the competitor's product, we characterize the responsive or efficient choice in equilibrium. To focus first on the competitive implications, we study a model where a firm can choose to be responsive at no additional fixed or marginal cost. We find that competing firms will choose the same configuration (responsive or efficient), and responsiveness tends to be favorable when demand uncertainty is high or when product competition is not too strong. Intense competition can drive firms to choose to be efficient rather than responsive even when there is no additional cost of being responsive. In such a case, both firms would be better off by choosing to be responsive but cannot credibly commit. We extend the basic model to study the impact of endogenized production timing, multiple productions and product holdback (or, equivalently, postponed production). For all these settings, we find structurally similar results; firms choose the same configuration, and the firms may miss Pareto‐improvements. Furthermore, through extensions to the basic model, we find that greater operational flexibility can make responsiveness look less attractive in the presence of product competition. In contrast to our basic model and other extensions, we find it is possible for one firm to be responsive while the other is efficient when there is either a fixed cost or variable cost premium associated with responsive delivery.     

The Independence Number of Graphs with a Forbidden Cycle and Ramsey Numbers

Let k 5 be a fixed integer and let m = (k – 1)/2. It is shown that the independence number of a C _k-free graph is at least c ₁[ d(v)^{1/(m – 1)}]^{(m – 1)/m} and that, for odd k, the Ramsey number r(C _k, K _n) is at most c ₂(n ^{m + 1}/log n)^1/m , where c ₁ = c ₁(m) > 0 and c ₂ = c ₂(m) > 0.     

P2P Marketplaces and Retailing in the Presence of Consumers' Valuation Uncertainty

Can peer‐to‐peer (P2P) marketplaces benefit traditional supply chains when consumers may experience valuation risk? P2P marketplaces can mitigate consumers' risk by allowing them to trade mismatched goods; yet, they also impose a threat to retailers and their suppliers as they compete over consumers. Further, do profit‐maximizing marketplaces always extract the entire consumer surplus from the online trades? Our two‐period model highlights the effects introduced by P2P marketplaces while accounting for the platform's pricing decisions. We prove that with low product unit cost, the P2P marketplace sets its transaction fee to the market clearing price, thereby extracting all of the seller surplus. In this range of product unit cost, the supply chain partners are worse off due to the emergence of a P2P marketplace. However, when the unit cost is high, the platform sets its transaction fee to be less than the market clearing price, intentionally leaving money on the table, as a mechanism to stimulate first period demand for new goods in expectation for some of them to be traded later, in the second period, via the marketplace. It is not until the surplus left with the sellers is sufficiently high that the supply chain partners manage to extract some of this surplus, ultimately making them better off due to a P2P marketplace. We further analyze the impact of a P2P marketplace on consumer surplus and social welfare. In addition, we consider model variants accounting for a frictionless platform and consumer strategic waiting.     

售电侧改革、市场主体变化与电价红利:基于讨价还价博弈

本文通过构建“一对多”和“多对多”讨价还价博弈模型,研究了售电侧改革前后,发电商和售电公司之间关于消费者剩余分配的博弈过程。具体来说,文章从售电侧改革带来的博弈主体与博弈机制变化角度,揭示了售电侧改革对用户电价红利的影响。研究发现:售电侧放开后,电力市场交易机制由“一对多”竞价上网变为“多对多”讨价还价匹配,造成了售电侧博弈主体的议价能力下降,发电侧博弈主体相对议价能力上升。发电商群体将索取更多的消费者剩余,从而推动发电侧整体报价的上涨,挤压了售电侧的利润空间,导致售电公司被迫抬高市场电价,最终剥夺了用户的电价红利。研究揭示了售电侧改革未能带来电价下降的根本原因。     

Strong Duality for a Multiple‐Good Monopolist

We characterize optimal mechanisms for the multiple‐good monopoly problem and provide a framework to find them. We show that a mechanism is optimal if and only if a measure μ derived from the buyer's type distribution satisfies certain stochastic dominance conditions. This measure expresses the marginal change in the seller's revenue under marginal changes in the rent paid to subsets of buyer types. As a corollary, we characterize the optimality of grand‐bundling mechanisms, strengthening several results in the literature, where only sufficient optimality conditions have been derived. As an application, we show that the optimal mechanism for n independent uniform items each supported on [c,c+1] is a grand‐bundling mechanism, as long as c is sufficiently large, extending Pavlov's result for two items Pavlov, 2011. At the same time, our characterization also implies that, for all c and for all sufficiently large n, the optimal mechanism for n independent uniform items supported on [c,c+1] is not a grand‐bundling mechanism.     

The empirical analysis of the -bilateral optimized combinatorial auction model

This study proposes a new and highly efficient dynamic combinatorial auction mechanism—the N-bilateral optimized combinatorial auction (N-BOCA). N-BOCA is a flexible iterative combinatorial auction model that offers more optimized trading for multiple suppliers and purchasers in the supply chain than one-sided combinatorial auction. We design the N-BOCA model from the perspectives of market architecture, trading rules, and decision strategy for winner determination, the decision strategy for winner determination needs flexible optimization modeling capability. Thus rule-based reasoning was applied for reflecting the flexible decision strategies. We also show the viability of N-BOCA through Paired Samples T-test experimentation. It shows that N-BOCA yields higher purchase efficiency and effectiveness than the one-auctioneer to multi-bidders (1-to-N) combinatorial auction mechanism.     

Sensitivity of the Optimum to Perturbations of the Profit or Weight of an Item in the Binary Knapsack Problem

In the binary single constraint Knapsack Problem, denoted KP, we are given a knapsack of fixed capacity c and a set of n items. Each item j, j = 1,...,n, has an associated size or weight w_j and a profit p_j. The goal is to determine whether or not item j, j = 1,...,n, should be included in the knapsack. The objective is to maximize the total profit without exceeding the capacity c of the knapsack. In this paper, we study the sensitivity of the optimum of the KP to perturbations of either the profit or the weight of an item. We give approximate and exact interval limits for both cases (profit and weight) and propose several polynomial time algorithms able to reach these interval limits. The performance of the proposed algorithms are evaluated on a large number of problem instances.     

Assortative Matching and Search

In Becker's (1973) neoclassical marriage market model, matching is positively assortaive if types are complements: i.e., match output f(x, y) is supermodular in x and y. We reprise this famous result assuming time‐intensive partner search and transferable output. We prove existence of a search equilibrium with a continuum of types, and then characterize matching. After showing that Becker's conditions on match output no longer suffice for assortative matching, we find sufficient conditions valid for any search frictions and type distribution: supermodularity not only of output f, but also of log f_x and log f_xy. Symmetric submodularity conditions imply negatively assortative matching. Examples show these conditions are necessary.     

Optimal algorithms for online time series search and one-way trading with interrelated prices

The basic models of online time series search and one-way trading are introduced by El-Yaniv et al. in Algorithmica 30(1), 101–139 (2001) where it is assumed that the prices are bounded within interval [m,M] (0<m<M). In this paper, we consider another case where every two consecutive prices are interrelated, that is, the variation range of each price depends on its preceding price. We present optimal deterministic online algorithms for the two problems, respectively. According to one conclusion in Algorithmica 30(1), 101–139 (2001), we further point out that for the case we considered, an optimal deterministic algorithm for the one-way trading problem can be regarded as an optimal randomized one for the time series search problem, and randomization is useless for the one-way trading problem.     

Competing Mechanisms in a Common Value Environment

Consider strategic risk‐neutral traders competing in schedules to supply liquidity to a risk‐averse agent who is privately informed about the value of the asset and his hedging needs. Imperfect competition in this common value environment is analyzed as a multi‐principal game in which liquidity suppliers offer trading mechanisms in a decentralized way. Each liquidity supplier behaves as a monopolist facing a residual demand curve resulting from the maximizing behavior of the informed agent and the trading mechanisms offered by his competitors. There exists a unique equilibrium in convex schedules. It is symmetric and differentiable and exhibits typical features of market‐power: Equilibrium trading volume is lower than ex ante efficiency would require. Liquidity suppliers charge positive mark‐ups and make positive expected profits, but these profits decrease with the number of competitors. In the limit, as this number goes to infinity, ask (resp. bid) prices converge towards the upper (resp. lower) tail expectations obtained in Glosten (1994) and expected profits are zero.     

Performance ratios of the Karmarkar-Karp differencing method

We consider the multiprocessor scheduling problem in which one must schedule n independent tasks nonpreemptively on m identical, parallel machines, such that the completion time of the last task is minimal. For this well-studied problem the Largest Differencing Method of Karmarkar and Karp outperforms other existing polynomial-time approximation algorithms from an average-case perspective. For m ≥ 3 the worst-case performance of the Largest Differencing Method has remained a challenging open problem. In this paper we show that the worst-case performance ratio is bounded between . For fixed m we establish further refined bounds in terms of n.     

进入中国的FDI的行为变迁对国际收支的影响研究

近年来,进入中国的FDI不断从出口导向型向市场寻求型转变,快速抢占中国市场。本文通过建立差分模型,考察FDI这一行为变迁对国际收支的影响。研究表明以占领东道国市场为目的FDI将在长时期内不断削减FDI产生的净出口效应,使得东道国国际收支顺差不断减小,且随着寻求市场型FDI存量占FDI的比重不断增大,极有可能导致FDI产生的国际收支净效益转为逆差,甚至引发国际收支危机。     

A Bias–Reduced Log–Periodogram Regression Estimator for the Long–Memory Parameter

In this paper, we propose a simple bias–reduced log–periodogram regression estimator, ^d_r, of the long–memory parameter, d, that eliminates the first– and higher–order biases of the Geweke and Porter–Hudak (1983) (GPH) estimator. The bias–reduced estimator is the same as the GPH estimator except that one includes frequencies to the power 2k for k=1,…,r, for some positive integer r, as additional regressors in the pseudo–regression model that yields the GPH estimator. The reduction in bias is obtained using assumptions on the spectrum only in a neighborhood of the zero frequency. Following the work of Robinson (1995b) and Hurvich, Deo, and Brodsky (1998), we establish the asymptotic bias, variance, and mean–squared error (MSE) of ^d_r, determine the asymptotic MSE optimal choice of the number of frequencies, m, to include in the regression, and establish the asymptotic normality of ^d_r. These results show that the bias of ^d_r goes to zero at a faster rate than that of the GPH estimator when the normalized spectrum at zero is sufficiently smooth, but that its variance only is increased by a multiplicative constant. We show that the bias–reduced estimator ^d_r attains the optimal rate of convergence for a class of spectral densities that includes those that are smooth of order s≥1 at zero when r≥(s−2)/2 and m is chosen appropriately. For s>2, the GPH estimator does not attain this rate. The proof uses results of Giraitis, Robinson, and Samarov (1997). We specify a data–dependent plug–in method for selecting the number of frequencies m to minimize asymptotic MSE for a given value of r. Some Monte Carlo simulation results for stationary Gaussian ARFIMA (1, d, 1) and (2, d, 0) models show that the bias–reduced estimators perform well relative to the standard log–periodogram regression estimator.     

O(m2) ALGORITHMS FOR THE TWO AND THREE SUBLOT LOT STREAMING PROBLEM

Lot streaming is the process of splitting a job or lot into sublots to reduce its makespan on a sequence of machines. The goal in the lot streaming problem is to find the optimal size of each sublot that will minimize the makespan. The makespan is defined as the time the last sublot completes its processing on the last machine. If the sizes of these sublots are restricted to remain the same on all machines, the solution is called a consistent sublot solution. However, if the sizes of the sublots are allowed to vary, the solution is referred to as a nonconsistent or variable sublot solution. Also, if the machines must be in operation continuously from the first to the last sublot, the solution is a no idling solution. When setups are explicitly considered in the problem, there will be two cases. If setups on each machine require some portion of the first sublot be present by the machine, the problem is referred to as the attached setup time problem. If setups can be performed ahead of time before the first sublot reaches the particular machine, the corresponding problem is referred to as the detached setup problem. Finally, if the machines are allowed to be idle between the processing of sublots, the resultant solution is an intermittent idling solution. In this paper, the consistent sublot lot streaming problem with intermittent idling and no setups is discussed. The models developed also assume that the number of sublots are fixed and known. The m machine two sublot lot streaming problem is reviewed. An algorithm for the three sublot, m machine problem is derived using a network representation of the problem. The complexity of the algorithm is O (m²). Finally, using the insights from three sublot problem, a heuristic algorithm is provided for the m machine, n sublot problems. The results on the proposed heuristic are very encouraging; average percent deviation from optimal makespan is approximately at 0.76% on 155 randomly generated problems with different m and n values.     

A Polynomial Time Approximation Scheme for the Problem of Interconnecting Highways

The objective of the Interconnecting Highways problem is to construct roads of minimum total length to interconnect n given highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a polynomial time approximation scheme for this problem by applying Arora's framework (Arora, 1998; also available from http:www.cs.princeton.edu/~arora). For every fixed c > 1 and given any n line segments in the plane, a randomized version of the scheme finds a -approximation to the optimal cost in O(n ^O(c)log(n) time.     

L(j,k)- and circular L(j,k)-labellings for the products of complete graphs

Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ _j,k -number of G, denoted by λ _j,k (G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} such that |f(u)−f(v)| _m ≥j if u and v are adjacent; and |f(u)−f(v)| _m ≥k if u and v are at distance two apart, where |x| _m =min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ _j,k -number of G and denoted by σ _j,k (G). The λ _j,k -numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ _j,k -numbers of direct products of two complete graphs and the σ _j,k -numbers of direct products and Cartesian products of two complete graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; NSFC, China, grant 10171013; and Southeast University Science Foundation grant XJ0607230.     

Hybrid and Size‐Corrected Subsampling Methods

This paper considers inference in a broad class of nonregular models. The models considered are nonregular in the sense that standard test statistics have asymptotic distributions that are discontinuous in some parameters. It is shown in Andrews and Guggenberger (2009a) that standard fixed critical value, subsampling, and m out of n bootstrap methods often have incorrect asymptotic size in such models. This paper introduces general methods of constructing tests and confidence intervals that have correct asymptotic size. In particular, we consider a hybrid subsampling/fixed‐critical‐value method and size‐correction methods. The paper discusses two examples in detail. They are (i) confidence intervals in an autoregressive model with a root that may be close to unity and conditional heteroskedasticity of unknown form and (ii) tests and confidence intervals based on a post‐conservative model selection estimator.