Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions

In pay-per-click sponsored search auctions which are currently extensively used by search engines, the auction for a keyword involves a certain number of advertisers (say k) competing for available slots (say m) to display their advertisements (ads for short). A sponsored search auction for a keyword is typically conducted for a number of rounds (say T). There are click probabilities mu(ij) associated with each agent slot pair (agent i and slot j). The search engine would like to maximize the social welfare of the advertisers, that is, the sum of values of the advertisers for the keyword. However, the search engine does not know the true values advertisers have for a click to their respective advertisements and also does not know the click probabilities. A key problem for the search engine therefore is to learn these click probabilities during the initial rounds of the auction and also to ensure that the auction mechanism is truthful. Mechanisms for addressing such learning and incentives issues have recently been introduced. These mechanisms, due to their connection to the multi-armed bandit problem, are aptly referred to as multi-armed bandit (MAB) mechanisms. When m = 1, exact characterizations for truthful MAB mechanisms are available in the literature. Recent work has focused on the more realistic but non-trivial general case when m > 1 and a few promising results have started appearing. In this article, we consider this general case when m > 1 and prove several interesting results. Our contributions include: (1) When, mu(ij)s are unconstrained, we prove that any truthful mechanism must satisfy strong pointwise monotonicity and show that the regret will be Theta T7) for such mechanisms. (2) When the clicks on the ads follow a certain click precedence property, we show that weak pointwise monotonicity is necessary for MAB mechanisms to be truthful. (3) If the search engine has a certain coarse pre-estimate of mu(ij) values and wishes to update them during the course of the T rounds, we show that weak pointwise monotonicity and type-I separatedness are necessary while weak pointwise monotonicity and type-II separatedness are sufficient conditions for the MAB mechanisms to be truthful. (4) If the click probabilities are separable into agent-specific and slot-specific terms, we provide a characterization of MAB mechanisms that are truthful in expectation.

Spectral moment sum rules for the retarded Green's function and self-energy of the inhomogeneous Bose-Hubbard model in equilibrium and nonequilibrium

We derive exact expressions for the zeroth and the first three spectral moment sum rules for the retarded Green's function and for the zeroth and the first spectral moment sum rules for the retarded self-energy of the inhomogeneous Bose-Hubbard model in nonequilibrium, when the local on-site repulsion and the chemical potential are time-dependent, and in the presence of an external time-dependent electromagnetic field. We also evaluate these expressions for the homogeneous case in equilibrium, where all time dependence and external fields vanish. Unlike similar sum rules for the Fermi-Hubbard model, in the Bose-Hubbard model case, the sum rules often depend on expectation values that cannot be determined simply from parameters in the Hamiltonian like the interaction strength and chemical potential but require knowledge of equal-time many-body expectation values from some other source. We show how one can approximately evaluate these expectation values for the Mott-insulating phase in a systematic strong-coupling expansion in powers of the hopping divided by the interaction. We compare the exact moment relations to the calculated moments of spectral functions determined from a variety of different numerical approximations and use them to benchmark their accuracy. DOI: 10.1103/PhysRevA.87.013628

Semi-supervised SVMs for classification with unknown class proportions and a small labeled dataset

In the design of practical web page classification systems one often encounters a situation in which the labeled training set is created by choosing some examples from each class; but, the class proportions in this set are not the same as those in the test distribution to which the classifier will be actually applied. The problem is made worse when the amount of training data is also small. In this paper we explore and adapt binary SVM methods that make use of unlabeled data from the test distribution, viz., Transductive SVMs (TSVMs) and expectation regularization/constraint (ER/EC) methods to deal with this situation. We empirically show that when the labeled training data is small, TSVM designed using the class ratio tuned by minimizing the loss on the labeled set yields the best performance; its performance is good even when the deviation between the class ratios of the labeled training set and the test set is quite large. When the labeled training data is sufficiently large, an unsupervised Gaussian mixture model can be used to get a very good estimate of the class ratio in the test set; also, when this estimate is used, both TSVM and EC/ER give their best possible performance, with TSVM coming out superior. The ideas in the paper can be easily extended to multi-class SVMs and MaxEnt models.

Capacity of fading gaussian channel with an energy harvesting sensor node

Network life time maximization is becoming an important design goal in wireless sensor networks. Energy harvesting has recently become a preferred choice for achieving this goal as it provides near perpetual operation. We study such a sensor node with an energy harvesting source and compare various architectures by which the harvested energy is used. We find its Shannon capacity when it is transmitting its observations over a fading AWGN channel with perfect/no channel state information provided at the transmitter. We obtain an achievable rate when there are inefficiencies in energy storage and the capacity when energy is spent in activities other than transmission.

Further results on geometric properties of a family of relative entropies

This paper extends some geometric properties of a one-parameter family of relative entropies. These arise as redundancies when cumulants of compressed lengths are considered instead of expected compressed lengths. These parametric relative entropies are a generalization of the Kullback-Leibler divergence. They satisfy the Pythagorean property and behave like squared distances. This property, which was known for finite alphabet spaces, is now extended for general measure spaces. Existence of projections onto convex and certain closed sets is also established. Our results may have applications in the Rényi entropy maximization rule of statistical physics.

Breakdown of the Stokes-Einstein relation in two, three, and four dimensions

The breakdown of the Stokes-Einstein (SE) relation between diffusivity and viscosity at low temperatures is considered to be one of the hallmarks of glassy dynamics in liquids. Theoretical analyses relate this breakdown with the presence of heterogeneous dynamics, and by extension, with the fragility of glass formers. We perform an investigation of the breakdown of the SE relation in 2, 3, and 4 dimensions in order to understand these interrelations. Results from simulations of model glass formers show that the degree of the breakdown of the SE relation decreases with increasing spatial dimensionality. The breakdown itself can be rationalized via the difference between the activation free energies for diffusivity and viscosity (or relaxation times) in the Adam-Gibbs relation in three and four dimensions. The behavior in two dimensions also can be understood in terms of a generalized Adam-Gibbs relation that is observed in previous work. We calculate various measures of heterogeneity of dynamics and find that the degree of the SE breakdown and measures of heterogeneity of dynamics are generally well correlated but with some exceptions. The two-dimensional systems we study show deviations from the pattern of behavior of the three-and four-dimensional systems both at high and low temperatures. The fragility of the studied liquids is found to increase with spatial dimensionality, contrary to the expectation based on the association of fragility with heterogeneous dynamics.

Bounds on the sum-rate capacity of the Gaussian MIMO X channel

We consider the MIMO X channel (XC), a system consisting of two transmit-receive pairs, where each transmitter communicates with both the receivers. Both the transmitters and receivers are equipped with multiple antennas. First, we derive an upper bound on the sum-rate capacity of the MIMO XC under individual power constraint at each transmitter. The sum-rate capacity of the two-user multiple access channel (MAC) that results when receiver cooperation is assumed forms an upper bound on the sum-rate capacity of the MIMO XC. We tighten this bound by considering noise correlation between the receivers and deriving the worst noise covariance matrix. It is shown that the worst noise covariance matrix is a saddle-point of a zero-sum, two-player convex-concave game, which is solved through a primal-dual interior point method that solves the maximization and the minimization parts of the problem simultaneously. Next, we propose an achievable scheme which employs dirty paper coding at the transmitters and successive decoding at the receivers. We show that the derived upper bound is close to the achievable region of the proposed scheme at low to medium SNRs.

Rheometry of granular materials in cylindrical Couette cells: Anomalous stress caused by gravity and shear

The cylindrical Couette device is commonly employed to study the rheology of fluids, but seldom used for dense granular materials. Plasticity theories used for granular flows predict a stress field that is independent of the shear rate, but otherwise similar to that in fluids. In this paper we report detailed measurements of the stress as a function of depth, and show that the stress profile differs fundamentally from that of fluids, from the predictions of plasticity theories, and from intuitive expectation. In the static state, a part of the weight of the material is transferred to the walls by a downward vertical shear stress, bringing about the well-known Janssen saturation of the stress in vertical columns. When the material is sheared, the vertical shear stress changes sign, and the magnitudes of all components of the stress rise rapidly with depth. These qualitative features are preserved over a range of the Couette gap and shear rate, for smooth and rough walls and two model granular materials. To explain the anomalous rheological response, we consider some hypotheses that seem plausibleapriori, but showthat none survive after careful analysis of the experimental observations. We argue that the anomalous stress is due to an anisotropic fabric caused by the combined actions of gravity, shear, and frictional walls, for which we present indirect evidence from our experiments. A general theoretical framework for anisotropic plasticity is then presented. The detailed mechanics of how an anisotropic fabric is brought about by the above-mentioned factors is not clear, and promises to be a challenging problem for future investigations. (C) 2013 AIP Publishing LLC.

Inference for the Component and System Lifetime Distribution of a k-unit Parallel System Based on System Data

In this paper, we consider the inference for the component and system lifetime distribution of a k-unit parallel system with independent components based on system data. The components are assumed to have identical Weibull distribution. We obtain the maximum likelihood estimates of the unknown parameters based on system data. The Fisher information matrix has been derived. We propose -expectation tolerance interval and -content -level tolerance interval for the life distribution of the system. Performance of the estimators and tolerance intervals is investigated via simulation study. A simulated dataset is analyzed for illustration.

Integrated sustainable irrigation planning with multiobjective Fuzzy optimization approach

Multiobjective fuzzy methodology is applied to a case study of Khadakwasla complex irrigation project located near Pune city of Maharashtra State, India. Three objectives, namely, maximization of net benefits, crop production and labour employment are considered. Effect of reuse of wastewater on the planning scenario is also studied. Three membership functions, namely, nonlinear, hyperbolic and exponential are analyzed for multiobjective fuzzy optimization. In the present study, objective functions are considered as fuzzy in nature whereas inflows are considered as dependable. It is concluded that exponential and hyperbolic membership functions provided similar cropping pattern for most of the situations whereas nonlinear membership functions provided different cropping pattern. However, in all the three cases, irrigation intensities are more than the existing irrigation intensity.

Flying between Sky Islands: The Effect of Naturally Fragmented Habitat on Butterfly Population Structure

High elevation montane areas are called ``sky islands'' when they occur as a series of high mountains separated by lowland valleys. Different climatic conditions at high elevations makes sky islands a specialized type of habitat, rendering them naturally fragmented compared to more continuous habitat at lower elevations. Species in sky islands face unsuitable climate in the intervening valleys when moving from one montane area to another. The high elevation shola-grassland mosaic in the Western Ghats of southern India form one such sky island complex. The fragmented patches make this area ideal to study the effect of the spatial orientation of suitable habitat patches on population genetic structure of species found in these areas. Past studies have suggested that sky islands tend to have genetically structured populations, possibly due to reduced gene flow between montane areas. To test this hypothesis, we adopted the comparative approach. Using Amplified Fragment Length Polymorphisms, we compared population genetic structures of two closely related, similar sized butterfly species: Heteropsis oculus, a high elevation shola-grassland specialist restricted to the southern Western Ghats, and Mycalesis patnia, found more continuously distributed in lower elevations. In all analyses, as per expectation the sky island specialist H. oculus exhibited a greater degree of population genetic structure than M. patnia, implying a difference in geneflow. This difference in geneflow in turn appears to be due to the natural fragmentation of the sky island complexes. Detailed analysis of a subset of H. oculus samples from one sky island complex (the Anamalais) showed a surprising genetic break. A possible reason for this break could be unsuitable conditions of higher temperature and lower rainfall in the intervening valley region. Thus, sky island species are not only restricted by lack of habitat continuity between montane areas, but also by the nature of the intervening habitat.

Extension of TSVM to multi-class and hierarchical text classification problems With general losses

Transductive SVM (TSVM) is a well known semi-supervised large margin learning method for binary text classification. In this paper we extend this method to multi-class and hierarchical classification problems. We point out that the determination of labels of unlabeled examples with fixed classifier weights is a linear programming problem. We devise an efficient technique for solving it. The method is applicable to general loss functions. We demonstrate the value of the new method using large margin loss on a number of multi-class and hierarchical classification datasets. For maxent loss we show empirically that our method is better than expectation regularization/constraint and posterior regularization methods, and competitive with the version of entropy regularization method which uses label constraints.

Moving to stay in place: behavioral mechanisms for coexistence of African large carnivores

Most ecosystems have multiple predator species that not only compete for shared prey, but also pose direct threats to each other. These intraguild interactions are key drivers of carnivore community structure, with ecosystem-wide cascading effects. Yet, behavioral mechanisms for coexistence of multiple carnivore species remain poorly understood. The challenges of studying large, free-ranging carnivores have resulted in mainly coarse-scale examination of behavioral strategies without information about all interacting competitors. We overcame some of these challenges by examining the concurrent fine-scale movement decisions of almost all individuals of four large mammalian carnivore species in a closed terrestrial system. We found that the intensity of intraguild interactions did not follow a simple hierarchical allometric pattern, because spatial and behavioral tactics of subordinate species changed with threat and resource levels across seasons. Lions (Panthera leo) were generally unrestricted and anchored themselves in areas rich in not only their principal prey, but also, during periods of resource limitation (dry season), rich in the main prey for other carnivores. Because of this, the greatest cost (potential intraguild predation) for subordinate carnivores was spatially coupled with the highest potential benefit of resource acquisition (prey-rich areas), especially in the dry season. Leopard (P. pardus) and cheetah (Acinonyx jubatus) overlapped with the home range of lions but minimized their risk using fine-scaled avoidance behaviors and restricted resource acquisition tactics. The cost of intraguild competition was most apparent for cheetahs, especially during the wet season, as areas with energetically rewarding large prey (wildebeest) were avoided when they overlapped highly with the activity areas of lions. Contrary to expectation, the smallest species (African wild dog, Lycaon pictus) did not avoid only lions, but also used multiple tactics to minimize encountering all other competitors. Intraguild competition thus forced wild dogs into areas with the lowest resource availability year round. Coexistence of multiple carnivore species has typically been explained by dietary niche separation, but our multi-scaled movement results suggest that differences in resource acquisition may instead be a consequence of avoiding intraguild competition. We generate a more realistic representation of hierarchical behavioral interactions that may ultimately drive spatially explicit trophic structures of multi-predator communities.

Quantum Phase Diagram of One-Dimensional Spin and Hubbard Models with Transitions to Bond Order Wave Phases

Similar quantum phase diagrams and transitions are found for three classes of one-dimensional models with equally spaced sites, singlet ground states (GS), inversion symmetry at sites and a bond order wave (BOW) phase in some sectors. The models are frustrated spin-1/2 chains with variable range exchange, half-filled Hubbard models with spin-independent interactions and modified Hubbard models with site energies for describing organic charge transfer salts. In some range of parameters, the models have a first order quantum transition at which the GS expectation value of the sublattice spin < S-A(2)> of odd or even-numbered sites is discontinuous. There is an intermediate BOW phase for other model parameters that lead to two continuous quantum transitions with continuous < S-A(2)>. Exact diagonalization of finite systems and symmetry arguments provide a unified picture of familiar 1D models that have appeared separately in widely different contexts.

Quantum Phase Diagram of One-Dimensional Spin and Hubbard Models with Transitions to Bond Order Wave Phases

Similar quantum phase diagrams and transitions are found for three classes of one-dimensional models with equally spaced sites, singlet ground states (GS), inversion symmetry at sites and a bond order wave (BOW) phase in some sectors. The models are frustrated spin-1/2 chains with variable range exchange, half-filled Hubbard models with spin-independent interactions and modified Hubbard models with site energies for describing organic charge transfer salts. In some range of parameters, the models have a first order quantum transition at which the GS expectation value of the sublattice spin < S-A(2)> of odd or even-numbered sites is discontinuous. There is an intermediate BOW phase for other model parameters that lead to two continuous quantum transitions with continuous < S-A(2)>. Exact diagonalization of finite systems and symmetry arguments provide a unified picture of familiar 1D models that have appeared separately in widely different contexts.