What does haggling at a garage sale have to do with load balancing in distributed systems? How does bidding in an art auction relate to cloud service orchestration? Familiarity with the ideas and technologies involved in cloud computing is becoming ever more important for developers. This talk will demonstrate how you can use game theory — the study of strategic decision making — to design more efficient, and innovative, distributed systems.
My talk will reveal 'game theoretic' thinking as an important tool in the distributed systems domain, and also provide attendees with basic tools for framing their problems using this skill.
This talk will present two game theory examples and show how they relate to a particular branch of cloud computing. Each example will begin with a seemingly unrelated scenario, followed by an explanation of how the story ties into cloud computing. Once the link has been established, I will show how to construct a simple game theory model for that example. The talk will slowly build in more complexity such that we end up with practical solutions to real problems.
The talk will be useful for anyone who has worked with distributed systems, as well as those who are curious about them and would like to learn more. I’ll keep the maths simple, and the game theory examples will appeal to both mathematical and non-mathematical minds.
I'll start with a short anecdote to draw the audience in - for example, a story based around game of 'Chicken': http://en.wikipedia.org/wiki/Chicken_%28game%29. It's an example that many audience members will have encountered, if not in real life, then in a film or book.
I'll then tie that in to who I am and why I came to be giving this talk.
2 Game Theory Introduction
I'll give basic pointers about game theory and introduce some key terminology.
I'll then explain how that terminology applies to the opening example, to help orient audience members who are new to game theory.
3 Resource Allocation Example
You are trying to sell your old bike to a friend. What can game theory tell us about how this transaction will complete?
Here I introduce Bargaining Theory and the concept of surplus in transactions.
I'll discuss a basic example of how we can use bargaining theory to model resource allocation in the cloud.
We'll work through a simple problem. For example, given the processing power and utility functions of the computers in a system, how do we start to think about how many jobs we should send to each one?
I'll then analyse how the solution gives us a starting point from which we can extrapolate more complex algorithms.
After this first example, I might also outline an auction scenario example, showing how it can help model distribution of services across a cloud network.
4 Assumptions and Constraints
I will introduce some criticisms of game theory regarding unrealistic assumptions about agent behaviour.
I'll discuss how the initial assumptions and constraints applied in this talk provide a helpful starting point to which we can gradually introduce more complexity. This helps us to grasp the essence of the problem before building up to more practical solutions.
5 What will the audience take away from the talk?
The audience will see that you don’t need maths to understand complex issues using Game Theory. In the realm of distributed systems, parts of a system can be modelled as a game, introducing competition or consensus between components to achieve desired system behaviour.
There are other applications of game theory in this field to explore. For example, non-cooperative games provide a useful model for cloud security, and coalition theory can help us to analyse competition amongst PaaS companies.
I’ll also share actionable next steps for audience members, including further reading and exercises, to encourage attendees to incorporate this mode of thinking into their workflow.
Ruby developers must increasingly interact with distributed systems and cloud technology, as I learned when I started my current job. With little real-world programming experience, I was thrown into the deep end of a complex distributed system. I had to find a way to digest a lot of information in a way that made sense to me. However, distributed system design can be dense and challenging, and I found it hard to understand much of the material on the topic. Having learned game theory through applications in economics, I learned it could also be used to help understand distributed systems.
I have been studying and reading about game theory for over six years now. It was a focus of my course of study at a world-leading university. Pursuing my keen interest in the topic, I have given a number of engaging game theory seminars and presentations. These activities have provided me with an intermediate-level understanding of the domain. For this talk, I am excited to delve into the mathematical problems presented in academic papers, and reframe some of the key ideas in a creative and accessible way.
Nadia is a software engineer at Pivotal Labs London, recently working on the Cloud Foundry team. She joined the company after graduating from a software development bootcamp. Before that, while studying at Oxford for a degree in Economics, she fell in love with game theory. Nadia is a tech startup enthusiast, and in her spare time she runs The StoryGraph, an online creative writing publication.