10:00am - 12:00pmTropical and combinatorial methods in economics
Chair(s): Ngoc Mai Tran (The University of Texas at Austin, United States of America)
Over the past ten years, combinatorial auctions and mechanism designs have posed interesting challenges at the intersection of tropical geometry, matroid theory, discrete convex analysis and integer programming. This minisymposium features experts who work at this intersection discussing the latest developments and potential approaches to major conjectures concerning valuated matroids (also known as gross substitutes or $M^natural$-concave functions).
(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)
On the Construction of Substitutes
Eric Balkanski
Harvard
Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many different characterizations are known for this class, but providing a constructive description remains a major open problem. The construction problem asks how to construct all gross substitutes from a class of simpler functions using a set of operations. Since gross substitutes are a natural generalization of matroids to real-valued functions, matroid rank functions form a desirable such class of simpler functions.
Shioura proved that a rich class of gross substitutes can be expressed as sums of matroid rank functions, but it is open whether all gross substitutes can be constructed this way. Our main result is a negative answer showing that some gross substitutes cannot be expressed as positive linear combinations of matroid rank functions. En route, we provide necessary and sufficient conditions for the sum to preserve substitutability, uncover a new operation preserving substitutability and fully describe all substitutes with at most 4 items.
Joint work with Renato Paes Leme.
Connection Between Discrete Convex Analysis and Auction Theory
Akiyoshi Shioura
Tokyo Institute of Technology
Discrete convex analysis is a theory of discrete convexity in combinatorial optimization. In this talk we explain the connection between discrete convex analysis and auctions with multiple differentiated items. In particular, we show that computation of an equilibrium price vector can be reduced to the minimization of an L-convex function, and the existing iterative auction algorithms can be regarded as specialized implementation of the algorithms for L-convex function minimization.
Transversal valuated matroids
Alex Fink
Queen Mary University of London
As every first course in linear algebra tells us, there are a great number of ways to describe a linear subspace of K^n when K is a field. When K is the tropical semiring, many of these cease to agree, but tropical geometers have a consensus as to which of them give the correct notion of tropical linear subspace (one that does is Plücker vectors). My subject will be one of the "wrong" descriptions, namely row spaces of matrices, which give a subset of the tropical linear spaces. We obtain tropical analogues of results from the '70s on presentations of transversal matroids. Some of this work is joint with Felipe Rincón; the rest is joint with Jorge Alberto Olarte.
