| Title | : | The power of two choices when the rich get richer: multiple choice at the multiplex |
| Speaker | : | Amanda Redlich (Brown University) |
| Details | : | Mon, 15 May, 2017 11:00 AM @ BSB 361 |
| Abstract: | : | A quick abstract:
Suppose you are a foreigner in a new city who wants to go to a movie. When you arrive at the multiplex, you see there are three different movies that start soon. How do you pick which one to watch? This talk will give a simple randomized algorithm that models a natural decision-making process in such contexts, discuss its potential applications, and analyze it mathematically.
A formal abstract: The well-known power of two choices allocation algorithm, first introduced by Azar, Broder, Karlin, and Upfal in 1994, creates a balanced allocation by, for each placement, selecting two options at random and opting for the lesser-loaded of the two. Since its introduction many variations have been studied: using more than two choices, selecting options non-uniformly, breaking ties in a biased way, looking at the heavily-loaded case, etc. Here I discuss a new variation: for each placement, choose the more-loaded option. This rich-get-richer process is a natural model for many real-world processes. And, it creates a distribution with some interesting mathematical properties. I'll define the process and analyze it rigorously, and also share some open questions. |
