Abstracts

Quantitative Gibbard-Satterthwaite theorems
Nathan Keller, Bar-Ilan University

Abstract: The well-known Gibbard-Satterthwaite theorem in Social Choice theory asserts that any election with at least three alternatives which is not a dictatorship can be manipulated. That is, there always exist situations in which some voter will "gain" from voting for another alternative instead of his preferred one. While the theorem shows that only a dictatorship is perfectly immune to manipulations, one may ask whether there exist election rules in which manipulation is possible so rarely that it can be practically neglected.

In this talk, we answer this question on the negative for three alternatives. Specifically, we present a quantitative version of the Gibbard-Satterthwaite theorem: if an election on three alternatives is not very close to a dictatorship and the probability of each alternative to be elected is non-negligible, then even a random manipulation by a randomly chosen voter will succeed with a non-negligible probability.

Our proof uses the quantitative versions of Arrow's impossibility theorem (whose proof involves discrete harmonic analysis), and a new directed isoperimetric inequality, which we prove using the FKG correlation inequality.

In the talk, we will present a sketch of our proof, and report on further progress by several other researchers, which recently culminated in a quantitative Gibbard-Satterthwaite theorem for any number of alternatives obtained by Mossel and Racz. Time permitting, we will show the application of the results to the field of Algorithmic game theory.

Joint work with Ehud Friedgut, Gil Kalai, and Noam Nisan.

Back

Transitive sets in tournaments
Eli Berger, Haifa University

Abstract: A tournament is a directed graph where each two vertices are connected in exactly one direction. A set of vertices in a tournament is called transitive if it contains no directed triangle. If H is a fixed tournament, we explore the class of tournaments not containing H. We can characterise for which H, a graph not containing H has a linear size transitive set, and give some results related to the conjecture that for every H, a graph not containing H has a polynomial size transitive set.

This is joint work with Krzysztof Choromanski, Maria Chudnovsky, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour and Stéphan Thomassé.

Back

Large distance 'codes' in the unit ball of l_1
Alex Samorodnitsky, Hebrew University

Abstract: We consider the following question: How many points can there be in R^n, such that the l_1 norm of each point is at most 1, and the l_1 distance between any two distinct points is at least 2 - epsilon. It is not hard to construct many such points taking them to be normalized elements of an appropriate constant weight binary code. Here 'many' means

exp{c epsilon log 1/epsilon n}

This is optimal up to the value of the constant in the exponent. As observed recently by Lee and Moharrami, a matching upper bound follows from the known bound for the Euclidean space, due to Kabatiansky and Levenshtein (with a simpler proof by Alon), combined with the embedding, due to Kahane, of l_1 in the square of the Euclidean norm.

We give a direct combinatorial proof of the upper bound, which also shows that large l_1 'codes' are indeed 'similar' to constant-weight binary codes.

Back

Eigenvalues of the Adin-Roichman matrices
Gil Alon, Open University

Abstract: In the context of character formulas for the symmetric group, Ron Adin and Yuval Roichman have defined two families of matrices, (A_n) and (B_n). These matrices bear a resemblance to the Walsh-Hadamard matrices: both A_n and B_n are 2^n by 2^n matrices of integers, and they have a simple recursive definition. Adin and Roichman proved that these matrices are invertible, and conjectured what their eigenvalues are. We will present a proof to this conjecture. The proof uses combinatorial tools and objects such as the Mobius inversion formula and the Thue-Morse sequence.

Back

On the group of balanced Abelian group-valued labelings on graphs
Yonah Cherniavsky, Ariel University

Abstract: We discuss functions from the edges of an undirected graph to an Abelian group. Such functions, when the sum of their values along any cycle is zero, are called balanced. By a cycle we mean a closed path with no repeating edges. The set of all the balanced edge functions is a subgroup of the free Abelian group of all the edge functions. We describe the structure of this subgroup.

Next, we discuss functions from the vertices of an undirected graph to an Abelian group. We establish the necessary and the sufficient condition on a vertex function such that exist edge functions to the same Abelian group, for which the sum of the values of both functions along any cycle is zero. The initial and final vertex of a cycle is taken only as a one summand in that sum. The set of all the vertex functions which satisfies this condition is a subgroup of the free Abelian group of all the vertex functions. We find the structure of this subgroup.

Finally, we combine both of the above results to obtain the structure of the group of the balanced Abelian group labelings on undirected graphs.

This is joint work with V. E. Levit and A. Goldstein

Back