Rumors and Playing Games

A rumor from FOCS on approximate Nash Equilibrium is partially true

Paul Spirakis is a senior researcher who has made many important contributions to theory. He has hundreds of publications that cover many areas of theory. What is so impressive about Paul is that he has been able to blend theory and practice in a very fruitful way. This is a pretty unique skill that few have.

Today I want to talk about a new result of his on finding approximate Nash Equilibrium for non-zero sum games.

The coolest rumor I heard at this year’s FOCS was that “someone” had proved a sub-exponential bound on the running time of an algorithm for approximate Nash Equilibrium. This was quite exciting and it is what I refer to in my discussion of Theory Day. I eventually tracked the rumor down and discovered the source was the pretty paper that I plan to discuss today. The paper does not quite have such a result, but definitely makes an important step in our understanding of games.

The rumor that I heard at FOCS turned out to be wrong. Oh well. That’s the nature of rumors: by definition a rumor is not always true; otherwise, it would not be a rumor. At least this rumor was partially true.

Years ago, in 1969, there was a great rumor that started right after Steve Cook proved his famous theorem that characterizes polynomial time. He proved:

Theorem: The following three conditions are equivalent for any language :

1. is accepted by some deterministic auxiliary pushdown machine with logspace storage.
2. is accepted by some non-deterministic auxiliary pushdown machine with logspace storage.
3. is in P.

This is a beautiful result, which in my opinion was not expected. An auxiliary pushdown automata with auxiliary logspace storage is a machine that can read the input two-ways, and store information on a regular Turing tape of length at most . In addition, the machine has a pushdown, which it can use also to store information.

Note, a pushdown only allows operations on the top: the top symbol can be read, a symbol can be pushed onto the pushdown, or a symbol can be removed from the top. That’s all. Symbols below the top symbol cannot be read without popping off the top symbol.

Almost immediately someone well known, I will call them X, claimed that Steve’s result could be extended “slightly.” In particular, X claimed that the same theorem could be proved with pushdown replaced by stack. A stack is not the same as a pushdown. It has one important extra property: a stack allows the reading of the symbols in the pushdown without popping off any symbols. A stack only allows this in a read-only mode. That is when inside the pushdown, symbols can only be read. Symbols can be changed at the top as usual.

We could not figure out how the new proof went, and worse X went on a camping vacation. So he was unreachable—this is well before cell phones. The theory community was all abuzz, since it was believed that an auxiliary stack machine could accept more than P. It would have been a great result. Clearly, X did not see this, or he would have been more circumspect about his claim.

Finally, X returned and was asked how his proof went. He explained the proof, and it was immediately clear that the proof did not work. He had forgotten one small point: a stack machine could run for more than exponential time unlike a pushdown machine. [I fixed an error here.] He had to retract his claim. Sometimes rumors are false.

Now let’s turn to non-zero sum games and a new approach to getting approximate Nash Equilibrium.

Win-Lose Games

The paper of Haralampos Tsaknakis, and Paul Spirakis is mostly a new approach to finding approximate Nash Equilibrium (NE) for general two player game through a reduction to a restricted class of games.

This class is special, but still quite interesting. It is the class of symmetric win-lose games. Such a game has one by - matrix : the matrix is the payoff for the row player and is the payoff for the column player.

The restriction to - values is why it is called a “win-lose” game, and the fact that one player uses the transpose of the other player’s matrix is why it is called symmetric. Finding a Nash Equilibrium in even win-lose games is as hard as the general case thanks to the beautiful result of Tim Abbott, Daniel Kane, and Paul Valiant.

Their proof is quite clever. As someone who has worked a bit on games, I was impressed that they could prove this result. In many complexity situations the - case is universal; however, proving that for games is not so easy. My intuition was that this, while probably true, would be very hard to prove.

Approximate Solutions

Since the problem of finding exact Nash Equilibrium for even win-lose games is as hard as solving the general case, it is natural to look for approximate NE’s. This is exactly what Haralampos and Paul do in their paper. They compare their new result with a result of Evangelos Markakis, Aranyak Mehta, and myself, which we proved in a earlier paper:

Theorem: For any there is an algorithm that finds an approximate Nash equilibrium for a symmetric win-lose game of size , in running time bounded by where .

The main result of Paul’s paper is:

Theorem: For any there is an algorithm that finds an approximate Nash equilibrium for a symmetric win-lose game of size , in running time bounded by where . The value of is equal to:

where are the eigenvalues of the graph induced by the game matrix.

This result is neat, in my opinion, since it addresses the barrier discovered by Constantinos Daskalakis and Christos Papadimitriou in their paper titled “On oblivious PTAS’s for Nash Equilibrium.” Constantinos and Christos show essentially that to get good approximations for NE’s, one must look at the structure of the payoff matrices: it is not enough to just examine the strategies as we did in our result.

Sparse Games

I am currently running an open problem seminar and we discussed Paul’s paper in a recent class. We noticed first that the value of in his theorem could be changed from

to

This follows since the sum of eigenvalues is , so the new measure is exactly twice the old, and this will have no effect on the results—all can be swept under the constant in the big-O notation.

Then, we considered sparse games: games where the induced graph has edges. For such games the value of the critical parameter is bounded by . The proof of this is quite simple:

where is the degree of the vertex. This last quantity is easily seen to be at most if the graph is sparse.

Based on these simple insights my students Atish Das Sarma, Subrahmanyam Kalyanasundaram, and Shiva Kintali believe that they can prove the following theorem:

“Theorem”: There is a PTAS for finding approximate NE’s for the class of symmetric win-lose games whose induced graph has bounded degree.

Unfortunately, the proof of this, while it looks like it will work, does not seem to be able handle sparse graphs. The reason is that a sparse graph could fail to have some technical properties that Paul’s theorem requires. We are hopeful that this can be fixed.

For random sparse symmetric win-lose games they do believe that it should be possible to prove the following theorem:

“Theorem”: There is a PTAS for finding approximate NE’s for the class of random sparse win-lose games that works with high probability.

There has already been some nice work on random games by Imre Bárány, Santosh Vempala and Adrian Vetta. Their result works for dense games where the values are Gaussian, while we are looking at sparse games with - values.

Open Problems

The major open problem is: is there an algorithm that runs in time for any non-zero sum game and finds an approximate Nash equilibrium? Can one even prove this for a special class of games?

On Mathematical Diseases

Mathematical diseases: symptoms and examples

Underwood Dudley is a number theorist, who is perhaps best known for his popular books on mathematics. The most famous one is A Budget of Trisections, which studies the many failed attempts at the ancient problem of trisecting an angle with only a ruler and a compass. This problem is impossible, yet that has not stopped some people from working day and night looking for a solution. Trying to find such a solution is an obsession for some; it’s almost like they have a malady that forces them to work on the problem.

Today I plan on talking about other mathematical obsessions. They are like diseases that affect some, and make them feel they have to work on certain mathematical problems. Perhaps P=NP is one?

The Iceberg Effect in Theory Research

The iceberg effect in research: how theorems can be lost

Fred is my favorite name, when I need a “random” name. You might have also noticed that the picture is not even a picture of a person—it’s an iceberg. I will explain why in a moment.

Usually I talk about real people, but today I thought I would use phony names to protect the innocent—or at least protect my friends.

I plan to talk about an issue that comes up in research:

Is the fact X a new result? Or is it a known result?

Highlights of FOCS Theory Day

A summary of a great day of talks before FOCS at Theory Day

Dick Karp was the leadoff speaker this Saturday at the FOCS Theory Day
in Atlanta. He was followed by Mihalis Yannakakis, Noga Alon, and Manny Blum. Sounds to me like a lineup for a baseball team that is in the World Series. I can almost hear an announcer saying:

Now batting cleanup, Mannnnny Blummmmm.

And the crowd goes wild.

Today I thought I would write a summary of what Dick and the others said Saturday. The talks were webcast, but perhaps not all of you watched them. In any event I will add some additional comments that I hope you enjoy.

Helping Wall Street Cheat With Theory

How to create “bad” derivatives that cannot be detected

Sanjeev Arora is the one of the most creative theorists in the world. He helped create the concept of Probabilistically Checkable Proofs along with Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, and Mario Szegedy. On his own he found a wonderful approximation algorithm for the Euclidean TSP, and has done many other terrific things. I was at Princeton when we hired him, and it was clear back then that he was special.

Today I had planned to talk about some of the papers of FOCS 2009, but will instead talk about a new paper of Arora with Boaz Barak, Markus Brunnermeier, and Rong Ge (ABBG) on finance. I really like their paper, and it seems to me to be one of those seminal papers that could launch a whole subfield.

Happy Fiftieth Birthday FOCS

A look back at some the early days of the FOCS conference

Alvy Ray Smith is a famous researcher who has won many awards for his seminal work in computer graphics. He is a theorist also: he has had several papers published at FOCS, for example.

Today I thought, since FOCS’s anniversary is soon, that it would be fun to look back at the first conferences and see what researchers were doing. Below is a singing tribute to FOCS:

Multi-Party Protocols and FOCS 2009

Multi-party protocols, bounded width programs, concentration theorems, and FOCS 2009

Ashok Chandra is a famous theorist who has done seminal work in the many different areas. His early work was in program schema, an area that was central to theory in the 1970’s. Chandra then moved into other areas of theory and among other great things co-invented the notion of Turing Machine Alternation.

Later in his career, while still an active researcher, he began to manage research groups: first a small one at IBM Yorktown, then a much larger one at IBM Almaden, and later groups at other major companies including Microsoft. As a manager, one example of his leadership was the invention by his group at Almaden of that little trackpoint device that plays the role of a mouse. The trackpointer eventually appeared on the keyboards of IBM’s Thinkpad laptops—now called Lenovo laptops—a wonderful example of successful technology transfer.

Today I want to talk about mutli-party protocols, an area that Chandra helped create in the 1980’s. Then, I will connect this work with a new paper that is about to appear in FOCS in days. This is the FOCS and I am looking forward to attending it, even though I will not get any Delta miles for this one—it is in Atlanta.

Magical Results and P=NP

Which is more likely: intractable problems or magical results?

Martin Kruskal was a famous mathematician who won many awards for his work in diverse areas of applied mathematics. He is perhaps best known, among his peers, for his important joint work with Norman Zabusky; work which helped start the soliton revolution. He is also known among magicians, for a brilliant illusion that is called the “Kruskal Count.” See this memorial page about Kruskal for a list of his accomplishments.

Today I want to talk about some other magical aspects of mathematics. One of the great things about mathematics is that often there are results that seem to be “impossible.” Magical.

The Surprising Power of Rational Functions

Newman’s theorem on rational approximations and complexity theory

Donald Newman was not a theorist, but was a mathematician who worked on many topics during his career. One of his results is a lovely theorem that shows that the approximation of continuous functions by rational functions can be very different from the approximation by polynomials.

Today I want to talk about this famous theorem, and discuss some applications to theory. If you do not know this theorem you may enjoy seeing it. Even if you do know it, you may enjoy seeing some thoughts I have on a potential application of this theorem.

The World is Digital

One of the biggest insights of computer science is that the world is digital

Alan Kay is a brilliant computer scientist who has won the Turing Award, along with many other honors. He is famous for creating the Dynabook concept—the idea that became the laptop, and for creating many programming languages, such as Smalltalk.

Today I want to talk about one of the biggest results in all of Computer Science. No, it is not the Halting Problem, it is not the P=NP question, it is not that Linear Programming is in P, nor any of the many other beautiful results of theory. It is, in my opinion, the realization that the world is digital (WID).