Hausdorff School: Economics and Tropical Geometry

Monday, May 9

09:00 Registration
09:30 - 10:30 Michael Joswig: Tropical Hypersurfaces
10:30 - 11:00 Coffee break
11:00 - 12:00 Elizabeth Baldwin: Tropical Hypersurfaces in Economics, and the Unimodularity Theorem
12:00 - 14:00 Lunch break
14:00 - 15:00 Kazuo Murota: Discrete Convex Analysis I: Concepts of discrete convex functions
15:00 - 15:30 Coffee break
15:30 - 17:00 Polymake Interactive Session, bring your laptop recommended.

Tuesday, May 10

09:30 - 10:30 Kazuo Murota: Discrete Convex Analysis II: Properties of discrete convex functions
10:30 - 11:00 Coffee break and Group Photo
11:00 - 12:00 Michael Joswig: Tropical Convexity
12:00 - 14:00 Lunch break
14:00 - 15:00 John Weymark: A geometric approach to dominant strategy implementation
15:00 - 15:30 Coffee break
15:30 - 17:00 Problem Session

Wednesday, May 11

09:30 - 10:30 Michael Joswig: Tropical Linear Programming
10:30 - 11:00 Coffee break
11:00 - 12:00 Elizabeth Baldwin: The Extended Product-Mix Auction
12:00 - 14:00 Lunch break
14:00 - 16:00 Excursion

Thursday, May 12

09:30 - 10:30 Yoshinori Shiozawa: Some New Topics in International Trade Theory
10:30 - 11:00 Coffee break
11:00 - 12:00 Kazuo Murota: Discrete Convex Analysis III: Algorithms for discrete convex functions
12:00 - 14:00 Lunch break
14:00 - 15:00 Problem Session
15:00 - 15:30 Coffee break
15:30 - 17:00 Problem Session

Friday, May 13

09:30 - 10:30 Diane Maclagan: Valuated matroids and tropical algebra
10:30 - 11:00 Coffee break
11:00 - 12:00 Elizabeth Baldwin: Tropical Intersections, and applying the Tropical Bezout-Bernstein Theorem in Economics
12:00 - 14:00 Lunch break
14:00 - 16:00 Discussions

Abstracts

Elizabeth Baldwin:Tropical Hypersurfaces in Economics, and the Unimodularity Theorem (work joint with Paul Klemperer)

We study how an agent's demand depends on prices, for related but different indivisible goods. The set of prices at which demand changes forms a tropical hypersurface. Simple geometric properties translate directly to economic properties, providing a new taxonomy for agents' valuations. Thus we classify valuations into "demand types". The unimodularity theorem gives a necessary and sufficient condition for existence of competitive equilibrium. This generalises existing results as well as opening up new and very different possibilities. The result is applicable to both auction design and matching.

Elizabeth Baldwin: The Extended Product-Mix Auction (work joint with Paul Klemperer and Paul Goldberg)

The Product-Mix Auction was developed in response to the financial crisis, to allow simultaneous sales of different, closely related, financial commodities. Our geometric techniques allow us represent all "strong substitute" or "M-natural concave" valuations in a parsimonious form, and in ongoing work we are developing efficient algorithms to find equilibrium for such cases.

Elizabeth Baldwin: Tropical Intersections, and applying the Tropical Bezout-Bernstein Theorem in Economics (work joint with Paul Klemperer)

Even when equilibrium cannot be guaranteed via the "demand type", our techniques allow analysis of specific sets of individual valuations. Equilibrium existence is closely related to the nature, or "multiplicity", of stable intersections between tropical hypersurfaces. Moreover, these multiplicities are important for counting certain vertices in these intersections. We thus derive a very different means to check for equilibrium.

Michael Joswig: Tropical Hypersurfaces

The tropical semiring is the triplet $\mathbb{T} = \mathbb{R} \cup ... $. Evaluating a tropical multivariate polynomial leads to a piecewise linear function from R^d to R, and the domain of non-linearity is a tropical hypersurface. It is a basic fact that the same objects can also be described in terms of classical algebraic hypersurfaces over fields of Puiseux series. The purpose of this lecture is to show how these notions are related to classical concepts in polyhedral geometry and linear optimization.

Michael Joswig: Tropical Convexity

Finitely generated semimodules of T^dhave a very strong combinatorial flavor which borrows from polyhedral geometry (as they can be explained via tropical hypersurfaces which correspond to products of linear forms). This leads to the study of tropical point configurations, tropical polytopes and related polyhedral subdivisions of R^d. This topic is closely linked to graph algorithms known in combinatorial optimization and also to the braid arrangements.

Michael Joswig: Tropical Linear Programming

Tropicalizing classical linear programs leads to tropical linear programs. These are interesting since they are related to deep open problems in computational complexity. For instance, to decide the feasibility of a tropical linear program is known to be in the intersection of the complexity classes P and NP, but there is no polynomial time algorithm known. We will present a new result about the interior point method for solving classical linear programs; this is obtained through tropical linear programming.

Diane Maclagan: Valuated matroids and tropical algebra

In this talk I will highlight the role that valuated matroids play in tropical geometry. I will focus in particular on the algebraic side, whether they give extra structure to the semiring of tropical polynomials. The algebraic geometry motivation for this comes from work with Felipe Rincon on tropical schemes.

Kazuo Murota: Discrete Convex Analysis I: Concepts of discrete convex functions

Discrete convex analysis is a theory that aims at a discrete analogue of convex analysis for nonlinear discrete optimization.

fundamental classes of discrete convex functions are introduced, including submodular functions, integrally convex functions, M-convex functions and L-convex functions. Emphasis is put on the connection between M-natural convexity and gross substitute property, as well as the relation between submodularity and convexity/concavity.

Kazuo Murota: Discrete Convex Analysis II: Properties of discrete convex functions

In the second lecture, fundamental properties of discrete convex functions are explained, including:
(i) Operations such as addition, scaling, convolution and transformation by networks.
(ii) Conjugacy relation between L-convexity and M-convexity under Legendre transformation, along with its implication in auction theory.
(iii) Duality theorems such as separation theorem and Fenchel-type minimax theorem.

Kazuo Murota: Discrete Convex Analysis III: Algorithms for discrete convex functions

In the third lecture, algorithmic aspects of minimization of discrete convex functions are discussed, including:
(i) Local optimality criterion for global minimality, which varies with types of discrete convexity.
(ii) Descent algorithms for M-convex and L-convex functions.
(iii) Proximity property under scaling, which often leads to efficient descent algorithms.
(iv) M-convex intersection algorithm for minimizing the sum of two M-convex functions, which is also used to compute the convolution of M-convex functions.

Yoshinori Shiozawa: Some New Topics in International Trade Theory

International trade has been one of the major subjects of economics since the mercantilist era. However, it was not known until 2010 that the Ricardian trade theory is in fact a theory of subtropical convex geometry. The epithet “subtropical” stands for tropical semi-ring with maximization and ordinary multiplication over positive real numbers. The lecture is composed of three parts: (1) a brief introduction to Ricardian trade economy, (2) why subtropical algebra is a good description of Ricardian trade economy, and (3) some open questions in this theory. Basic text is my paper: Subtropical Convex Geometry as the Ricardian Theory of International Trade (uploaded in ResearchGate).

John A. Weymark: A geometric approach to dominant strategy implementation

The objective is to chose one alternative from a finite set of alternatives Abased on the values that the individuals in the set N assign to them. These values are private information, so incentives must be provided for individuals to reveal this information. The type t^i \in T^i of individual i \in N is a vector v^i \in \mathbb{R}^{|A|} whose j\/th component is the value assigned to the j\/th alternative. Let T = \prod_{i \in N} T^i. A mechanism is a function g \colon T \to A that specifies what is chosen as a function of the reported types. A payment function P \colon T \to \mathbb{R}^n specifies what each person pays as a function of the reported types. Individual i\/'s utility when t = (t^1, \ldots, t^n) is reported is v^i(g(t)|t^i) - P_i(t). The function g is dominant strategy implementable on the domain T if there is a payment function P such that each individual i has an incentive to truthfully report his type whatever it is. The valuation type space is partitioned into cells of the form g^{-1}(a) for a \in A. When g is dominant strategy implementable, this partition can be described in terms of the polyhedral geometry of tropical hypersurfaces. If T is a convex product set, using this geometry, simple necessary and sufficient conditions for g to be dominant strategy implementable can be obtained in terms of the sums of edge weights of cycles in a directed graph defined from the valuations.