Entries Tagged "game theory"

Page 1 of 3

A Self-Enforcing Protocol to Solve Gerrymandering

In 2009, I wrote:

There are several ways two people can divide a piece of cake in half. One way is to find someone impartial to do it for them. This works, but it requires another person. Another way is for one person to divide the piece, and the other person to complain (to the police, a judge, or his parents) if he doesn’t think it’s fair. This also works, but still requires another person—­at least to resolve disputes. A third way is for one person to do the dividing, and for the other person to choose the half he wants.

The point is that unlike protocols that require a neutral third party to complete (arbitrated), or protocols that require that neutral third party to resolve disputes (adjudicated), self-enforcing protocols just work. Cut-and-choose works because neither side can cheat. And while the math can get really complicated, the idea generalizes to multiple people.

Well, someone just solved gerrymandering in this way. Prior solutions required either a bipartisan commission to create fair voting districts (arbitrated), or require a judge to approve district boundaries (adjudicated), their solution is self-enforcing.

And it’s trivial to explain:

  • One party defines a map of equal-population contiguous districts.
  • Then, the second party combines pairs of contiguous districts to create the final map.

It’s not obvious that this solution works. You could imagine that all the districts are defined so that one party has a slight majority. In that case, no combination of pairs will make that map fair. But real-world gerrymandering is never that clean. There’s “cracking,” where a party’s voters are split amongst several districts to dilute its power; and “packing,” where a party’s voters are concentrated in a single district so its influence can be minimized elsewhere. It turns out that this “define-combine procedure” works; the combining party can undo any damage that the defining party does—that the results are fair. The paper has all the details, and they’re fascinating.

Of course, a theoretical solution is not a political solution. But it’s really neat to have a theoretical solution.

Posted on February 2, 2024 at 7:01 AM • View Comments

Uber Drivers Hacking the System to Cause Surge Pricing

Interesting story about Uber drivers who have figured out how to game the company’s algorithms to cause surge pricing:

According to the study. drivers manipulate Uber’s algorithm by logging out of the app at the same time, making it think that there is a shortage of cars.

[…]

The study said drivers have been coordinating forced surge pricing, after interviews with drivers in London and New York, and research on online forums such as Uberpeople.net. In a post on the website for drivers, seen by the researchers, one person said: “Guys, stay logged off until surge. Less supply high demand = surge.”

.

Passengers, of course, have long had tricks to avoid surge pricing.

I expect to see more of this sort of thing as algorithms become more prominent in our lives.

Posted on August 8, 2017 at 9:35 AM • View Comments

Shadow Brokers Releases the Rest of Their NSA Hacking Tools

Last August, an unknown group called the Shadow Brokers released a bunch of NSA tools to the public. The common guesses were that the tools were discovered on an external staging server, and that the hack and release was the work of the Russians (back then, that wasn’t controversial). This was me:

Okay, so let’s think about the game theory here. Some group stole all of this data in 2013 and kept it secret for three years. Now they want the world to know it was stolen. Which governments might behave this way? The obvious list is short: China and Russia. Were I betting, I would bet Russia, and that it’s a signal to the Obama Administration: “Before you even think of sanctioning us for the DNC hack, know where we’ve been and what we can do to you.”

They published a second, encrypted, file. My speculation:

They claim to be auctioning off the rest of the data to the highest bidder. I think that’s PR nonsense. More likely, that second file is random nonsense, and this is all we’re going to get. It’s a lot, though.

I was wrong. On November 1, the Shadow Brokers released some more documents, and two days ago they released the key to that original encrypted archive:

EQGRP-Auction-Files is CrDj”(;Va.*NdlnzB9M?@K2)#>deB7mN

I don’t think their statement is worth reading for content. I still believe the Russia are more likely to be the perpetrator than China.

There’s not much yet on the contents of this dump of Top Secret NSA hacking tools, but it can’t be a fun weekend at Ft. Meade. I’m sure that by now they have enough information to know exactly where and when the data got stolen, and maybe even detailed information on who did it. My guess is that we’ll never see that information, though.

EDITED TO ADD (4/11): Seems like there’s not a lot here.

Posted on April 10, 2017 at 5:51 AM • View Comments

Prisoner's Dilemma Experiment Illustrates Four Basic Phenotypes

If you’ve read my book Liars and Outliers, you know I like the prisoner’s dilemma as a way to think about trust and security. There is an enormous amount of research—both theoretical and experimental—about the dilemma, which is why I found this new research so interesting. Here’s a decent summary:

The question is not just how people play these games­—there are hundreds of research papers on that­—but instead whether people fall into behavioral types that explain their behavior across different games. Using standard statistical methods, the researchers identified four such player types: optimists (20 percent), who always go for the highest payoff, hoping the other player will coordinate to achieve that goal; pessimists (30 percent), who act according to the opposite assumption; the envious (21 percent), who try to score more points than their partners; and the trustful (17 percent), who always cooperate. The remaining 12 percent appeared to make their choices completely at random.

Posted on August 18, 2016 at 5:36 AM • View Comments

Major NSA/Equation Group Leak

The NSA was badly hacked in 2013, and we’re just now learning about it.

A group of hackers called “The Shadow Brokers” claim to have hacked the NSA, and are posting data to prove it. The data is source code from “The Equation Group,” which is a sophisticated piece of malware exposed last year and attributed to the NSA. Some details:

The Shadow Brokers claimed to have hacked the Equation Group and stolen some of its hacking tools. They publicized the dump on Saturday, tweeting a link to the manifesto to a series of media companies.

The dumped files mostly contain installation scripts, configurations for command and control servers, and exploits targeted to specific routers and firewalls. The names of some of the tools correspond with names used in Snowden documents, such as “BANANAGLEE” or “EPICBANANA.”

Nicholas Weaver has analyzed the data and believes it real:

But the proof itself, appear to be very real. The proof file is 134 MB of data compressed, expanding out to a 301 MB archive. This archive appears to contain a large fraction of the NSA’s implant framework for firewalls, including what appears to be several versions of different implants, server side utility scripts, and eight apparent exploits for a variety of targets.

The exploits themselves appear to target Fortinet, Cisco, Shaanxi Networkcloud Information Technology (sxnc.com.cn) Firewalls, and similar network security systems. I will leave it to others to analyze the reliability, versions supported, and other details. But nothing I’ve found in either the exploits or elsewhere is newer than 2013.

Because of the sheer volume and quality, it is overwhelmingly likely this data is authentic. And it does not appear to be information taken from comprised systems. Instead the exploits, binaries with help strings, server configuration scripts, 5 separate versions of one implant framework, and all sort of other features indicate that this is analyst-side code­—the kind that probably never leaves the NSA.

I agree with him. This just isn’t something that can be faked in this way. (Good proof would be for The Intercept to run the code names in the new leak against their database, and confirm that some of the previously unpublished ones are legitimate.)

This is definitely not Snowden stuff. This isn’t the sort of data he took, and the release mechanism is not one that any of the reporters with access to the material would use. This is someone else, probably an outsider…probably a government.

Weaver again:

But the big picture is a far scarier one. Somebody managed to steal 301 MB of data from a TS//SCI system at some point between 2013 and today. Possibly, even probably, it occurred in 2013. But the theft also could have occurred yesterday with a simple utility run to scrub all newer documents. Relying on the file timestamps­—which are easy to modify­—the most likely date of acquisition was June 11, 2013. That is two weeks after Snowden fled to Hong Kong and six days after the first Guardian publication. That would make sense, since in the immediate response to the leaks as the NSA furiously ran down possibly sources, it may have accidentally or deliberately eliminated this adversary’s access.

Okay, so let’s think about the game theory here. Some group stole all of this data in 2013 and kept it secret for three years. Now they want the world to know it was stolen. Which governments might behave this way? The obvious list is short: China and Russia. Were I betting, I would bet Russia, and that it’s a signal to the Obama Administration: “Before you even think of sanctioning us for the DNC hack, know where we’ve been and what we can do to you.”

They claim to be auctioning off the rest of the data to the highest bidder. I think that’s PR nonsense. More likely, that second file is random nonsense, and this is all we’re going to get. It’s a lot, though. Yesterday was a very bad day for the NSA.

EDITED TO ADD: Snowden’s comments. He thinks it’s an “NSA malware staging server” that was hacked.

EDITED TO ADD (8/18): Dave Aitel also thinks it’s Russia.

EDITED TO ADD (8/19): Two news articles.

Cisco has analyzed the vulnerabilities for their products found in the data. They found several that they patched years ago, and one new one they didn’t know about yet. See also this about the vulnerabilities.

EDITED TO ADD (8/20): More about the vulnerabilities found in the data.

Previously unreleased material from the Snowden archive proves that this data dump is real, and that the Equation Group is the NSA.

EDITED TO ADD (8/26): I wrote an essay about this here.

EDITED TO ADD (9/13): Someone who < a href="http://xorcat.net/2016/08/16/equationgroup-tool-leak-extrabacon-demo/">played with some of the vulnerabilities.

Posted on August 16, 2016 at 10:43 AM • View Comments

Psychological Model of Selfishness

This is interesting:

Game theory decision-making is based entirely on reason, but humans don’t always behave rationally. David Rand, assistant professor of psychology, economics, cognitive science, and management at Yale University, and psychology doctoral student Adam Bear incorporated theories on intuition into their model, allowing agents to make a decision either based on instinct or rational deliberation.

In the model, there are multiple games of prisoners dilemma. But while some have the standard set-up, others introduce punishment for those who refuse to cooperate with a willing partner. Rand and Bear found that agents who went through many games with repercussions for selfishness became instinctively cooperative, though they could override their instinct to behave selfishly in cases where it made sense to do so.

However, those who became instinctively selfish were far less flexible. Even in situations where refusing to cooperate was punished, they would not then deliberate and rationally choose to cooperate instead.

The paper:

Abstract: Humans often cooperate with strangers, despite the costs involved. A long tradition of theoretical modeling has sought ultimate evolutionary explanations for this seemingly altruistic behavior. More recently, an entirely separate body of experimental work has begun to investigate cooperation’s proximate cognitive underpinnings using a dual-process framework: Is deliberative self-control necessary to reign in selfish impulses, or does self-interested deliberation restrain an intuitive desire to cooperate? Integrating these ultimate and proximate approaches, we introduce dual-process cognition into a formal game-theoretic model of the evolution of cooperation. Agents play prisoner’s dilemma games, some of which are one-shot and others of which involve reciprocity. They can either respond by using a generalized intuition, which is not sensitive to whether the game is one-shot or reciprocal, or pay a (stochastically varying) cost to deliberate and tailor their strategy to the type of game they are facing. We find that, depending on the level of reciprocity and assortment, selection favors one of two strategies: intuitive defectors who never deliberate, or dual-process agents who intuitively cooperate but sometimes use deliberation to defect in one-shot games. Critically, selection never favors agents who use deliberation to override selfish impulses: Deliberation only serves to undermine cooperation with strangers. Thus, by introducing a formal theoretical framework for exploring cooperation through a dual-process lens, we provide a clear answer regarding the role of deliberation in cooperation based on evolutionary modeling, help to organize a growing body of sometimes-conflicting empirical results, and shed light on the nature of human cognition and social decision making.

Very much in line with what I wrote in Liars and Outliers.

Posted on January 28, 2016 at 6:18 AM • View Comments

Incenting Drug Dealers to Snitch on Each Other

Local police are trying to convince drug dealers to turn each other in by pointing out that it reduces competition.

It’s a comical tactic with serious results: “We offer a free service to help you eliminate your drug competition!” Under a large marijuana leaf, the flier contained a blank form encouraging drug dealers to identify the competition and provide contact information. It also asked respondents to identify the hours the competition was most active.

Posted on August 11, 2015 at 6:41 AM • View Comments

"Cooperating with the Future"

This is an interesting paper—the full version is behind a paywall—about how we as humans can motivate people to cooperate with future generations.

Abstract: Overexploitation of renewable resources today has a high cost on the welfare of future generations. Unlike in other public goods games, however, future generations cannot reciprocate actions made today. What mechanisms can maintain cooperation with the future? To answer this question, we devise a new experimental paradigm, the ‘Intergenerational Goods Game’. A line-up of successive groups (generations) can each either extract a resource to exhaustion or leave something for the next group. Exhausting the resource maximizes the payoff for the present generation, but leaves all future generations empty-handed. Here we show that the resource is almost always destroyed if extraction decisions are made individually. This failure to cooperate with the future is driven primarily by a minority of individuals who extract far more than what is sustainable. In contrast, when extractions are democratically decided by vote, the resource is consistently sustained. Voting is effective for two reasons. First, it allows a majority of cooperators to restrain defectors. Second, it reassures conditional cooperators that their efforts are not futile. Voting, however, only promotes sustainability if it is binding for all involved. Our results have implications for policy interventions designed to sustain intergenerational public goods.

Here’s a Q&A with and essay by the author. Article on the research.

EDITED TO ADD (12/10): A low-res version of the full article can be viewed here.

Posted on November 27, 2014 at 8:32 AM • View Comments

One-Shot vs. Iterated Prisoner's Dilemma

This post by Aleatha Parker-Wood is very applicable to the things I wrote in Liars & Outliers:

A lot of fundamental social problems can be modeled as a disconnection between people who believe (correctly or incorrectly) that they are playing a non-iterated game (in the game theory sense of the word), and people who believe that (correctly or incorrectly) that they are playing an iterated game.

For instance, mechanisms such as reputation mechanisms, ostracism, shaming, etc., are all predicated on the idea that the person you’re shaming will reappear and have further interactions with the group. Legal punishment is only useful if you can catch the person, and if the cost of the punishment is more than the benefit of the crime.

If it is possible to act as if the game you are playing is a one-shot game (for instance, you have a very large population to hide in, you don’t need to ever interact with people again, or you can be anonymous), your optimal strategies are going to be different than if you will have to play the game many times, and live with the legal or social consequences of your actions. If you can make enough money as CEO to retire immediately, you may choose to do so, even if you’re so terrible at running the company that no one will ever hire you again.

Social cohesion can be thought of as a manifestation of how “iterated” people feel their interactions are, how likely they are to interact with the same people again and again and have to deal with long term consequences of locally optimal choices, or whether they feel they can “opt out” of consequences of interacting with some set of people in a poor way.

Posted on May 23, 2013 at 9:18 AM • View Comments

1 2 3

Sidebar photo of Bruce Schneier by Joe MacInnis.