CSCE 411 Lecture 29

Lecture Slides

« previous | Monday, November 5, 2012 | next »

The Hat Game

Players cannot do better than 50%, but as a team, they can do much better by spreading out the "good guesses" and concentrating the "bad guesses"

In General

When played over all combinations with $n$ players, any strategy produces $k$ correct guesses and $k$ incorrect guesses. The best possible guess arrangement is:

• 1 correct guess per winning combination
• $n$ correct guesses per losing combination

This is called a perfect strategy and cannot be obtained for certain numbers of players.

We've already solved for $n=3$, but what about other $n$?

Finding a Perfect Strategy

Let $H$ be the set of all possible hat configurations (0 for one color, 1 for the other)

Let $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(H)$ be the number of places in which two elements of $H$ differ.

Example:

1 0 0 1 0 1 1 0 1
1 0 1 1 0 1 0 0 1

dist(H) = 2

Let a ball of radius $r$ around $h\in H$ be the set of all configurations whose distance from $h$ is at most $r$.

Example:

h: 1001
B[1](H) = 0001, 1101, 1011,1000

Note that $|B_1(h)|=n+1$

Let $S$ be a deterministic strategy.

Let $L$ be the set of all hat configurations where a team playing according to $S$ loses.

Let $W$ be the set of all hat configurations where a team playing according to $S$ wins.

Note $L\cup W=H$, and $L$ and $W$ are mutually exclusive and mutually exhaustive.

Suppose $h$ and $h^{\prime }$ are elements of $H$ that differ only in the $i$^th entry.

According to $S$, if Player $i$ guesses correctly in $h$, then he guesses incorrectly in $h^{\prime }$, and vice versa.

Every element $h\in H$ is contained in a ball of radius 1 around some element of $L$.

In a perfect strategy $S$, the balls of radius 1 around l do not overlap

Let a Perfect code of length $n$ be a subset $L\in H$ such that the balls of radius 1 around the points of $L$ include all of $H$ and do not overlap.

A perfect strategy yields a perfect code:

Instructions for each player:

• If the hat configuration might be in $L$, guess so that if it's in $L$, you'll be wrong.
• If you can tell that the configuration is not in $L$, pass.

If $S$ is a perfect strategy for $n$ players, then the probability of winning is $\frac{n}{n+1}$.

Do perfect codes exist for $n>3$? Yes:

A perfect code of length $n$ exists for $n=2^m-1$.

Proof: A perfect code splits $H$ into disjoint balls of radius 1. Each ball has $n+1$ points and $H$ has 2^n points, so $2^n$ is divisible by $n+1$, so $n+1$ is a power of 2, so $n=2^m-1$

NP-Completeness

Lecture Slides

Intrinsic hardness of problems.

NP = set of problems that can be checked quickly, but take a long time to solve (i.e. difficult)

Informal discussion: we will never get very formal in this course.

Polynomial Time Algorithms

Most of the algorithms we've seen so far run in time that is upper bounded by a polynomial in the input size ($O(n^k)$):

• Sorting: $O(n^2)$, $O(n\log n)$.
• Matrix Multiplication: $O(n^3)$, $O(n^{{\log }_{2}7})$
• Graph Algorithms: $O(V+E)$, $O(E\log V)$

In fact, the running time of these algorithms are bounded by small polynomials.

Categorization

We call computational problem tractable iff it can be solved in polynomial time.

Decision Problems and Class P

Computational problem with yes/no answer is called a decision problem

$P$ is class of all tractable decision problems.