Keywords

1 Introduction

General equilibrium theory and (noncooperative) game theory are among the most succesful and well-studied areas in economic theory. The former seeks to explain the existence of equilibria in multiple markets at the same time. The latter serves as the primary tool for predicting, analysing and describing the behaviour of rational agents’ actions both in and out of equilibrium.

Here we try to combine the two approaches for exchange economies. Specifically, we ask how much any individual agent can gain from strategically misreporting his utility function. The results presented here suggest that, contrary to previous findings in Fisher markets, the gains from strategic behaviour may be significant, even allowing an agent to improve his equilibrium utility without bound. If we impose (common) restrictions, the utility gain in Cobb–Douglas markets is bounded by the number of commodities, but it may exceed the upper bound from Fisher markets, which can be shown by means of an example. The results obtained show a sharp contrast with the findings in the Fisher market setup [6, 7]: there, incentive ratios are bounded by the small constants 2, 2 and \(e^{1/e} \approx 1.44\) for linear, Leontief and Cobb–Douglas markets, respectively.

1.1 Related Work

In a Fisher market [3] agents possess an amount of money rather than a bundle of commodities as in exchange economies. The idea that an agent may act strategically in such a market by misreporting his utility function in order to get a better equilibrium bundle, compared to the scenario where everyone is truthful, was already considered in [1] for the case of linear utility functions. The incentive ratio was first coined in [7], where the strategic variable of interest is the (Leontief) utility function of a player and bidding the true budget is a dominant strategy. In [5, 6], a slightly more sophisticated version of the incentive ratio is presented, in which players may also strategise on their endowments. The “exchange market game” is introduced in [11], and agents have linear utility functions. They may lie about their utility function to manipulate the outcome of the exchange process. It is consequently shown that a symmetric strategy profile is a Nash equilibrium if and only if it is conflict-free. In [4], price of anarchy bounds are computed for linear, Leontief and Cobb–Douglas markets in Fisher markets. The strategic variable of interest is the utility function. It primarily differs from the analysis presented here in that it focuses on welfare of all agents rather than measuring the benefits of strategic behaviour for one specific agent. It is known that the Walrasian mechanism is susceptible to manipulation via endowments: via withholding endowments and recovering it fully [13], recovering part of it [15, 16] and even destroying part of one’s initial endowment [2]. However, the aforementioned studies only show that manipulation of the equilibrium is possible, but do not quantify it.

The rest of this paper is organised as follows. Section 2 discusses the necessary machinery, definitions and introduces some notation. Section 3 presents the results for incentive ratios in Linear, Leontief and Cobb–Douglas exchange economies. The latter receives most attention. Finally, Sect. 4 concludes and provides some directions for future research.

2 Preliminaries

We use the following notation. Suppose \(x, y \in \mathbb {R}^n\). Then \( x \cdot y = \sum _{k = 1}^n x_k y_k\) denotes the dot product of x and y. \(x \le y\) means \(x_k \le y_k\) for \(k = 1, \dots , n\). For a vector \(u = (u_1, \dots , u_n)\), by \(u_{-i}\) we mean the vector \((u_1, \dots , u_{i-1}, u_{i+1}, \dots , u_n)\) (i.e. all entries except the i-th). We write \((u_i, u_{-i})\) for \((u_1, \dots , u_{i-1}, u_i, u_{i+1}, \dots , u_n)\). For positive integer n, we use [n] as shorthand notation for the set \(\{1, \dots , n\}\). \(I_m\) is the \(m \times m\) identity matrix. The transpose of a matrix M is denoted by \(M^T\), its determinant by \(\left| M \right| \) and its adjugate by Adj(M). If \(f : \mathbb {R}^m \rightarrow \mathbb {R}^n\), then Df(x) represents the Jacobian matrix of f at x.

We start with the definition of an exchange economy.

Definition 1 (Exchange Economy)

An (exchange) economy is a tuple \(\xi = ((u_i)_{i = 1} ^n, (e_i)_{i = 1}^n)\), where \(u_i: \mathbb {R}_{+}^m \rightarrow \mathbb {R}\) is the utility function of agent \(i \in [n]\) and \(e_i \in \mathbb {R}_{+}^m\) is a vector where \(e_{ij}\) indicates how much agent \(i \in [n]\) possesses of commodity \(j \in [m]\).

In an economy, agents obtain a bundle \(x_i \in \mathbb {R}_+^m\) by trading commodities given a price vector \(p \in \mathbb {R}^m\). If p is such a price vector, then every agent solves the following consumer problem (\(\mathcal {CP}\)).

Definition 2 (Demand)

We call the set of solutions to problem (\(\mathcal {CP}\)) the demand of agent i (at prices p).

We can write \(x_i(p, p \cdot e_i)\) to show explicitly that demand depends on endowments and prices. Since prices are in turn determined by endowments and utility functions, we may also write \(x_i(u_i, u_{-i}, e) \) or, when it is understood that \(u_{-i}\) and e are fixed, simply as \(x_i(u_i) \). We also need the notion of Walrasian or competitive equilibrium.

Definition 3 (Competitive/Walrasian Equilibrium)

A competitive equilibrium is a pair \((p,x) \in \mathbb {R}^m \times (\mathbb {R}_{+}^m)^n\) such that:

  1. 1.

    For all \(j \in [m], \sum _{i = 1}^n x_{ij} = \sum _{i = 1}^n e_{ij}\) i.e. markets clear.

  2. 2.

    For all \(i \in [n], \, x_i\) is a solution to (\(\mathcal {CP}\)), i.e. \(x_i\) is the best bundle among the bundles that he can afford.

2.1 Incentive Ratio

Every agent is characterized by two parameters, his endowment \(e_i\) and his utility function \(u_i\). Generally, different endowments and different utility functions will lead to different equilibria. What if an agent purposely misreports his utility function, thereby trying to get a better equilibrium allocation?

The incentive ratio is a concept introduced in [7]. It attempts to measure the (maximum) benefits of manipulating the equilibrium by strategically misreporting personal parameters. Formally, we define it as follows (adapted for exchange economies, the original definition was for Fisher markets, see also [5–7]):

Definition 4 (Incentive Ratio)

The incentive ratio of agent i in a market M (e.g. linear, Cobb–Douglas or Leontief), denoted \(\zeta _i^M\), is defined as:

$$\zeta _i^M = \max _{u_{-i} \in U_{-i}, e_{-i} \in (\mathbb {R}_+^{m})^{n-1}} \max _{u'_i \in U_i} \frac{\max _{x' \in \mathcal {E}(u'_i)} u_i(x'_i(u'_i, u_{-i}, e))}{\min _{x \in \mathcal {E}(u_i)} u_i(x_i(u_i, u_{-i}, e))} .$$

The incentive ratio of market M is subsequently defined as \(\zeta ^M = \max _{i \in [n]} \zeta _i^M\).

Remark 1

In this definition:

  • Variables with a prime \((')\) refer to the scenario in which agent i misreports his parameters (and all other agents report truthfully). That is, he reports \(u'_i\) and as a result, obtains a bundle \(x'_i(u'_i, u_{-i}, e)\). Notice that this bundle is evaluated by the true utility function.

  • Given that player i reports \(\tilde{u}_i\) (i.e. truthful or not) as his utility function (the other players report \(u_{-i}\)), we denote by \(\mathcal {E}( \tilde{u}_i)\) the set of equilibrium allocations, that is, \(\mathcal {E}(\tilde{u}_i) = \{x \in (\mathbb {R}_+^m)^n \vert \, \exists p \in \mathbb {R}_+^m \,\, (p,x) \text{ is } \text{ a } \text{ Walras } \text{ equilibrium }\}.\) Under some (mild) assumptions this set is nonempty, but it could contain multiple equilibrium allocations.

  • \(U_i\) contains the admissible strategies/utility functions for player i, including the one that agent he chooses when he misreports his utility function. We denote \(U_{-i} = \prod _{k \ne i} U_k\). We will only consider the case where all \(U_k\)’s are equal, thus \(U_{-i} = U^{n-1}\).

  • From the preceding arguments, we may restrict attention to agent i, thus we may rewrite the incentive ratio for the market M as

    $$\zeta ^M = \max _{u_{-i} \in U^{n-1}, e_{-i} \in (\mathbb {R}_+^{m})^{n-1}} \max _{u'_i \in U} \frac{\max _{x' \in \mathcal {E}(u'_i)} u_i(x'_i(u'_i, u_{-i}, e))}{\min _{x \in \mathcal {E}(u_i)} u_i(x_i(u_i, u_{-i}, e))} .$$

We will, without loss of generality, restrict ourselves to scenarios where \(e_i \in [0,1]^m\) for all \(i \in [n]\) and \(\sum _{i = 1}^n e_{ij} = 1\) for all \(j \in [m]\). The following Leontief example shows that the consequences from the nonuniqueness of equilibrium can be significant.

Example 1

\(e_1 = (1-\epsilon , \epsilon ), \) \(e_2 = (\epsilon , 1-\epsilon ), \) \(u_2(x_2) = \min \{x_{21},x_{22}\}, \) \(\epsilon > 0\), small

We have \(u_1(x'_1)/u_1(x_1) = (1+\delta )/(2(\epsilon +\delta -\delta \epsilon ))\). Letting \(\delta , \epsilon \) tend to 0, the incentive ratio tends to \(\infty \).

In [6, 7], the following markets are considered, with arbitrarily many agents and commodities: Linear, i.e. \(U = \{u(x) = \alpha \cdot x \mid \alpha \in \mathbb {R}_+^m \}\); Leontief, i.e. \(U = \{u(x) = \min _{j \in [m]} \{x_{j}/\alpha _{j}\} \mid \alpha \in \mathbb {R}_{++}^m \}\); Cobb–Douglas, i.e. \(U = \{ u(x) = \prod _{j = 1}^m x_{j}^{\alpha _{j}} \mid 0 \le \alpha _{j} \le 1\) for all \(j \in [m]\), \(\sum _{j = 1}^m \alpha _{j} = 1\}\). The tight bounds for Fisher markets are 2, 2 and \(e^{1/e}\) for linear, Leontief and Cobb–Douglas respectively.

3 Results

The incentive ratio is a first step to quantifying the possible gains of misreporting in exchange economies. From Example 1, even destroying part of one’s initial endowment (in the case \(e_i\) is the strategic variable of interest), can let the incentive ratio tend to infinity.

Without any further restrictions on the setup presented in [6, 7], also incentive ratios in linear and Cobb–Douglas exchange economies are unbounded. We treat here linear markets; see [12] for details on the Cobb–Douglas case.

Proposition 1

The incentive ratio for linear exchange economies equals \(+\infty \).

Proof

\(e_1 = (\epsilon , 1-\epsilon ), \) \(e_2 = (1-\epsilon , \epsilon ),\) \(u_2(x_2) = x_{21} + \frac{\delta }{1-\epsilon } x_{22}, \) \(\delta , \epsilon > 0\), small

We have \(u_1(x'_1)/u_1(x_1) = 1/(\delta +\epsilon ) \). Letting both \(\delta , \epsilon \) tend to 0, the incentive ratio tends to \(\infty \).    \(\square \)

Henceforth we focus on Cobb–Douglas markets and make the following assumption to ensure all equilibrium prices are positive; this is rather standard in algorithmic game theory.Footnote 1

Assumption 1

  • (Positivity of endowments). Every agent possesses a strictly positive amount of every commodity: \(\forall i \in [n], \forall j \in [m] \,\,\, e_{ij} > 0.\)

  • (Strong competitiveness (see e.g. [4])). Every commodity is demanded by at least one agent: \(\forall j \in [m] \, \exists i \in [n] \, \alpha _{ij} > 0\) and this remains true when agent i reports \(\alpha '_i\).

This entails that the demand of agent \(i \in [n]\) for commodity \(j \in [m]\) is given by \(x_{ij}(p, p \cdot e_i) = \alpha _{ij} p \cdot e_i/p_j\) and the economy excess demand function \(z(p) := \sum _{i=1}^n (x_i(p, p \cdot e_i) - e_i) = \sum _{i=1}^n x_i(p, p \cdot e_i) - 1\) has the gross substitute property, which implies that the equilibrium price is unique (see e.g. [10]). For markets with two commodities we have (for a proof see [12]), as in Fisher markets [6]:

Proposition 2

Consider a Cobb–Douglas market, \(n \ge 2\), \(m = 2\). The incentive ratio is \(e^{1/e}\) and this bound is tight.

The following example shows we can exceed the \(e^{1/e}\) bound.

Example 2

(Incentive ratio \(> e^{1/e}\) ). Suppose the market is as follows:

figure a

Therefore the incentive ratio is \(u_1(x'_1)/u_1(x_1) \approx 1.50\).

The remainder of this section is devoted to the proof that the incentive ratio for Cobb–Douglas markets is bounded. The following lemma is crucial. We only provide a sketch the proof here due to space constraints; see [12] for complete proofs.

Lemma 1

  1. (i)

    \(p_j(\alpha _i)\) reaches its maximum when \(\alpha _{ij} = 1\) and \(\alpha _{ik} = 0\) for all \(k \ne j\). I.e. for any chosen normalisation, \(p_j\) is maximal when \(\alpha _{ij} = 1\).

  2. (ii)

    \(\alpha '_{ij}/p'_j(\alpha '_i)\) reaches its maximum when \(\alpha '_{ij} = 1\) and \(\alpha '_{ik} = 0\) for all \(k \ne j\). I.e. for any chosen normalisation, \(\alpha '_{ij}/p'_j(\alpha '_i)\) is maximal when \(\alpha '_{ij} = 1\).

  3. (iii)

    Let \(A = (\alpha _{ji})_{1 \le i \le n, 1 \le j \le m}\) and similarly \(A'\) when agent i reports \(\alpha _i'\), \(E = (e_{ji})_{1 \le i \le n, 1 \le j \le m}\). Then the first row of \(Adj(EA^T-I_m)\) (\(Adj(E(A')^T-I_m)\)) contains the equilibrium price vector p (\(p'\)) (upto a nonzero constant). Moreover, \(p \cdot e_i = p' \cdot e_i\).

Proof (sketch). For the first two points, w.l.o.g. we focus on commodity m.

(i) This follows from the implicit function theorem applied to \(\left[ D_{\hat{p}} \hat{z}(p(\alpha ); \alpha )\right] ^{-1}\), a matrix in which all entries are negative, where \(p(\alpha )\) is the equilibrium price when players report strategies according to \(\alpha = (\alpha _1, \dots , \alpha _n)\), \(\hat{p}\) and \(\hat{z}\) are vectors with the first \(m-1\) entries from p and \(z(p(\alpha ))\).

(ii) The extreme value theorem assures a maximum is attained. Using necessary conditions for a maximum (see [9]) and homogeneity of degree 0 we get the proof.

(iii) This uses an argument along the lines of [14] and the fact that an equilibrium price vector p satisfies (see [8]) \(p^T (EA^T - I_m) = 0\). The budget of agent i, \(p \cdot e_i\), can be written as a matrix determinant that does not change following the increase of \(\alpha _{ij}\) to \(\alpha '_{ij}\) and a decrease of equal magnitude of \(\alpha _{ik}\) to \(\alpha '_{ik}\), \(1 \le j \ne k \le m\).    \(\square \)

Table 1. Upper bounds on the incentive ratio in \(n \times m\) exchange economies.
Full size table

Theorem 1

The incentive ratio for Cobb–Douglas markets is at most m.

Proof

$$\begin{aligned} \frac{u_i(x'_i)}{u_i(x_i)} = \prod _{j=1}^m \left( \frac{\alpha '_{ij}}{\alpha _{ij}}\frac{p' \cdot e_i}{p \cdot e_i}\frac{p_j}{p'_j}\right) ^{\alpha _{ij}}&\le \prod _{j=1}^m \left( \frac{1}{\alpha _{ij}}\frac{p' \cdot e_i}{p \cdot e_i}\max _{\alpha '_i} \frac{\alpha '_{ij}}{p'_j} \max _{\alpha _i} p_j \right) ^{\alpha _{ij}} \\&\le \prod _{j=1}^m \left( \frac{1}{\alpha _{ij}}\right) ^{\alpha _{ij}} \le m, \end{aligned}$$

where the second inequality follows from the lemma above and the last inequality from the weighted AM–GM inequality.   \(\square \)

We summarize the results presented here in Table 1.

4 Conclusion

Results for incentive ratios in Fisher markets were encouraging: the maximum gains from strategic behaviour were bounded by small constants and therefore equilibrium mechanisms could be expected to work rather well, meaning that the profits from (computationally challenging) strategic behaviour were small relative to the costs, and thus, not worthwhile on most occassions. However, the results here indicate that in the more general setup of exchange economies, results are diametrically different and without further restrictions, all ratios are unbounded. The Cobb–Douglas case demonstrates that, when equilibrium prices (and hence allocations and utilities) are unique, the incentive ratio is bounded by the number of commodities. Therefore it may be argued that, unlike in Fisher markets, gains from strategic behaviour can be significant and manipulation could be worthwhile.

For Cobb–Douglas markets, the case \(m=2\) demonstrates that the bound m is unlikely to be tight. This, and the question of the incentive ratio when agents are allowed to misreport their endowments in linear and Cobb–Douglas markets, are left as directions for future research. Allowing groups of agents to misreport their utility function and extending the results from Cobb–Douglas markets to, for example, any other market satisfying weak gross substitution, are other interesting possibilites.