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 interaction of theoretical computer science with game theory and economics has resulted in the emergence of two very interesting research directions. First, it has provided a new model for algorithm design, which is to optimize in the presence of strategic behavior. Second, it has prompted us to consider the computational aspects of various solution concepts from game theory, economics and auction design which have traditionally been considered mainly in a non-constructive manner. In this thesis we present progress along both these directions. We first consider optimization problems that arise in the design of combinatorial auctions. We provide an online algorithm in the important case of budget-bounded utilities. This model is motivated by the recent development of the business of online auctions of search engine advertisements. Our algorithm achieves a factor of $1-1/e$, via a new linear programming based technique to determine optimal tradeoffs between bids and budgets. We also provide lower bounds in terms of hardness of approximation in more general submodular settings, via a PCP-based reduction. Second, we consider truth-revelation in auctions, and provide an equivalence theorem between two notions of strategy-proofness in randomized auctions of digital goods. Last, we consider the problem of computing an approximate Nash equilibrium in multi-player general-sum games, for which we provide the first subexponential time algorithm.

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.

The trend towards personalized ubiquitous computing has led to the advent of a new generation of wireless technologies, namely wireless body area networks (WBANs), which connect the wearable devices into the Internet-of-Things. This thesis considers the problems of relay selection and power control in fading WBANs with energy-efficiency and security considerations. The main body of the thesis is formed by two papers. Ideas from probability theory are used, in the first paper, to construct a performance measure signifying the energy efficiency of transmission, while in the second paper, information-theoretic principles are leveraged to characterize the transmission secrecy at the wireless physical layer (PHY). The hypothesis is that exploiting spatial diversity through multi-hop relaying is an effective strategy in a WBAN to combat fading and enhance communication throughput. In order to analytically explore the problems of optimal relay selection and power control, proper tools from game theory are employed. In particular, non-cooperative game-theoretic frameworks are developed to model and analyze the strategic interactions among sensor nodes in a WBAN when seeking to optimize their transmissions in the uplink. Quality-of-service requirements are also incorporated into the game frameworks, in terms of upper bounds on the end-to-end delay and jitter incurred by multi-hop transmission, by borrowing relevant tools from queuing theory. The proposed game frameworks are proved to admit Nash equilibria, and distributed algorithms are devised that converge to stable Nash solutions. The frameworks are then evaluated using numerical simulations in conditions approximating actual deployment of WBANs. Performance behavior trade-offs are investigated in an IEEE 802.15.6-based ultra wideband WBAN considering various scenarios. The frameworks show remarkable promise in improving the energy efficiency and PHY secrecy of transmission, at the expense of an admissible increase in the end-to-end latency.

Made available in DSpace on 2016-08-02T21:42:28Z (GMT). No. of bitstreams: 1 Joao Almeida Santos.pdf: 1623220 bytes, checksum: 4565d7d0e83ab53ea398caa1496bbe7c (MD5) Previous issue date: 2012-12-18 / This paper presents the main aspects of Game Theory, showing its application as an analytical tool in People Management with respect to the variable salary. It considers the organization and worker as general concepts, without identifying the sector, business field, legal classification according to their revenue, total employees or market share of the organization. Likewise the concept worker receives no identification on the business field where they work, function, salary or professional training. The organization is any structure that generates goods and services for society and the worker is every element that employs its workforce in the production of goods and services. The objectives set for this study are: to identify the possibilities of application of Game Theory in People Management considering the variable salary as an element of conflict between the organization and the worker; to show whether the extensive form representation is more appropriate or not to analyze the clash scenario in the decision to hire or not the worker or pay more or pay less and the existence of Nash Equilibrium. The qualitative methodology with bibliographic and documentary support features this qualitative research according to the research methodology. Qualitative methods help to interpret the everyday phenomena, which may be composed of symbolic data located in a particular context. The documentary research is an important contribution to the study of the proposed topic, since qualitative research is not a rigidly structured proposal and this allows the researcher to use imagination and creativity to achieve the goal. The results obtained by the research point out that it is possible the application of Game Theory in People Management considering the clash between the players (the worker and the organization) about the salary, as can be seen in chapter 4 in the matrix representations of payoff of a strategic game and pictures 9, 10, 11, and 16. The representation in extensive form, is another goal, indicating the payoffs between two central decisions represented by X = flexibility with waiver of rights by workers and Y = flexibility / adaptation / negotiation, as shown in picture 16. By analyzing the picture, the personnel manager realizes existing strategies for organization and worker for decision making, while assessing the present situation and doing simulations for new proposals. Finally the Nash Equilibrium for application in People Management is discussed in section 4.1.3, making it possible to verify that both the worker and the organization can reach a favorable decision for both and keep their originally intended purposes. In picture 17, this balance is shown after the decision is made by the worker in face of the proposal made by the organization in the wake O2 and the worker got the sequence branch T2 with the value of 20 coins. The potentiality of Game Theory in People Management arises from the fact that those who work in an organization share good or bad results obtained by the choices of others, individual choices and the choices built collectively. When the worker decides to produce less, the company suffers a loss of income generated by the slower pace of work. / Esta dissertação apresenta os principais aspectos da Teoria dos Jogos, mostrando sua aplicação como instrumento analítico na Gestão de Pessoas no que diz respeito à variável salário. Considera a organização e o trabalhador como conceitos gerais, sem identificar o setor de atuação, ramo de atividade, classificação jurídica em função do seu faturamento, total de empregados ou participação de mercado dessa organização. Da mesma forma o conceito trabalhador não recebe qualquer identificação em relação ao setor de atividade onde trabalha, função, salário ou formação profissional. A organização é toda estrutura que gera bens e serviços para a sociedade e o trabalhador é todo elemento que emprega sua força de trabalho na produção de bens e serviços. Os objetivos estabelecidos para este estudo são: identificar as possibilidades de aplicação da Teoria dos Jogos na Gestão de Pessoas considerando a variável salário como elemento de conflito entre a organização e o trabalhador; mostrar se a forma de representação extensiva é mais apropriada ou não para analisar o cenário de embate na decisão de contratar ou não o trabalhador ou pagar mais ou menos salário e a existência do Equilíbrio de Nash. A metodologia qualitativa com apoio bibliográfico e documental caracteriza esta pesquisa qualitativa quanto a metodologia de pesquisa. Os métodos qualitativos contribuem para interpretar fenômenos do cotidiano, podendo ser composto por dados simbólicos situados em determinado contexto. A pesquisa documental é uma contribuição importante ao estudo do tema proposto, já que a pesquisa qualitativa não é uma proposta rigidamente estruturada e isto permite que o pesquisador use a imaginação e criatividade para atingir o objetivo. Os resultados obtidos pela pesquisa dão conta de que é possível a aplicação da Teoria dos Jogos na Gestão de Pessoas considerando o embate entre os jogadores (o trabalhador e a organização) em torno do salário, discutido no capítulo 4 nas representações da matriz de payoff de um jogo estratégico e nas figuras 9,10,11,e 16. A representação na forma extensiva, outro objetivo, indicando os payoffs entre duas decisões centrais representadas por X = flexibilização com renúncia dos direitos pelos trabalhadores e Y = flexibilização/adaptação/negociação, conforme figura 16. O gestor de pessoas percebe as estratégias existentes para a organização e trabalhador para a tomada de decisão, ao mesmo tempo em que pode avaliar a situação que esteja vivendo e fazer simulações em busca de novas propostas. Por fim, o Equilíbrio de Nash para a aplicação na Gestão de Pessoas é discutido no item 4.1.3, sendo possível verificar que tanto o trabalhador como a organização podem chegar a uma decisão favorável para ambos e manter seus objetivos pretendidos inicialmente. Na figura 17, esse equilíbrio é apresentado depois da tomada de decisão do trabalhador pela proposta feita pela organização na sequência O2 e o trabalhador ficou com o ramo de sequência T2 com o valor de 20 moedas. A potencialidade da Teoria dos Jogos na Gestão de Pessoas está no fato de que quem atua em uma organização compartilha resultados bons ou ruins obtidos pelas escolhas alheias, individuais e construídas coletivamente.