Energy accounting determines how much a software process contributes to the total system energy consumption. It is the foundation for evaluating software and has been widely used by operating system based energy management. While various energy accounting policies have been tried, there is no known way to evaluate them directly simply because it is hard to track every hardware use by software in a heterogeneous multicore system like modern smartphones and tablets. This work provides the ground truth for energy accounting based on multi-player game theory and offers the first evaluation of existing energy accounting policies, revealing their important flaws. The proposed ground truth is based on Shapley value, a single value solution to multi-player games of which four axiomatic properties are natural and self-evident to energy accounting. This work further provides a utility optimization formulation of energy management and shows, surprisingly, that energy accounting does not matter for existing energy management solutions that control the energy use of a process by giving it an energy budget, or budget based energy management (BEM). This work shows an optimal energy management (OEM) framework can always outperform BEM. While OEM does not require any form of energy accounting, it is related to Shapley value in that both require the system energy consumption for all possible combination of processes under question. This work reports a prototype implementation of both Shapley value-based energy accounting and OEM based scheduling. Using this prototype and smartphone workload, this work experimentally demonstrates how erroneous existing energy accounting policies can be, show that existing BEM solutions are unnecessarily complicated yet underperforming by 20% compared to OEM.

The objective of this work is to develop a scheme to minimize a combination of power consumption and congestion delay in communication networks. I model the network as a set of parallel links, with flows that are able to divide their traffic among the links available to them. Power consumption at each link is concave and increasing in the load, with a non-zero intercept at the origin corresponding to idle power consumption. I believe it is possible to minimize the overall power consumption by possibly sharing links and shutting down the idle links, as long as it does not lead to significant congestion in the network. In this project, I focus on developing incentives for flows to choose the minimum cost solution. My solutions involve two elements - (i) a mypopic and selfish controller adopted by each source, which attempts to minimize cost seen by that flow, and (ii) a pricing scheme at each link whose objective is to provide appropriate signals to the controllers at the source. I use ideas drawn from population games to choose the set of source controllers, while I experiment with using marginal costs and weighted Shapley values for the pricing scheme. I show that the weighted Shapley value as a pricing scheme is superior to that of marginal cost pricing in some simple cases.

We propose the use of methods based on the Shapley value to assess the fact that private returns to lower levels of educational attainment should incorporate prospective returns from higher attainment levels, since achieving primary education is a necessary condition to enter secondary and tertiary educational levels. We apply the proposed adjustment to a global dataset of private returns to different educational attainment levels and find that the corrected returns to education imply a large shift of returns from tertiary to primary schooling in countries at all income levels. (authors' abstract) / Series: Department of Economics Working Paper Series

Dans cette thèse, nous avons étudié quelques problèmes qui émergent des interactions entre la théorie des jeux et la théorie des treillis. Nous avons introduit la nouvelle notion de jeu multicritère avec interactions entre critères et proposé comme solution pour ces jeux le concept d'équilibre de Choquet-Nash. Nous avons aussi étudié le calcul de la valeur de Shapley d'un jeu coopératif sur un treillis. Plusieurs algorithmes ont été proposés. Un cas polynomial a été mis en exergue : celui des jeux de graphe pondéré sur un produit de chaînes. Nous avons également introduit le modèle de jeu coopératif sur un ordre colore. / In this thesis, we have studied some problems that emerge from the interactions between game theory and lattice theory. We introduced the new notion of multi-criteria game with interactions between criteria and proposed as a solution for these games the concept of Choquet-Nash equilibrium. We studied the computation of the Shapley value of a cooperative game on a lattice. Several algorithms have been proposed for this purpose. A polynomial case was highlighted : that of weighted graph games on a product of chains. We have also introduced the notion of a cooperative game on a set-coloured poset.

We consider a decentralized, two-echelon supply chain where the upper echelon --the supplier-- bears the inventory risk. To service the retailers, the supplier either keeps inventory reserved for each of her customers or else pools inventory to share among her customers. The common insight regarding inventory pooling is that it reduces costs and so increases profits for the supply chain party carrying inventory. However, it has recently been shown that inventory pooling may indeed reduce the total supply chain profits. We further show that inventory pooling may reduce supply chain profits even under traditional service contracts based on the frequently invoked measure of service, probability of stock-out. We model the inventory transactions among the retailers and the supplier as a cooperative game. The players have the option of reserving inventory or forming inventory-pooling coalitions. The total profit of the coalitions is allotted to the players using a profit-sharing mechanism based on Shapley value. We analyze the properties of the proposed profit-sharing scheme in two steps. We first consider a stylized model with two retailers who are not necessarily identical. Then we extend the analysis to an arbitrary number of identical retailers. In both cases, we assume the demand across retailers is independent. We find that the Shapley value allocations coordinate the supply chain and are individually rational. However for more than two retailers, they may not be in the core. Even when they satisfy all the stability properties, including membership in the core, they may be perceived unfair since a player's allocation can exceed his contribution to the total supply chain profit. In addition to analyzing the stability properties of the proposed allocation mechanism, we are also interested in the types of behavior the mechanism induces in the players. We find that the retailers prefer pooling partners with either very high or low service level requirements and the supplier prefers retailers with low service requirements since this gives her the ability to maximize her profit allocation. Finally, we analyze the effects of demand variance on the allocations and the profitability of strategic retailer coalitions.

The objective of this master thesis is to identify “key-drivers” embedded in customer satisfaction data. The data was collected by a large transportation sector corporation during five years and in four different countries. The questionnaire involved several different sections of questions and ranged from demographical information to satisfaction attributes with the vehicle, dealer and several problem areas. Various regression, correlation and cooperative game theory approaches were used to identify the key satisfiers and dissatisfiers. The theoretical and practical advantages of using the Shapley value, Canonical Correlation Analysis and Hierarchical Logistic Regression has been demonstrated and applied to market research.

We consider two game-theoretic settings to determine the optimal values of an issuer's interchange fee rate, an acquirer's merchant discount rate, and a merchant's retail prices for multiple products in a credit card network. In the first setting, we investigate a two-stage game problem in which the issuer and the acquirer first negotiate the interchange fee rate, and the acquirer and the retailer then determine their merchant discount rate and retail prices, respectively. In the second setting, motivated by the recent U.S. bill "H.R. 2695," we develop a three-player cooperative game in which the issuer, the acquirer, and the merchant form a grand coalition and bargain over the interchange fee rate and the merchant discount rate. Following the cooperative game, the retailer makes its retail pricing decisions. We derive both the Shapley value- and the nucleolus-characterized unique rates for the grand coalition. Comparing the two game settings, we show that the participation of the merchant in the negotiation process can result in the reduction of both rates. Moreover, the stability of the grand coalition in the cooperative game setting may require that the merchant should delegate the credit card business only to the issuer and the acquirer with sufficiently low operation costs. We also find that the large, highly-specialized merchants and banks are more likely to join the cooperative negotiation whereas the small firms may prefer the two-stage game setting. Our numerical experiments demonstrate that the acquirer's and the issuer's unit operation costs more significantly impact both rates in the cooperative game setting than in the two-stage game setting.

In hosting environments such as Infrastructure as a Service (IaaS) clouds, desirable application performance is typically guaranteed through the use of Service Level Agreements (SLAs), which specify minimal fractions of resource capacities that must be allocated by a service provider for unencumbered use by customers to ensure proper operation of their workloads. Most IaaS offerings are presented to customers as fixed-size and fixed-price SLAs, that do not match well the needs of specific applications. Furthermore, arbitrary colocation of applications with different SLAs may result in inefficient utilization of hosts' resources, resulting in economically undesirable customer behavior. In this thesis, we propose the design and architecture of a Colocation as a Service (CaaS) framework: a set of strategic and operational services that allow the efficient colocation of customer workloads. CaaS strategic services provide customers the means to specify their application workload using an SLA language that provides them the opportunity and incentive to take advantage of any tolerances they may have regarding the scheduling of their workloads. CaaS operational services provide the information necessary for, and carry out the reconfigurations mandated by strategic services. We recognize that it could be the case that there are multiple, yet functionally equivalent ways to express an SLA. Thus, towards that end, we present a service that allows the provably-safe transformation of SLAs from one form to another for the purpose of achieving more efficient colocation. Our CaaS framework could be incorporated into an IaaS offering by providers or it could be implemented as a value added proposition by IaaS resellers. To establish the practicality of such offerings, we present a prototype implementation of our proposed CaaS framework.

La thèse propose quatre contributions sur la méthode axiomatique. Les trois premiers chapitres utilisent le formalisme des jeux coopératifs à utilité transférable. Dans les deux premiers chapitres, une étude systématique de l'opération de nullification est menée. Les axiomes de retraits sont transformés en axiomes de nullification. Des caractérisations existantes de règles d’allocation sont revisitées, et des résultats totalement neufs sont présentés. Le troisième chapitre introduit et caractérise une valeur de Shapley proportionnelle, où les dividendes d’Harsanyi sont partagés en proportion des capacités des singletons concernés. Le quatrième chapitre propose une variante multi-dimensionnelle de l’indice de Hirsch. Une caractérisation axiomatique et une application aux classements sportifs sont fournies. / The dissertation provides four contributions on the axiomatic method. The first three chapters deal with cooperative games with transferable utility. In the first two chapters, a systematic study of the nullification operation is done. The removal axioms are translated into their nullified counterparts. Some existing characterizations are revisited, and completely new results are presented. The third chapter introduces and characterizes a proportional Shapley value in which the Harsanyi dividends are shared in proportion to the stand-alone worths of the concerned players. The fourth chapter proposes a multi-dimensional variant of the Hirsch index. An axiomatic characterization and an application to sports rankings are provided.

Diese Dissertation präsentiert Modelle zur Lösung von Verhandlungsproblemen mit diskreten Strukturen. Hauptgrundlage der Betrachtung ist dabei die Erweiterung und Anwendung von Theorien der kooperativen Spieltheorie. Insbesondere der Shapley-Wert spielt eine wichtige Rolle. Als erste Problemklasse werden kooperative Spiele präsentiert, bei denen einige Spiele feste Auszahlungen erhalten. Als zweite Problemklasse werden kooperative Spiele untersucht, deren Lösungen ausschließlich ganzzahlig sein dürfen.