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?
