Multi-Armed Bandit Mechanisms for Multi-Slot Sponsored Searth 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 ads. This auction is typically conducted for a number of rounds (say T). There are click probabilities mu_ij associated with agent-slot pairs. The search engine's goal is to maximize social welfare, for example, the sum of values of the advertisers. The search engine does not know the true value of an advertiser for a click to her ad and also does not know the click probabilities mu_ij s. A key problem for the search engine therefore is to learn these during the T 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 and would be referred to as multi-armed-bandit (MAB) mechanisms. When m = 1,characterizations for truthful MAB mechanisms are available in the literature and it has been shown that the regret for such mechanisms will be O(T^{2/3}). In this paper, we seek to derive a characterization in the realistic but nontrivial general case when m > 1 and obtain several interesting results.

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.

Sufficient conditions for formation of a network topology by self-interested agents

Networks such as organizational network of a global company play an important role in a variety of knowledge management and information diffusion tasks. The nodes in these networks correspond to individuals who are self-interested. The topology of these networks often plays a crucial role in deciding the ease and speed with which certain tasks can be accomplished using these networks. Consequently, growing a stable network having a certain topology is of interest. Motivated by this, we study the following important problem: given a certain desired network topology, under what conditions would best response (link addition/deletion) strategies played by self-interested agents lead to formation of a pairwise stable network with only that topology. We study this interesting reverse engineering problem by proposing a natural model of recursive network formation. In this model, nodes enter the network sequentially and the utility of a node captures principal determinants of network formation, namely (1) benefits from immediate neighbors, (2) costs of maintaining links with immediate neighbors, (3) benefits from indirect neighbors, (4) bridging benefits, and (5) network entry fee. Based on this model, we analyze relevant network topologies such as star graph, complete graph, bipartite Turan graph, and multiple stars with interconnected centers, and derive a set of sufficient conditions under which these topologies emerge as pairwise stable networks. We also study the social welfare properties of the above topologies.

Social Life of Captive Asian Elephants (Elephas maximus) in Southern India: Implications for Elephant Welfare

Asian elephants in the wild live in complex social societies; in captivity, however, management often occurs in solitary conditions, especially at the temples and private places of India. To investigate the effect of social isolation, this study assessed the social group sizes and the presence of stereotypies among 140 captive Asian elephants managed in 3 captive systems (private, temple, and forest department) in Tamil Nadu, India, between 2003 and 2005. The majority of the facilities in the private (82%) and temple (95%) systems held a single elephant without opportunity for social interaction. The forest department managed the elephants in significantly larger groups than the private and temple systems. Among the 3 systems, the proportion of elephants with stereotypies was the highest in temple (49%) followed by private system (26%) and the forest department facility (6%); this correlates with the social isolation trend observed in the 3 systems and suggests a possible link between social isolation and abnormal elephant behavior separate from other environmental factors. The results of this study indicate it would be of greater benefit to elephant well being to keep the patchily distributed solitary temple and private elephants who are socially compatible and free from contagious diseases in small social groups at ocommon elephant houseso for socialization.

Corporate social responsibilities of Indian public sector enterprises-a case study of Bharat Heavy Electricals Limited (BHEL)

The high level of public accountability attached to Public Sector Enterprises as a result of public ownership makes them socially responsible. The Committee of Public Undertakings in 1992 examined the issue relating to social obligations of Central Public Sector Enterprises and observed that ``being part of the `State', every Public Sector enterprise has a moral responsibility to play an active role in discharging the social obligations endowed on a welfare state, subject to the financial health of the enterprise''. It issued the Corporate Social Responsibility Guidelines in 2010 where all Central Public Enterprises, through a Board Resolution, are mandated to create a CSR budget as a specified percentage of net profit of the previous year. This paper examines the CSR activities of the biggest engineering public sector organization in India, Bharath Heavy Electricals Limited. The objectives are twofold, one, to develop a case study of the organization about the funds allocated and utilized for various CSR activities, and two, to examine its status with regard to other organizations, the 2010 guidelines, and the local socio-economic development. Secondary data analysis results show three interesting trends. One, it reveals increasing organizational social orientation with the formal guidelines in place. Two, Firms can no longer continue to exploit environmental resources and escape from their responsibilities by acting separate entities regardless of the interest of the society and Three the thrust of CSR in public sector is on inclusive growth, sustainable development and capacity building with due attention to the socio-economic needs of the neglected and marginalized sections of the society.