Feeds:
Posts

## Communication Complexity of Mixed-Nash Equilibria

In a previous post I discussed the communication complexity of reaching a pure Nash equilibrium.  The communication complexity model aims to capture the basic information transfer bottleneck between the different players in a games, abstracting away the question of incentives, and focusing on the need of communicating the different preferences (utilities) of the players that are assumed to initially be privately known.  The previous post introduced the  model of communication complexity and applied it to the question of finding a pure Nash equilibrium (if it exists).  The bottom line was that, in the general case, essentially all information about the utilities must be transferred and no “shortcuts” are possible.  In a multi-player game this amount of information is exponential in the number of players, implying that convergence to equilibrium, in general, is impractical, and special properties of the game must be used in order to reach equilibrium in reasonable time (one such property was demonstrated: dominance-solvable games).

This post discusses the issue of convergence to a mixed Nash equilibrium, as studied by Sergiu Hart and Yishay Mansour in How Long to Equilibrium? The Communication Complexity of Uncoupled Equilibrium Procedures.   The setting, as in my previous post, has each one of $n$ players holding his utility function $u_i : S_1 \times ... \times S_n \rightarrow \Re$, where each $S_j$ is the set of strategies of player $j$, and for ease of notation lets have $|S_j|=m$ for all $j$.  We will assume that all utilities are finitely represented, i.e. are rational numbers, say with $k$-bit numerator and denominator.  Can a mixed Nash equilibrium be found by communicating significantly less than $m^n \cdot k$ bits — the size of each utility function?  Maybe it can be done by communicating only a polynomial (in $n$, $m$, and $k$) bits?  This would be a necessary condition for efficient convergence of any  (uncoupled) dynamics between the players.

Before we look deeper into at this question, let us look at the similar problem of finding a correlated  equilibrium.  In this case it turns out that a polynomial amount of communication suffices and thus only a tiny fraction of the private information needs to be transferred. You can see a previous post of mine for background on correlated equilibrium.

### The Communication Complexity of Correlated Equilibrium

Let us recall that a correlated equilibrium is a probability distribution on the strategy profiles $p : S_1 \times ... \times S_n \rightarrow \Re$ that satisfies linear inequalities of the following form:  for every player $i$, and every two strategies of $i$, $s_i, s'_i$ : $\sum_{s_{-i}} p(s_i,s_{-i}) u_i(s_i,s_{-i}) \ge \sum_{s_{-i}} p(s_i,s_{-i}) u_i(s'_i,s_{-i})$, where the sum ranges over all strategy profiles $s_{-i}$ of the other players.  The interpretation is that $s_i$ is indeed a best-reply to the conditional distribution $p(s_i,\cdot)$ on $s_{-i}$.

[Edited on Oct 2nd: Albert Xin Jiang was kind enough to point out that the next paragraph is, well, wrong, so I'm striking it out.  In order to show that finding a correlated equilibrium can be done with low communication complexity, one must run the Ellipsoid algorithm on the dual LP (which has polynomial many variables) rather than on the primal (which has exponentially many variables).  How to do so effectively is shown in a paper by Papadimitriou and Roughgarden, and Hart and Mansour show that the algorithm can be implemented with low communication.]

As being a correlated equilibrium is defined by a set of linear inequalities, we can find a correlated equilibrium using linear programming.  Let us see how the players can jointly run the Ellipsoid LP algorithm while keeping the amount of communication in check.  The Ellipsoid algorithm runs in time polynomial in $m$, $n$, and $k$ as long as it has access to a separation oracle.  Such an oracle must be able to answer queries of the following form: given an unfeasible point, in our case a candidate distribution $p$, it must find a constraint, in our case a player $i$ and strategies $s_i, s'_i$, where the corresponding inequality is violated by $p$.  The main point is that each of the inequalities can be checked by a single player since it depends only on a single utility function.  Thus to implement the separation oracle, each player must either report a violated constraint or a single bit specifying that all his constraints are satisfied — all together taking $O(n + \log m)$ bits of communication.  When the algorithm terminates — after a polynomial number of steps (polynomial in $n$, $m$, and $k$) — all players know the answer, which is a correlated equilibrium.   (Note that even though a correlated equilibrium is an exponential-sized object, it will turn out to have a polynomial-sized support.)

While this low-communication algorithm can not be viewed as natural dynamics that efficiently converge to a correlated equilibrium, it does point out that some dynamics that converge efficiently do exist.   The question of finding natural dynamics then gets more pressing and indeed it turns out that natural dynamics do exist as well: dynamics based on regret minimization (see my previous post.)

### Mixed-Nash Equilibria

Now, once we have what to aim for — a similarly low-communication way of reaching a mixed-Nash equilibrium — let us look at the problem carefully again.  First, we must recall that Nash equilibria may be irrational even if all utilities are rational, so a Nash equilibrium can not be “printed” as binary numbers in any finite time.  Still, in our communication complexity formulation this shouldn’t be a problem since any representation of the equilibrium is in principle acceptable as long as it is uniquely determined by the communication.  Closely related to this is the fact that the representation of a Nash equilibrium in an $n$-player game may require exponentially many bits of precision, even if the utilities themselves have only short descriptions.  As before, while the required precision itself is not a lower bound on the communication complexity, Hart and Mansour do show how to use this precision to obtain a lower bound.  Below I give a different, somewhat stronger proof.

Let us start with the following 2-player bi-strategy game, where $0 is an arbitrary parameter.

r, 0                0, r

0, 1-r            1-r, 0

It is easy to see that the only Nash equilibrium of this game has each player choosing his second strategy with probability exactly $r$ and his first with probability $1-r$.  This family of games suffices for giving a tight lower bound for the special case of two-player ($n=2$) bi-strategy ($m=2$) games.

Lemma: The communication complexity of finding a Nash equilibrium in two-player bi-strategy games, where all utilities are given by $k$-bit integers, is $\Theta(k)$.

The upper bound is trivial and the lower bound is implied by games of the previous form where $r$ ranges over all fractions of the form $r = x/2^k$, for integer $0 since each of these games has a different (unique) answer giving $2^k$ different such answers, which thus requires at least $k$ bits of communication just to get all possibilities.

The dependence of the communication complexity on $m$, the number of strategies of each player, is still unclear.  However, Hart and Mansour show that the dependence on the number of players, $n$, is exponential.  The basic idea is that with $n$ players we can get doubly-exponential  many different answers.  A clean way to show this is to “simulate” utilities of representation length $k=2^{\Theta(n)}$, and then invoke the previous bound.

Win-Lose Simulation Lemma: For every $n$-player game with utilities that are $k$-bit integers, there exists an $(n + 3\log k)$-player game, with the following properties:

• The new game is a win-lose game, i.e. all utilities are 0 or 1.
• Each of the first $n$ players has the same set of strategies as in the original game.  The utility of each of these players is fully determined (in an easy manner) by his utility in the original game.
• Each of the final $3 \log k$ players has 2 strategies.  The utilities of each of these are constants not depending on the original game at all.
• The Nash equilibria of the new game are in 1-1 correspondence with those of the original game: the mixed strategies of each of the first $n$ players are identical, while the strategies of the final $3\log k$ players are fixed constants independent of the game.

From this we immediately get our theorem.

Theorem: The communication complexity of finding a Nash equilibrium in $n$-player bi-strategy win-lose games is $2^{\Theta(n)}$.

The upper bound is trivial and the lower bound is implied by the lower bound on 2-player games with $k$-bit utilities via this reduction using $n=2+3\log k$ players.

### Proof of Win-Lose Simulation lemma

It remains to prove the simulation lemma.  We will do so in three steps: first construct a fixed game whose unique equilibrium has exponentially low probabilities, then use this game to simulate games with utilities that are all powers of two, and finally use these to simulate general games with integer utilities.

The first step of the reduction is the following construction:

Construction: for each $t$ there exist $(2t)$-player win-lose bi-strategy games such that the unique Nash equilibrium has, for each $1 \le i \le t$, players $2i-1$ and $2i$ choosing their first strategy with probability exactly $2^{-2^{i-1}}$.

Proof: for $t=1$, this is exactly “matching pennies”, i.e. the $2 \times 2$ game described above for $r=1/2$ (after scaling by a factor of 2).  Now for the induction step we start with $t-1$ pairs of players as promised by the induction hypothesis, and we keep these players’ utilities completely independent of the soon to be introduced 2 new players, so we know that in every Nash equilibrium of the currently constructed $2t$-player game these will still mix exactly as stated by the fact above for $t-1$.  In particular the last pair of players in the $(2t-2)$-player game choose their first strategy with probability $2^{-2^{t-2}}$.  The point is that with these players in place, we can easily simulate the $2 \times 2$ game above for $r=2^{-2^{t-1}}$.  To simulate a “$r$ entry”, we define the utility as 1 when the last pair of players in the $(2t-2)$-player game play their first strategy (which happens with probability $2^{-2^{t-2}} \times 2^{-2^{t-2}} = 2^{-2^{t-1}} = r$) and 0 otherwise, while to define a $1-r$ entry we define the opposite.

Our next step is to simulate (in the sense of the lemma) games where all utilities are powers of two in the range $1, 2, 4 , ..., 2^k$, equivalently, after scaling, in the range $1, 1/2, 1/4, ..., 2^{-k}$.  This is done by adding to the original players $t=2\log k$ players as defined in the construction above.  We can now replace each utility of the original players of the form $2^{-x}$ where $x$‘s binary representation is $x = \sum_{i=1}^{t} x_i 2^{i-1}$ with a utility of 1 whenever, for every $i$ with $x_i=1$, new player $2i$ plays his first strategy,(and 0 otherwise).  This happens with probability $\Pi_{i|x_i=1} 2^{-2^{i-1}} = 2^{-\sum_{i |x_i=1} 2^{i-1}} = 2^{-x}$, as needed.

Our final step is simulating games with utilities that are general $k$-bit integers by games that have all their utilities powers of two, as in the previous step.  This is done by adding another $\log k$ bi-strategy players, paired into $\log k/2$ independent “matching pennies” games, and thus each of them always evenly mixes between his two strategies.  To simulate a utility of $y=\sum_{i=1}^k y_i 2^{i-1}$ in the original game, we give, in the new game, a utility of $y_i 2^{i-1}$ whenever the $\log k$ new players played a sequence of strategies which is the binary representation of $i$ (and 0 otherwise). The expected value is exactly $y/k$, completing the simulation (as the scaling by a factor of $k$ does not matter).

### What remains?

The previous lower bound leaves much to be desired: while it does give an exponential lower bound in the input parameters, this is done at the cost of having an exponentially long output.  If we also take the output length into account (in any representation) then the bound is no more than linear — trivial.  Indeed, in the formal description of the computational Nash equilibrium problem, one formally has an input parameter $\epsilon$ that specifies how close to an equilibrium do we demand the output to be, and the algorithm is allowed to run in time that is polynomial in $\log \epsilon$.  (See a previous post on the subtleties of this approximation parameter $\epsilon$.)  Taking this approach, the lower bound is trivial too as it is bounded from above by $\log\epsilon$.

Thus, the main open problem that remains is that of determining the communication complexity of finding a mixed-Nash equilibrium when the precision required at the output is only polynomial in the other parameters.

## SIEPR & Microsoft Conference On Internet Economics

The Stanford Institute for Economic and Policy Research, jointly with Microsoft, is holding a conference on Internet Economics on September 24-25.  Many papers are available on the web site.

## A rant on academic output

What is considered academic work?  I.e. what is society paying us (university professors) for?  What should be considered as criteria for academic promotion and hiring?

It seems to me that there has been a continuing narrowing in the way that the academic establishment is answering this question.  It is getting closer to being narrowly defined as  “international journal publications” (in CS, also conference publications).  The two other pillars of academic duty are losing their gravitas: teaching is often belittled in practice  (despite much lip service to the contrary) and academic administrative duties (department chairing, editorships) are loosing their prestige.  Other forms of publication (national journals, popular press, even academic books) are getting less credit.  (It used to be standard for Israeli economists to publish in Hebrew on the Israeli economy, but little academic credit is given for this anymore.) Founding commercial companies or consulting for them is frowned upon in some places, and slightly encouraged in others, but certainly not considered part of the academic work.    Having a wide disciplinary knowledge (or even being a Renaissance man) is not expected or rewarded.  Being involved with public policy, K12 eduction, public opinion, or politics is definitely not considered part of one’s academic mandate.

This is all not new.  Am just ranting here?  Maybe.  But what I don’t quite understand is why we, tenured professors, keep going in this direction. Regarding our own work, we can do whatever we want — we are tenured — why are we so “academic”?  Regarding others — it is us who sit in all these promotion, hiring, and tenure committees — why don’t we take the wider view more often?

The DoubleClick Ad Exchange is a real-time marketplace to buy and sell display advertising space. By establishing an open marketplace where prices are set in a real-time auction, the Ad Exchange enables display ads and ad space to be allocated much more efficiently and easily across the web. It’s just like a stock exchange, which enables stocks to be traded in an open way.

There are some existing competitors, but Google’s entry may be game-changing.  Lots of research problems beg themselves.

## New paper on “Goal Oriented Communication”

An intriguing paper titled “A Theory of Goal-Oriented Communication” by Oded Goldreich, Brendan Juba, and Madhu Sudan has recently been uploaded to the ECCC, expanding a line of work started by the last two authors here and here.  The basic issue studied is how is it possible to effectively communicate without agreeing on a language in advance.  The basic result obtained is that, as long as the parties can “sense” whether some progress is made toward their goals,  prior agreement about a language is not necessary and a “universal”  protocol exists.  My nerdier side cannot help but thinking about the application to communicating with an alien species (which I bet the authors did not mention on purpose.)

It is obviously hard to tell yet whether this is a beginning of a great new intellectual journey or just a blind alley but,  In any case, I suppose that this is the kind of work sought by the ICS conference.    Despite the game-theoretic-sounding notion of the goals of the communicating parties that underlines the model, conspicuously absent are notions of rationality.

## Fisher Model of Markets

Much of the recent theoretical computational work on market equilibrium uses the, so called, Fisher Model (see chapters 5 and 6 of the AGT book or talks and papers on Vijay Vazirani’s home page.)  The model is somewhat simpler than Arrow-Debreu markets in that one party, the seller, brings into the market all goods except for money, which is the only thing that the others bring.  This seemingly small variation seems to make handling it more tractable. In his ALGO invited talk, Vijay opined that Irving Fisher, the model’s father, is somewhat forgotten today probably due to his famous words just days before the stock market crash of 1929: “Stock prices have reached what looks like a permanently high plateau.” Vijay pointed out that Fisher’s comments just a little later are captured on youtube:

## WINE 2009 Accepted Papers

WINE 2009 will be held in Rome on December 14–18.  The lists of accepted papers have been published: regular papers and short papers, as well as tutorials and invited speakers.

## Report from Algo 2009

I just returned from ALGO 2009 in Copenhagen.
Algo is composed of ESA — the main European algorithms conference — co-located
with a few smaller workshops.  ALGO had about 200 participants mostly from Europe but from other places as well (As usual a bunch of Israelis and also
I met a significant number of
attendees from China: from Tsinghua and Fudan universities, and from Microsoft Reserach in Beijing.)  The acceptence rate for papers sumitted to ESA was about 25%.
The social program included a dinner in Tivoli garden and a (perfectly engineered) bike ride throug the streets of Copenhagen.
X and Y already blogged about ESA so I’ll just mention the AGT sessions (even though I arrived late and missed them):
<ul>
<li>Yossi Azar, Benjamin Birnbaum, Anna Karlin and Thach Nguyen. On Revenue Maximization in Second-Price Ad Auctions.
<li>Martin Hoefer and Alexander Skopalik. Altruism in Atomic Congestion Games.
<li>Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang and Jiajie Zhu. Bounded Budget Betweenness Centrality Game for Strategic Network Formations.
<li>Elliot Anshelevich and Bugra Caskurlu. Exact and Approximate Equilibria for Optimal Group Network Formation.
<li>George Christodoulou, Elias Koutsoupias and Paul Spirakis. On the performance of approximate equilibria in congestion games.
</ul>
Additionally, two invited talks were related to AGT: my own talk on Google’s auction for TV ads (paper, slides), and Vijay Vazirani’s talk
on combinatorial algorithms for market equilibrium and for the Nash bargaining solution.  Both of these problems (in some variant) can be described
by convex optimization programs that are surprisingly very similar to each other: the “market clearing conditions” are linear constraints and the optimization
goals are, respecitevly, of the form $\sum_i m_i\log v_i$ and $\sum_i \log (v_i - c_i)$.  While these can be solved in polynomial time by
general comvex programming, Vijay called for, and discovered, combinatorial algorithms that shed more light on the structure of these problem.
Vijay’s market equilibrium model was the continuous analog and inspiration of the discrete one that underlines the auction for TV ads that I presented, so
I was naturally quite interested.

I just returned from ALGO 2009 in Copenhagen.    AlGO is composed of ESA — the main European algorithms conference — co-located with a few smaller workshops.  ALGO had about 200 participants mostly from Europe but from other places as well (I met a significant number of  attendees from China: from Tsinghua and Fudan universities, and from Microsoft research in Beijing.)  The acceptance rate for papers submitted to ESA was about 25%. The social program included a dinner in Tivoli gardens and a (perfectly engineered) bike ride through the streets of Copenhagen, and the whole affair was quite enjoyable.

Others (here and here) have already blogged about ESA so I’ll just mention the AGT sessions (even though I arrived late and missed them):

1. Yossi Azar, Benjamin Birnbaum, Anna Karlin and Thach Nguyen. On Revenue Maximization in Second-Price Ad Auctions.
2. Mohammad Mahdian and Grant Wang. Clustering-Based Bidding Languages for Sponsored Search.
3. Martin Hoefer and Alexander Skopalik. Altruism in Atomic Congestion Games.
4. Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang and Jiajie Zhu. Bounded Budget Betweenness Centrality Game for Strategic Network Formations.
5. Elliot Anshelevich and Bugra Caskurlu. Exact and Approximate Equilibria for Optimal Group Network Formation.
6. George Christodoulou, Elias Koutsoupias and Paul Spirakis. On the performance of approximate equilibria in congestion games.

Additionally, two invited talks were related to AGT: my own talk on Google’s auction for TV ads (paper, slides), and Vijay Vazirani’s talk on combinatorial algorithms for market equilibrium and for the Nash bargaining solution.  Both of these problems (in some variant) can be described by convex optimization programs that are surprisingly very similar to each other: the “market clearing conditions” are linear constraints and the optimization goals are, respectively, of the form $\sum_i m_i\log v_i$ and $\sum_i \log (v_i - c_i)$.  While these can be solved in polynomial time by general convex programming, Vijay called for, and discovered, combinatorial algorithms that shed more light on the structure of these problem. Vijay’s market equilibrium model was the continuous analog and inspiration of the discrete one that underlines the auction for TV ads that I presented, so I was naturally quite interested.

## STOC 2010 CFP

The STOC 2010 Call for Papers is out.  Submission deadline is November 5th, 2009 and the conference will be held in Cambridge, Massachusetts, fromSunday June 6 to Tuesday June 8, 2010.

The most interesting part of the CFP is:

The extended abstract should be addressed insofar as possible to a broad spectrum of CS Theory researchers. Authors should clearly convey to such a reader the main new ideas in the paper. One suggested, but not required, way of achieving this is to include a short section containing either the equivalent of a brief oral presentation of the work, or a discussion of the conceptual contributions of the paper, or a sketch of the key ideas in the proof of the simplest non-trivial statement of the main result.

Authors should substantiate the principal claims in the paper. If necessary, some material may be placed in a clearly marked appendix that will be read at the discretion of the program committee. There are no format requirements regarding such an appendix. (Authors are encouraged to simply attach a copy of the full paper, if ready.)

## CS and Economics — different attitudes

An NSF-targeted workshop on Research Issues at the Interface of Computer Science and Economics has just taken place in Cornell, attended by many central people in the area (but not by me), including several bloggers that reported on it (Lance, Muthu a b c, and Rakesh). This is another one in a sequence of workshops where economists and computer scientists meet to exchange ideas, results, and points of view.

A fruitful issue in the interface is taking account of computational complexity in economic and game-theoretic settings.  This has received much attention (e.g. in Rakesh’s post), and while it certainly is a key issue, I disagree that this is the core issue in this interface.  I believe that even more interesting is the combination and interplay of the different research attitudes of the two communities, a combination that is needed for studying the future economic issues brought by technological advances.

I believe that much of the difference in attitudes comes from economists’ emphasis on “what is” vs. CS emphasis on “what can be”.   Even theoretical economists try to talk about the real world, their examples and motivations are real existing industries and situations, and their philosophical point of view is mostly scientific: understand the world.  Computer Scientists prepare for the future, knowing that most of what exists today will soon become obsolete.  Our motivations and examples often assume a few more years of the steady march of Moore’s law.  These attitudes are the outcome of different situations of these disciplines: economic work that did not correspond with reality was eventually ignored, while CS work that was not forward looking became obsolete.  This distinction is obviously somewhat simplistic and exaggerated, but this does  seem like the general spirit of things.  Indeed the sub-area of economics that was most natural for computer scientists to “blend with” was Mechanism Design which unusually  in economics has an engineering spirit of  “what can be” .  I feel that many of the technical and  cultural differences between the communities have their roots with this difference.

Economists and Game-theorists take their models much more seriously and literally than computer scientists do.  While an economists’ model should correspond to some real phenomena, a CS model should correspond to a host of unknown future situations.  A CS reader is more willing to take the leap of imagination between the model as stated and various unknown future scenarios.  In compensation, the CS reader expects a take-away that transcends the model, often found in the form of mathematical depth.  An economics reader is much more skeptical of a model and demands specific justification, but on the other hand, mathematical depth is not seen as a feature but rather as a nuisance to be buried in the appendix.

The Bayesian point of view of economists vs. the worst-case point of view of computer scientists have a similar root, I think.  In a situation that already exists, there is obviously some empirical distribution, and it is hard to argue against taking it into account.  In a situation that doesn’t exist, there is yet no empirical distribution, so in order to prepare for it we need to either theoretically guess the future distribution, or prepare for worst case.  CS has learned that the first option does not work well.

There are other high-level differences I can think of, but let me give two specific ones.  How does one interpret a 4/3-approximation result in a network setting?  While an economist will certainly consider a loss of 33% to be a negative result (as it would be in almost an existing scenario), a computer scientist will view it as giving up a few months of technological advance — a negligible cost compared to the other difficulties facing the adoption of anything new.

In Mechanism Design, computer scientist focus on the simplest model (dominant-strategy implementation; independent private values; risk-neutrality) and spend most of their efforts exploring the limits of the model, inventing new mechanisms, or proving impossibility, for various  scenarios which are obviously unrealistic today.  Economic theory, on the other hand, has moved on to more sophisticated models (risk aversion, dependent values, etc.), and is not as concerned with the limits of the model — until a real application emerges, like spectrum auctions.

I think that the future exploration of the interface of economics and CS should not only combine notions and results from both fields, but also combine attitudes and points of view.  The latter is even more difficult to do well.