# Puzzling Adventures: The Fair Way to Get a College Scholarship: Let's Make a Deal

How should teachers rank their students' performance?

One hundred students are competing for college scholarships. They come from 10 schools (10 students per school). From each school, one student has declared physics as a major; one has declared chemistry; one, biology; one, psychology; one, mathematics; one, economics; one, anthropology; one, linguistics; one, English; and one, history. So, the group has 10 students for each of these majors.

Each of three judges is going to rank the students in 10 ranks from best (rank 1) to worst (rank 10). That is, each judge is to assign ten 1s, ten 2s, and so on up to ten 10s. So, each judge will assign one rank per student.

In previous years, some of the losing students have alleged that the judges were biased, so we want to ensure two "fairness" constraints that will require some planning on the part of the judge. In the rankings done by each judge:

1. Each school will receive 10 different ranking scores.
2. Each major will receive 10 different ranking scores.

So, among the economics majors, for example, each judge should assign one 1, one 2, one 3, and so on up to one 10. Similarly, among the students from Pleasanttown High School, each judge should assign one 1, one 2, and so on up to one 10.

Each student's three scores (one from each judge) will be averaged.

Our problem is to ensure that each judge obeys the constraints but without our knowing how that judge voted. That is, out of respect for the privacy of the judging, we want to know for certain that the judges obeyed the constraints but nothing more.

To show you that this is at least conceivable, suppose we imagine a variant of Monty Hall's game show, Let's Make a Deal, using cards in which all of them are worth zero except one that is worth \$10,000. The Master of Ceremonies begins the game by arranging the cards face down. The contestant could choose one, which the MC would turn over and then give the corresponding reward. If the contestant loses, he or she might then challenge the MC to see whether there is in fact one card that is worth \$10,000. To prove this, the MC could take the cards, shuffle them in front of the contestant, and then reveal them. The net effect is that the MC has proved that he has not cheated. At the same time, he has not revealed the original position of the prize card.

Problem:
Imagine that each judge is given 100 opaque cards that hold the name, school and major of the student on one side and are blank on the other. Each judge also has 100 adhesives, ten identical 1s, ten identical 2s, and so on up to ten 10s. Can you design a protocol to ensure that each judge meets the constraints, but without allowing anyone to infer a judge's votes?

Thanks to Michael Rabin for this approach to demonstrating knowledge without revealing secrets. He used it to form a "zero-knowledge" proof for Sudoku.

Dennis Shasha is at the Courant Institute of Mathematical Sciences, New York University. His most recent puzzle book, Puzzles for Programmers and Pros, was published in May 2007 by John Wiley and Sons/Wrox.

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• AccuWeather | 5 hours ago | 1

### Large 200 MPH Tornado Hits Suburb of Oklahoma City

• Guest Blog | 6 hours ago

### Angelina Jolie and the One Percent

• Molecules to Medicine | 12 hours ago

### The s**t hits the fan - FDA, INDs, and fecal microbiota transplants

• Observations | 12 hours ago

### See Mercury, Venus and Jupiter in Tightest Night Sky Cluster until 2026

• News | 13 hours ago

More »

## Latest from SA Blog Network

• ### #SciAmBlogs Monday - eating healthfully, DSM-5, polyploidy, fecal transplants, non-identical twins, and more.

STAFF
The Network Central | 4 hours ago
• ### Angelina Jolie and the One Percent

Guest Blog | 6 hours ago
• ### A Beautiful Fungus Graveyard

Oscillator | 9 hours ago
• ### Self-Publishing Tools for Science Artists

Symbiartic | 10 hours ago
• ### The s**t hits the fan - FDA, INDs, and fecal microbiota transplants

Molecules to Medicine | 12 hours ago

Puzzling Adventures: The Fair Way to Get a College Scholarship: Let's Make a Deal

X

### Subscribe Today

Save 66% off the cover price and get a free gift!

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X