Events

Some issues on algorithmic game theory

John Realpe

Game theory aims to model situations in which multiple participants interact or affect each other’s outcomes. A standard approach is to describe such situations as a single multi-player game and find an equilibrium strategy profile for it. However, not only most algorithms for finding equilibria are computationally expensive, but also the description complexity of N-person games is exponential in N. This calls for more succinct representations that exploit structure in specific classes of games. Two proposals of interest are known as graphical and potential games. The former assumes that payoffs of each player are determined by the actions of only a small subpopulation. In the latter the payoffs depend only on the number of players that are playing a particular strategy and not on their identity. In this talk, a rough review on some aspects of this subject shall be presented.

References:
[1] M. Kearns, M. Littman, and S. Singh. Graphical models for game theory. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pages 253–260, 2001.
[2] Ortiz, L. E., & Kearns, M. (2003). Nash propagation for loopy graphical games. In Advances in Neural Information Processing Systems 15, Vol. 1, pp. 793–800.
[3] Vöcking, B. 2006. Congestion games: Optimization in competition. In Proceedings of the 2nd Algorithms and Complexity in Durham Workshop, H. Broersma, S. Dantchev, M. Johnson, and S. Szeider, Eds. Kings College Publications, London, 9-20. .

Pseudocodewords of regular LDPC: a tiny tutorial, some results and ideas for further analysis

Chiara Ravazzi

Low-density parity-check (LDPC) codes are a family of highly efficient codes. It is well known that for these codes the belief propagation algorithm can be fruitfully used. The low complexity of the BP algorithm comes from the fact that it operates locally on a Tanner graph associated to the code. However, the algorithm cannot distinguish if it is acting on the graph itself or on some finite unramified cover of the graph [1]. This leads to introduce the notion of pseudo-codewords and to consider the minimum pseudo-weight as a measure of goodness of the code representation [1,2]. We will discuss some deterministic bounds [3, 4] on the minimum pseudo-weight for regular LDPC codes with some proposals for new approaches to study the minimum pseudo-weight distribution of an ensemble of regular LDPC through some techniques coming from the analysis of non binary codes [5].

References:
[1] P.O. Vontobel and R. Koetter, <80><9C>Graph-cover decoding and finite-length analysis of message-passingiterative decoding of LDPC codes<80><9D>, submitted to IEEE Trans. on Inform. Theory.
[2] J. Feldman, M.J. Wainwright, and D.R. Karger, <80><9C>Using linear programming to decode binary linear codes<80><9D>, IEEE Trans. on Inform. Theory, vol. IT-51, no. 3, pp. 954-972, Mar. 2005.
[3] P.O. Vontobel and R. Koetter, <80><9C>Lower bounds on the minimum pseudo-weight of linear codes<80><9D>, Proc. IEEE Intern. Symp. Inform. Theory, Chicago, IL, USA, p. 70, June 27 - July 2, 2004.
[4] C. A. Kelley D. Sridhara, <80><9C>Pseudocodewords of Tanner Graphs<80><9D>, submitted to IEEE Trans.on Inform. Theory.
[5] G. Como, F. Fagnani, <80><9C>Average spectra and minimum distances of low density parity check codes over cyclic groups<80><9D>, SIAM J. on Discrete Mathematics, 23, pp. 19-53, 2008.

Inverse Ising Problems (II)

Mauro Cirio

Given some partial information about a system we like to reconstruct the interaction pattern of its elements. These elements can be neurons in a neural network, genes in a cell, pixels in an image or computers in the Internet. In the simplest scenario we assume that elements take only two states and interact pairwise. In this talk I will introduce some methods that people use to deal with this problem.

References:
[1] William Bialek et. al, Faster solutions of the inverse pairwise Ising problem, 2007.
[2] M. Mezard and T. Mora, Constraint satisfaction problems and neural networks: a statistical physics perspective, 2008. .

Inverse Ising Problems (I)

Abolfazl Ramezanpour

Given some partial information about a system we like to reconstruct the interaction pattern of its elements. These elements can be neurons in a neural network, genes in a cell, pixels in an image or computers in the Internet. In the simplest scenario we assume that elements take only two states and interact pairwise. In this talk I will introduce some methods that people use to deal with this problem.

References:
[1] William Bialek et. al, Faster solutions of the inverse pairwise Ising problem, 2007.
[2] M. Mezard and T. Mora, Constraint satisfaction problems and neural networks: a statistical physics perspective, 2008.

On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations

Serena Bradde

The cavity method is a well established technique for solving classical spin models on sparse random graphs (mean-field models with finite connectivity). Laumann, Scardicchio and Sondhi [arXiv:0706.4391] proposed recently an extension of this method to quantum spin-1/2 models in a transverse field, using a discretized Suzuki-Trotter imaginary time formalism. Here we show how to take analytically the continuous imaginary time limit. Our main technical contribution is an explicit procedure to generate the spin trajectories in a path integral representation of the imaginary time dynamics. As a side result we also show how this procedure can be used in simple heat-bath like Monte Carlo simulations of generic quantum spin models. The replica symmetric continuous time quantum cavity method is formulated for a wide class of models, and applied as a simple example on the Bethe lattice ferromagnet in a transverse field. The results of the methods are confronted with various approximation schemes in this particular case. On this system we performed quantum Monte Carlo simulations that confirm the exactness of the cavity method in the thermodynamic limit.

Reference:
[1] F. Krzakala, A. Rosso, G. Semerjian and F. Zamponi, (2008) .

Add to calendar
Syndicate content