A competitive electricity market has been established in many European countries including the Czech Republic. The electricity market includes a limited number of significant producers and traders, which can be described by oligopoly model. Since the electricity transmission and distribution are regulated, I consider two types of players performing in the electricity market: producers of electricity and traders, who buy electricity from producers and sell it to final customers. I derive oligopoly model with producers and traders "a la Cournot" and calculate a formula of equilibrium strategies. I use these theoretical findings to build a dynamic oligopoly model Ele. Ele is formulated as a mixed complementary problem and calibrated on data for the Czech Republic and neighbor states for several scenarios. The model was specified and calculated in GAMS software by the PATH solver. The results represent a Nash equilibrium. That means for individual producers: electricity generation, investment in new power plants construction and emission permits purchases. For traders the results are: equilibrium purchases, sales and cross-border transfers of electricity in each particular time period. Ele derives also equilibrium regional wholesale and retail electricity prices, emission permit prices and prices of cross-border auctions. Ele results point to an economic profitability of new nuclear power plants constructions. Further, I formulate a game in short-term electricity market, where I advise to Czech market participants, subjects of settlement, how much and in which circumstances to buy or sell electricity. Equilibrium results obtained through simulations based on the principle of a fictive game show that the current payment system of imbalance in the Czech Republic does not increase the risk of instability of electricity networks.

Les défis auxquels sont confrontés les différents secteurs de l’économie, répondent à l'évolution et à la spécialisation des consommateurs et des producteurs, dont les besoins sont de plus en plus complexes. À cet égard, au cours des 5 dernières années, les marchés de l'électricité ont subi un processus évolutif qui vise à répondre aux besoins de tous les intervenants dans des scénarios de développement durable.Aussi les agents impliqués dans les marchés de l'électricité, exposés à des risques opérationnels, juridiques, éthiques, financiers, entre autres, doivent‐ils se spécialiser pour s'approprier notamment de nouvelles technologies. Cette recherche porte principalement sur l'étude du risque financier tout à s'attachant à prendre en compte les nombreuses spécificités des marchés de l'électricité dans le but d'assurer le bon fonctionnement du marché et de ses participants.Dans les développements antérieurs, certains modèles se sont concentrés sur les phénomènes de pannes de courant électrique, d'instabilité du réseau, de variations de puissance, de réseaux intelligents, entre autres. D'autres études ont abordé la question de la prédiction de variables comme le prix et la stratégie d'entreprise, dans le but d'accroître les profits des participants. Ce projet de thèse propose un modèle financier complexe, qui se traduit par le calcul d'un équilibre de marché à partir des conditions initiales et des contraintes de risque. En utilisant la théorie des jeux, nous expliquons l'instabilité de l’équilibre. Nous montrons, en dépit de la complexité, qu'il est possible de trouver un scénario optimal en termes de rentabilité pour le système et les agents.Ce travail est structuré de la façon suivante. Dans le premier chapitre, une revue des études antérieures est présentée afin d’établir le contexte de la recherche. Le chapitre 2 décrit le marché de l'électricité colombienne avec ses particularités. Dans le chapitre 3, les indicateurs de risque (KRI) sont définis. Ils constitueront une partie fondamentale du modèle complet présenté dans le chapitre 4. Enfin, le chapitre 5, d'une part, présente les résultats obtenus et, d'autre part, discute de différentes voies d'approfondissement. / The challenges faced by different sectors of the economy, respond to the evolution and specialization of consumers and producers, where the needs are becoming more complex. In this sense, during the last 5 years the electricity markets have undergone an evolutionary pro- cess that aims to meet the needs of all stakeholders in the midst of sustainability scenarios.Thus, the agents involved in the electricity market, present a num- ber of exhibitions of operational nature, legal, ethical, financial, among others, which require a specialization allowing the entry of new tech- nologies. This research project focuses on the study of financial risk, which despite being so specific, consider many elements with the aim of ensuring the functioning of the market and its participants.In previous studies, some models have concentrated on the in- vestigation of blackouts phenomena, the stability of the network, the dynamic power system, and Smart grids, among others. Mean- while other investigations have addressed the problem of forecasting different variables like the spot price and corporate strategy, with the aim of increasing the profitability of the participants. Now, this project presents the proposal of a complex financial model, which results in calculating a market equilibrium considering initial condi- tions and risk constraints. Using game theory it demonstrates equi- librium instability and that through complexity it is possible to find an optimal scenario in terms of profitability for the system and the agents.In chapter 1 it carried out a review of previous studies in order to justify the investigation, then Chapter 2 includes a description of the Colombian electricity market, with different specifications. In chap- ter 3 the KRI are defined, and they will be integrated in Chapter 4 as a fundamental part of the comprehensive model. Finally, Chapter 5 includes the results of the study ending with some possible further studies and additional considerations.

In the field of VLSI circuit optimization, the scaling of semiconductor devices has led to the miniaturization of the feature sizes resulting in a significant increase in the integration density and size of the circuits. At the nanometer level, due to the effects of manufacturing process variations, the design optimization process has transitioned from the deterministic domain to the stochastic domain, and the inter-relationships among the specification parameters like delay, power, reliability, noise and area have become more intricate. New methods are required to examine these metrics in a unified manner, thus necessitating the need for multi-metric optimization. The optimization algorithms need to be accurate and efficient enough to handle large circuits. As the size of an optimization problem increases significantly, the ability to cluster the design metrics or the parameters of the problem for computational efficiency as well as better analysis of possible trade-offs becomes critical. In this dissertation research, several utilitarian methods are investigated for variation aware multi-metric optimization in VLSI circuit design and spatial pattern clustering. A novel algorithm based on the concepts of utility theory and risk minimization is developed for variation aware multi-metric optimization of delay, power and crosstalk noise, through gate sizing. The algorithm can model device and interconnect variations independent of the underlying distributions and works by identifying a deterministic linear equivalent model from a fundamentally stochastic optimization problem. Furthermore, a multi-metric gate sizing optimization framework is developed that is independent of the optimization methodology, and can be implemented using any mathematical programming approach. It is generalized and reconfigurable such that the metrics can be selected, removed, or prioritized for relative importance depending upon the design requirements. In multi-objective optimization, the existence of multiple conflicting objectives makes the clustering problem challenging. Since game theory provides a natural framework for examining conflicting situations, a game theoretic algorithm for multi-objective clustering is introduced in this dissertation research. The problem of multi-metric clustering is formulated as a normal form multi-step game and solved using Nash equilibrium theory. This algorithm has useful applications in several engineering and multi-disciplinary domains which is illustrated by its mapping to the problem of robot team formation in the field in multi-emergency search and rescue. The various algorithms developed in this dissertation achieve significantly better optimization and run times as compared to other methods, ensure high utility levels, are deterministic in nature and hence can be applied to very large designs. The algorithms have been rigorously tested on the appropriate benchmarks and data sets to establish their efficacy as feasible solution methods. Various quantitative sensitivity analysis have been performed to identify the inter-relationships between the various design parameters.

In this dissertation, we study the interplay between a firm’s operations strategy, with regard to its capacity management, and its marketing decision of product differentiation. For this, we study a market comprising heterogeneous customers who differ in their preferences for time and price. Time sensitive customers are willing to pay a price premium for a shorter delivery time, while price sensitive customers are willing to accept a longer delivery time in return for a lower price. Firms exploit this heterogeneity in customers’ preferences, and offer a menu of products/services that differ only in their guaranteed delivery times and prices. From demand perspective, when customers are allowed to self-select according to their preferences, different products act as substitutes, affecting each other’s demand. Customized product for each segment, on the other hand, results in independent demand for each product. On the supply side, a firm may either share the same processing capacity to serve the two market segments, or may dicate capacity for each segment. Our objective is to understand the interaction between product substitution and the firm’s operations strategy (dedicated versus shared capacity), and how they shape the optimal product differentiation strategy. To address the above issue, we first study this problem for a single monopolist firm, which offers two versions of the same basic product: (i) regular product at a lower price but with a longer delivery time, and (ii) express product at a higher price but with a shorter delivery time. Demand for each product arrives according to a Poisson process with a rate that depends both on its price and delivery time. In addition, if the products are substitutable, each product’s demand is also influenced by the price and delivery time of the other product. Demands within each category are served on a first-come-first-serve basis. However, customers for express product are always given priority over the other category when they are served using shared resources. There is a standard delivery time for the regular product, and the firm’s objective is to appropriately price the two products and select the express delivery time so as to maximize its profit rate. The firm simultaneously needs to decide its installed processing capacity so as to meet its promised delivery times with a high degree of reliability. While the problem in a dedicated capacity setting is solved analytically, the same becomes very challenging in a shared capacity setting, especially in the absence of an analytical characterization of the delivery time distribution of regular customers in a priority queue. We develop a solution algorithm, using matrix geometric method in a cutting plane framework, to solve the problem numerically in a shared capacity setting. Our study shows that in a highly capacitated system, if the firm decides to move from a dedicated to a shared capacity setting, it will need to offer more differentiated products, whether the products are substitutable or not. In contrast, when customers are allowed to self-select, such that independent products become substitutable, a more homogeneous pricing scheme results. However, the effect of substitution on optimal delivery time differentiation depends on the firm’s capacity strategy and cost, as well as market characteristics. The optimal response to any change in capacity cost also depends on the firm’s operations strategy. In a dedicated capacity scenario, the optimal response to an increase in capacity cost is always to offer more homogeneous prices and delivery times. In a shared capacity setting, it is again optimal to quote more homogeneous delivery times, but increase or decrease the price differentiation depending on whether the status-quo capacity cost is high or low, respectively. We demonstrate that the above results are corroborated by real-life practices, and provide a number of managerial implications in terms of dealing with issues like volatile fuel prices. We further extend our study to a competitive setting with two firms, each of which may either share its processing capacities for the two products, or may dedicate capacity for each product. The demand faced by each firm for a given product now also depends on the price and delivery time quoted for the same product by the other firm. We observe that the qualitative results of a monopolistic setting also extend to a competitive setting. Specifically, in a highly capacitated system, the equilibrium prices and delivery times are such that they result in more differentiated products when both the firms use shared capacities as compared to the scenario when both the firms use dedicated capacities. When the competing firms are asymmetric, they exploit their distinctive characteristics to differentiate their products. Further, the effects of these asymmetries also depend on the capacity strategy used by the competing firms. Our numerical results suggest that the firm with expensive capacity always offers more homogeneous delivery times. However, its decision on how to differentiate its prices depends on the capacity setting of the two firms as well as the actual level of their capacity costs. On the other hand, the firm with a larger market base always offers more differentiated prices as well as delivery times, irrespective of the capacity setting of the competing firms.

In this dissertation, we study the interplay between a firm’s operations strategy, with regard to its capacity management, and its marketing decision of product differentiation. For this, we study a market comprising heterogeneous customers who differ in their preferences for time and price. Time sensitive customers are willing to pay a price premium for a shorter delivery time, while price sensitive customers are willing to accept a longer delivery time in return for a lower price. Firms exploit this heterogeneity in customers’ preferences, and offer a menu of products/services that differ only in their guaranteed delivery times and prices. From demand perspective, when customers are allowed to self-select according to their preferences, different products act as substitutes, affecting each other’s demand. Customized product for each segment, on the other hand, results in independent demand for each product. On the supply side, a firm may either share the same processing capacity to serve the two market segments, or may dicate capacity for each segment. Our objective is to understand the interaction between product substitution and the firm’s operations strategy (dedicated versus shared capacity), and how they shape the optimal product differentiation strategy. To address the above issue, we first study this problem for a single monopolist firm, which offers two versions of the same basic product: (i) regular product at a lower price but with a longer delivery time, and (ii) express product at a higher price but with a shorter delivery time. Demand for each product arrives according to a Poisson process with a rate that depends both on its price and delivery time. In addition, if the products are substitutable, each product’s demand is also influenced by the price and delivery time of the other product. Demands within each category are served on a first-come-first-serve basis. However, customers for express product are always given priority over the other category when they are served using shared resources. There is a standard delivery time for the regular product, and the firm’s objective is to appropriately price the two products and select the express delivery time so as to maximize its profit rate. The firm simultaneously needs to decide its installed processing capacity so as to meet its promised delivery times with a high degree of reliability. While the problem in a dedicated capacity setting is solved analytically, the same becomes very challenging in a shared capacity setting, especially in the absence of an analytical characterization of the delivery time distribution of regular customers in a priority queue. We develop a solution algorithm, using matrix geometric method in a cutting plane framework, to solve the problem numerically in a shared capacity setting. Our study shows that in a highly capacitated system, if the firm decides to move from a dedicated to a shared capacity setting, it will need to offer more differentiated products, whether the products are substitutable or not. In contrast, when customers are allowed to self-select, such that independent products become substitutable, a more homogeneous pricing scheme results. However, the effect of substitution on optimal delivery time differentiation depends on the firm’s capacity strategy and cost, as well as market characteristics. The optimal response to any change in capacity cost also depends on the firm’s operations strategy. In a dedicated capacity scenario, the optimal response to an increase in capacity cost is always to offer more homogeneous prices and delivery times. In a shared capacity setting, it is again optimal to quote more homogeneous delivery times, but increase or decrease the price differentiation depending on whether the status-quo capacity cost is high or low, respectively. We demonstrate that the above results are corroborated by real-life practices, and provide a number of managerial implications in terms of dealing with issues like volatile fuel prices. We further extend our study to a competitive setting with two firms, each of which may either share its processing capacities for the two products, or may dedicate capacity for each product. The demand faced by each firm for a given product now also depends on the price and delivery time quoted for the same product by the other firm. We observe that the qualitative results of a monopolistic setting also extend to a competitive setting. Specifically, in a highly capacitated system, the equilibrium prices and delivery times are such that they result in more differentiated products when both the firms use shared capacities as compared to the scenario when both the firms use dedicated capacities. When the competing firms are asymmetric, they exploit their distinctive characteristics to differentiate their products. Further, the effects of these asymmetries also depend on the capacity strategy used by the competing firms. Our numerical results suggest that the firm with expensive capacity always offers more homogeneous delivery times. However, its decision on how to differentiate its prices depends on the capacity setting of the two firms as well as the actual level of their capacity costs. On the other hand, the firm with a larger market base always offers more differentiated prices as well as delivery times, irrespective of the capacity setting of the competing firms.

The occurrence of catastrophic incidents in the process industry leave a marked legacy of resulting in staggering economic and societal losses incurred by the company, the government and the society. The work described herein is a novel approach proposed to help predict and mitigate potential catastrophes from occurring and for understanding the stakes at risk for better risk informed decision making. The methodology includes societal impact as risk measures along with tangible asset damage monetization. Predicting incidents as leading metrics is pivotal to improving plant processes and, for individual and societal safety in the vicinity of the plant (portfolio). From this study it can be concluded that the comprehensive judgments of all the risks and losses should entail the analysis of the overall results of all possible incident scenarios. Value-at-Risk (VaR) is most suitable as an overall measure for many scenarios and for large number of portfolio assets. FN-curves and F$-curves can be correlated and this is very beneficial for understanding the trends of historical incidents in the U.S. chemical process industry. Analyzing historical databases can provide valuable information on the incident occurrences and their consequences as lagging metrics (or lagging indicators) for the mitigation of the portfolio risks. From this study it can be concluded that there is a strong statistical relationship between the different consequence tiers of the safety pyramid and Heinrich‘s safety pyramid is comparable to data mined from the HSEES database. Furthermore, any chemical plant operation is robust only when a strategic balance is struck between optimal plant operations and, maintaining health, safety and sustaining environment. The balance emerges from choosing the best option amidst several conflicting parameters. Strategies for normative decision making should be utilized for making choices under uncertainty. Hence, decision theory is utilized here for laying the framework for choice making of optimum portfolio option among several competing portfolios. For understanding the strategic interactions of the different contributing representative sets that play a key role in determining the most preferred action for optimum production and safety, the concepts of game theory are utilized and framework has been provided as novel application to chemical process industry.

Strategic behaviors in electricity markets are analyzed. Three related topics are investigated. The first topic is a research about the NE search algorithm for complex non-cooperative games in electricity markets with transmission constraints. Hybrid co-evolutionary programming is suggested and simulated for complex examples. The second topic is an analysis about the competing pricing mechanisms of uniform and pay-as-bid pricing in an electricity market. We prove that for a two-player static game the Nash Equilibrium under pay-as-bid pricing will yield less total revenue in expectation than under uniform pricing when demand is inelastic. The third topic is to address a market power mitigation issue of the current Texas electricity market by limiting Transmission Congestion Right (TCR) ownership. The strategic coordination of inter zonal scheduling and balancing market manipulation is analyzed. A market power measurement algorithm useful to determine the proper level of TCR ownership limitation is suggested. / text

Στα πλαίσια της διατριβής αναπτύξαμε δύο από τους πρώτους αλγορίθμους υπολογισμού μιας ε-προσεγγιστικής ισορροπίας Nash για την περίπτωση όπου το ε είναι κάποια σταθερά. Οι προσεγγίσεις που επιτυγχάνουν οι αλγόριθμοί μας είναι ε=3/4 και ε=(2+λ)/4 αντίστοιχα, όπου λ είναι το ελάχιστο, μεταξύ όλων των ισορροπιών Nash, κέρδος για έναν παίκτη. Επιπλέον, μελετήσαμε μια ευρεία κλάση τυχαίων παιγνίων δύο παικτών, για την οποία υπολογίσαμε μια πολύ καλή ε-προσεγγιστική ισορροπία Nash, με το ε να τείνει στο 0 καθώς το πλήθος των διαθέσιμων στρατηγικών των παικτών τείνει στο άπειρο. Οι αρχές της θεωρίας παιγνίων είναι χρήσιμες στην ανάλυση της επίδρασης που έχει στην καθολική απόδοση ενός συστήματος διαμοιραζόμενων πόρων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών του. Προς την κατεύθυνση αυτή, εστιάσαμε στο πρόβλημα της εξισορρόπησης φορτίου. Μελετήσαμε διάφορα μοντέλα πληροφόρησης (π.χ. όταν όλα τα φορτία είναι άγνωστα ή όταν κάθε παίκτης γνωρίζει το μέγεθος του δικού του φορτίου) και αναλύσαμε για το καθένα το σύνολο και τις ιδιότητες των ισορροπιών Nash. Yπολογίσαμε επίσης φράγματα στο λόγο απόκλισης, ο οποίος εκφράζει την επίδραση που έχει στην απόδοση του συστήματος η εγωιστική συμπεριφορά των χρηστών του. Εκτός από τα υπολογιστικά θέματα που σχετίζονται με τη θεωρία παιγνίων, έχει ενδιαφέρον να μελετηθεί κατά πόσο μπορεί η θεωρία παιγνίων να βοηθήσει στην ανάπτυξη και ανάλυση αλγορίθμων για υπολογιστικά δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης. Προς αυτήν την κατεύθυνση, μελετήσαμε από παιγνιοθεωρητική σκοπιά το πρόβλημα χρωματισμού των κορυφών ενός γραφήματος. Ορίσαμε κατάλληλα το παίγνιο χρωματισμού γραφήματος και αποδείξαμε ότι κάθε παίγνιο χρωματισμού γραφήματος έχει πάντα μια αγνή ισορροπία Nash, και ότι κάθε αγνή ισορροπία Nash αντιστοιχεί σε ορθό χρωματισμό του γραφήματος. Δείξαμε επίσης ότι υπάρχει πάντα μια αγνή ισορροπία Nash που χρησιμοποιεί βέλτιστο αριθμό χρωμάτων, δηλαδή ίσο με το χρωματικό αριθμό του γραφήματος. Επιπλέον, περιγράψαμε και αναλύσαμε έναν πολυωνυμικό αλγόριθμο που υπολογίζει μια αγνή ισορροπία Nash για ένα οποιοδήποτε παίγνιο χρωματισμού γραφήματος και χρησιμοποιεί συνολικά ένα πλήθος χρωμάτων που ικανοποιεί ταυτόχρονα τα περισσότερα κλασικά γνωστά φράγματα στο χρωματικό αριθμό. / We developed two algorithms for computing an e-approximate Nash equilibrium for the case where e is an absolute constant. The approximations achieved by our algorithms are e=3/4 and e=(2+l)/4 respectively, where $\lambda$ is the minimum, among all Nash equilibria, payoff of either player. Furthermore, we studied a wide class of random two player games, for which we showed how to compute an e-approximate Nash equilibrium, where e tends to zero as the number of strategies of the players tends to infinity. Game theoretic concepts are useful in determining the impact that selfish behavior plays on the global performance of a system involving selfish entities. Towards this direction, we focused on the problem of load balancing. We studied the case where the agents are not necessarily fully informed about the exact values of their loads. We focused on several models of information (e.g. when all agents know nothing about the loads, or when each agents knows her own load) and, for each model, we characterized the set of Nash equilibria and analyzed their properties. Moreover, we bounded the coordination ratio, a measure which captures the impact that selfish behavior has to the global performance of the system, in contrast to the performance achieved by an optimum centralized algorithm. Besides the computational issues related to game theory, it is interesting to investigate whether game theory can help us in developing and analyzing algorithms for computationally difficult combinatorial optimization problems. Towards this direction, we studied from a game theoretic point of view the problem of vertex coloring. In particular, we properly defined the graph coloring game and we proved that every graph coloring game has a pure Nash equilibrium, and each pure Nash equilibrium corresponds to a proper coloring of the graph. We also showed that there exists a pure Nash equilibrium that uses an optimum number of colors, i.e. equal to the chromatic number. Furthermore, we developed and analyzed a polynomial time algorithm that computes a pure Nash equilibrium for any graph coloring game, using a number of colors satisfying most of the known classical bounds on the chromatic number.

The contemporary Internet ecosystem today has gone through series of evolutionary changes during the last forty or fifty years. Though it was designed as a network with fixed nodes, it has scaled well enough with the development of new technologies both in fixed and wireless networks. Initially, the communication model of the Internet was based on the telephone network (and can be considered as the 1st Generation Internet). Later, its transition as a client-server model made it a network where communication systems exchange data over dedicated links. This 2nd Generation Internet, over the years, has been challenged by many problems and issues such as network congestion, path failure, DOS attacks, mobility issues for wireless networks, etc. The Internet users always look for some information, irrespectively where it is located or stored. This approach is the basic building block for a network architecture where information is considered as the premier entity. Such networks, in general, are termed as Information Centric Network (ICN), where information takes centric position superseding the node centric approach like in the current Internet. The problems faced by the current Internet architecture, mentioned above, can be handled with a unifying approach by putting the information at the centre of the network architecture. On a global scale, this network architecture design is termed as the Future Information Centric Internet. Similarly, Mobile Internet usage has increased overwhelmingly in the last decade. There has been an estimated 1.2 billion mobile broad-band subscriptions for 2.4 billion Internet users in 2011. Because of the increased spectrum efficiency and ubiquitous availability of cellular connectivity, the seamless mobility and connectivity is now considered as daily life commodity. However, in the case of the Internet, IP based mobility solutions cannot catch up in performance with the fast evolution of cellular networks. Therefore, one of the primary goals for the Future Internet is the design of mobility management schemes that overcome the issues in wireless networks such as handover and location management, multihoming, security, etc. In this thesis, we have proposed a mobility management solution in wireless networks in the context of ICN in general and in the context of Network of Information (NetInf) in particular. NetInf is ICN-based Future Internet architecture. We propose a NetInf Mobile Node (NetInf MN) architecture which is backward compatible with the current Internet architecture as well. This cross architecture design for mobility support works closely with Central Control Unit (CCU) (network entity) for improved performance in case of handover management in wireless networks. The Virtual Node Layer (VNL) algorithm explains how different modules of NetInf MN and CCU units work together. The game theoretical and Reinforcement Learning (CODIPAS-RL) scheme based mathematical model shows how handover management and data relaying in the wireless networks can increase the network coverage through cooperative diversity. Simulation results show that the proposed model achieves both Nash and Stackelberg equilibria where as the selected CODIPAS-RL scheme reaches global optimum. Finally, as a use case example of NetInf architecture, we propose the NetInf Email service that does not require dedicated servers or dedicated port unlike the current email service. The use of asymmetric keys as user's ID is the unique feature proposed for this service. The NetInf email service architecture framework presented, explains how different architectural components work together. We discuss different challenges and requirements related to this service. The prototype developed for the Network of Information will be used for the implementation of this service

Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη καταστάσεων ανταγωνισμού μεταξύ χρηστών, για τη χρησιμοποίηση ενός συνόλου κοινόχρηστων πόρων. Για την μοντελοποίηση και ανάλυση των καταστάσεων αυτών χρησιμοποιούμε ως εργαλεία, έννοιες από την θεωρία παιγνίων, όπως ισορροπίες Nash, παίγνια συμφόρησης και μηχανισμοί συντονισμού. Ο κάθε κοινόχρηστος πόρος χρεώνει κάποιο κόστος στους χρήστες που τον χρησιμοποιούν. Θεωρούμε ότι οι χρήστες των κοινόχρηστων πόρων είναι εγωιστικοί, δηλαδή μοναδική τους επιδίωξη είναι η μεγιστοποίηση της προσωπικής τους ωφέλειας. Μια ισορροπία Nash είναι μια κατάσταση όπου κανένας χρήστης δεν μπορεί να αυξήσει το εγωιστικό του όφελος αν αλλάξει μονομερώς την στρατηγική του. Πιο συγκεκριμένα ασχολούμαστε με το KP-μοντέλο γνωστό και ως μοντέλο παράλληλων ακμών και ιδιαίτερα με μεθόδους σύγκλισης σε αγνές ισορροπίες Nash, όπου δηλαδή οι στρατηγικές (ακμές) των χρηστών είναι ντετερμινιστικές. Γενικά, ένα παίγνιο (σύστημα) δεν έχει πάντα μια αγνή ισορροπία Nash. Ωστόσο, εμείς θα μελετήσουμε περιπτώσεις που εγγυημένα έχουν τουλάχιστον μια αγνή ισορροπία Nash. Ονομάζουμε πολιτική χρέωσης των ακμών τον τρόπο με τον οποίο υπολογίζεται το κόστος του κάθε χρήστη όταν χρησιμοποιεί μια ακμή. Μια μέθοδος σύγκλισης σε μια αγνή ισορροπία Nash, είναι να επιτραπεί στους χρήστες να αλλάζουν εγωιστικά τις στρατηγικές τους μέχρι να καταλήξουν σε μια αγνή ισορροπία Nash. Ενδιαφερόμαστε για την ταχύτητα σύγκλισης σε μια αγνή ισορροπία Nash, δηλαδή το πλήθος των εγωιστικών αλλαγών στρατηγικών μέχρι να καταλήξουμε σε ισορροπία. Αρχικά, χρησιμοποιείται η πολιτική χρέωσης συνολικού φορτίου (Makespan), όπου κάθε ακμή χρεώνει το συνολικό της φορτίο σε κάθε χρήστη που την χρησιμοποιεί. Στην πιο απλή περίπτωση, η όλη διαδικασία χωρίζεται σε βήματα. Σε κάθε βήμα επιλέγεται, από το σύνολο των χρηστών που έχουν όφελος να αλλάξουν στρατηγική, ένας χρήστης ο οποίος αλλάζει στρατηγική. Η επιλογή γίνεται με βάση κάποιον αλγόριθμο προτεραιότητας. Για το μοντέλο αυτό, που ονομάζεται ESS-μοντέλο, η ταχύτητα σύγκλισης είναι στη χειρότερη περίπτωση εκθετική στο πλήθος των χρηστών. Παρουσιάζουμε την επίδραση των αλγορίθμων προτεραιότητας στην ταχύτητα σύγκλισης καθώς και αποτελέσματα για τρεις διαφορετικές κατηγορίες ακμών. Μια άλλη προσέγγιση, με εφαρμογή στα κατανεμημένα συστήματα, είναι η παράλληλη αλλαγή στρατηγικών από τους χρήστες (rerouting), όπου περισσότεροι από έναν χρήστες μπορούν να αλλάξουν ταυτόχρονα τη στρατηγική τους. Το μοντέλο αυτό υπερτερεί του ESS στην ταχύτητα σύγκλισης καθώς και στο πλήθος των πραγματικών καταστάσεων που μοντελοποιεί. Στη γενικότερη περίπτωση, όπου οι χρήστες επιτρέπεται να συνάπτουν συνασπισμούς (coalitions) μεταξύ τους, χρησιμοποιούμε έννοιες από τη συνεργατική θεωρία παιγνίων. Οπότε έχουμε να αντιμετωπίσουμε ομάδες χρηστών που αλλάζουν εγωιστικά τις ομαδικές στρατηγικές τους. Παρουσιάζουμε ένα ψευδοπολυωνυμικό φράγμα στην ταχύτητα σύγκλισης για μια ειδική περίπτωση όπου οι ακμές είναι πανομοιότυπες και επιτρέπονται συνασπισμοί πλήθους το πολύ δύο χρηστών. Ένας άλλος τρόπος σύγκλισης σε μια αγνή ισορροπία Nash είναι η κατασκευή ενός αλγορίθμου που αναθέτει στρατηγικές στους χρήστες, όχι απαραίτητα με βάση τα εγωιστικά κριτήρια του καθενός, χωρίς να αυξάνει το κοινωνικό κόστος. Με τον όρο κοινωνικό κόστος αναφερόμαστε σε μια συνολική μετρική της απόδοσης του συστήματος σε συνάρτηση με τις στρατηγικές των χρηστών του συστήματος. Ο αλγόριθμος Nashify που παρουσιάζουμε, συγκλίνει σε μια αγνή ισορροπία Nash σε πολυωνυμικό πλήθος βημάτων, χωρίς να αυξάνει το κοινωνικό κόστος. Στη συνέχεια, εισάγουμε την έννοια των μηχανισμών συντονισμού. Οι μηχανισμοί συντονισμού είναι ένα σύνολο πολιτικών χρέωσης για τις ακμές, που έχουν ως στόχο την παροχή κινήτρων στους εγωιστικούς χρήστες έτσι ώστε οι εγωιστικές αλλαγές των στρατηγικών τους να συγκλίνουν σε αγνές ισορροπίες Nash με μειωμένο κοινωνικό κόστος. Στην παρούσα εργασία, μελετάμε την επίδραση των μηχανισμών συντονισμού στην ταχύτητα σύγκλισης των εγωιστικών χρηστών σε μια ισορροπία Nash. Εξετάζουμε εκτός από την πολιτική χρέωσης συνολικού φορτίου (makespan) και κάποιες διαφορετικές πολιτικές χρέωσης (SJF, LJF, FIFO) και μελετάμε την επίδραση των αλγορίθμων προτεραιότητας στην ταχύτητα σύγκλισης τους. Παρουσιάζουμε και αποδεικνύουμε φράγματα στην ταχύτητα σύγκλισης για τις SJF και LJF πολιτικές που χρεώνουν τους χρήστες με βάση το μέγεθος των βαρών τους. Τέλος αποδεικνύουμε για την πολιτική χρέωσης FIFO, ένα γραμμικό άνω φράγμα στην ταχύτητα σύγκλισης για την ειδική περίπτωση των πανομοιότυπων ακμών και ένα ψευδοπολυωνυμικό άνω φράγμα για την γενική περίπτωση των ακμών. Τελικά, αξιολογούμε πειραματικά την επίδραση των αλγορίθμων προτεραιότητας στις πολιτικές χρέωσης στο ESS μοντέλo με πανομοιότυπες ακμές. Ουσιαστικά, συγκρίνουμε τις πολιτικές χρέωσης συνολικού φορτίου, SJF, LJF και FIFO καθώς και το συνεργατικό με το μη συνεργατικό μοντέλο σχετικά με τη ταχύτητα σύγκλισης τους. Παρατηρούμε ότι για την συνολικού φορτίου, SJF, LJF και FIFO πολιτική χρέωσης τα πειραματικά αποτελέσματα επαληθεύουν τα θεωρητικά φράγματα. Δηλαδή η FIFO πολιτική παρουσιάζει ταχύτερη σύγκλιση από τις υπόλοιπες πολιτικές ανεξάρτητα του αλγόριθμου προτεραιότητας. Για την περίπτωση των συνασπισμών με πολιτική χρέωσης συνολικού φορτίου, παρατηρούμε ότι η ταχύτητα σύγκλισης είναι πολυωνυμική στο πλήθος των χρηστών ακόμα και στην χειρότερη επιλογή συνασπισμών. Το αποτέλεσμα αυτό υποδεικνύει ότι το ψευδοπολυωνυμικό θεωρητικό άνω φράγμα μπορεί να βελτιωθεί. / General goal of the current diploma thesis is the study of competitive situations among users of a set of global resources. In order to analyze and model these situations we use as tools, game theoretic elements, such as Nash equilibrium, congestion games and coordination mechanisms. Every global resource debit a cost value to its users. We assume that the users are selfish, that is their sole objective is the maximization of their personal benefit. An Nash equilibrium is a situation in which no user can increase his personal benefit by changing only his or her own strategy unilaterally. More specific, we are interested in the KP-model or parallel links model and we study convergence methods to pure Nash equilibrium, in which all the strategies a user can select are deterministic. Generally, a game has not always a pure Nash equilibrium. Although we are going to study cases in which there is always at least one Nash equilibrium. We define as cost policy of an edge the function which computes the cost of each user of this edge. A method of convergence in a pure Nash equilibrium is, starting from an initial configuration, to allow all users to selfishly change their strategies (one after the other) until they reach a pure Nash equilibrium. We are interested in the convergence time to pure Nash equilibrium, that is the number of these selfish moves. Firstly, we study the makespan cost policy, in which each edge debits its total load to everyone that use it. In the most simple case, the whole procedure is divided into several steps. At each step, the priority algorithm choose one user from the set of users that benefit by changing their current strategy. For this model, named ESS-model, the convergence time is at the worst case exponential to the number of users. We present the effect of several priority algorithms to the convergence time and results for the major different cases of edges (identical, related, unrelated). Another approach, with applications to distributed systems, is the concurrent change of strategies (rerouting) in which more than one users can change simultaneously their strategies. This model is more powerful than ESS because of its real life applications. Another model we study is that of coalitions, in which the users can contract alliances. This model comes from cooperative game theory. In this case we have to deal with groups of users changing selfishly their group strategies. We present a pseudo-polynomial bound to the convergence time in the identical machines model with coalitions of at most 2 users. Another model of convergence, a little different than the others stated above, is the construction of an algorithm that delegates strategies to the users unselfishly without increasing the social cost. Informally, social cost is a total metric of the system performance depending on the users strategies. This model is named nashification and the algorithm nashify that provides converge to a pure Nash equilibrium in polynomial number of steps without increasing the social cost. As far as the coordination mechanisms are concerned, they are a set of cost policies for the edges, that provides motives to the selfish users in order to converge to a pure Nash equilibrium with decreased social cost. In this thesis, we study the effect of coordination mechanisms in the convergence time. We examine, except from makespan, the sjf, ljf and fifo cost policies. Sjf and ljf policies debit the users concerning their weights. The thesis results are divided in two categories. On the one hand, we prove upper and lower bounds of convergence time for sjf, ljf and fifo policies. Especially for fifo we prove in identical machines case a tight linear bound which is independent from the priority algorithm and a pseudo-polynomial bound in unrelated machines case. On the other hand, we implement all the above mentioned models and analyze them experimentally. In our experiments there are 3 parameters: the priority algorithm, the cost policy, and the number of coalitions. In all cases the experimental results follows the theoretical with one exception which is the most interesting among the experiments. In the case of coalitions with at most 2 users the theoretical upper bound is pseudo-polynomial to the number of users but the experimental results shows that the convergence time is polynomial. These results force us to conjecture that there is a polynomial upper bound.