Rutgers Discrete Mathematics Seminar

Title: Games of Hide-and-seek with Balls in Boxes

Speaker: Thomas Lidbetter, Rutgers

Date: Monday, April 9, 2018 2:00 pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


We consider zero-sum games in which one player (the Hider) hides k balls among n boxes and the other player (the Searcher) inspects the boxes one by one until finding all k balls. The Searcher has to pay a cost to inspect each box, and may or may not be limited to finding at most one ball each time she inspects a box. We may consider two different objectives for the Searcher: to minimize the total cost incurred in finding all the balls, or to minimize her regret, which is the total cost minus what she'd pay if she knew where all the balls were. We seek optimal (min-max) solutions for both players. No knowledge of game theory will be assumed - the fundamentals of zero-sum games will be explained.