Jiajin’s TCS Notes

The Stable Marriage Problem has been introduced in a previous post. In this post, let us view this problem in a game theoretic view. In particular, let’s consider the following scenario:

Each man and woman has a preference list of his/her possible partners and this preference list is private information only known by himself/herself. When the game starts, each person states a preference list, . An algorithm produces a stable matching according to the stated preference lists .

Now the question is:

Does any incentive exist such that someone can propose a and get a better partner?

The answer is YES. Formally, there does not exist an algorithm such that it can produce a stable matching according to the stated preference lists and telling truth is a dominant strategy for all players. The prove that truth revelation is not a dominant strategy, we need to prove for some strategies other players use, player has a better strategy than stating the truth preference list .

To prove this, Roth uses an instance of size 3. In this instance, only 2 matchings (man-optimal and woman optimal, respectively) are possible. Therefore any stable matching algorithm must produce either or . Let’s consider the algorithm finding $M_1$ first. If all the others tell the truth, we can find a woman such that giving a particular preference list will leads the algorithm to find , which is more preferable to . Therefore true telling is not a dominant strategy when we use algorithm to produce . The case of is similar

In this SODA ‘08 paper, they studied the problem of sampling stable matchings in the variants of stable marriage problem. It’s interesting to see that producing a fair stable marriage is a not-so-easy problem.

In the standard stable marriage problem, we have two sets and , corresponding men and women. Each person has a preference list of his/her possible partner of opposite sex. The goal is to produce a stable matching such that there does not exist a pair of and who prefer each other than their spouses in the matching. This problem has been solved by Gale and Shapley using a very simple polynomial time algorithm to produce a man-optimal matching. Here man-optimal matching means that men like their spouses better than those in any other stable matching. The matching Gale-Shapley algorithm produces also has the property that it is the worst stable matching women can get.

A fair stable matching roughly means that, in this stable matching, some men have their best achievable spouses and this is also true for some women. Since some instances of stable marriage problem do not have such stable matchings (one can find instances only have man and woman optimal matchings), we hope we can have a random sampling procedure to achieve the fairness in a expected sense. It is known that all the stable matchings of a stable marriage problem instance forms a distributive lattice. A simple idea is to do some random walk on this lattice. But they said this is hard. Instead, they studies some restricted models such as

• k-attributes model Each person has k attributes and we rank them by projecting a point in into a line.
• k-range model Any person has a predetermined rank and it can only fall into the set in any person’s preference list.
• k-list model Each gender is partitioned into different groups. People in the same group have the same preference list.

They studied the distributive lattice structure under these constrained model and devise some algorithms using Markov Chain to sample stable matchings uniformly.

Since I don’t know anything about Markov Chain except its name. I cannot describe any details of this paper. Hope in the near future, I can understand this paper better.

In this paper, Chen and Deng proved that, given payoff matrix, finding 2-player Nash Equilibrium is PPAD-Complete. So what is PPAD?

Let’s first start on TFNP (Total Functions in NP) . A polynomial time predicate function is that for every , there exists at least one that makes latex true. A TFNP is the problem that given an input , find a making true.

One subproblem class of TFNP is PPA where it ensures the existence of a . Formally, there is a lemma PPA (Polynomial Parity Argument) says that all graphs of maximum degree 2 have even number of leaves. Then given a leaf, you want to search another leaf.

PPAD is the problem defined on directed graphs where vertex has at most one incoming edge and and one outcoming edge. Formally, given an exponential-sized graph, where for each vertex , a polynomial-time computable function can give its successor (outcoming edge) and predecessor (incoming edge); and there exists a vertex in this graph that only has successor. The problem here is to find a s.t. vertex has no successor or predecessor.

Theoretical computer science is a fantastic topic in Computer Science. It mainly concerns the understanding of computation. Unlike other sub-field in CS, where experiments are more involved, rigorous and mathematics is in the spirit of TCS. I think I would save my unmatured and naive comments on TCS, but start to share my thoughts on topics, techniques, etc. on TCS. Therefore this blog is a place for me to summarize my understanding on TCS when I am doing the research. Other topics such as musing on how to do research, complaints on pathetic graduate student life will also appear in this blog. The posts will be written in English since I would like to train my English writing skills, otherwise the 90+ HKD for “The Elements of Style” bought in PAGE ONE is meaningless.

Now let’s start and have fun.

Since I have no class in SJTU at this last semester, I go to Fudan to listen my future adviser’s lectures and participate seminars of the theory group in Fudan.

From last week, we were going to have lectures of PCP Theorem each week. PCP Theorem is the most important result in Complexity Theory in the last ten years. The statement is quite amazing at first glance.

For any language L in NP, there exists a verifier V that uses O(log n) random bits and makes O(1) queries to the proof such that

• If x belongs to L, there exist a proof π, such that Pr[V(π,x) = 1] = 1
• If x does not belong to L, for any proof π, Pr[V(π,x)=1] < s

Here V(π,x)=1 means x belongs to L.

I omit the introduction in this post, anyone who has interest can read this post by Lance. We use Sudan’s notes in our lectures, which now I thought is really a bad idea. In Sudan’s notes, he still use multivariate polynomials to amplify the gap in the original proof of PCP theorem. This proof is so complicated that currently I have no idea what’s going on. It is really a pity we didn’t follow the new astonishing proof by Dinur, whose technique of gap amplification is now used by almost every PCP lectures and books (even by Arora himself).

The problem is learned from “Algorithm Design” by Kleinberg and Tardos, Chapter 2, ex. 8. But the first time I heard this problem, it was said to be an interview problem of Google.

You are doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as follows. You have a ladder with rungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break. We call this the highest safe rung.

The trade-off here is the number of broken jars and the times of the drops. If the binary search is chosen, you can use only times to find the highest safe rung. As a result, you will also consume broken jars. On the other hand, if you want to conserve the jars, linear search could be used - drop the jar from the lowest rung. In the worse case, the number of tries to find the highest safe rung will be .

How can we find some optimal strategy which decrease the times of drops in the worst case when we only have jars? A simple and intuitive approach is to mix the binary search and linear search. For an example, if we have jars, first use a binary search from buttop to top so that a upper bound can be found. Then a linear search can be executed in a limited range. This strategy can be extended to any . Just do the binary search until you have only one jar. But this simple approach is not exactly what we want. It only improve a constant factor compared with the linear search.

If we choose , magic happens. We can use the first to find the upper bound, then we use another  to find the highest safe rung. Also this approach can be extended when . Is this the optimistic way to solve this problem? Let’s find a proof later.

The computable functions are countable since each computable function has its correspondence Turing machine, which has its finite description. The finite description can have 1-1 map to strings, then finally correspond to the nature numbers.

But the set of all functions is uncountable. We can just choose a subset - Boolean functions. The Boolean functions are defined as . We construct a 1-1 map of Boolean function to real numbers in [0, 1), which is sure uncountable. For each in [0, 1), we have a Boolean function  such that is the th bit of binary representation of .

if is a power of 2, prove this assertion:

Proposition 1

If we use some algebra technique, the proof must be boring and intristinc. I remember the standard method to proof the is to use induction on . But here we have a very cool combinatorial method. Consider the following problem:

Proposition 2

Consider a  chessboard, where is a power of 2. Prove that all the squares of the chessboard except one can be covered with 3 L-shaped tiles.

It is obivous that Proposition 1 directly follows Proposition 2 and proving Proposition 2 should be more interesting than just manipulating algebra.