Στην παρούσα διπλωματικής εργασία εφαρμόζουμε τις αρχές της Θεωρίας Παιγνίων, και συγκεκριμένα τις έννοιες των Ισορροπιών Nash και των Παι­γνίου Συμφόρησης, ώστε να αναλύσουμε την επίδραση που έχει στην καθο­λική απόδοση ενός δικτύου και γενικότερα ενός συστήματος διαμοιραζόμενων πόρων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών του. Αρχικά ασχολούμαστε με το πρόβλημα της εγωιστικής δρομολόγησης φορ­τίων από μια κοινή πηγή προς έναν κοινό προορισμό σε ένα δίκτυο επικοι­νωνίας. Σε ένα τέτοιο περιβάλλον οι χρήστες επιλέγουν εγωιστικά τις στρα­τηγικές τους, οι οποίες στην περίπτωση μας αντιστοιχούν σε μονοπάτια από την πηγή προς τον προορισμό Όταν οι χρήστες δρομολογούν τα φορτία τους σύμφωνα με τις στρατηγικές που επιλέγουν, έρχονται αντιμέτωποι με μια κα­θυστέρηση που προκαλείται από τα φορτία όλων των χρηστών καθώς διαμοι­ράζονται τις ακμές. Κάθε χρήστης στοχεύει στην ελαχιστοποίηση του εγωι­στικού τον κόστους, που αντιστοιχεί σε αυτήν ακριβώς την καθυστέρηση, γεγονός που συνήθως έρχεται σε αντίθεση με το στόχο της βελτιστοποίησης της καθολικής απόδοσης του δικτύου. Η θεωρία των ισορροπιών Nash μας παρέχει μία σημαντική αρχή επίλυ­σης για τέτοιου είδους καταστάσεις: μια ισορροπία Nash, είναι μια κατάσταση του συστήματος τέτοια ώστε δεν υπάρχει κάποιος χρήστης που να μπορεί να μειώσει το εγωιστικό του κόστος αλλάζοντας μονομερώς τη στρατηγική του. Σε ένα τέτοιο δίκτυο λοιπόν περιμένουμε οι χρήστες να καταλήξουν σε μια ισορροπία Nash. Ωστόσο, ο υπολογισμός μιας τέτοιας ισορροπίας παραμέ­νει ένα πρόβλημα του οποίου η πολυπλοκότητα είναι, στη γενική περίπτωση, άγνωστη. Στα πλαίσια αυτής της διπλωματικής εργασίας δείχνουμε πειραματικά ότι ο υπολογισμός μιας αγνής ισορροπίας Nash σε ένα περιβάλλον εγωιστικής δρομολόγησης, όπου η καθυστέρηση σε κάθε ακμή ισούται με το φορτίο της. μπορεί να γίνει σε πολυωνυμικό χρόνο για μια μεγάλη ποικιλία δικτύων και κατανομών των φορτίων των χρηστών. Επιπλέον, προτείνουμε μια αρχική ανάθεση χρηστών σε μονοπάτια η οποία, όπως δείχνουν οι προσομοιώσεις μας, οδηγεί σε μια αξιοσημείωτη μείωση του συνολικού αριθμού των βημάτων που απαιτούνται ώστε να καταλήξουμε σε μια αγνή ισορροπία Nash. Επίσης αποδεικνύουμε την ύπαρξη αγνών ισορροπιών Nash και για την περίπτωση που η καθυστέρηση σε κάθε ακμή είναι εκθετική συνάρτηση του φορτίου της. Στη συνέχεια προτείνουμε και αναλύουμε ένα νέο μηχανισμό κόστους που θέτει τιμές για την ανταγωνιστική χρησιμοποίηση πόρων από ένα σύνολο χρη­στών. Το βασικό πλεονέκτημα αυτού του μηχανισμού είναι ότι οι πόροι θέ­τουν τα κόστη με έναν ισοδύναμο, δίκαιο τρόπο, και το πλέον σημαντικό είναι ότι κανένας πόρος δεν επωφελείται εις βάρος των χρηστών. Αυτός ο δίκαιος μηχανισμός κόστους επαγάγει ένα μη συνεργατικό παί­γνιο μεταξύ των χρηστών, για το οποίο αναλύουμε τις ισορροπίες Nash. Απο­δεικνύουμε ότι δεν υπάρχουν αγνές ισορροπίες Nash, εκτός από την περί­πτωση όπου όλα τα φορτία είναι ίσα, ενώ δείχνουμε ότι υπάρχει πάντα μία πλήρως μικτή ισορροπία Nash. Επίσης αναλύουμε για το παίγνιο αυτό το Κόστος της Αναρχίας, που εκφράζει την απόκλιση της απόδοσης του συ­στήματος στη χειρότερη ισορροπία Nash από τη βέλτιστη απόδοση. Αποδει­κνύουμε ότι το Κόστος της Αναρχίας στη χειρότερη περίπτωση είναι γραμ­μικό ως προς το πλήθος των χρηστών και ότι το φράγμα αυτό είναι αυστηρό. Ωστόσο προτείνουμε δύο τρόπους για να μετριάσουμε τη δυσάρεστη αυτή διαπίστωση. Καταρχήν, μελετάμε την περίπτωση όπου τα φορτία των χρηστών επιλέ­γονται από μία πολύ ευρεία οικογένεια φραγμένων κατανομών πιθανότητας. Ορίζουμε το Διαχεόμενο Κόστος της Αναρχίας το οποίο λαμβάνει υπόψη την κατανομή πιθανότητας των φορτίων και αποδεικνύουμε ότι Διαχεόμενο Κόστος της Αναρχίας φράσσεται εκ των άνω από μία μικρή σταθερά. Επιπλέον, προτείνουμε έναν υβριδικό μηχανισμό κόστους, ο οποίος επιτυγχάνει ένα ση­μαντικά μικρότερο Κόστος της Αναρχίας, ενώ το κέρδος κάθε πόρου παρα­μένει αμελητέο. / -

Στην εργασία αυτή ασχολούμαστε με το πρόβλημα της δρομολόγησης ενός συνόλου αιτήσεων επικοινωνίας σε WDM (Wavelength Division Multiplexing) πλήρως οπτικά δίκτυα από την άποψη της θεωρίας παιγνίων. Αν θεωρήσουμε κάθε αίτηση δρομολόγησης (ζεύγος κόμβων αφετηρία-προορισμός) ως παίκτη, τότε μία στρατηγική περιλαμβάνει ένα μονοπάτι από τον κόμβο-αφετηρία στον κόμβο-προορισμό και μία συχνότητα (χρώμα). Λαμβάνοντας υπόψη τον περιορισμό ότι δύο παίκτες δεν μπορούν να χρησιμοποιήσουν την ίδια συχνότητα στην ίδια ακμή, θεωρούμε ότι το κόστος δύο αλληλοσυγκρουόμενων στρατηγικών είναι απαγορευτικά μεγάλο. Στο παραπάνω πλαίσιο, μελετάμε διάφορες φυσικές συναρτήσεις κόστους επικεντρώνοντας στην ύπαρξη αμιγών σημείων ισορροπίας Nash και στην υπολογιστική πολυπλοκότητα αναγνώρισης και υπολογισμού τους. / We consider the problem of routing a number of communication requests in WDM (wavelength division multiplexing) all-optical networks from the standpoint of game theory. If we view each routing request (pair of source-target nodes) as a player, then a strategy consists of a path from the source to the target and a frequency (color). To reflect the restriction that two requests must not use the same frequency on the same edge, conflicting strategies are assigned a prohibitively high cost. Under this formulation, we consider several natural cost functions focusing on the existence of Nash equilibria and on the complexity of recognizing and computing them.

No description available.

An integrated simulation, learning, and game-theoretic framework is proposed to address the dynamics of supply chain competition. The proposed framework is composed of 1) simulation-based game platform, 2) game solving and analysis module, and 3) multi-agent reinforcement learning module. The simulation-based game platform supports multi-paradigm modeling, such as agent-based modeling, discrete-event simulation, and system dynamics modeling. The game solving and analysis module is designed to include various parts including strategy refinement, data sampling, game solving, equilibrium conditions, solution evaluation, as well as comparative statistics under varying parameter values. The learning module facilitates the decision making of each supply chain competitor under the stochastic and uncertain environments considering different learning strategies. The proposed integrated framework is illustrated for a supply chain system under the newsvendor problem setting in several phases. At phase 1, an extended newsvendor competition considering both the product sale price and service level under an uncertain demand is studied. Assuming that each retailer has the full knowledge of the other retailer's decision space and profit function, we derived the existence and uniqueness conditions of a pure strategy Nash equilibrium with respect to the price and service dominance under additive and multiplicative demand forms. Furthermore, we compared the bounds and obtained various managerial insights. At phase 2, to extend the number of decision variables and enrich the payoff function of the problem considered at phase 1, a hybrid simulation-based framework involving systems dynamics and agent-based modeling is presented, followed by a novel game solving procedure, where the procedural components include strategy refinement, data sampling, gaming solving, and performance evaluation. Various numerical analyses based on the proposed procedure are presented, such as equilibrium accuracy, quality, and asymptotic/marginal stability. At phase 3, multi-agent reinforcement learning technique is employed for the competition scenarios under a partial/incomplete information setting, where each retailer can only observe the opponent' behaviors and adapt to them. Under such a setting, we studied different learning policies and learning rates with different decay patterns between the two competitors. Furthermore, the convergence issues are discussed as well. Finally, the best learning strategies under different problem scenarios are devised.

In an electricity market cleared by merit-order economic dispatch we identify necessary and sufficient conditions under which the market outcomes supported by pure strategy Nash equilibria (NE) exist when generating companies (Gencos) game through continuously variable incremental cost (IC) block offers. A Genco may own any number of units, each unit having multiple blocks with each block being offered at a constant IC. / Next, a mixed-integer linear programming (MILP) scheme devoid of approximations or iterations is developed to identify all possible NE. The MILP scheme is systematic and general but computationally demanding for large systems. Thus, an alternative significantly faster lambda-iterative approach that does not require the use of MILP was also developed. / Once all NE are found, one critical question is to identify the one whose corresponding gaming strategy may be considered by all Gencos as being the most rational. To answer this, this thesis proposes the use of a measure based on the potential profit gain and loss by each Genco for each NE. The most rational offer strategy for each Genco in terms of gaming or not gaming that best meets their risk/benefit expectations is the one corresponding to the NE with the largest gain to loss ratio. / The computation of all NE is tested on several systems of up to ninety generating units, each with four incremental cost blocks. These NE are then used to examine how market power is influenced by market parameters, specifically, the number of competing Gencos, their size and true ICs, as well as the level of demand and price cap.

Separate essays on entrepreneurship, joint venturing, and trade comprise this thesis. The emergence of entrepreneurship is common in the real world but relatively less so in classical economic models. If industry incumbents are attributed with full rationality and perfect foresight, then there are few, if any, profitable opportunities left for new entrants (entrepreneurs) to exploit. This essay explains how entrepreneurs can emerge in a dynamic world when firms must choose between a technology strategy that is either statically or dynamically efficient. A model is developed which shows how such opportunities for new entry can occur when incumbents are caught in a Prisoners’ Dilemma game involving technology strategy. A relevance measure and policy implications are then explored. Joint ventures, especially of the R&D type, are becoming increasingly important as a way to gain needed technological and market competencies. Unfortunately, many joint ventures have the characteristics of a Prisoners’ Dilemma. Firms may cooperate or defect in the venture. If contracts, side-payments, and third-party verification of the venture outcome are unavailable, then the dominant solution to the Prisoners’ Dilemma (mutual defection) results. This paper proposes the use of an ex-ante auction to obtain a Pareto-improvement for these ventures. A Pareto-improvement is assured when non-transferable costs and benefits of firms are not conditional on joint venture strategies. When this condition is not met restrictions are required to obtain the Pareto-improvement. The problem of trade between countries that share an international open access resource is becoming significant as the world reaches the limits of critical shared resource stocks. It is modelled as a world with one primary factor, two intermediate goods, one final good (harvested from the open access resource), and two nations where it is assumed that either the trading takes place over one stage (nations are price-takers), or two stages (nations have market power). Imperfect competition and open access generated externalities affect the trading efficiency. To maximize world welfare this essay recommends subsidizing R&D where comparative advantage exists, and creating international agreements to ensure the one-stage game structure is used when trading.

Separate essays on entrepreneurship, joint venturing, and trade comprise this thesis. The emergence of entrepreneurship is common in the real world but relatively less so in classical economic models. If industry incumbents are attributed with full rationality and perfect foresight, then there are few, if any, profitable opportunities left for new entrants (entrepreneurs) to exploit. This essay explains how entrepreneurs can emerge in a dynamic world when firms must choose between a technology strategy that is either statically or dynamically efficient. A model is developed which shows how such opportunities for new entry can occur when incumbents are caught in a Prisoners’ Dilemma game involving technology strategy. A relevance measure and policy implications are then explored. Joint ventures, especially of the R&D type, are becoming increasingly important as a way to gain needed technological and market competencies. Unfortunately, many joint ventures have the characteristics of a Prisoners’ Dilemma. Firms may cooperate or defect in the venture. If contracts, side-payments, and third-party verification of the venture outcome are unavailable, then the dominant solution to the Prisoners’ Dilemma (mutual defection) results. This paper proposes the use of an ex-ante auction to obtain a Pareto-improvement for these ventures. A Pareto-improvement is assured when non-transferable costs and benefits of firms are not conditional on joint venture strategies. When this condition is not met restrictions are required to obtain the Pareto-improvement. The problem of trade between countries that share an international open access resource is becoming significant as the world reaches the limits of critical shared resource stocks. It is modelled as a world with one primary factor, two intermediate goods, one final good (harvested from the open access resource), and two nations where it is assumed that either the trading takes place over one stage (nations are price-takers), or two stages (nations have market power). Imperfect competition and open access generated externalities affect the trading efficiency. To maximize world welfare this essay recommends subsidizing R&D where comparative advantage exists, and creating international agreements to ensure the one-stage game structure is used when trading.

Knowledge is an asset that can give an organization competitive edge. However, knowledge creation is an expensive activity. One of the reasons organizations form knowledge creation collaborations is to share resources that are needed to create knowledge. This dissertation models the dyadic collaborations as games between the partners and arrives at resource-sharing schemes for them. Specifically, the collaborations are modeled as two games- Stackelberg Leader-Follower game and Partnership game. The types of collaborations are distinguished based on the nature of the marginal return functions with respect to knowledge creation investments for each of the collaborating organizations. Three essays are presented and discussed. In Essay 1, collaborations between organizations characterized by decreasing marginal returns with respect to investments are modeled as a partnership game. In Essay 2, collaborations between organizations characterized by increasing marginal returns with respect to investments are modeled as a Stackelberg Leader-Follower game. In Essay 3, collaborations where the leader organization is characterized by decreasing marginal returns with respect to investment and the follower organization is characterized by increasing marginal returns with respect to investments are studied. The solutions for the game in terms of the participation rate, knowledge creation investments, and the system gain are presented for each essay. The results are analyzed and the observations are stated as propositions. The propositions provide guidelines for collaborating organizations to arrive at a resource-sharing scheme. Additionally, the results suggest conditions under which the potential partners collaborate specifically with respect to the participation rate and the system gain. The results of Essays 2 and 3 provide conditions for participation rate. The results of Essay 3 provide the conditions of expected system gain under which the follower organization will collaborate with a potential leader organization. The results have implications for several stages of the alliance management process such as partner selection, gauging the behavior of potential and current partners, and renegotiation of alliance terms.

<p>Algorithms for finding game-theoretic solutions are now used in several real-world security applications. Many of these applications are based on different but related game-theoretical models collectively known as security games. Much of the research in this area has focused on the two-player setting in which the first player (leader, defender) commits to a strategy, after which the second player (follower, attacker) observes that strategy and responds to it. This is commonly known as the Stackelberg, or leader-follower, model. If none of the players can observe the actions of the others then such a setting is called a simultaneous-move game. A common solution concept in simultaneous-move games is the Nash equilibrium (NE). In the present dissertation, we contribute to this line of research in two ways.</p><p>First, we consider new ways of modeling commitment. We propose the new model in which the leader can commit to a correlated strategy. We show that this model is equivalent to the Stackelberg model in two-player games and is different from the existing models in games with three or more players. We propose an algorithm for computing a solution to this model in polynomial time. We also consider a leader-follower setting in which the players are uncertain about whether the follower can observe. We describe an iterative algorithm for solving such games.</p><p>Second, we analyze the computational complexity of computing Stackelberg and NE strategies in security games. We describe algorithms to solve some variants of the security game model in polynomial time and prove NP-hardness of solving other variants of the model. We also extend the family of security games by allowing the attacker have multiple resources. We provide an algorithm for computing an NE of such games in polynomial time, and we show that computing a Stackelberg strategy is NP-hard.</p> / Dissertation

<p>This dissertation explores decision problems faced by organizations willing to address or support the incorporation of sustainability aspects on their "business as usual" activities. We study to specific problems. First, we analyze the decision problem of a forest manager who, in addition to selling timber, has the option of selling carbon offsets for the carbon sequestered by the forest. We study both the single-rotation and the multiple-rotations harvesting problems, and develop stochastic dynamic programming models to find the optimal harvesting and offset-selling policy, the expected optimal harvesting time, and the expected optimal reward under different offset-trading schemes. Then, we study the case in which an organization (sustainability buyer) outsources sustainability efforts to another organization (sustainability seller). While buyers cannot directly exert sustainability efforts, they can provide economic or technical support to their sellers in order to incentivize these efforts. We investigate how the effort and support decisions change according to characteristics of stakeholders, buyers, and sellers. Considering that buyers can compete on the sustainability effort exerted by their sellers, we extend our analysis to the case of competing buyers, and we determine conditions under which sharing sellers is preferred by the buyers to having separate sellers for each buyer.</p> / Dissertation