Load management based on dynamic pricing has been advocated as a key approach for demand-side management in smart grids. By appropriately pricing energy, economic incentives are given to consumers to shift their usage away from peak hours, thereby limiting the amount of energy that needs to be produced. However, traditional pricing-based load management methods usually rely on the assumption that the statistics of the system dynamics (e.g. the time-varying electricity price, the arrival distribution of consumers' load demands) are known a priori, which is not true in practice. In this paper, we propose a novel price-dependent load scheduling algorithm which, unlike previous works, can operate optimally in systems where such statistical knowledge is unknown. We consider a power grid system where each consumer is equipped with an energy storage device that has the capability of storing electrical energy during peak hours. Specifically, we allow each consumer to proactively determine the amount of energy to purchase from the utility companies (or energy producers) while taking into consideration that its load demand and the electricity price dynamically vary over time in an a priori unknown manner. We first assume that all the dynamics are known and formulate the real-time load scheduling as a Markov decision process and systematically unravel the structural properties exhibited by the resulting optimal load scheduling policy. By utilizing these structural properties, we then prove that our proposed load scheduling algorithm can learn the system dynamics in an online manner and converge to the optimal solution. A distinctive feature of our algorithm is that it actively exploits partial information about the system dynamics so that less information needs to be learned than when using conventional reinforcement learning methods, which significantly improves the adaptation speed and the runtime performance. Our simulation results demonstrate that the proposed load scheduling algorithm achieves efficiency by more than 30% compared to existing state-of-the-art online learning algorithms.

Crowdsourcing systems (e.g. Yahoo! Answers and Amazon Mechanical Turk) provide a platform for requesters, who have tasks to solve, to ask for help from workers. Vital to the proliferation of crowdsourcing systems is incentivizing the workers to exert high effort to provide high-quality services. Reputation mechanisms have been shown to work effectively as incentive schemes in crowdsourcing systems. A reputation agency updates the reputations of the workers based on the requesters' reports on the quality of the workers' services. A low-reputation worker is less likely to get served when it requests help, which provides incentives for the workers to obtain a high reputation by exerting high effort. However, reputation update errors are inevitable, because of either system errors such as loss of reports, or inaccurate reports, resulting from the difficulty in accurately assessing the quality of a worker's service. The reputation update error prevents existing reputation mechanisms from achieving the social optimum. In this paper, we propose a simple binary reputation mechanism, which has only two reputation labels (“good” and “bad”). To the best of our knowledge, our proposed reputation mechanism is the first that is proven to be able to achieve the social optimum even in the presence of reputation update errors. We provide design guidelines for socially-optimal binary reputation mechanisms.

Networked agents often share security risks but lack the incentive to make (sufficient) security investments if the cost exceeds their own benefit even though doing that would be socially beneficial. In this paper, we develop a systematic and rigorous framework based on rating systems for analyzing and significantly improving the mutual security of a network of agents that interact frequently over a long period of time. When designing the optimal rating systems, we explicitly consider that monitoring the agents' investment actions is imperfect and the heterogeneity of agents in terms of both generated traffic and underlying connectivity. Our analysis shows how the optimal rating system design should adapt to different monitoring and connectivity conditions. Even though this paper considers a simplified model of the networked agents' security, our analysis provides important and useful insights for designing rating systems that can significantly improve the mutual security of real networks in a variety of practical scenarios.

In this paper, we propose a novel game-theoretic framework for analyzing and understanding how strategic networks are formed endogenously, driven by the self-interested decisions of individual agents aiming to maximize their own utilities by trading-off the costs and benefits of forming links with other agents. We explicitly model and analyze the scenario in which agents benefit from disseminating their own information to other agents. We rigorously prove that the equilibria of strategic networks frequently exhibit a core-periphery structure, where there are only few agents at the center (core) of the network while the majority of agents are at the periphery of the network and communicate with other agents via links maintained by the “core” agents, who play the role of “connectors” in the network. Also, we are able to determine under what conditions the strategic networks operating in equilibrium are minimally connected (i.e. there is a unique path between any two agents) and have short network diameters. These properties are commonly observed on the Internet and important because they ensure the efficiency and robustness of the resulting equilibrium networks. However, none of these has been rigorously proven in a formal framework before.

This paper presents the first study of the endogenous formation of networks by strategic, self-interested agents who benefit from producing and disseminating information. This work departs from previous works on network formation (especially in the economics literature) which assume that agents benefit only by acquiring information produced by other agents. The strategic production and dissemination of information have striking consequences. We show first that the network structure that emerges (in equilibrium) typically displays a core-periphery structure, with the few agents at the core playing the role of eeconnectorsee, creating and maintaining links to the agents at the periphery. We then determine conditions under which the networks that emerge are minimally connected and have short network diameters (properties that are important for efficiency). Finally, we show that the number of agents who produce information and the total amount of information produced in the network grow at the same rate as the agent population; this is in stark contrast to the "law of the few" that had been established in previous works which do not consider information dissemination.

Social cloud systems, which aggregate the computing capabilities of a large pool of users, have emerged in recent years as a key solution for resource provision and sharing in large-scale online communities due to their inherent flexibility and cost-effectiveness. However, the performance and reliability of these systems depend on the users' cooperative behavior in sharing their computing capabilities. Hence, incentive mechanisms are needed to deter users from free-riding. In this paper, we first model the selfish behavior of the users supplying resources and aiming to maximize their own benefits, and compute the performance of the resulting non-cooperative equilibrium, which is highly inefficient. We then augment the existing job allocation schemes currently implemented in social cloud systems with a novel class of incentive mechanisms based on reputation-based pricing and collective punishment schemes that compel suppliers to change their selfish strategies in a manner that improves the efficiency of the system. We study the cloud system operator's problem of jointly optimizing the incentive mechanism and the job allocation scheme in order to find an optimal social cloud protocol which eliminates the free-riding behavior of suppliers while maximizing the social welfare of the system. We rigorously prove that, using only simple designs for both the incentive mechanism and the job allocation scheme, the resulting protocol provides significant improvements in terms of the social welfare compared to existing social cloud systems.

Crowdsourcing websites (e.g. Yahoo! Answers, Amazon Mechanical Turk, and etc.) emerged in recent years that allow requesters from all around the world to post tasks and seek help from an equally global pool of workers. However, intrinsic incentive problems reside in crowdsourcing applications as workers and requester are selfish and aim to strategically maximize their own benefit. In this paper, we propose to provide incentives for workers to exert effort using a novel game-theoretic model based on repeated games. As there is always a gap in the social welfare between the non-cooperative equilibria emerging when workers pursue their self-interests and the desirable Pareto efficient outcome, we propose a novel class of incentive protocols based on social norms which integrates reputation mechanisms into the existing pricing schemes currently implemented on crowdsourcing websites, in order to improve the performance of the non-cooperative equilibria emerging in such applications. We first formulate the exchanges on a crowdsourcing website as a two-sided market where requesters and workers are matched and play gift-giving games repeatedly. Subsequently, we study the protocol designer's problem of finding an optimal and sustainable (equilibrium) protocol which achieves the highest social welfare for that website. We prove that the proposed incentives protocol can make the website operate close to Pareto efficiency. Moreover, we also examine an alternative scenario, where the protocol designer aims at maximizing the revenue of the website and evaluate the performance of the optimal protocol.

Social computing provide a popular, cost-effective and scalable framework for building new engineering systems as well as improving the performance of numerous existing systems. However, the self-interest of agents of such systems generates intrinsic incentive problems. This work analyzes these incentive problems from several points of view. First, we analyze the trade-offs (of each individual agent) between the costs and benefits of producing information personally and forming links to collect information (from other agents), and the strategic implications of these trade-offs. A central point of the analysis is that information is assumed to be heterogeneous (rather than homogeneous as in previous analyses) and agents value this heterogeneity. The analysis has implications for the topology that emerges endogenously. For large populations, the implication is that the topology is necessarily of a core-periphery type: hub agents (at the core of the network) produce and share most of the information, while spoke agents (at the periphery of the network) derive most of their information from hub agents, producing little of it themselves. As the population becomes larger, the number of hub agents and the total amount of information produced grow in proportion to the total population. Our conclusions had been conjectured for many social computing systems but not been previously derived in any formal framework, and are in stark contradiction to the "law of the few" that had been established in previous work, under the assumption that information is homogeneous and part of the endowment of agents, rather than heterogeneous and produced.

The design of incentive schemes for P2P multimedia sharing networks is challenging due to the unique features exhibited by such networks: large populations of anonymous peers interacting infrequently, asymmetric interests of peers, network errors, and multiple concurrent transactions. In this paper, we design and rigorously analyze a new family of incentive protocols that utilizes social norms for multimedia sharing. In particular, we show that, given the network and peers' characteristics, social norms can be effectively designed to deter free-riders by reducing their reputations and thus, the services which they receive from the P2P network. Unlike existing research, which deploys ad- hoc reputation schemes in P2P networks, our proposed framework rigorously determines the optimal social norm and associated reputation scheme to be used by a particular P2P system, characterized by its specific network characteristics. We also investigate how the design of the optimal social norms needs to change to account for the impact of altruistic and malicious peers. Our results show that optimal social norms are capable of providing significant improvements in the sharing efficiency of multimedia P2P networks. Specifically, depending on the network environment, the proposed social-norm based P2P protocols are able to outperform conventional Tit-for-Tat protocols by up to 8dB in terms of video quality.

In this paper, we build an analytical framework for the design and analysis of a new family of social norm based incentive mechanisms for peer-to-peer (P2P) networks. With this framework, we provide conditions on network parameters under which we can construct social norm equilibrium that induces peers to contribute their resources in their self-interest. Using an illustrative example of a social norm, we study the impacts of network parameters and non-strategic peers on the performance.

We start by formulating the resource sharing in peer-to-peer (P2P) networks as a random-matching gift-giving game, where self-interested peers aim at maximizing their own long-term utilities. In order to provide incentives for the peers to voluntarily share their resources, we propose to design protocols that operate according to pre-determined social norms. To optimize their long-term performance when playing such a game, peers can learn to play the best response by solving individual stochastic control problems. We first show that when a peer learns in an environment in which its opponents play a fixed strategy, learning will provide an advantage for this peer (i.e. it will lead to an increased utility for the learning peer). If all the peers in the network learn, we prove that learning remains beneficial for the peers. Moreover, we prove that the network will converge to the "fully-cooperative state" (where a socially optimal outcome is attained) if the update error γ of the peers' reputations is sufficiently small and the benefit of participating in the stage game is sufficiently larger than the incurred cost.