Tropical Geometry and Mechanism Design

I would like to give a (very) leisurely overview to some recent work that Ngoc Tran and I did. It applies Tropical Geometry to Mechanism Design in Economics. Since I would like to keep this accessible to both, mathematicians and economists, I will start with a minimal introduction to Mechanism Design, followed by the basics of Tropical Convex Geometry. If you are versed in either subject (or ideally both), just jump ahead. I will then discuss the basic intuition of the paper and hint at why the tropical approach is useful.

What is Mechanism Design about?

Mechanisms can serve as a game theoretic model of institutions. Let me start with a textbook example. Imagine a society that needs to decide whether to build a bridge (which also needs to be financed). The government could simply ask everybody how much having a bridge is worth to them. If the statements are high enough, then the bridge will be built. But here is the crux, the government will have to make agents pay something, and this payment might depend on what was said before. So there is potentially a strategic motive to lie …

This is what economists call a situation with incomplete information, that is, each player privately knows how much the bridge is worth to him, but the government doesn’t. However, to make an efficient decision and set payments the government needs to know.

In economic theory this is modeled more abstractly as a mechanism design problem. We want to decide on one of [m]:=\{1, \ldots m\} possible outcomes. Outcomes in the example above are either building a bridge or not. But they may be more complicated, such as trading probabilities in an auction (which is also a example of a mechanism). Each player, call him i \in [n], has a fixed true type t^i in some set T_i\in \mathbb{R}^m, which only he knows and is randomly determined prior to the game. Types measure the valuation (in monetary terms) for each of the outcomes. Think of the mechanism as a decision device or a central authority: players can send a message to the mechanism containing their valuation. The mechanism collects the statements (r_1, \ldots r_n) (which may be false) and decides on an outcome in [m] and a vector of payments (P_1, ..., P_n)\in \mathbb{R}^n.
Thus formally a mechanism is just a collection of function f:T_1\times \ldots \times T_n \to [m] and P_i(t_1, \ldots, t_n) \in \mathbb{R} for all i\in [n].

Note that we took the domain to be T_1\times \ldots \times T_n, that is, each player can only communicate one of his possible valuations, not some more elaborate message. As it turns out this is without loss in relevant cases (this is known as the Revelation Principle).

Players are self interested, they don’t care about telling the truth. Rather they will report whatever type is best for them. However, the institution can incentivize players to tell the truth by setting payments. In the example above payments could serve two purposes, financing the bridge and incentivizing players. We shall think only about the simple case in which payments serve the sole purpose of inducing truth-telling.

For any outcome j \in [m] player i \in [n] derives utility t^i_j\in \mathbb{R} for some true type t^i \in T_i. Recall that this is measured in monetary terms. If i reports s\in T_i, say, and the others report (t^1, ..., t^{i-1}, t^{i+1}, ..., t^n), the outcome would be f(t^1, ..., t^{i-1}, s, t^{i+1}, ... t^n)\in [m]. We now enter the world of game theory, players need to take into account what others say and will behave strategically. A particularly simple solution-concept for such situations that makes most such complicated considerations obsolete is what is called dominant strategy equilibria. The assumption imposed is very stringent, namely that players report a type that is best for them no matter what others say. But it is also appealing in this context since it reduces the amount of information the mechanism needs and is that very robust. In particular it makes the problem simple, since it allows us to focus on one player at a time. To this end fix a player i and vector of reports (t^1, ..., t^{i-1}, t^{i+1}, ..., t^n). Now let s\mapsto g(s)=f(t^1, ..., t^{i-1}, s, t^{i+1}, ..., t^n) be the outcome that announcement s of player i would entail and set p(s)=P_i(t^1, ..., t^{i-1}, s, t^{i+1}, ..., t^n). Then, the player will tell the truth to the mechanism whenever

t_{g(t)}-p(t) \geq t_{g(s)}-p(s)

for all t, s \in T_i and all i\in [n]. We call this the dominant strategy incentive constraints. If for a given function g there exists a P such that these inequalities hold, we say that g is truthfully implementable.

One of the basic problems is to find mechanisms under which players will tell the truth. Naturally there are many more questions economists are interested in, for example whether we can reach an economically efficient allocation or which mechanisms maximize profits? (In fact, profit maximization is something that drives a lot of the interest for designing auctions, ranging from the simple ones you face on eBay to the more elaborate ones governments run to allocate cellular phone frequencies).

What is Tropical Convex Geometry?

Again, let me start with a familiar example from classical convexity. To keep things simple, let us think about a polytope in \mathbb{R}^n. We have two ways to describe its points. Either as convex combinations of its extremal points or as the finite intersection of half spaces. Tropical geometry is done in a somewhat different space but this intuition remains valid.

Replace the addition and multiplication you know from \mathbb{R} by the following operations a \underline{\oplus} b= \min\{a, b\} and a \underline{\odot} b= a +b. These operations turn \mathbb{R} into the tropical min-plus semi-ring (\mathbb{R}, \underline{\oplus}, \underline{\odot}). Note that we lack an additive inverse, so this world is algebriacally different from (\mathbb{R}, +, \cdot) as you know it. There is a dual version, obtained by setting a\overline{\oplus} b= \max\{a, b\} and a \overline{\odot} b= a +b, the max-plus semi-ring. Just as in classical linear algebra you can extend these operations to obtain something that behaves like a vector-space (which here formally is a semi-module), in which you can multiply tropical matrices, etc.

Now that we entered the realm of tropical linear algebra, we can ask what classical objects such as determinants, eigenvectors and eigenvalues, and hyperplanes look like. As it turns out these concepts have tropical analogues with very useful interpretations (for example in terms of matchings, paths in graphs and combinatorics, respectively. But this is best left for a post in of its own…).

Though we develop also the algebraic view in the paper, the most intuitive way of approaching the theory is via hyperplanes. So what matters to us for the moment is only what hyperplanes look like and which information they encode. To this end it is helpful to keep the intuition from the introductory example in mind.

Classically a hyperplane in \mathbb{R}^n can be described by a vector a\in \mathbb{R}^n. It is given by the set of points \{x\in \mathbb{R}^n~:~ a_1\cdot x_1 +\ldots + a_n\cdot x_n =0\}, i.e. points for which the inner product vanishes. If you simply replace addition and multiplication by its tropical min-plus analogues you get the tropical inner product. Explicitly, a_1\odot x_1 \oplus \ldots \oplus a_n\odot x_n= \min\{a_1+ x_1, \ldots, a_n+ x_n\}. This is a concave, piecewise linear function. However, it is not clear what vanishing means. As it turns out (and there is an algebraic reason for this), a useful definition is the following.

\underline{\mathcal{H}}(a)=\{ x\in \mathbb{R}^n~:~ \min\{a_1+ x_1, \ldots, a_n+ x_n\}~ \text{is attained at least twice} \}

Equivalently these are the points for which the convex function is not linear.

If you play a bit with this definition, you will notice that you can normalize one coordinate. Formally this is done by quotienting tropical scalar multiplication \mathbb{R}^n / \mathbb{R}\cdot \mathbf{1} \cong \mathbb{R}^{n-1}. Here \mathbf{1} is a vector of ones and the homeomorphism sends [(x_1, \ldots, x_n)] \mapsto (x_2-x_1, \ldots, x_n - x_1). We call this space the tropical projective torus, \mathbb{TP}^{n-1}. I invite you to spend a few minutes to work out the following examples of min-plus and max-plus tropical hyperplanes in the two-dimensional tropical torus supported by a point [(a_1, a_2, a_3)]=[(0, a_2-a_1, a_3-a_1)].

Tropical Hyperplanes

Contrary to the familiar world of hyperplanes and half spaces, tropical hyperplanes in \mathbb{TP}^{m-1} partition the space into m sectors. Thus, they encode a lot of combinatorial information.

For example, the point labeled p in the figure satisfies p_2-p_1 - (a_2-a_1) \geq 0 and p_3-p_1 - (a_3-a_1) \geq 0. We label the cone enclosed by the two red lines in which p lies by 3, the third sector of \underline{\mathcal{H}}(a), since for points there the minimum in the topical inner product of p and a is attained in the third coordinate. Similarly for the other sectors. There is a systematic way of using this information that is elegantly encapsulated in the concept of covectors (or combinatorial types as they are originally known). Given k hyperplanes supported at q_1, \ldots, q_n in \mathbb{TP}^{m-1} and a point p, one can ask for its relative position. One thus obtains a collection of data that indicates in which sector(s) of each hyperplane the point lies. Accordingly, one gets a list of inequalities as the ones above involving the coordinates of the hyperplanes and the point.

Such considerations are related to the notion of tropical convexity that formalizes the dual description of tropical polytopes.

Before I finally come to our application, some cultural edification on the origins of the adjective tropical is not out of place. Tropical geometry was pioneered by the Hungarian born Brazilian mathematician Imre Simon. Later in a humorous moment it appears, french mathematicians added the adjective tropical, in his honor as a reference to Brazil.

Mechanism Design via Tropical Geometry

Fix an outcome function g. Let us return the the incentive constraints mentioned above and rewrite them as follows.

 t_{g(t)}-t_{g(s)} -(p(t)-p(s)) \geq 0

 This now looks like the covector condition we just saw with p a point relative to a hyperplane supported by t.

Note that by adding a smart zero to this equation (and thus normalizing with respect to the utility of a fixed outcome, 1\in [m], say) we can assume that types are a subset of \mathbb{TP}^{m-1}.

The mechanism can only tie payments to outcomes, not the announcements directly (otherwise, if two statements didn’t change the outcome, the player would always report the type that minimized his payment). Now, there is a way (either via a hyper-graphs or a positioning argument of tropical hyperplanes) to reduce this possibly huge number of incentive constraints to m relevant points in \mathbb{TP}^{m-1}, and m tropical hyperplanes supported by them. The simplest non-technical way of thinking about these points is the following.

The mechanism would like the subset g^{-1}(j) of types to receive allocation j. Of all these types an agent could possibly have, one can ask which gains the most from lying to change the allocation to k, i.e. for which type the difference t_k-t_j is largest. If the mechanism manages to prevent that type from lying, it will also ensure that all other types tell the truth. What you get from this consideration is

L^{g,t_{-i}}_{jk} := \inf_{t \in g^{-1}(j)}\{t_j - t_k\}

For each pair j, k \in [m] this determines a matrix. Denote each of its row-vectors by L_j for j \in [m]. The entries of the vector -L_j correspond to utility gains from lying to the mechanism relative to the outcome the mechanism would like to implement.

Let us consider an incentive compatible example with m=3 (building a bridge, a tunnel or none, say). In this case we can geometrically depict the mechanism in \mathbb{TP}^2 \cong \mathbb{R}^2 (utilities of the bridge relative to nothing and the tunnel relative to nothing). If we associate to each point L_1, L_2, L_3 a pair of hyperplanes, one min-plus and max-plus, we get something that looks like this.

Mechanism Tropical Hyperplane

The gray shaded areas are the types. Note that if we let

 \overline{\mathcal{L}}_j(L_j) = \{t \in \mathbb{TP}^{m-1}: L_{jk} + t_k \leq t_j \mbox{ for } k \neq j \}.

(sector j of hyperplane j) then

T_i \subseteq \bigcup_{k=1}^m \overline{\mathcal{L}}_k

That is, types are entirely contained in the union over the outcomes of the relevant sectors. All the types in a given sector have the same incentives. Also hyperplanes “stick close” to the type-space. This follows from the consideration made about L_{jk}^{g, t_{-i}}. Thus the collection of the relevant sectors separates types according to their incentives.

The mechanism must now find payments that offsets these incentives. To do this, consider a min-plus hyperplane with apex L_j:

\underline{\mathcal{H}}(L_j)=\min\{ L_{j1}+x_1, \ldots , L_{jm}+x_m \}

By definition, for any point q in its j‘th sector, the minimum is attained in the j‘th coordinate. Thus, for all k\in[m]

q_j \leq q_k +L_{jk} = q_k + \inf_{t \in g^{-1}(j)}\{t_j - t_k\}

and hence, for all t\in g^{-1}(j):

t_{g(t)}-q_{g(t)} \geq t_{g(s)}-q_{g(s)}

Thus by setting a price q in the j‘th min plus sector of hyperplane \mathcal{\underline{H}}(L_j), all types that the mechanism would like to receive allocation j will report the truth. Hence if we dually define

\underline{\mathcal{L}}_j = \{t \in \mathbb{TP}^{m-1}: L_{jk} + t_k \geq t_j \mbox{ for } k \neq j\}.

Then the set of incentive compatible payments (that is payments that induce truth-telling for all types simultaneously) is the set

\mathsf{Eig}_0(L) := \bigcap_{j=1}^m\underline{\mathcal{L}}_j.

The notation here is rather suggestive. I focused here on the geometric intuition that can be formalized via covectors. However, the theory can also be developed via tropical linear algebra. Then the set of payments is the min-plus eigenspace of the matrix L in the case in which the tropical eigenvalue is zero. The paper develops this basic idea systematically: In economics it is related to a network approach to mechanism design, in tropical geometry to the tropical spectral theory of matrices and polytropes.

You can also invert this procedure to get a geometric way to derive incentive compatible mechanisms starting with just the type space. The idea is simple. Just place hyperplanes in such a way that sectors relevant sectors partition the type space appropriately (also these hyperplanes cannot be “far away” from the types). This allowed us to fully characterize all mechanisms that are incentive compatible using a purely geometric argument that does not rely on convex analysis, as is usually done. Also this gives insights into classical ideas from mechanism design such as revenue equivalence.

Why is Tropical Geometry useful for Mechanism Design?

By using tropical geometry in mechanism design we can develop a systematic graphical and geometric toolbox for some mechanism design problems. In some examples the framework is so simple, that it could be put in an undergraduate intermediate micro textbook… This is one of the powers of the visual apparatus that comes with tropical geometry. But there is also rigorous mathematics behind it which makes many proofs that  previously required cumbersome arguments and heavy machinery, intuitive and simple.

Mathematicians like to look at a problem in a way that makes it easily tractable yet  preserves a maximum of structure. In using tropical geometry, we are able to give incentive constraints algebraic structure. This allows us, for example, to give a (tropical) linear algebraic basis of payments. Why is this interesting you ask? Typically we rely on revenue equivalence to derive incentive compatible payments. Revenue equivalence corresponds to the case in which the basis consist of a single vector. However, using tropical geometry, we get a hold on the general case more easily and can move away from the all or nothing case, i.e. having Revenue Equivalence or not. The dimension of the tropical span being anywhere between 1, \ldots, m has an interesting economic interpretation in terms of information rents. It shows that in choosing payments the mechanism shifts rents between different types. Thus beyond supplying mathematical structure, the tropical viewpoint may be able to add some clarity when it comes to  economic theorizing.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s