Der Elfmeterschuss steht stellvertretend für eine ganze Kategorie sozialer Interaktionen - den Nullsummenspielen. Diese sind insofern von besonderem Interesse, als sich hier Akteure mit exakt gegenläufigen Interessen gegenüber stehen, die weder kommunizieren wollen noch können, dennoch interagieren und dabei eine stabile und vorhersagbare Form von sozialer Ordnung entstehen lassen. Und dies obschon beide Akteure gerade kein Interesse an der Entstehung oder Aufrechterhaltung einer solchen Ordnung haben. Die Fragestellung des Artikels: Verhalten sich Bundesligaspieler (Schützen und Torhüter) beim Elfmeterschuss gemäß den Vorhersagen der Spieltheorie? Die Analyse wird folgendermaßen gegliedert. Im nächsten Abschnitt werden erst die fußballerischen Grundlagen des Problems gelegt. Dann wird das Entscheidungsproblem spieltheoretisch analysiert und daraus ein entsprechendes LÄosungskonzept in Hypothesenform deduziert. Darauf folgt eine Darstellung des Stands der Forschung. Die empirische Überprüfung der Hypothesen mittels eines Datensatzes aus der ersten Bundesliga erfolgt in Abschnitt 4. Im letzen Abschnitt werden die Ergebnisse diskutiert und dabei insbesondere die Fragen in den Vordergrund gerückt, welche theoretischen Implikationen sich aus der Analyse für den RC-Ansatz im allgemeinen und die Spieltheorie im speziellen ergeben und was daraus aus methodischer Sicht zur Überprüfung von spieltheoretischen Hypothesen geschlossen werden kann.

The objective of this thesis is to develop decentralized methods for building robust multi-agent networks through self-organization. Multi-agent networks appear in a large number of natural and engineered systems, including but not limited to, biological networks, social networks, communication systems, transportation systems, power grids, and robotic swarms. Networked systems typically consist of numerous components that interact with each other to achieve some collaborative tasks such as flocking, coverage optimization, load balancing, or distributed estimation, to name a few. Multi-agent networks are often modeled via interaction graphs, where the nodes represent the agents and the edges denote direct interactions between the corresponding agents. Interaction graphs play a significant role in the overall behavior and performance of multi-agent networks. There- fore, graph theoretic analysis of networked systems has received a considerable amount of attention within the last decade. In many applications, network components are likely to face various functional or structural disturbances including, but not limited to, component failures, noise, or malicious attacks. Hence, a desirable network property is robustness, which is the ability to perform reasonably well even when the network is subjected to such perturbations. In this thesis, robustness in multi-agent networks is pursued in two parts. The first part presents a decentralized graph reconfiguration scheme for formation of robust interaction graphs. Particularly, the proposed scheme transforms any interaction graph into a random regular graph, which is robust to the perturbations of their nodes/links. The second part presents a decentralized coverage control scheme for optimal protection of networks by some mobile security resources. As such, the proposed scheme drives a group of arbitrarily deployed resources to optimal locations on a network in a decentralized fashion.

In this thesis we study problems in the context of inventory control and facility location. In chapter 2 we study the competition among risk averse newsvendors. We showed that the well-known result for the single-product monopoly firm, which states higher risk aversion causes the firm to reduce its order quantity, cease to hold under the competition. We concluded that the higher risk aversion does not necessarily cause both firms to reduce their order quantity. We showed that the impact of risk aversion on equilibrium quantities is a trade-off between two effects: (a) Own risk aversion increment which causes that the firm reduces its order quantity and (b) Effect of spillover demand from competitor which causes that the firm increases its order quantity. We also show which firm raises its order quantity as both firms become more risk averse depending on their attributes: profitability ratio (overstocking to understocking ratio), initial risk aversion level and demand characteristic (distribution and substitution). In Chapter 3, we study how the operational decisions of a firm's manager depend on her own incentives, the capital structure, and financial decisions in the context of the newsvendor framework. We showed that in contrast to common practices, tying the manager's compensation to stock price (equity value) may not be optimal for shareholders. We propose to tie the managers' compensation to the firm value or include a debt-like instrument in the compensation package to mitigate the risk taking behaviour of the managers. We also show how the board of directors can modify the compensation structure based on the state of the economy and publicly available information about company's demand. In Chapter 4, we study the effect of risk attitude of decision makers on well-known location problems with uncertain demand. In addition to providing mathematical formulations for those problems, we also discussed how we can solve these problems using linearization techniques. We also shed some light on the importance of considering the volatility and correlation structure. Furthermore, we apply a Bayesian updating method, a useful tool for updating the probability distribution to incorporate the consultants' view about uncertain factors in location problems.

In this thesis, we examine stochastic techniques for overcoming game theoretic and computational issues in the collective decision making process of self-interested individuals. In particular, we examine truthful, stochastic mechanisms, for settings with a strong budget balance constraint (i.e. there is no net flow of money into or away from the agents). Building on past results in AI and computational social choice, we characterise affine-maximising social choice functions that are implementable in truthful mechanisms for the setting of heterogeneous item allocation with unit demand agents. We further provide a characterisation of affine maximisers with the strong budget balance constraint. These mechanisms reveal impossibility results and poor worst-case performance that motivates us to examine stochastic solutions. To adequately compare stochastic mechanisms, we introduce and discuss measures that capture the behaviour of stochastic mechanisms, based on techniques used in stochastic algorithm design. When applied to deterministic mechanisms, these measures correspond directly to existing deterministic measures. While these approaches have more general applicability, in this work we assess mechanisms based on overall agent utility (efficiency and social surplus ratio) as well as fairness (envy and envy-freeness). We observe that mechanisms can (and typically must) achieve truthfulness and strong budget balance using one of two techniques: labelling a subset of agents as ``auctioneers'' who cannot affect the outcome, but collect any surplus; and partitioning agents into disjoint groups, such that each partition solves a subproblem of the overall decision making process. Worst-case analysis of random-auctioneer and random-partition stochastic mechanisms show large improvements over deterministic mechanisms for heterogeneous item allocation. In addition to this allocation problem, we apply our techniques to envy-freeness in the room assignment-rent division problem, for which no truthful deterministic mechanism is possible. We show how stochastic mechanisms give an improved probability of envy-freeness and low expected level of envy for a truthful mechanism. The random-auctioneer technique also improves the worst-case performance of the public good (or public project) problem. Communication and computational complexity are two other important concerns of computational social choice. Both the random-auctioneer and random-partition approaches offer a flexible trade-off between low complexity of the mechanism, and high overall outcome quality measured, for example, by total agent utility. They enable truthful and feasible solutions to be incrementally improved on as the mechanism receives more information and is allowed more processing time. The majority of our results are based on optimising worst-case performance, since this provides guarantees on how a mechanism will perform, regardless of the agents that use it. To complement these results, we perform empirical, average-case analyses on our mechanisms. Finally, while strong budget balance is a fixed constraint in our particular social choice problems, we show empirically that this can improve the overall utility of agents compared to a utility-maximising assignment that requires a budget imbalanced mechanism.

It seems like teaching about games should be easy. After all, students enjoy engaging with course content and have extensive experience with videogames. However, games education can be surprisingly complex. I explore the question of what it means to understand games by looking at the challenges and problems faced by students taking games-related classes. My findings include realizing that extensive prior videogame experience often interferes with students abilities to reason critically and analytically about games, and that students have difficulties articulating their experiences and observations about games. In response to these challenges, my research explores how we can use online learning environments to support learning about games by (1) helping students get more from their experiences with games, and (2) helping students use what they know to establish deeper understanding. I explore these strategies through the design and use of two online learning environments: GameLog and the Game Ontology Wiki. GameLog is an online blogging environment designed to help students reflect on their game playing experiences. The Game Ontology wiki provides a context for students to contribute and participate legitimately and authentically in the Game Ontology Project. The Game Ontology Project is a games studies research project that is creating a framework for describing, analyzing and studying games. GameLog and the Game Ontology Wiki were used in university level games-related classes. Results show that students found that participating in these online learning environments was a positive learning experience that helped them broaden and deepen their understanding of videogames. Students found that by reflecting on their experiences playing games they began to understand how game design elements helped shape that experience. Most importantly, they stepped back from their traditional role of gamers or fans and engaged in reasoning critically and analytically about the games they were studying. With GameLog, I show how blogging about experiences of gameplay can be a useful activity for supporting learning and understanding about games. For the Game Ontology Wiki, I show how it is possible to design learning environments that are approachable to learners and allow them to contribute legitimately to external communities of practice.

In this thesis, we do an algorithmic study of optimization problems in budgeted auctions, and some well known covering problems in the multi-agent setting. We give new results for the design of approximation algorithms, online algorithms and hardness of approximation for these problems. Along the way we give new insights for many other related problems. Budgeted Auction. We study the following allocation problem which arises in budgeted auctions (such as advertisement auctions run by Google, Microsoft, Yahoo! etc.) : Given a set of m indivisible items and n agents; agent i is willing to pay b[subscript ij] for item j and has an overall budget of B[subscript i] (i.e. the maximum total amount he is willing to pay). The goal is to allocate items to the agents so as to maximize the total revenue obtained. We study the computation complexity of the above allocation problem, and give improved results for the approximation and the hardness of approximation. We also study the above allocation problem in an online setting. Online version of the problem has motivation in the sponsored search auctions which are run by search engines. Lastly, we propose a new bidding language for the budgeted auctions: decreasing bid curves with budget constraints. We make a case for why this language is better both for the sellers and for the buyers. Multi-agent Covering Problems. To motivate this class of problems, consider the network design problem of constructing a spanning tree of a graph, assuming there are many agents willing to construct different parts of the tree. The cost of each agent for constructing a particular set of edges could be a complex function. For instance, some agents might provide discounts depending on how many edges they construct. The algorithmic question that one would be interested in is: Can we find a spanning tree of minimum cost in polynomial time in these complex settings? Note that such an algorithm will have to find a spanning tree, and partition its edges among the agents. Above are the type of questions that we are trying to answer for various combinatorial problems. We look at the case when the agents' cost functions are submodular. These functions form a rich class and capture the natural properties of economies of scale or the law of diminishing returns.We study the following fundamental problems in this setting- Vertex Cover, Spanning Tree, Perfect Matching, Reverse Auctions. We look at both the single agent and the multi-agent case, and study the approximability of each of these problems.

In this thesis, we examine stochastic techniques for overcoming game theoretic and computational issues in the collective decision making process of self-interested individuals. In particular, we examine truthful, stochastic mechanisms, for settings with a strong budget balance constraint (i.e. there is no net flow of money into or away from the agents). Building on past results in AI and computational social choice, we characterise affine-maximising social choice functions that are implementable in truthful mechanisms for the setting of heterogeneous item allocation with unit demand agents. We further provide a characterisation of affine maximisers with the strong budget balance constraint. These mechanisms reveal impossibility results and poor worst-case performance that motivates us to examine stochastic solutions. To adequately compare stochastic mechanisms, we introduce and discuss measures that capture the behaviour of stochastic mechanisms, based on techniques used in stochastic algorithm design. When applied to deterministic mechanisms, these measures correspond directly to existing deterministic measures. While these approaches have more general applicability, in this work we assess mechanisms based on overall agent utility (efficiency and social surplus ratio) as well as fairness (envy and envy-freeness). We observe that mechanisms can (and typically must) achieve truthfulness and strong budget balance using one of two techniques: labelling a subset of agents as ``auctioneers'' who cannot affect the outcome, but collect any surplus; and partitioning agents into disjoint groups, such that each partition solves a subproblem of the overall decision making process. Worst-case analysis of random-auctioneer and random-partition stochastic mechanisms show large improvements over deterministic mechanisms for heterogeneous item allocation. In addition to this allocation problem, we apply our techniques to envy-freeness in the room assignment-rent division problem, for which no truthful deterministic mechanism is possible. We show how stochastic mechanisms give an improved probability of envy-freeness and low expected level of envy for a truthful mechanism. The random-auctioneer technique also improves the worst-case performance of the public good (or public project) problem. Communication and computational complexity are two other important concerns of computational social choice. Both the random-auctioneer and random-partition approaches offer a flexible trade-off between low complexity of the mechanism, and high overall outcome quality measured, for example, by total agent utility. They enable truthful and feasible solutions to be incrementally improved on as the mechanism receives more information and is allowed more processing time. The majority of our results are based on optimising worst-case performance, since this provides guarantees on how a mechanism will perform, regardless of the agents that use it. To complement these results, we perform empirical, average-case analyses on our mechanisms. Finally, while strong budget balance is a fixed constraint in our particular social choice problems, we show empirically that this can improve the overall utility of agents compared to a utility-maximising assignment that requires a budget imbalanced mechanism.

Nowadays, with the rapid expansion of increasing utilization of renewable energy sources, power grid is evolving into a much complex man-made system in the technological age. Under the new circumstances, traditional methodologies for power system security analysis are facing a serious challenge. For the past decade, many countries have experienced large blackouts, which expose potential problems of current models and methodologies in power industry. On the other hand, since the 9.11 event and frequent suicide bombing attacks in some countries, terrorism has become a major threat for national security. With the extensive growth of terrorism activities, power system, the significant critical infrastructure, probably becomes the target of terrorists. If this happens, the impact is dramatically severe and may yield more frequent blackouts. This Ph.D. thesis aims at developing some advanced models and methodologies for exploring the vulnerability of power system and protecting it against potential terrorism threat. The dissertation mainly consists of the following four parts. (1)Complex network theory based power system security and vulnerability analysis methodologies are introduced. Mathematically, an interconnected complex power grid can be described as a complex network of nodes connected by edges. Generally speaking, topology parameters of network structure include important information of the structure. That is to say, some critical nodes and lines can have significant impact on large-scale blackouts. The thesis will present a new methodology to recognize those critical nodes and lines in power grids. (2)Complex system theory based power grid security and vulnerability analysis methodologies are presented. Power grid is a complex dynamic evolutionary system over years with continuous expansion so as to underpin the ongoing increase of power demand. Some properties of complex systems may have important relationship with large-scale blackouts. In other words, there may be some stages of evolutionary power systems that would be more likely to cause large blackouts. The thesis will investigate the relationship to identify those critical stages of power grids. (3)Game theory is applied to methodologies for power system security and vulnerability analysis. Terrorists are often considered as fully intelligent and strategic actors who can even hire scientists and power engineers to seek the vulnerability of power systems and then launch a vital attack. Game theory does treat actors as fully strategic players and has been successfully applied to many disciplines including economics, political science and military. The thesis will present new models and analysis methods for protecting power systems under terrorism attacks. (4)Cyber security technology is considered in power system security and vulnerability analysis. It is known that information technology plays an import role in today and next generation grid. In this situation, cyber security should be an important issue. If it is vulnerable to malicious threats such as hackers and cyber-terrorists, power grid will not reach its full capabilities. The thesis will present an initial framework to reduce the vulnerability of power grid against potential cyber attack.

Nowadays, with the rapid expansion of increasing utilization of renewable energy sources, power grid is evolving into a much complex man-made system in the technological age. Under the new circumstances, traditional methodologies for power system security analysis are facing a serious challenge. For the past decade, many countries have experienced large blackouts, which expose potential problems of current models and methodologies in power industry. On the other hand, since the 9.11 event and frequent suicide bombing attacks in some countries, terrorism has become a major threat for national security. With the extensive growth of terrorism activities, power system, the significant critical infrastructure, probably becomes the target of terrorists. If this happens, the impact is dramatically severe and may yield more frequent blackouts. This Ph.D. thesis aims at developing some advanced models and methodologies for exploring the vulnerability of power system and protecting it against potential terrorism threat. The dissertation mainly consists of the following four parts. (1)Complex network theory based power system security and vulnerability analysis methodologies are introduced. Mathematically, an interconnected complex power grid can be described as a complex network of nodes connected by edges. Generally speaking, topology parameters of network structure include important information of the structure. That is to say, some critical nodes and lines can have significant impact on large-scale blackouts. The thesis will present a new methodology to recognize those critical nodes and lines in power grids. (2)Complex system theory based power grid security and vulnerability analysis methodologies are presented. Power grid is a complex dynamic evolutionary system over years with continuous expansion so as to underpin the ongoing increase of power demand. Some properties of complex systems may have important relationship with large-scale blackouts. In other words, there may be some stages of evolutionary power systems that would be more likely to cause large blackouts. The thesis will investigate the relationship to identify those critical stages of power grids. (3)Game theory is applied to methodologies for power system security and vulnerability analysis. Terrorists are often considered as fully intelligent and strategic actors who can even hire scientists and power engineers to seek the vulnerability of power systems and then launch a vital attack. Game theory does treat actors as fully strategic players and has been successfully applied to many disciplines including economics, political science and military. The thesis will present new models and analysis methods for protecting power systems under terrorism attacks. (4)Cyber security technology is considered in power system security and vulnerability analysis. It is known that information technology plays an import role in today and next generation grid. In this situation, cyber security should be an important issue. If it is vulnerable to malicious threats such as hackers and cyber-terrorists, power grid will not reach its full capabilities. The thesis will present an initial framework to reduce the vulnerability of power grid against potential cyber attack.

Nowadays, with the rapid expansion of increasing utilization of renewable energy sources, power grid is evolving into a much complex man-made system in the technological age. Under the new circumstances, traditional methodologies for power system security analysis are facing a serious challenge. For the past decade, many countries have experienced large blackouts, which expose potential problems of current models and methodologies in power industry. On the other hand, since the 9.11 event and frequent suicide bombing attacks in some countries, terrorism has become a major threat for national security. With the extensive growth of terrorism activities, power system, the significant critical infrastructure, probably becomes the target of terrorists. If this happens, the impact is dramatically severe and may yield more frequent blackouts. This Ph.D. thesis aims at developing some advanced models and methodologies for exploring the vulnerability of power system and protecting it against potential terrorism threat. The dissertation mainly consists of the following four parts. (1)Complex network theory based power system security and vulnerability analysis methodologies are introduced. Mathematically, an interconnected complex power grid can be described as a complex network of nodes connected by edges. Generally speaking, topology parameters of network structure include important information of the structure. That is to say, some critical nodes and lines can have significant impact on large-scale blackouts. The thesis will present a new methodology to recognize those critical nodes and lines in power grids. (2)Complex system theory based power grid security and vulnerability analysis methodologies are presented. Power grid is a complex dynamic evolutionary system over years with continuous expansion so as to underpin the ongoing increase of power demand. Some properties of complex systems may have important relationship with large-scale blackouts. In other words, there may be some stages of evolutionary power systems that would be more likely to cause large blackouts. The thesis will investigate the relationship to identify those critical stages of power grids. (3)Game theory is applied to methodologies for power system security and vulnerability analysis. Terrorists are often considered as fully intelligent and strategic actors who can even hire scientists and power engineers to seek the vulnerability of power systems and then launch a vital attack. Game theory does treat actors as fully strategic players and has been successfully applied to many disciplines including economics, political science and military. The thesis will present new models and analysis methods for protecting power systems under terrorism attacks. (4)Cyber security technology is considered in power system security and vulnerability analysis. It is known that information technology plays an import role in today and next generation grid. In this situation, cyber security should be an important issue. If it is vulnerable to malicious threats such as hackers and cyber-terrorists, power grid will not reach its full capabilities. The thesis will present an initial framework to reduce the vulnerability of power grid against potential cyber attack.