Playing Games In The Clouds

by Nadia Odunayo

In the video titled "Playing Games In The Clouds" presented by Nadia Odunayo at RailsConf 2015, the speaker explores the intersection of game theory and cloud computing, demonstrating how strategic decision-making can optimize distributed systems.

Key points discussed in the presentation include:

Introduction to Game Theory: Odunayo begins with a relatable anecdote involving two university students who missed an exam due to a flat tire, illustrating the necessity of strategic interaction and decision-making, which is the core of game theory.
Understanding Distributed Systems: The speaker connects game theory with distributed computing, explaining how challenges in cloud computing can be approached through familiar concepts such as load balancing and resource allocation.
Bargaining Theory: The first example involves bargaining between two individuals over a bag of sweets, emphasizing how surplus resources can be shared efficiently and the importance of achieving a Nash equilibrium for optimal outcomes.
Load Balancing Game: Odunayo discusses a distributed system with two computers, explaining how jobs can be allocated based on their processing capabilities, which helps achieve efficient load distribution and minimizes execution time.
Auction Theory: Moving to the second game, she introduces the second-price auction concept, where participants bid for resources, highlighting how truthful bidding leads to optimal outcomes. This method can be used to allocate computing resources effectively in distributed systems.
Game Theory Applications: The speaker showcases how auction mechanisms can streamline resource allocation, especially when machines report their capabilities truthfully, thereby improving system performance and resilience against failures.
Conclusions: Odunayo concludes that insights into machine capabilities enhance decision-making in resource management, advocating for the relevance of game theory in technology development.

Overall, Odunayo's talk emphasizes that understanding and applying game-theoretic principles can lead to designing innovative and efficient distributed systems. She encourages the audience to explore further literature on game theory to bridge theoretical concepts with practical applications in areas like cloud computing.

The main takeaways are:
- Game theory offers valuable insights into optimizing distributed systems.
- Efficient job allocation can significantly improve the performance of cloud applications.
- Auction frameworks are beneficial for revealing machines' capabilities, leading to better resource distribution strategies.

Odunayo ends her talk by inviting the audience to engage further, suggesting an interactive exploration of game theory.

00:00:12.480 I want to start with a story about two university students and their final chemistry exam. They were smart and received A's in chemistry all semester. But the night before their final exam, they went parking in another state and did not get back until after the exam was over. They had to come up with an excuse. So, they went to their professor and said, "We're really sorry; we would have made it back in time for the test, but we were coming back from visiting a friend and had a flat tire. We need a makeup test." The professor thought it over and eventually agreed, sending them to separate rooms to take the test.

00:01:12.000 So, stories like this got me into game theory. I am a software engineer working at Pivotal Labs in London, primarily working on their cloud-based platforms as a service. I found the whole cloud computing space challenging to grasp. When you don't understand something, it's really helpful to put it into concepts you're familiar with, and for me, that was game theory.

00:01:30.800 I studied economics at university and gained experience in it, which was one of my favorite subjects. Through my reading, I discovered how game theory can provide interesting clarity in the distributed systems space, and I would like to share some of my findings with you today. We will start with a basic introduction to game theory, followed by two games, one related to bargaining and the other about auctions. Then, I will show how these simple examples have been extended to real-life case studies before we wrap up.

00:01:57.280 By the end, I hope to show you that not only is game theory a useful tool for providing sophisticated solutions in industry systems, but you can also discover how to efficiently allocate jobs in the systems that you build or work with. So, let's begin with more about game theory.

00:02:25.120 Game theory is the study of strategic interactions between rational agents. Its applications include economics, politics, biology, and computer science. Game theory was developed by John von Neumann and Oskar Morgenstern in 1944, with many other scholars extensively developing it in the 1950s. It applies to a wide range of games and interactions, typically seen in scenarios like the one we just talked about.

00:02:48.160 Despite its strength, all games, no matter the context, have some basic components. There are always at least two players, and each player has a strategy based on the actions they can take. Each player receives payoffs for every possible outcome.

00:03:09.040 We are going to look at a game that helps us solve the load-balancing problem. Imagine a distributed system with two computers where jobs are being sent to a task distributor, which must decide how many jobs to send to each computer.

00:03:38.159 In our first game about bargaining, one afternoon, you and your friend Gemma are walking along the street when you come across a bag of sweets on the floor. You want the sweets, but now you have to negotiate how you're going to split them. Bargaining theory attempts to answer how you will eventually divide those sweets between yourselves. Another way to phrase this is that bargaining theory asks how surplus will be shared between agents.

00:03:59.680 In the case of the sweets, there is surplus to be gained by sharing. The maximum surplus is equivalent to you getting the sweets and the other person getting nothing. In discussing these scenarios, it's useful to visualize them in relation to the previous example, showing all the possible payoffs you can achieve by dividing the sweets. The outer edge of the graph will represent a situation where all the sweets are allocated, and any point inside the purple area indicates that there are some sweets left on the floor after your negotiations.

00:04:38.560 The access represents the generous payoffs you can achieve with sharing. Essentially, we find a Nash equilibrium somewhere on the frontier, where you both have higher utility than if you had taken none of the sweets. In this example, I am simplifying by assuming the payoffs are linear.

00:05:06.880 So, what does this say about the allocation of resources? We can use bargaining theory to think about how resources should be allocated within a distributed system. When some computers are heavily loaded while others are underutilized, we can face poor system performance, and we want to mitigate against that.

00:05:36.000 Returning to our distribution system where two computers need to work together to complete tasks, we think about the nature of the players: the computers. Each computer has a different processing rate, which we know from the outset. Each computer's strategy is to accept a predetermined number of incoming jobs, and the payoff for each computer relates to the final job load.

00:06:05.600 Now, we assume that the computers will be better off by joining forces. In this system, computer A can handle five jobs every second, while computer B can handle two. Together, they need to complete four jobs. This leads us to the conclusion that we want to distribute the jobs in a manner that optimally minimizes execution time.

00:06:38.160 Once we have an optimal job allocation, we can no longer redistribute jobs in a way that negatively impacts one computer's performance while keeping the overall execution time either increases or remains constant.

00:07:05.280 Thus, we can think of a payoff function which can look something like this: log of x minus y, where x is the processing rate of the computer and y is the rate of incoming jobs being sent to the computer. The important takeaway is that as the number of jobs increases for a computer, the time it takes to complete those jobs increases exponentially.

00:07:34.000 Now, we want to maximize a function that represents this relationship. By substituting the processing rates into the function, we can create constraints based on the total number of jobs needing processing, which in this case is four.

00:08:02.800 When we graph this function, we're trying to find a point where happiness in the system is maximized. If you calculate the proper allocation, it turns out that you send 3.5 jobs to computer A and half a job to computer B. However, how does this look from a higher-level overview of the frontier?

00:08:32.720 In this scenario, we see a curved frontier where multiple jobs are being handled. The outer line represents how different processing rates influence the job allocation. When we calculate the performance of the system, we see a 1.33-second response time. If we shift jobs around and adjust allocations, we see how changing the load can lead to increased response times.

00:09:04.640 This primary takeaway is that efficient distribution of resources can be found through principles of game theory. While we only looked at a scenario with two computers, this concept can be extended to larger systems.

00:09:31.920 Now, let's look at another game. In this case, you and Gemma decide that instead of splitting the sweets, you'd be better off taking them to the school playground and auctioning them off to your friends.

00:09:57.920 So, how does this auction work? We look at a second-price auction concept. Participants in the auction simultaneously submit their bids, and the person who places the highest bid wins but only pays the value of the second-highest bid. This format might seem odd, but it produces interesting results.

00:10:30.800 Let's look at an example of three participants: Lucy bids $25, Mark bids $5, and Helen bids $10. Given this, Lucy will win the auction but will only pay $10. The strategy is interesting, as participants will typically aim to bid honestly and according to their valuations.

00:11:10.560 The concept of a dominant strategy arises here, meaning that if a strategy provides the highest possible payoff to a player regardless of what others do, it's optimal. A strategic dominant bid in a second-price auction is always to bid your true value.

00:11:46.560 Let's examine our previous example. If all participants bid according to their true values, they will maximize their outcomes without risking overbidding and potentially incurring losses.

00:12:12.880 In the end, using auction theory allows us to apply these principles to determine the resource capabilities of machines within a distributed system. In this case, if we consider two computers, each with known capabilities, they can auction off their resources, facilitating improved efficiency when handling tasks.

00:12:43.200 In distributed systems, when we incorporate auction-like mechanisms, we can ensure that the machines will truthfully report their capabilities and streamline resource allocation. We need to account for conditions where job allocation can become complex due to the unique characteristics of each job.

00:13:20.000 In summary, if we consider a distributed system with three machines, you can set algorithms based on Nash's bargaining solutions so that they work optimally. For instance, if one machine can’t keep up, it will be removed to improve overall system efficiency.

00:14:00.160 It’s been shown that simpler algorithms tend to lead to better performance than more complex models. The findings demonstrate that the average completion time remains consistent when using effective algorithms.

00:14:34.800 Taking this further, platforms that incorporate auction elements can optimize resource usage when orchestrating applications, effectively lowering computational complexity while enhancing overall system performance.

00:15:05.680 Suppose the resources are owned by self-interested agents. In that case, it may expose vulnerabilities in the performance of distributed systems. These frameworks can be instrumental in protecting optimal performance through second-price auction theory, which encourages machines to accurately report their capabilities.

00:15:43.680 And ultimately, the systems built on game-theoretic principles can adapt more effectively to failures and enhance resilience in the face of adversities, thereby showcasing a powerful approach to robust distributed system design.

00:16:20.640 So, what are the specific takeaways from today? When we have insight into machine capabilities, we can make informed decisions about resource allocation. In settings where capabilities are unknown, auction frameworks become crucial for revealing essential information.

00:17:27.680 Yet, it's worth noting that while game theory is criticized in human contexts, it can offer immense value in computing. Computers can be likened to rational agents, following predefined rules and responding to data inputs. When uncertainties arise, game theoretical frameworks provide tools for better analysis and understanding.

00:18:08.000 You don’t need advanced mathematics to apply these principles; rather, consider modeling different components of your system as a game. By collaborating and establishing what types of contracts and competitions exist, you can design much more effective systems.

00:18:41.920 Before concluding, I encourage exploring more resources on game theory and its parallels in various contexts, including cloud computing and database management. You'll find a wealth of information connecting theoretical concepts with practical applications.

00:19:32.080 As I wrap up, if you're intrigued by the topics shared today, I suggest looking into related literature, such as blog posts and books regarding game theory applications. Thank you for your attention today, and I'd like to end by asking: would you like to play a game?