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.

Biomass to liquid transportation fuel via Fischer Tropsch synthesis - Technology review and current scenario

Current global energy scenario and the environmental deterioration aspect motivates substituting fossil fuel with a renewable energy resource - especially transport fuel. This paper reviews the current status of trending biomass to liquid (BTL) conversion processes and focuses on the technological developments in Fischer Tropsch (FT) process. FT catalysts in use, and recent understanding of FT kinetics are explored. Liquid fuels produced via FT process from biomass derived syngas promises an attractive, clean, carbon neutral and sustainable energy source for the transportation sector. Performance of the FT process with various catalysts, operating conditions and its influence on the FT products are also presented. Experience from large scale commercial installations of FT plants, primarily utilizing coal based gasifiers, are discussed. Though biomass gasification plants exist for power generation via gas engines with power output of about 2 MWe; there are only a few equivalent sized FT plants for biomass derived syngas. This paper discusses the recent developments in conversion of biomass to liquid (BTL) transportation fuels via FT reaction and worldwide attempts to commercialize this process. All the data presented and analysed here have been consolidated from research experiences at laboratory scale as well as from industrial systems. Economic aspects of BTL are reviewed and compared. (C) 2015 Elsevier Ltd. All rights reserved.