This thesis looks into the economics of crowdsourcing using game theoretic modeling. The art of aggregating information and expertise from a diverse population has been in practice since a long time. The Internet and the revolution in communication and computational technologies have made this task easier and given birth to a new era of online resource aggregation, which is now popularly referred to as crowdsourcing. Two important features of this aggregation technique are: (a) crowdsourcing is always human driven, hence the participants are rational and intelligent, and they have a payoff function that they aim to maximize, and (b) the participants are connected over a social network which helps to reach out to a large set of individuals. To understand the behavior and the outcome of such a strategic crowd, we need to understand the economics of a crowdsourcing network. In this thesis, we have considered the following three major facets of the strategic crowdsourcing problem. (i) Elicitation of the true qualities of the crowd workers: As the crowd is often unstructured and unknown to the designer, it is important to ensure if the crowdsourced job is indeed performed at the highest quality, and this requires elicitation of the true qualities which are typically the participants' private information. (ii) Resource critical task execution ensuring the authenticity of both the information and the identity of the participants: Due to the diverse geographical, cultural, socio-economic reasons, crowdsourcing entails certain manipulations that are unusual in the classical theory. The design has to be robust enough to handle fake identities or incorrect information provided by the crowd while performing crowdsourcing contests. (iii) Improving the productive output of the crowdsourcing network: As the designer's goal is to maximize a certain measurable output of the crowdsourcing system, an interesting question is how one can design the incentive scheme and/or the network so that the system performs at an optimal level taking into account the strategic nature of the individuals. In the thesis, we design novel mechanisms to solve the problems above using game theoretic modeling. Our investigation helps in understanding certain limits of achievability, and provides design protocols in order to make crowdsourcing more reliable, effective, and productive.

This research involves the design, development, and theoretical demonstration of models resulting in integrated misbehavior resolution protocols for ad hoc networked devices. Game theory was used to analyze strategic interaction among independent devices with conflicting interests. Packet forwarding at the routing layer of autonomous ad hoc networks was investigated. Unlike existing reputation based or payment schemes, this model is based on repeated interactions. To enforce cooperation, a community enforcement mechanism was used, whereby selfish nodes that drop packets were punished not only by the victim, but also by all nodes in the network. Then, a stochastic packet forwarding game strategy was introduced. Our solution relaxed the uniform traffic demand that was pervasive in other works. To address the concerns of imperfect private monitoring in resource aware ad hoc networks, a belief-free equilibrium scheme was developed that reduces the impact of noise in cooperation. This scheme also eliminated the need to infer the private history of other nodes. Moreover, it simplified the computation of an optimal strategy. The belief-free approach reduced the node overhead and was easily tractable. Hence it made the system operation feasible. Motivated by the versatile nature of evolutionary game theory, the assumption of a rational node is relaxed, leading to the development of a framework for mitigating routing selfishness and misbehavior in Multi hop networks. This is accomplished by setting nodes to play a fixed strategy rather than independently choosing a rational strategy. A range of simulations was carried out that showed improved cooperation between selfish nodes when compared to older results. Cooperation among ad hoc nodes can also protect a network from malicious attacks. In the absence of a central trusted entity, many security mechanisms and privacy protections require cooperation among ad hoc nodes to protect a network from malicious attacks. Therefore, using game theory and evolutionary game theory, a mathematical framework has been developed that explores trust mechanisms to achieve security in the network. This framework is one of the first steps towards the synthesis of an integrated solution that demonstrates that security solely depends on the initial trust level that nodes have for each other.

No description available.

Energy consumption and its management have been clearly identified as a challenge in computing and communication system design, where energy economy is obviously of paramount importance for battery powered devices. This thesis addresses the energy efficiency of mobile communication at the user end in the context of cellular networks. We argue that energy efficiency starts by energy awareness and propose EnergyBox, a parametrised tool that enables accurate and repeatable energy quantification at the user end using real data traffic traces as input. EnergyBox offers an abstraction of the underlying states for operation of the wireless interfaces and allows to estimate the energy consumption for different operator settings and device characteristics. The tool is used throughout the thesis to quantify and reveal inefficient data communication patterns of widely used mobile applications. We consider two different perspectives in the search of energy-efficient solutions. From the application perspective, we show that systematically quantifying the energy consumption of design choices (e.g., communication patterns, protocols, and data formats) contributes to a significantly smaller energy footprint. From the system perspective, we devise a cross-layer solution that schedules packet transmissions based on the knowledge of the network parameters that impact the energy consumption of the handset. These attempts show that application level decisions require a better understanding of possible energy apportionment policies at system level. Finally, we study the generic problem of determining the contribution of an entity (e.g., application) to the total energy consumption of a given system (e.g., mobile device). We compare the state-of-the-art policies in terms of fairness leveraging cooperative game theory and analyse their required information and computational complexity. We show that providing incentives to reduce the total energy consumption of the system (as part of fairness) is tightly coupled to the policy selection. Our study provides guidelines to select an appropriate policy depending on the characteristics of the system.

Doctor of Philosophy / Department of Electrical and Computer Engineering / Balasubramaniam Natarajan / With the explosive growth of wireless systems and services, bandwidth has become a treasured commodity. Traditionally, licensed frequency bands were exclusively reserved for use by the primary license holders (primary users), whereas, unlicensed frequency bands allow spectrum sharing. Recent spectrum measurements indicate that many licensed bands remain relatively unused for most of the time. Therefore, allowing secondary users (users without a license to operate in the band) to operate with minimal or no interference to primary users is one way of sharing spectrum to increase efficiency. Recently, Federal Communications Commission (FCC) has opened up licensed bands for opportunistic use by secondary users. A cognitive radio (CR) is one enabling technology for systems supporting opportunistic use. A cognitive radio adapts to the environment it operates in by sensing the spectrum and quickly decides on appropriate frequency bands and transmission parameters to use in order to achieve certain performance goals. A cognitive radio network (CRN) refers to a network of cognitive radios/secondary users. In this dissertation, we consider a competitive CRN with multiple channels available for opportunistic use by multiple secondary users. We also assume that multiple secondary users may coexist in a channel and each secondary user (SU) can use multiple channels to satisfy their rate requirements. In this context, firstly, we introduce an integrated modeling and forecasting tool that provides an upper bound estimate of the number of secondary users that may be demanding access to each of the channels at the next instant. Assuming a continuous time Markov chain model for both primary and secondary users activities, we propose a Kalman filter based approach for estimating the number of primary and secondary users. These estimates are in turn used to predict the number of primary and secondary users in a future time instant. We extend the modeling and forecasting framework to the case when SU traffic is governed by Erlangian process. Secondly, assuming that scheduling is complete and SUs have identified the channels to use, we propose two quality of service (QoS) constrained resource allocation frameworks. Our measures for QoS include signal to interference plus noise ratio (SINR) /bit error rate (BER) and total rate requirement. In the first framework, we determine the minimum transmit power that SUs should employ in order to maintain a certain SINR and use that result to calculate the optimal rate allocation strategy across channels. The rate allocation problem is formulated as a maximum flow problem in graph theory. We also propose a simple heuristic to determine the rate allocation. In the second framework, both transmit power and rate per channel are simultaneously optimized with the help of a bi-objective optimization problem formulation. Unlike prior efforts, we transform the BER requirement constraint into a convex constraint in order to guarantee optimality of resulting solutions. Thirdly, we borrow ideas from social behavioral models such as Homo Egualis (HE), Homo Parochius (HP) and Homo Reciprocan (HR) models and apply it to the resource management solutions to maintain fairness among SUs in a competitive CRN setting. Finally, we develop distributed user-based approaches based on ``Dual Decomposition Theory" and ``Game Theory" to solve the proposed resource allocation frameworks. In summary, our body of work represents significant ground breaking advances in the analysis of competitive CRNs.

ITC/USA 2006 Conference Proceedings / The Forty-Second Annual International Telemetering Conference and Technical Exhibition / October 23-26, 2006 / Town and Country Resort & Convention Center, San Diego, California / Spectrum allocation in wireless communication and telemetry systems of the future may be performed in a dynamic and distributed manner, as opposed to static centralized regulations currently in place. This paper surveys a new area of research in the communications field known as cognitive radio which will allow dynamic sharing of spectral bands. An introduction to cognitive radio, a review of existing research results, and discussion of open problems in the area is provided.

This thesis is concerned with game-theoretic models of oligopoly resource markets. They revolve around an open market, on which a number of firms sell a common resource. The market price-demand relationship means that the price (demand) that results from the firm’s production (pricing) decisions is a function of the decisions of all firms selling to that market. This means that firms must generally anticipate the actions of competing firms when determining their own strategies, which means that these models often need to be analysed using game theory. We focus on games in which the resource is exhaustible, with the exception of Chapter 5, in which the majority of the analysis is carried out in an inexhaustible resources setting. Exhaustibility introduces an additional complication into these games; that of allocating the extraction and sale of a limited resource pool over time. We consider several separate areas of extension, which we outline below. In Chapter 2, we consider a dynamic Stackelberg game. Stackelberg competition is an asymmetric form of competition in which one player (the leader) has the ability to pre-commit to and announce a strategy in advance. The ability to pre-commit to a strategy is almost always highly valuable, and in this case allows the leader to drive down the follower’s production by pre-committing to drive up their own. We follow the framework used in [62] to analyse Cournot competition to derive our results. In Chapter 3, we compare the two settings in which resource extraction models are usually formulated: Open-Loop, in which the players determine their strategies as functions of time and the initial resource levels of the players only; and Feedback-Loop, in which the players determine their strategies at each point in time as a function of the current resource levels at that time. Our focus is on the investigation of the relationship between the difference in the production or value of a firm under these two models, and the distribution of resources across the firms. In Chapter 4, we consider a common property resource game. These involve multiple firms which can extract from a common resource pool. We study a widely-used Open- viii Loop model, as formulated in [79]. We examine the result that analysis of the problem by standard methods results in two candidate equilibria, and argue that one of these equilibria can be ruled out by construction of a superior response. In Chapter 5, we analyse joint constraints on production, namely constraints which are met when the total production is above or below a certain level. It is a well- established result that these constraints can result in multiple equilibria. We provide several brief extensions to existing uniqueness results. We also demonstrate methods by which these results can be utilised to analyse games with piecewise-linear windfall taxes or congestion charges. Finally, we discuss the problems of extending these results to games with resource exhaustibility.

Chapter 1 : I attempt a detailed literature review on the passage from the probabilistic versions of the Condorcet Jury Theorem to models augmented by the concept of strategic agents, including both theoretical and relevant empirical work. In the first part, I explore the most influential relevant game theoretic models and their main predictions. In the second part, I review what voting experiments have to say about these predictions, with a brief mention of the experiments' key methodological aspects. In the final part, I provide with an attempt to map the recent strategic voting literature in terms of structure and scope. I close with a philosophical question on the exogeneity of a "correct" choice of a voting outcome, which is inherent in the current strategic voting literature. Chapter 2 : I develop a two stage game with individually costly political action and costless voting on a binary agenda where, in equilibrium, agents rationally cast honest votes in the voting stage. I show that a positive but sufficiently low individual cost of political action can lead to a loss in aggregate welfare for any electorate size. When the individual cost of political action is lower than the signalling gain, agents will engage in informative political action. In the voting stage, since everyone's signal is revealed, agents will unanimously vote for the same policy. Therefore, the result of the ballot will be exactly the same as the one without prior communication, but with the additional aggregate cost of political action. However, when agents have heterogeneous prior beliefs, society is large and the state of the world is sufficiently uncertain, a moderate individual cost of political action can induce informative collective action of only a subset of the members of society, which increases ex ante aggregate welfare relative to no political action. The size of the subset of agents engaging in collective action depends on the dispersion of prior opinions. Chapter 3 : This chapter shows theoretically that hearing expert opinions can be a double-edged sword for decision making committees. We study a majoritarian voting game of common interest where committee members receive not only private information, but also expert information that is more accurate than private information and observed by all members. We identify three types of equilibria of interest, namely i) the symmetric mixed strategy equilibrium where each member randomizes between following the private and public signals should they disagree; ii) the asymmetric pure strategy equilibrium where a certain number of members always follow the public signal while the others always follow the private signal; and iii) a class of equilibria where a supermajority and hence the committee decision always follow the expert signal. We find that in the first two equilibria, the expert signal is collectively taken into account in such a way that it enhances the efficiency (accuracy) of the committee decision, and a fortiori the CJT holds. However, in the third type of equilibria, private information is not reflected in the committee decision and the efficiency of committee decision is identical to that of public information, which may well be lower than the efficiency the committee could achieve without expert information. In other words, the introduction of expert information might reduce efficiency in equilibrium. Chapter 4 : In this chapter we present experimental results on the theory of the previous chapter. In the laboratory, too many subjects voted according to expert information compared to the predictions from the efficient equilibria. The majority decisions followed the expert signal most of the time, which is consistent with the class of obedient equilibria mentioned in the previous chapter. Another interesting finding is the marked heterogeneity in voting behaviour. We argue that the voters' behaviour in our data can be best described as that in an obedient equilibrium where a supermajority (and hence the decision) always follow the expert signal so that no voter is pivotal. A large efficiency loss manifests due to the presence of expert information when the committee size was large. We suggest that it may be desirable for expert information to be revealed only to a subset of committee members. Finally, in the Appendix we describe a new alternative method for producing the signal matrix of the game. Chapter 5 : There is a significant gap between the theoretical predictions and the empirical evidence about the efficiency of policies in reducing crime rates. This chapter argues that one important reason for this is that the current literature of economics of crime overlooks an important hysteresis effect in criminal behaviour. One important consequence of hysteresis is that the effect on an outcome variable from positive exogenous variations in the determining variables has a different magnitude from negative variations. We present a simple model that characterises hysteresis in both the micro and macro levels. When the probability of punishment decreases, some law abiding agents will find it more beneficial to enter a criminal career. If the probability of punishment returns to its original level, a subset of these agents will continue with their career in crime. We show that, when crime choice exhibits weak hysteresis at the individual level, crime rate in a society consisted from a continuum of agents that follows any non-uniform distribution will exhibit strong hysteresis. Only when punishment is extremely severe the effect of hysteresis ceases to exist. The theoretical predictions corroborate the argument that policy makers should be more inclined to set pre-emptive policies rather than mitigating measures.

<p>Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance. </p><p>The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.</p><p>The main contributions of the thesis can be placed in one of the following categories.</p><p>1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.</p><p>2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.</p><p>3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.</p><p>4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.</p> / Dissertation

There is a major trend that manufacturers sell their services to customers instead of selling their products. These services can be provided through leasing, warranty, or maintenance outsourcing. In this dissertation, we have studied leasing and maintenance outsourcing services from different aspects of reliability-based maintenance, game-theoretic decision making, and inventory and supply chain management. We have studied how different interactions and relationships between the manufacturer and customer in service contracting affect the decisions they make and the profits they gain. The methods used to tackle the related decision-making processes are stochastic modeling, non-convex optimization, game-theoretical framework, and simulation. For equipment leasing, two non-cooperative game-theoretic models and a cooperative model have been developed to describe the relationships between the manufacturer (lessor) and customer (lessee). Through the lease contracts, the lessor decides on the maintenance policy of the leased equipment, and the lessee decides on the lease period and usage rate. In the non-cooperative simultaneous move scenario, the lessee and the lessor act simultaneously and independently to make their decisions. In the leader-follower non- cooperative contract, the lessor is the leader who specifies the maintenance policy first, and the lessee, as the follower, decides on the lease period and usage rate accordingly. We have next determined the total maximum profit and shown that the Nash and Stackelberg equilibria are different from the total maximum solution. As a result, the players can increase their total profit by cooperation. We have implemented the cooperative solution as an equilibrium through a nonlinear transfer-payment contract. Our results illustrate that cooperation can be regarded as a value-added strategy in establishing such lease contracts. Besides, our numerical results show that although cooperation always increases the total profit of the players, the magnitude of increase is case specific. When the lease price is low or the revenue is high, the profits in the non-cooperative contracts will be close to the cooperative alternative, while the cooperation may increase the total profit significantly in other cases. For maintenance outsourcing, we have studied different bargaining scenarios in determining the contract terms. First, we have considered the Nash bargaining solution to compute the bargaining profit of players. Next, we have considered the case where players pose threat against each other in order to increase their own bargaining position. We have determined the optimal threat strategy for each player. Our result shows that although such threatening decreases the efficiency of the contract, it can dramatically increase the profit of the player with a higher bargaining position. We have finally provided a solution to the problem of how the service agent and customer can cooperate and negotiate on the price. We have determined the discounted price as a result of negotiation. Indeed, the discounted price induces the customer to choose the total maximum maintenance policy. Our numerical examples illustrate the feasibility of using such a price-discount contract in maintenance service outsourcing. Moreover, one can see that both the customer and agent can benefit from this price-discount contract.