Cloud computing has changed how services are provided and supported through the computing infrastructure. It has the advantages such as flexibility , scalability , compatibility and availability . However, the current architecture design also brings in some troublesome problems, like the balance of cooperation benefits and privacy concerns between the cloud provider and the cloud users, and the balance of cooperation benefits and free-rider concerns between different cloud users. Theses two problems together form the incentive problem in cloud environment. The first conflict lies between the reliance of services and the concerns of secrets of cloud users. To solve it, we proposes a novel architecture, NeuCloud, to enable partially, trusted, transparently, accountably privacy manipulation and revelation. With the help of this architecture, the privacy-sensitive users can be more confident to move to public clouds. A trusted computing base is not enough, in order to stimulate incentive-compatible privacy trading, we present a theoretical framework and provide the guidelines for cloud provider to compensate the cloud user's privacy-risk-aversion. We implement the NeuCloud and evaluate it. Moreover, a improved model of NeuCloud is discussed. The second part of this thesis strives to solve the free-rider problem in cloud environment. For example, the VM-colocation attacks have become serious threats to cloud environment. We propose to construct an incentive-compatible moving-target-defense by periodically migrating VMs, making it much harder for adversaries to locate the target VMs. We developed theories about whether the migration of VMs is worthy and how the optimal migration interval can be determined. To the best of our knowledge, our work is the first effort to develop a formal and quantified model to guide the migration strategy of clouds to improve security. Our analysis shows that our placement based defense can significantly improve the security level of the cloud with acceptable costs. In summary, the main objective of this study is to provide an incentive-compatible to eliminate the cloud user's privacy or cooperative concerns. The proposed methodology can directly be applied in commercial cloud and help this new computing fashion go further in the history. The theoretical part of this work can be extended to other fields where privacy and free-rider concerns exist.

Algorithmic mechanism design deals with efficiently-computable algorithmic constructions in the presence of strategic players who hold the inputs to the problem and may misreport their input if doing so benefits them. Algorithmic mechanism design finds applications in a variety of internet settings such as resource allocation, facility location and e-commerce, such as sponsored search auctions. There is an extensive amount of work in algorithmic mechanism design on packing problems such as single-item auctions, multi-unit auctions and combinatorial auctions. But, surprisingly, covering problems, also called procurement auctions, have almost been completely unexplored, especially in the multidimensional setting. In this thesis, we systematically investigate multidimensional covering mechanism- design problems, wherein there are m items that need to be covered and n players who provide covering objects, with each player i having a private cost for the covering objects he provides. A feasible solution to the covering problem is a collection of covering objects (obtained from the various players) that together cover all items. Two widely considered objectives in mechanism design are: (i) cost-minimization (CM) which aims to minimize the total cost incurred by the players and the mechanism designer; and (ii) payment minimization (PayM), which aims to minimize the payment to players. Covering mechanism design problems turn out to behave quite differently from packing mechanism design problems. In particular, various techniques utilized successfully for packing problems do not perform well for covering mechanism design problems, and this necessitates new approaches and solution concepts. In this thesis we devise various techniques for handling covering mechanism design problems, which yield a variety of results for both the CM and PayM objectives. In our investigation of the CM objective, we focus on two representative covering problems: uncapacitated facility location (UFL) and vertex cover. For multi-dimensional UFL, we give a black-box method to transform any Lagrangian-multiplier-preserving ??-approximation algorithm for UFL into a truthful-in-expectation, ??-approximation mechanism. This yields the first result for multi-dimensional UFL, namely a truthful-in-expectation 2-approximation mechanism. For multi-dimensional VCP (Multi-VCP), we develop a decomposition method that reduces the mechanism-design problem into the simpler task of constructing threshold mechanisms, which are a restricted class of truthful mechanisms, for simpler (in terms of graph structure or problem dimension) instances of Multi-VCP. By suitably designing the decomposition and the threshold mechanisms it uses as building blocks, we obtain truthful mechanisms with approximation ratios (n is the number of nodes): (1) O(r2 log n) for r-dimensional VCP; and (2) O(r log n) for r-dimensional VCP on any proper minor-closed family of graphs (which improves to O(log n) if no two neighbors of a node belong to the same player). These are the first truthful mechanisms for Multi-VCP with non-trivial approximation guarantees. For the PayM objective, we work in the oft-used Bayesian setting, where players??? types are drawn from an underlying distribution and may be correlated, and the goal is to minimize the expected total payment made by the mechanism. We consider the problem of designing incentive compatible, ex-post individually rational (IR) mechanisms for covering problems in the above model. The standard notion of incentive compatibility (IC) in such settings is Bayesian incentive compatibility (BIC), but this notion is over-reliant on having precise knowledge of the underlying distribution, which makes it a rather non- robust notion. We formulate a notion of IC that we call robust Bayesian IC (robust BIC) that is substantially more robust than BIC, and develop black-box reductions from robust BIC-mechanism design to algorithm design. This black-box reduction applies to single- dimensional settings even when we only have an LP-relative approximation algorithm for the algorithmic problem. We obtain near-optimal mechanisms for various covering settings including single- and multi-item procurement auctions, various single-dimensional covering problems, and multidimensional facility location problems. Finally, we study the notion of frugality, which considers the PayM objective but in a worst-case setting, where one does not have prior information about the players??? types. We show that some of our mechanisms developed for the CM objective are also good with respect to certain oft-used frugality benchmarks proposed in the literature. We also introduce an alternate benchmark for frugality, which more directly reflects the goal that the mechanism???s payment be close to the best possible payment, and obtain some preliminary results with respect to this benchmark.

Software Maintenance is becoming more and more challenging due to rapidly changing customer needs, technologies and need for highly skilled labor. Many problems that existed a decade ago continue to exist or have even grown. In this context organizations find it difficult to match engineer interest, skill to particular customer problem. Thus making it difficult for organization to keep the selfish and rational engineers motivated and productive. In this thesis we have used game theory and mechanism design to model the interactions among such selfish engineers to motivate truth revelation using incentive based allocation schemes for software maintenance problems, especially Ticket Allocation Problem. Ticket allocation or problem allocation is a key problem in the software maintenance process.Tickets are usually allocated by the manager or the technical lead. In allocating a ticket, the manager or technical lead is normally guided by the complexity assessment of the ticket as provided by the maintenance engineers, who are entrusted with the responsibility of fixing the problem.The rationality of the maintenance engineers could induce them to report the complexity in an untruthfulway so as to increase their payoffs.This leads to non-optimal ticket allocation. In this thesis we first address the problem of eliciting ticket complexities in a truthfulway from each individual maintenance engineer, using a mechanism design approach. In particular, we model the problem as that of designing an incentive compatible mechanism and we offer two possible solutions.The first one, TA-DSIC, a Dominant Strategy Incentive Compatible (DSIC) solution and the second solution, TA-BIC, is a Bayesian Incentive Compatible mechanism. We show that the proposed mechanisms outperform conventional allocation protocols in the context of a representative software maintenance organization. In this thesis,we next address the incentive compatibility issue for group ticket allocation problem .Many times a ticket is also allocated to more than one engineers. This may be due to a quick customer delivery(time)deadline. The decision of such allocation is generally taken by the lead, based on customer deadlines and a guided complexity assessment from each maintenance engineer.The decision of allocation in such case should ensure that every individual reveals truth in the proposed group(or coalition) and has incentive to participate in the game as individual and in the coalition. We formulate this problem as Normal form game and propose three mechanisms, (1)Division of Labor, (2)Extended Second Price and (3)Greedy Division of Labor. We show that the proposed mechanisms are DSIC and we discuss their rationality properties.

No description available.

No description available.

A computational grid is a hardware and software infrastructure that provides dependable, consistent, pervasive, and inexpensive access to high-end computational capabilities. In the presence of grid users who are autonomous, rational, and intelligent, there is an overall degradation of the total efficiency of the computational grid in comparison to what can be achieved when the participating users are centrally coordinated . This loss in efficiency might arise due to an unwillingness on the part of some of the grid resource providers to either not perform completely or not perform to the fullest capability, the computational jobs of other users in the grid. In this thesis, our attention is focused on designing grid resource procurement mechanisms which a grid user can use for procuring resources in a computational grid based on bids submitted by autonomous, rational, and intelligent resource providers. Specifically, we follow a game theoretic and mechanism design approach to design three elegant, different incentive compatible procurement mechanisms for this purpose: G-DSIC (Grid-Dominant Strategy Incentive Compatible) mechanism which guarantees that truthful bidding is a best response for each resource provider, irrespective of what the other resource providers bid G-BIC (Grid-Bayesian Nash Incentive Compatible) mechanism which only guarantees that truthful bidding is a best response for each resource provider whenever all other resource providers also bid truthfully G-OPT (Grid-Optimal) mechanism which minimizes the cost to the grid user, satisfying at the same time, (1) Bayesian Incentive Compatibility (which guarantees that truthful bidding is a best response for each resource provider whenever all other resource providers also bid truthfully) and (2) Individual Rationality (which guarantees that the resource providers have non-negative payoffs if they participate in the bidding process). We evaluate the relative merits and demerits of the above three mechanisms using game theoretical analysis and numerical experiments. The mechanisms developed in this thesis are in the context of parameter sweep type of jobs, which consist of multiple homogeneous and independent tasks. We believe the use of the mechanisms proposed transcends beyond parameter sweep type of jobs and in general, the proposed mechanisms could be extended to provide a robust way of procuring resources in a computational grid where the resource providers exhibit rational and strategic behavior.

An ad hoc wireless network is an infrastructure-less, autonomous system of nodes connected through wireless links. In many current applications of ad hoc wireless networks, individual wireless nodes are autonomous, rational, and intelligent and are often referred to as selfish nodes, following game theoretic terminology. In an ad hoc wireless network, a typical node may be an intermediate node of a route from a source node to a destination node and therefore is often required to forward packets so as to enable communication to be established. Selfish nodes may not always forward the packets since the forwarding activity consumes the node’s own resources. Such behavior by individual nodes may lead to suboptimal situations where nodes, through their actions, lead to a state that is undesirable from an overall network viewpoint. To counter this, there is a need to stimulate cooperation through methods such as providing appropriate incentives. In this thesis, our interest is in designing rigorous incentive based methods for stimulating cooperation among wireless nodes, in the specific context of broadcast. In particular, we address the Incentive Compatible Broadcast problem: how do we design broadcast protocols that induce truth revelation by the individual wireless nodes? We do this using a game theory and mechanism design framework. Incentive compatibility of broadcast protocols could manifest in two forms: (1) Dominant Strategy Incentive Compatibility (DSIC) (also called strategy-proofness) and (2) Bayesian incentive compatibility (BIC). A DSIC broadcast protocol is one which makes it a best response for every wireless node to reveal its true type, regardless of what the other nodes reveal. A BIC broadcast protocol is one which makes truth revelation a best response for a node, given that the other nodes are truthful. The DSIC property is stronger and more desirable but more difficult to achieve. On the other hand, the BIC property is much weaker and easier to achieve. In this thesis, we first design a DSIC broadcast protocol for ad hoc networks using the well known VCG (Vickrey-Clarke-Groves) mechanisms and investigate its properties and performance. Next, we design a BIC broadcast protocol, investigate its properties, and compare its performance with that of the DSIC broadcast protocol. Both the protocols developed in this thesis provide an elegant solution to the incentive compatible broadcast problem in ad hoc networks with selfish nodes and help stimulate cooperation among the selfish wireless nodes.