nhaliday + communication-complexity   16

Correlated Equilibria in Game Theory | Azimuth
Given this, it’s not surprising that Nash equilibria can be hard to find. Last September a paper came out making this precise, in a strong way:

• Yakov Babichenko and Aviad Rubinstein, Communication complexity of approximate Nash equilibria.

The authors show there’s no guaranteed method for players to find even an approximate Nash equilibrium unless they tell each other almost everything about their preferences. This makes finding the Nash equilibrium prohibitively difficult to find when there are lots of players… in general. There are particular games where it’s not difficult, and that makes these games important: for example, if you’re trying to run a government well. (A laughable notion these days, but still one can hope.)

Klarreich’s article in Quanta gives a nice readable account of this work and also a more practical alternative to the concept of Nash equilibrium. It’s called a ‘correlated equilibrium’, and it was invented by the mathematician Robert Aumann in 1974. You can see an attempt to define it here:
baez  org:bleg  nibble  mathtariat  commentary  summary  news  org:mag  org:sci  popsci  equilibrium  GT-101  game-theory  acm  conceptual-vocab  concept  definition  thinking  signaling  coordination  tcs  complexity  communication-complexity  lower-bounds  no-go  liner-notes  big-surf  papers  research  algorithmic-econ  volo-avolo 
july 2017 by nhaliday
6.896: Essential Coding Theory
- probabilistic method and Chernoff bound for Shannon coding
- probabilistic method for asymptotically good Hamming codes (Gilbert coding)
- sparsity used for LDPC codes
mit  course  yoga  tcs  complexity  coding-theory  math.AG  fields  polynomials  pigeonhole-markov  linear-algebra  probabilistic-method  lecture-notes  bits  sparsity  concentration-of-measure  linear-programming  linearity  expanders  hamming  pseudorandomness  crypto  rigorous-crypto  communication-complexity  no-go  madhu-sudan  shannon  unit  p:**  quixotic 
february 2017 by nhaliday
Computational Complexity: Favorite Theorems: The Yao Principle
The Yao Principle applies when we don't consider the algorithmic complexity of the players. For example in communication complexity we have two players who each have a separate half of an input string and they want to compute some function of the input with the minimum amount of communication between them. The Yao principle states that the best probabilistic strategies for the players will achieve exactly the communication bounds as the best deterministic strategy over a worst-case distribution of inputs.

The Yao Principle plays a smaller role where we measure the running time of an algorithm since applying the Principle would require solving an extremely large linear program. But since so many of our bounds are in information-based models like communication and decision-tree complexity, the Yao Principle, though not particularly complicated, plays an important role in lower bounds in a large number of results in our field.
tcstariat  tcs  complexity  adversarial  rand-approx  algorithms  game-theory  yoga  levers  communication-complexity  random  lower-bounds  average-case  nibble  org:bleg 
january 2017 by nhaliday

bundles : academetcs

related tags

acm  adversarial  algebraic-complexity  algorithmic-econ  algorithms  analogy  approximation  average-case  baez  big-surf  binomial  bits  boaz-barak  books  circuits  coding-theory  commentary  communication-complexity  complexity  compressed-sensing  concentration-of-measure  concept  conceptual-vocab  coordination  counting  course  crypto  curiosity  dana-moshkovitz  data-structures  definition  draft  dropbox  elegance  entropy-like  equilibrium  expanders  expert  expert-experience  fields  game-theory  graphs  GT-101  hamming  hardness  harvard  hashing  hierarchy  homepage  information-theory  lecture-notes  levers  linear-algebra  linear-programming  linearity  liner-notes  list  lower-bounds  madhu-sudan  math.AG  math.GR  math.NT  mathtariat  metabuch  mihai  mit  motivation  naturality  news  nibble  no-go  norms  ocw  open-problems  org:bleg  org:edu  org:junk  org:mag  org:sci  overflow  p:*  p:**  p:someday  papers  pcp  pdf  people  pigeonhole-markov  polynomials  popsci  princeton  probabilistic-method  problem-solving  prof  pseudorandomness  q-n-a  questions  quixotic  rand-approx  rand-complexity  random  reflection  relativization  research  research-program  rigorous-crypto  salil-vadhan  shannon  signaling  space-complexity  sparsity  spectral  stanford  sublinear  summary  synthesis  tcs  tcstariat  thinking  tidbits  tim-roughgarden  topics  UGC  unit  valiant  volo-avolo  washington  wigderson  wiki  yoga  👳 

Copy this bookmark: