Design of incentive compatible protocols for wireless networks: A game theoretic approach

In this thesis work, we design rigorous and efficient protocols/mechanisms for different types of wireless networks using a mechanism design [1] and game theoretic approach [2]. Our work can broadly be viewed in two parts. In the first part, we concentrate on ad hoc wireless networks [3] and [4]. In particular, we consider broadcast in these networks where each node is owned by independent and selfish users. Being selfish, these nodes do not forward the broadcast packets. All existing protocols for broadcast assume that nodes forward the transit packets. So, there is need for developing new broadcast protocols to overcome node selfishness. In our paper [5], we develop a strategy proof pricing mechanism which we call immediate predecessor node pricing mechanism (IPNPM) and an efficient new broadcast protocol based on IPNPM. We show the efficacy of our proposed broadcast protocol using simulation results.

Stock Option Compensation in Finland: An Analysis of Economic Determinants, Contracting Frequency, and Design

This paper addresses several questions in the compensation literature by examining stock option compensation practices of Finnish firms. First, the results indicate that principal-agent theory succeeds quite well in predicting the use of stock options. Proxies for monitoring costs, growth opportunities, ownership structure, and risk are found to determine the use of incentives consistent with theory. Furthermore, the paper examines whether determinants of stock options targeted to top management differ from determinants of broad-based stock option plans. Some evidence is found that factors driving these two types of incentives differ. Second, the results reveal that systematic risk significantly increases the likelihood that firms adopt stock option plans, whereas total firm risk and unsystematic risk do not seem to affect this decision. Third, the results show that growth opportunities are related to time-dimensional contracting frequency, consistent with the argument that incentive levels deviate more rapidly from optimum in firms with high growth opportunities. Finally, the results suggest that vesting schedules are decreasing in financial leverage, and that contract maturity is decreasing in firm focus. In addition, both vesting schedules and contract maturity tend to be longer in firms involving state ownership.

The EC context for private forestry incentive evaluation.

XVIII IUFRO World Congress, Ljubljana 1986.

Incentive mechanism to control customer buy-down behaviour

Airlines have successfully practiced revenue management over the past four decades and enhanced their revenue. Most of the traditional models that are applied assume that customers buying a high-fare class ticket will not purchase a low-fare class ticket even if it is available. This is not a very realistic assumption and has led to revenue leakage due to customers exhibiting buy-down behaviour. This paper aims at devising a suitable incentive mechanism that would incite the customer to reveal his nature. This helps in reducing revenue leakage. We show that the proposed incentive mechanism is profitable to both the buyer and seller and hence ensures the buyers participation in the mechanism. Journal of the Operational Research Society (2011) 62, 1566-1573. doi:10.1057/jors.2010.57 Published online 11 August 2010

Identifying Robust Plans through Plan Diagram Reduction

Estimates of predicate selectivities by database query optimizers often differ significantly from those actually encountered during query execution, leading to poor plan choices and inflated response times. In this paper, we investigate mitigating this problem by replacing selectivity error-sensitive plan choices with alternative plans that provide robust performance. Our approach is based on the recent observation that even the complex and dense "plan diagrams" associated with industrial-strength optimizers can be efficiently reduced to "anorexic" equivalents featuring only a few plans, without materially impacting query processing quality. Extensive experimentation with a rich set of TPC-H and TPC-DS-based query templates in a variety of database environments indicate that plan diagram reduction typically retains plans that are substantially resistant to selectivity errors on the base relations. However, it can sometimes also be severely counter-productive, with the replacements performing much worse. We address this problem through a generalized mathematical characterization of plan cost behavior over the parameter space, which lends itself to efficient criteria of when it is safe to reduce. Our strategies are fully non-invasive and have been implemented in the Picasso optimizer visualization tool.

Broadcast in Adhoc Wireless Networks with Selfish Nodes: A Bayesian Incentive Compatibility Approach

We consider the incentive compatible broadcast (ICB) problem in ad hoc wireless networks with selfish nodes. We design a Bayesian incentive compatible broadcast (BIC-B) protocol to address this problem. VCG mechanism based schemes have been popularly used in the literature to design dominant strategy incentive compatible (DSIC) protocols for ad hoc wireless networks. VCG based mechanisms have two critical limitations: (i) the network is required to be bi-connected, (ii) the resulting protocol is not budget balanced. Our proposed BIC-B protocol overcomes these difficulties. We also prove the optimality of the proposed scheme.

Incentive Compatible Mechanisms for Resource Procurement in Computational Grids with Rational resource Providers

In a computational grid, the presence of grid resource providers who are rational and intelligent could lead to an overall degradation in the efficiency of the grid. In this paper, we design incentive compatible grid resource procurement mechanisms which ensure that the efficiency of the grid is not affected by the rational behavior of resource providers.In particular, we offer three elegant incentive compatible mechanisms for this purpose: (1) G-DSIC (Grid-Dominant Strategy Incentive Compatible) mechanism (2) G-BIC (Grid-Bayesian Nash Incentive Compatible) mechanism (3) G-OPT(Grid-Optimal) mechanism which minimizes the cost to the grid user, satisfying at the same time, (a) Bayesian incentive compatibility and (b) individual rationality. We evaluate the relative merits and demerits of the above three mechanisms using game theoretical analysis and numerical experiments.

Incentive compatible mechanisms for group ticket allocation in software maintenance services

A customer reported problem (or Trouble Ticket) in software maintenance is typically solved by one or more maintenance engineers. The decision of allocating the ticket to one or more engineers is generally taken by the lead, based on customer delivery deadlines and a guided complexity assessment from each maintenance engineer. The key challenge in such a scenario is two folds, un-truthful (hiked up) elicitation of ticket complexity by each engineer to the lead and the decision of allocating the ticket to a group of engineers who will solve the ticket with in customer deadline. The decision of allocation should ensure Individual and Coalitional Rationality along with Coalitional Stability. In this paper we use game theory to examine the issue of truthful elicitation of ticket complexities by engineers for solving ticket as a group given a specific customer delivery deadline. We formulate this problem as strategic form game and propose two mechanisms, (1) Division of Labor (DOL) and (2) Extended Second Price (ESP). In the proposed mechanisms we show that truth telling by each engineer constitutes a Dominant Strategy Nash Equilibrium of the underlying game. Also we analyze the existence of Individual Rationality (IR) and Coalitional Rationality (CR) properties to motivate voluntary and group participation. We use Core, solution concept from co-operative game theory to analyze the stability of the proposed group based on the allocation and payments.

Understanding How the Brain Changes Its Mind: Microstimulation in the Macaque Frontal Eye Field Reveals How Saccade Plans Are Changed

Accumulator models that integrate incoming sensory information into motor plans provide a robust framework to understand decision making. However, their applicability to situations that demand a change of plan raises an interesting problem for the brain. This is because interruption of the current motor plan must occur by a competing motor plan, which is necessarily weaker in strength. To understand how changes of mind get expressed in behavior, we used a version of the double-step task called the redirect task, in which monkeys were trained to modify a saccade plan. We microstimulated the frontal eye fields during redirect behavior and systematically measured the deviation of the evoked saccade from the response field to causally track the changing saccade plan. Further, to identify the underlying mechanisms, eight different computational models of redirect behavior were assessed. It was observed that the model that included an independent, spatially specific inhibitory process, in addition to the two accumulators representing the preparatory processes of initial and final motor plans, best predicted the performance and the pattern of saccade deviation profile in the task. Such an inhibitory process suppressed the preparation of the initial motor plan, allowing the final motor plan to proceed unhindered. Thus, changes of mind are consistent with the notion of a spatially specific, inhibitory process that inhibits the current inappropriate plan, allowing expression of the new plan.

Incentive Compatible Influence Maximization in Social Networks with Application to Viral Marketing

Information diffusion and influence maximization are important and extensively studied problems in social networks. Various models and algorithms have been proposed in the literature in the context of the influence maximization problem. A crucial assumption in all these studies is that the influence probabilities are known to the social planner. This assumption is unrealistic since the influence probabilities are usually private information of the individual agents and strategic agents may not reveal them truthfully. Moreover, the influence probabilities could vary significantly with the type of the information flowing in the network and the time at which the information is propagating in the network. In this paper, we use a mechanism design approach to elicit influence probabilities truthfully from the agents. Our main contribution is to design a scoring rule based mechanism in the context of the influencer-influencee model. In particular, we show the incentive compatibility of the mechanisms and propose a reverse weighted scoring rule based mechanism as an appropriate mechanism to use.

Queuing of concurrent movement plans by Basal Ganglia

How the brain converts parallel representations of movement goals into sequential movements is not known. We tested the role of basal ganglia (BG) in the temporal control of movement sequences by a convergent approach involving inactivation of the BG by muscimol injections into the caudate nucleus of monkeys and assessing behavior of Parkinson's disease patients, performing a modified double-step saccade task. We tested a critical prediction of a class of competitive queuing models that explains serial behavior as the outcome of a selection of concurrently activated goals. In congruence with these models, we found that inactivation or impairment of the BG unmasked the parallel nature of goal representations such that a significantly greater extent of averaged saccades, curved saccades, and saccade sequence errors were observed. These results suggest that the BG perform a form of competitive queuing, holding the second movement plan in abeyance while the first movement is being executed, allowing the proper temporal control of movement sequences.

Optimal incentive timing strategies for product marketing on social networks

We consider the problem of devising incentive strategies for viral marketing of a product. In particular, we assume that the seller can influence penetration of the product by offering two incentive programs: a) direct incentives to potential buyers (influence) and b) referral rewards for customers who influence potential buyers to make the purchase (exploit connections). The problem is to determine the optimal timing of these programs over a finite time horizon. In contrast to algorithmic perspective popular in the literature, we take a mean-field approach and formulate the problem as a continuous-time deterministic optimal control problem. We show that the optimal strategy for the seller has a simple structure and can take both forms, namely, influence-and-exploit and exploit-and-influence. We also show that in some cases it may optimal for the seller to deploy incentive programs mostly for low degree nodes. We support our theoretical results through numerical studies and provide practical insights by analyzing various scenarios.

Why Economists Reject Long-Term Fisheries Management Plans?

Most fisheries agencies conduct biological and economic assessments independently. This independent conduct may lead to situations in which economists reject management plans proposed by biologists. The objective of this study is to show how to find optimal strategies that may satisfy biologists and economists' conditions. In particular we characterize optimal fishing trajectories that maximize the present value of a discounted economic indicator taking into account the age-structure of the population as in stock assessment methodologies. This approach is applied to the Northern Stock of Hake. Our main empirical findings are: i) Optimal policy may be far away from any of the classical scenarios proposed by biologists, ii) The more the future is discounted, the higher the likelihood of finding contradictions among scenarios proposed by biologists and conclusions from economic analysis, iii) Optimal management reduces the risk of the stock falling under precautionary levels, especially if the future is not discounted to much, and iv) Optimal stationary fishing rate may be very different depending on the economic indicator used as reference.

What lies beneath: responding to forest development plans: a guide for First Nations

pdf contains 60 pages