On the throughput-WIP trade-off in queueing systems, diminishing returns and the threshold property: A linear programming approach

We present a new unifying framework for investigating throughput-WIP(Work-in-Process) optimal control problems in queueing systems,based on reformulating them as linear programming (LP) problems withspecial structure: We show that if a throughput-WIP performance pairin a stochastic system satisfies the Threshold Property we introducein this paper, then we can reformulate the problem of optimizing alinear objective of throughput-WIP performance as a (semi-infinite)LP problem over a polygon with special structure (a thresholdpolygon). The strong structural properties of such polygones explainthe optimality of threshold policies for optimizing linearperformance objectives: their vertices correspond to the performancepairs of threshold policies. We analyze in this framework theversatile input-output queueing intensity control model introduced byChen and Yao (1990), obtaining a variety of new results, including (a)an exact reformulation of the control problem as an LP problem over athreshold polygon; (b) an analytical characterization of the Min WIPfunction (giving the minimum WIP level required to attain a targetthroughput level); (c) an LP Value Decomposition Theorem that relatesthe objective value under an arbitrary policy with that of a giventhreshold policy (thus revealing the LP interpretation of Chen andYao's optimality conditions); (d) diminishing returns and invarianceproperties of throughput-WIP performance, which underlie thresholdoptimality; (e) a unified treatment of the time-discounted andtime-average cases.

Worst-case bounds for the logarithmic loss of predictors

We investigate on-line prediction of individual sequences. Given a class of predictors, the goal is to predict as well as the best predictor in the class, where the loss is measured by the self information (logarithmic) loss function. The excess loss (regret) is closely related to the redundancy of the associated lossless universal code. Using Shtarkov's theorem and tools from empirical process theory, we prove a general upper bound on the best possible (minimax) regret. The bound depends on certain metric properties of the class of predictors. We apply the bound to both parametric and nonparametric classes ofpredictors. Finally, we point out a suboptimal behavior of the popular Bayesian weighted average algorithm.

Reputation and honesty in a market for information

Previous works on asymmetric information in asset markets tendto focus on the potential gains in the asset market itself. We focus on the market for information and conduct an experimental study to explore, in a game of finite but uncertain duration, whether reputation can be an effective constraint on deliberate misinformation. At the beginning of each period, an uninformed potential asset buyer can purchase information, at a fixed price and from a fully-informed source, about the value of the asset in that period. The informational insiders cannot purchase the asset and are given short-term incentives to provide false information when the asset value is low. Our model predicts that, in accordance with the Folk Theorem, Pareto-superior outcomes featuring truthful revelation should be sustainable. However, this depends critically on beliefs about rationality and behavior. We find that, overall, sellers are truthful 89% of the time. More significantly, the observed frequency of truthfulness is 81% when the asset value is low. Our result is consistent with both mixed-strategy and trigger strategy interpretations and provides evidence that most subjects correctly anticipate rational behavior. We discuss applications to financial markets, media regulation, and the stability of cartels.

Homotopy Batalin-Vilkovisky algebras

This paper provides an explicit cofibrant resolution of the operad encoding Batalin-Vilkovisky algebras. Thus it defines the notion of homotopy Batalin-Vilkovisky algebras with the required homotopy properties. To define this resolution we extend the theory of Koszul duality to operads and properads that are defind by quadratic and linear relations. The operad encoding Batalin-Vilkovisky algebras is shown to be Koszul in this sense. This allows us to prove a Poincare-Birkhoff-Witt Theorem for such an operad and to give an explicit small quasi-free resolution for it. This particular resolution enables us to describe the deformation theory and homotopy theory of BV-algebras and of homotopy BV-algebras. We show that any topological conformal field theory carries a homotopy BV-algebra structure which lifts the BV-algebra structure on homology. The same result is proved for the singular chain complex of the double loop space of a topological space endowed with an action of the circle. We also prove the cyclic Deligne conjecture with this cofibrant resolution of the operad BV. We develop the general obstruction theory for algebras over the Koszul resolution of a properad and apply it to extend a conjecture of Lian-Zuckerman, showing that certain vertex algebras have an explicit homotopy BV-algebra structure.

Borcherds products and arithmetic intersection theory on Hilbert modular surfaces

We prove an arithmetic version of a theorem of Hirzebruch and Zagier saying that Hirzebruch-Zagier divisors on a Hilbert modular surface are the coefficients of an elliptic modular form of weight 2. Moreover, we determine the arithmetic selfintersection number of the line bundle of modular forms equipped with its Petersson metric on a regular model of a Hilbert modular surface, and we study Faltings heights of arithmetic Hirzebruch-Zagier divisors.

Bounds on multisecant lines

The purpose of this paper is two fold. First, we give an upper bound on the orderof a multisecant line to an integral arithmetically Cohen-Macaulay subscheme in Pn of codimension two in terms of the Hilbert function. Secondly, we givean explicit description of the singular locus of the blow up of an arbitrary local ring at a complete intersection ideal. This description is used to refine standardlinking theorem. These results are tied together by the construction of sharp examples for the bound, which uses the linking theorems.

Semi-purity of tempered Deligne cohomology

In this paper we define the formal and tempered Deligne cohomology groups, that are obtained by applying the Deligne complex functor to the complexes of formal differential forms and tempered currents respectively. We then prove the existence of a duality between them, a vanishing theorem for the former and a semipurity property for the latter. The motivation of these results comes from the study of covariant arithmetic Chow groups. The semipurity property of tempered Deligne cohomology implies, in particular, that several definitions of covariant arithmetic Chow groups agree for projective arithmetic varieties.

Thermal activation and ATP dependence of the cytoskeleton remodeling dynamics

The cytoskeleton (CSK) is a nonequilibrium polymer network that uses hydrolyzable sources of free energy such as adenosine triphosphate (ATP) to remodel its internal structure. As in inert nonequilibrium soft materials, CSK remodeling has been associated with structural rearrangements driven by energy-activated processes. We carry out particle tracking and traction microscopy measurements of alveolar epithelial cells at various temperatures and ATP concentrations. We provide the first experimental evidence that the remodeling dynamics of the CSK is driven by structural rearrangements over free-energy barriers induced by thermally activated forces mediated by ATP. The measured activation energy of these forces is ~40kBTr (kB being the Boltzmann constant and Tr being the room temperature). Our experiments provide clues to understand the analogy between the dynamics of the living CSK and that of inert nonequilibrium soft materials.

The set of undominated imputations and the core: an axiomatic approach

This paper provides an axiomatic framework to compare the D-core (the set of undominatedimputations) and the core of a cooperative game with transferable utility. Theorem1 states that the D-core is the only solution satisfying projection consistency, reasonableness (from above), (*)-antimonotonicity, and modularity. Theorem 2 characterizes the core replacing (*)-antimonotonicity by antimonotonicity. Moreover, these axioms alsocharacterize the core on the domain of convex games, totally balanced games, balancedgames, and superadditive games

Differential equations driven by fractional Brownian motion

A global existence and uniqueness result of the solution for multidimensional, time dependent, stochastic differential equations driven by a fractional Brownian motion with Hurst parameter H> is proved. It is shown, also, that the solution has finite moments. The result is based on a deterministic existence and uniqueness theorem whose proof uses a contraction principle and a priori estimates.

Low energy excitations of double quantum dots in the lowest Landau level regime

We study the spectrum and magnetic properties of double quantum dots in the lowest Landau level for different values of the hopping and Zeeman parameters by means of exact diagonalization techniques in systems of N=6 and 7 electrons and a filling factor close to 2. We compare our results with those obtained in double quantum layers and single quantum dots. The Kohn theorem is also discussed.

Correlations derived from modern nucleon-nucleon potentials

Various modern nucleon-nucleon (NN) potentials yield a very accurate fit to the nucleon-nucleon scattering phase shifts. The differences between these interactions in describing properties of nuclear matter are investigated. Various contributions to the total energy are evaluated employing the Hellmann-Feynman theorem. Special attention is paid to the two-nucleon correlation functions derived from these interactions. Differences in the predictions of the various interactions can be traced back to the inclusion of nonlocal terms.

Diffusion on a solid surface: anomalous is normal

We present a numerical study of classical particles diffusing on a solid surface. The particles motion is modeled by an underdamped Langevin equation with ordinary thermal noise. The particle-surface interaction is described by a periodic or a random two-dimensional potential. The model leads to a rich variety of different transport regimes, some of which correspond to anomalous diffusion such as has recently been observed in experiments and Monte Carlo simulations. We show that this anomalous behavior is controlled by the friction coefficient and stress that it emerges naturally in a system described by ordinary canonical Maxwell-Boltzmann statistics.

From subdiffusion to superdiffusion of particles on solid surfaces

We present a numerical and partially analytical study of classical particles obeying a Langevin equation that describes diffusion on a surface modeled by a two-dimensional potential. The potential may be either periodic or random. Depending on the potential and the damping, we observe superdiffusion, large-step diffusion, diffusion, and subdiffusion. Superdiffusive behavior is associated with low damping and is in most cases transient, albeit often long. Subdiffusive behavior is associated with highly damped particles in random potentials. In some cases subdiffusive behavior persists over our entire simulation and may be characterized as metastable. In any case, we stress that this rich variety of behaviors emerges naturally from an ordinary Langevin equation for a system described by ordinary canonical Maxwell-Boltzmann statistics.

Heat fluctuations in Brownian transducers

The heat fluctuation probability distribution function in Brownian transducers operating between two heat reservoirs is studied. We find, both analytically and numerically, that the recently proposed fluctuation theorem for heat exchange [C. Jarzynski and D. K. Wojcik, Phys. Rev. Lett. 92, 230602 (2004)] has to be applied carefully when the coupling mechanism between both baths is considered. We also conjecture how to extend such a relation when an external work is present.