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.

Stable matchings were introduced in 1962 by David Gale and Lloyd Shapley to study the college admissions problem. The seminal work of Gale and Shapley has motivated hundreds of research papers and found applications in many areas of mathematics, computer science, economics, and even medicine. This thesis studies stable matchings in graphs and hypergraphs. We begin by introducing the work of Gale and Shapley. Their main contribution was the proof that every bipartite graph has a stable matching. Our discussion revolves around the Gale-Shapley algorithm and highlights some of the interesting properties of stable matchings in bipartite graphs. We then progress to non-bipartite graphs. Contrary to bipartite graphs, we may not be able to find a stable matching in a non-bipartite graph. Some of the work of Irving will be surveyed, including his extension of the Gale-Shapley algorithm. Irving's algorithm shows that many of the properties of bipartite stable matchings remain when the general case is examined. In 1991, Tan showed how to extend the fundamental theorem of Gale and Shapley to non-bipartite graphs. He proved that every graph contains a set of edges that is very similar to a stable matching. In the process, he found a characterization of graphs with stable matchings based on a modification of Irving's algorithm. Aharoni and Fleiner gave a non-constructive proof of Tan's Theorem in 2003. Their proof relies on a powerful topological result, due to Scarf in 1965. In fact, their result extends beyond graphs and shows that every hypergraph has a fractional stable matching. We show how their work provides new and simpler proofs to several of Tan's results. We then consider fractional stable matchings from a linear programming perspective. Vande Vate obtained the first formulation for complete bipartite graphs in 1989. Further, he showed that the extreme points of the solution set exactly correspond to stable matchings. Roth, Rothblum, and Vande Vate extended Vande Vate's work to arbitrary bipartite graphs. Abeledo and Rothblum further noticed that this new formulation can model fractional stable matchings in non-bipartite graphs in 1994. Remarkably, these formulations yield analogous results to those obtained from Gale-Shapley's and Irving's algorithms. Without the presence of an algorithm, the properties are obtained through clever applications of duality and complementary slackness. We will also discuss stable matchings in hypergraphs. However, the desirable properties that are present in graphs no longer hold. To rectify this problem, we introduce a new ``majority" stable matchings for 3-uniform hypergraphs and show that, under this stronger definition, many properties extend beyond graphs. Once again, the linear programming tools of duality and complementary slackness are invaluable to our analysis. We will conclude with a discussion of two open problems relating to stable matchings in 3-uniform hypergraphs.

Stable matchings were introduced in 1962 by David Gale and Lloyd Shapley to study the college admissions problem. The seminal work of Gale and Shapley has motivated hundreds of research papers and found applications in many areas of mathematics, computer science, economics, and even medicine. This thesis studies stable matchings in graphs and hypergraphs. We begin by introducing the work of Gale and Shapley. Their main contribution was the proof that every bipartite graph has a stable matching. Our discussion revolves around the Gale-Shapley algorithm and highlights some of the interesting properties of stable matchings in bipartite graphs. We then progress to non-bipartite graphs. Contrary to bipartite graphs, we may not be able to find a stable matching in a non-bipartite graph. Some of the work of Irving will be surveyed, including his extension of the Gale-Shapley algorithm. Irving's algorithm shows that many of the properties of bipartite stable matchings remain when the general case is examined. In 1991, Tan showed how to extend the fundamental theorem of Gale and Shapley to non-bipartite graphs. He proved that every graph contains a set of edges that is very similar to a stable matching. In the process, he found a characterization of graphs with stable matchings based on a modification of Irving's algorithm. Aharoni and Fleiner gave a non-constructive proof of Tan's Theorem in 2003. Their proof relies on a powerful topological result, due to Scarf in 1965. In fact, their result extends beyond graphs and shows that every hypergraph has a fractional stable matching. We show how their work provides new and simpler proofs to several of Tan's results. We then consider fractional stable matchings from a linear programming perspective. Vande Vate obtained the first formulation for complete bipartite graphs in 1989. Further, he showed that the extreme points of the solution set exactly correspond to stable matchings. Roth, Rothblum, and Vande Vate extended Vande Vate's work to arbitrary bipartite graphs. Abeledo and Rothblum further noticed that this new formulation can model fractional stable matchings in non-bipartite graphs in 1994. Remarkably, these formulations yield analogous results to those obtained from Gale-Shapley's and Irving's algorithms. Without the presence of an algorithm, the properties are obtained through clever applications of duality and complementary slackness. We will also discuss stable matchings in hypergraphs. However, the desirable properties that are present in graphs no longer hold. To rectify this problem, we introduce a new ``majority" stable matchings for 3-uniform hypergraphs and show that, under this stronger definition, many properties extend beyond graphs. Once again, the linear programming tools of duality and complementary slackness are invaluable to our analysis. We will conclude with a discussion of two open problems relating to stable matchings in 3-uniform hypergraphs.

L'origen del present treball se situa en l'afany de modelització de fenòmens cooperatius aplicats a situacions reals. Des d'aquest punt de vista, parteix la idea d'estudiar el Consorci de Biblioteques Universitàries de Catalunya (CBUC).La intenció és estudiar com cal distribuir els costos que genera el CBUC entre els seus membres. En aquest sentit, el punt de vista de la Teoria de Jocs hi juga un paper interessant.En el capítol es presenta l'estructura de funcionament del CBUC, els seus objectius i els serveis que presta. En particular, ens centrem en la Biblioteca Digital de Catalunya, que és la institució que proveeix els membres del CBUC de l'accés a revistes científiques en format electrònic. Es presenten els models de fixació de preus d'algunes de les editorials amb què manté contacte el Consorci i els mètodes d'assignació dels costos generats per la subscripció de les revistes electròniques per part del Consorci. En el capítol 3 es presenta el model teòric d'estudi a partir del problema de demanda, basat en un conjunt de compradors interessats en l'adquisició d'un conjunt de béns que controla un venedor, el subconjunt de béns que desitja adquirir cadascun dels compradors i per les funcions de costos que determinen el preu dels béns.Seguint una anàlisi cooperativa, associem a cada problema de demanda un joc cooperatiu de costos que anomenem joc de costos cooperatiu de demanda. El joc determina per a cada coalició possible de jugadors, el cost d'adquisició d'un conjunt de béns quan cooperen entre ells.L'objectiu és determinar possibles solucions al problema de repartiment de costos que es genera en la compra conjunta. Així s'estudien condicions per determinar l'existència de distribucions en el core. Es simplifica el model general restringint les demandes dels jugadors (problema de demanda binària) i es determina el valor de Shapley del joc associat.En el cas de funcions de costos constants, el principal resultat és la descripció algèbrica que es realitza de la classe dels jocs constants de demanda. El capítol 4 estudia els jocs de demanda amb descompte, originats a partir de l'acord entre el CBUC i l'editorial Academic Press. Les funcions de costos que avaluen els costos dels béns introdueixen descomptes a partir del volum de demanda. Les funcions determinen l'obtenció de jocs còncaus.Els jocs de demanda amb descompte guarden relació amb els bankruptcy games o jocs de fallida. La relació permet l'obtenció de resultats sobre el core del joc i el valor de Shapley.Finalment, s'hi inclou una aplicació del model estudiat, basat en les dades reals de l'acord entre el CBUC i l'editorial Academic Press Ideal. L'aplicació compara la distribució que usa el CBUC per assignar costos amb les solucions clàssiques de la Teoria de Jocs obtingudes del joc de demanda amb descompte associat al problema. Es proposa el valor de Shapley com la solució més adient.El capítol 5 presenta els jocs de demanda amb externalitats, que parteix de l'acord entre el CBUC i l'editorial Kluwer. El model es basa en l'obligatorietat per part dels compradors d'adquirir tots el paquet de béns del venedor.El joc resultant és 1-còncau. En destaca la importància degut a què no existeix massa literatura sobre jocs k-convex originada en problemes. La 1-concavitat implica l'existència de distribucions en el core, la determinació de la seva estructura i l'obtenció de fórmules per al nucleolus i el valor de tau.Finalment, s'analitza una aplicació del model de demanda amb externalitats basada en les dades de l'acord entre el CBUC i l'editorial Kluwer. Les solucions estudiades en el model es presenten com a alternatives al mètode de distribució determinat pel Consorci. Es proposa el nucleolus com aquell concepte de solució que millor s'adapta a la problemàtica presentada.En l'apèndix s'adjunten els quadres necessaris per a la resolució de les aplicacions dels capítols 4 i 5.

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.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Cette thèse porte sur les mécanismes d’allocation de biens indivisibles en présence d’externalités dans les préférences individuelles. Ces externalités rendent difficile en pratique la collecte d’une information complète sur les préférences. Aussi, l’analyse normative des mécanismes d’allocation requiert de formuler des hypothèses sur la manière d’étendre l’information collectée aux préférences sur les allocations. Cette approche revient à définir des restrictions sur le domaine de préférences admissibles, une démarche bien connue de la théorie du choix social. Les trois premiers chapitres portent sur l’analyse du marché de Shapley-Scarf dans lequel les échanges sont organisés entre coalitions. Les chapitres 1 et 2 établissent des restrictions de domaine garantissant l’existence de différents types d’équilibre concurrentiel. Dans le chapitre 3, l’ensemble des biens est muni d’une géographie, ce qui permet de définir la distance entre partenaires comme source d’externalité. Nous identifions certains domaines de préférences qui assurent la non-vacuité de différents types de Coeur. Le chapitre 4 porte sur le cas de biens indivisibles publics purs. Nous montrons que le problème est formellement équivalent à celui du choix d’un comité dont les membres sont choisis dans des ensembles distincts. Nous caractérisons certains domaines de préférences sur les comités pour lesquels le choix majoritaire membre par membre est cohérent avec le choix majoritaire du comité dans son ensemble. / This thesis focuses on the allocation of indivisible goods in presence of externality in individual preferences. This externality creates a difficulty with collecting full information about preferences. Therefore, conducting a normative analysis of allocation mechanisms requires assumptions on how reported preferences can be extended to preferences over outcomes. This approach is in line with the literature on preference domain restriction well-known in Social Choice theory. The first three chapters focus on Shapley-Scarf markets where trades are organized among coalitions. Coalitional trade generates externalities in individual valuations of allocations. Chapters 1 and 2 investigate domain restrictions ensuring the existence of various types of competitive equilibrium. Chapter 3 endows the set of goods with a geographical structure and considers distance to partners as a source of externality in preference. We identify domains of preference extensions which guarantee the existence of various types of core allocations. Chapter 4 focuses the case of pure public indivisible goods, which is formally identical to choosing a committee formed by several members, each selected from a specific set. We characterize preference domains over committees for which a well-defined seat-wise choice procedure based on majority voting is consistent with choosing a committee at once from majority voting.

Um die Auswirkung der Liberalisierung der EU-Erdgasmärkte auf die Macht der Marktteilnehmer zu studieren, entwickeln wir ein disaggregiertes Modell der eurasischen Erdgasversorgung. Wir modellieren die Abhängigkeiten zwischen den Spielern als kooperatives Spiel und berücksichtigen verschiedene Lösungen: den Shapley-Wert, den Nukleolus und den Kern. Im Kapitel 1 untersuchen wir die regionalen Auswirkungen der Liberalisierung des Zugangs zu den Übertragungsnetzen, sowie die Anreize für Fusionen und Kartelle. Im Kapitel 2 untersuchen wir die Auswirkung der Liberalisierung auf die Machtbalance zwischen den lokalen Champions, den Kunden und den Produzenten außerhalb EU. Wir unterscheiden zwischen zwei Schritten der Reform: 1.die Öffnung des Zugangs zu den Übertragungsnetzen und 2.die Öffnung des Zugangs zu den Vertriebssystemen. Für den Shapley-Wert finden wir geringe und heterogene Effekte des ersten Schritts. Die Auswirkungen des zweiten Schritts sind viel größer und ergeben ein klares Muster: alle lokalen Champions verlieren, während alle Kunden und alle externen Produzenten gewinnen. Da ein Drittel der Verluste der Champions innerhalb EU zu den Spielern im Ausland abfließt, können die aktuellen Reformen die Dominanz der bereits starken externen Produzenten verbessern. Wenn wir den Nukleolus heranziehen, profitieren die Produzenten außerhalb EU von der vollen Liberalisierung hingegen nicht. Im Kapitel 3 untersuchen wir die Beziehungen zwischen Shapley-Wert, Nukleolus und Kern. Für unser Modell ist der Shapley-Wert nie im Kern. Um ein Maß der Instabilität von Auszahlungen, die nicht im Kern liegen, zu erhalten, schlagen wir eine Erweiterung des starken epsilon-Kerns vor und betrachten 3 Metriken. Wir finden, daß die Liberalisierung die Instabilität des Shapley-Werts erhöht. Wir zeigen, daß die Liberalisierung den Kern komprimiert. Die Auswirkung auf den Nukleolus korrespondiert jedoch nicht immer mit der Verschiebung von Minimal- und Maximalwerten der Spieler im Kern. / To study the impact of the liberalization of EU natural gas markets on the power of market players we develop a disaggregated model of the Eurasian natural gas supply system. We model interdependenices among the players as a cooperative game for which we consider various solutions: the Shapley value, the nucleolus and the core. In the first paper we study regional impact of liberalization of access to transmission networks, incentives for mergers and cartels. In the second paper we study the impact of liberalization on the balance of power between ''local champions'', customers, and outside producers, such as Russian Gazprom. We distinguish between two steps of the reform: 1. opening access to transit pipes and 2. opening access to distribution systems, hence customers. Using the Shapley value, we find a modest and rather heterogeneous impact from the first step. The impact of the second step is much larger and yields a clear pattern: all local champions lose, while all customers and all outside producers gain. As one third of the losses of champions within EU leaks to players abroad, current reforms might enhance the dominance of already powerful outside producers. When we apply the nucleolus, in contrast, full liberalization does not benefit outside producers at all. In the third paper we focus on the relation of the Shapley value and the nucleolus to the core. For our model the Shapley value is never in the core. To evaluate the degree of instability of a payoff allocation which is not in the core, we propose an extension of the strong epsilon-core and consider three metrics. We find that liberalization increases the degree of instability of the Shapley value for all metrics. We show that liberalization compresses the core, but not always the nucleolus corresponds well to the shifts in the minimal and maximal values of players in the core.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal