Game Theory Goes to Dinner
Scenario: You're dining out with friends at an oh-so-trendy tapas place. The group decides to order one of everything on the menu—which includes dishes you like (mmm, chorizo) and dishes you don't (ugh, boquerones)—to share. How do you get the most enjoyment out of the meal?
For Katherine Stange, a postdoctoral researcher in mathematics, the answer lies in the application of game theory. With colleague Lionel Levine of Cornell, Stange modeled a simplified shared-platter scenario and arrived at some surprising—and some not-so-surprising—conclusions.
To operationalize the tapas quandary, the researchers assigned point values to different foods corresponding to their desirability from the perspective of individual diners and defined the most enjoyable meal as the one that racks up the highest total score. In situations where dining partners have opposite tastes, they reasoned, there's no problem—both can maximize their scores. But when diners salivate over the same dishes, that's when things get interesting.
One counterintuitive result: It pays to consider what your dining partner deems the least desirable dish. Why? If I know my dinner date will pass on pork, I can safely save the chorizo for last—even though it's one of my favorites—because I know it's unlikely to disappear before I've had a taste.
Along with Scott Sheffield of MIT, the researchers then modeled a complex scenario with two types of hypothetical diners they dubbed the "gallant knight" and the "boorish lout." Knights make selections that take into account the preferences of others, while louts always gobble up their favorites first. Stange and her colleagues showed mathematically that boorishness isn't necessarily bad, though; if everyone's trying to be gallant they may actually work at cross-purposes. Tell that to the guy who gets stuck with the check.
Fantastic Voyage for Tiny Device
It used to be that the only thing that could shrink to the size of a sesame seed and swim through your bloodstream was the Magic School Bus. Not any longer. A new kind of electronic medical device being developed by assistant professor of electrical engineering Ada Poon is small enough to venture into a person's blood vessels or digestive system. Powered and steered remotely by way of electromagnetic radio waves, the device has potential applications ranging from drug delivery to internal imaging to the removal of blood clots.
The project stems from Poon's previous research on wireless power. "We figured out that there's a certain optimal frequency where we could transmit the power efficiently to a device inside the body," she says. This was a major breakthrough, because the main obstacle in creating such a device is the relationship between the size of the device and the amount of power it can receive. By eliminating the need for bulky batteries and transmitting power at a frequency high enough to require only a minuscule antenna, Poon and her research team were able to create an implant that is extremely small—3 mm by 4 mm.
The implant's size isn't the only thing that sets it apart from other devices on the market or in development. Poon's device can be guided with great precision, making it ideal for handling tricky medical tasks. "The device is placed in a magnetic field, and by driving currents on the device we can manipulate forces on them to propel the device, so it can swim through any fluid medium," says Daniel Pivonka, MS '09, a doctoral candidate working with Poon. Their next step is to establish a data uplink for the device—a way for it to communicate with an external reader, sending out an alert if, for example, it encounters an object blocking its path.
While this project may seem plenty ambitious, for Poon it's one of many. She estimates that this type of locomotive device will be in clinical use in five to 10 years. In the meantime she's already started work on a wireless device small enough to fit inside a living cell.
— Helen Anderson, '14
CAPTCHA Cracker Safeguards Web
You wouldn't know it to look at him, but Elie Bursztein is one of the Internet's most badass bouncers. As a postdoctoral researcher in Stanford's Computer Security Lab, Bursztein specialized in cracking CAPTCHAs, those warped strings of letters and numbers that serve as entrance barriers to many websites. By discovering vulnerabilities in CAPTCHAs, Bursztein is able to recommend the best design principles for creators and help them polish their prototypes.
Invented in 2000 by a team of computer scientists at Carnegie Mellon, CAPTCHAs were designed to foil a spamming bot, but not a person. But as artificial intelligence has gotten more sophisticated, CAPTCHA creators have had to make them more complex, resulting in jumbles of characters that confound even human users.
In 2010, a company called NuCaptcha introduced a variant with moving text layered over video images that was easier for people, while still thwarting spammers. Starting that year, Bursztein's group—which had previously created Decaptcha, a computer program that uses artificial intelligence and machine vision to bypass audio- and text-based CAPTCHAs—began to test the security of NuCaptcha's video version. Using Decaptcha along with motion tracking and optical flow algorithms, they were the first to break video CAPTCHAs.
Bursztein's tips for improving security of text-based CAPTCHAs include randomizing the length and character size and including waves in the design. For video CAPTCHAs, he advised NuCaptcha to apply a concept called "tracking resistance" which involves adding another text object to act as a decoy and confuse computer algorithms.
Having helped to bolster security for a number of Internet companies, Bursztein is now recognized in "the halls of fame for security conservation" at Facebook, Wikipedia and Google (where he now works), among others. But, he says, security is about more than keeping the riffraff out; it's critical to democracy. "Security is essential to freedom of speech. By ensuring the integrity, confidentiality and anonymity (when desired) of Internet communication, we give people the confidence and the tools they need to express themselves without the fear of retaliation and coercion."
