Characterizing incentive compatible,Pareto optimal and sufficiently anonymous constrained combinatorial mechanisms

Abstract

We characterize the possibility space of deterministic, dominant-strategy incentive compatible, individually rational, and Pareto-optimal combinatorial auctions in a model with two players and two nonidentical items. Our model has multidimensional types, private values, quasilinear preferences for the players with one relaxation – one of the players is subject to a publicly-known budget constraint. We show that the space includes two types of mechanisms: VCG and dictatorial mechanisms. Furthermore when it is publicly known that the budgeted player is not constrained by his budget, VCG uniquely fulfills the basic properties of deterministic, dominant-strategy incentive compatible, individually rational, and Pareto-optimal. When it is publicly known that the budgeted player is constrained on all bundles then only a dictatorial solution will fulfill the above properties. Moreover when it is publicly known that the budgeted player is constrained on the largest bundle there are preferences under which the VCG mechanism uniquely fulfills these properties.

Keywords

Budget constraints dictatorship Pareto efficiency incentive compatibility

1. Introduction

¹
Multidimensional types, meaning that a player may have a separate arbitrary value for each of the four possible outcomes.

private values, nonnegative prices, quasilinear preferences for the players with one relaxation – one of the players is subject to a publicly known budget constraint. The investigated space is common to many problems.

This setting is somewhat more complex than that of common auction literature as it adds budgets and heterogeneity, which more accurately describe mechanisms used in practice. Indeed the investigated space better characterizes many real world problems such as commonly studied bandwidth (combinatorial) auctions. Consider the European 3G radio spectrum auction where telecom companies bid so high as to have jeopardized their financial viability and consequently considerably slowed down capital investment in 3G equipment. The phenomena in Europe highlights the potential gap between willingness to pay and ability to pay, and the potential of better understanding how budget constraints affect auction design. Further consider that most goods are not sold in uniform bundles or used as single goods. Though blocks of radio bandwidth are apparently uniform, they are not identical. This can also be said for goods in supply chain auctions which are bundled to fulfill diverse bills of materials. The addition of the seemingly minor dimension of heterogeneity profoundly affects auction design complexity.

Our result characterizes the space of possible outcomes and prices in this context. For instance, the characterization answers whether and under which conditions it is possible for a small telecommunications company to fairly compete with better financed companies in a bandwidth auction.

Recently it was shown [13] that there is no deterministic combinatorial auction that is dominant-strategy incentive compatible, individually rational, and Pareto-optimal where players have publicly known budget constraints and the all-item bundle is nonarbitrarily allocated,2

A property we term nonarbitrary hoarding that intuitively means that a mechanism fulfills nonarbitrary hoarding if whenever both items are allocated to a single player the player is chosen nonarbitrarily, i.e., in accordance to the reported valuations and budget of the two players. Furthermore, the player chosen has to be able to afford the 2-item bundle more than the other player. See Definition 2.7 for formal definition.

in a model with multiple nonidentical items and nonnegative prices. Therefore in order to allow the characterization of the mechanisms’ possibility space some additional public knowledge needs to be assumed.

More specifically we prove that the space includes two types of mechanisms: VCG ([8,15,27]) and dictatorial mechanisms. The combinatorial space is divided by the budget-constrained player’s preference value for the two-item bundle. We show that if it is publicly known that the budget-constrained player values the two-item bundle less than his budget and the allocation of the two-item bundle is nonarbitrary then VCG is the unique mechanism that is dominant-strategy incentive compatible, individually rational and Pareto optimal. We also show that if it is publicly known that the budget-constrained player values the two-item bundle more than his budget then either there is a VCG mechanism or there is a family of dictatorial mechanisms with the non-constrained player as the dictator. The VCG mechanism is unique when it is publicly known that the non-constrained player values the two-item bundle less than the constrained player’s budget, and the family of dictatorial mechanisms is unique when it is publicly known that the budget-constrained player values all nonempty bundles more than his budget. The mechanisms in the dictatorial family are identical except for two price parameters that differentiate them.

It may seem that the conclusion from the characterization of this work calls for unrealistic publicly known conditions on the valuations. It is true that the characterization is indeed theoretical work and in practice the public knowledge of such conditions on the valuations may be lucking. Nevertheless the illustrative example above regarding the European 3G radio spectrum auction shows that gap between willingness to pay and ability to pay can be well observed by the market and publicly known.

It is well known that in quasilinear environments with a complete preference domain over at least three outcomes and non-constrained players, only VCG mechanisms satisfy the dominant-strategy incentive compatible property [25].3

In quasilinear environments only Groves mechanisms satisfy the dominant-strategy incentive compatible and Pareto optimal properties ([14,17]).

Nevertheless when preferences are subject to free disposal and no externalities are assumed, as is common in combinatorial auctions, then the possibility space of dominant-strategy incentive compatible combinatorial auctions in the multidimensional type model is not yet defined. Several papers investigate computationally feasible dominant-strategy incentive compatible (but inefficient) auctions with one-dimensional private values [20,23] as well as with multidimensional private-value settings with some additional restrictions on the preference space [3,10].

There are classic as well as recent results showing that dictatorship (or sequential dictatorship) is the only mechanism that is not subject to individual manipulations and is Pareto-optimal in mechanism design models without the quasilinearity assumption (see [1,6,12,16,26]). Arrow’s seminal impossibility [1] shows that for unrestricted domains (at least three possible outcomes) under; determinism and transitivity axioms, independence of irrelevant alternatives (IIA), and Pareto-optimality conditions, every social choice function must be a dictatorship or imposed. However, the conditions of Arrow’s theorem as well as the conditions of [12] and [26] can be satisfied when the requirement for unrestricted domains is relaxed, as was shown for one dimensional domains such as single peaked.

While the possibility/impossibility of maintaining Arrow’s desired properties is known for the whole space of the non-monetary domain of preferences, when restricting attention to the assumption of side payments and transferable currency much is yet left to be understood. One recent development in understanding the monetary (multi dimensional) domain is the work of [21] in which dictatorship mechanisms that are not subject to individual manipulations and are Pareto-optimal were shown in the quasilinear model with budget-constrained players.

1.1. Our contribution

Our contribution consists of several aspects. The first aspect shows that combinatorial auctions with a multidimensional type model in a rich “enough” preference space of four outcomes, require only VCG in order to fulfill the basic properties of deterministic, dominant-strategy incentive compatible, individually rational, and Pareto-optimal when both players are not constrained by their budget and the allocation of the all-item bundle is nonarbitrary. This aspect of the contribution takes a step toward a Roberts-like result [25] for the combinatorial auction domain as it includes the case where there are no budgets at all. The second aspect shows that when there exists at least one player who is budget constrained then there are preferences under which only a dictatorial solution will fulfill the above properties. Moreover, for preferences that allow a non-dictatorial solution to exist only VCG mechanism can fulfill these properties. This aspect shows an Arrow-like space for budgeted combinatorial auctions. The third aspect of our contribution shows that the above properties imply the useful property of player-auctioneer coalition resilience even when side payments are allowed. We termed the player-auctioneer coalition resilience property stability and use it to prove the uniqueness of VCG pricing when paid prices are all positive.

The stability property essentially bounds the prices of any mechanism (with strictly positive prices) from below, ensuring that no player has an incentive to collude with the auctioneer ex-post and offer the auctioneer side-payments such that the colluding player can win all the items. The need for the stability property to prove VCG pricing is not surprising given that stability is known to exist in one item Vickrey auctions. To observe that stability holds in one item Vickrey auctions, consider that the losing player can not afford to pay side payments to the auctioneer after the auction is concluded in order to convince the auctioneer to give him the item instead of giving it to the winning player.

1.2. Take home point and example

The take home point from our study is that the general space of dominant-strategy incentive compatible combinatorial auctions with budgets most likely includes only VCG and dictatorial mechanisms, and it appears that the dictatorial aspect depends on the introduction of budgets. We draw the above conclusion as the research community has indication to believe that the general space of dominant-strategy incentive compatible combinatorial auctions without budgets includes only VCG mechanisms. Therefore the discovery of dictatorial mechanisms in our study is most likely brought about by our inclusion of players with budgets.

We conclude this section with an example. Two telecommunications companies $T_{1}$ and $T_{2}$ are competing over bandwidth in a region with two distinct broadcast bands $c_{1}$ and $c_{2}$ . Company $T_{1}$ has a limited budget b of $500,000 to spend on bandwidth. On the other hand company $T_{2}$ is a large telecommunications company with practically unlimited funds to spend on the discussed region. If company $T_{1}$ does not value taking control of all the bandwidth available in the region more than b, i.e., $T_{1}$ values the allocation of the bundle $c_{1}$ , $c_{2}$ in $300,000, then $T_{1}$ and $T_{2}$ ’s bandwidth allocation will be determined and priced by VCG. Meaning, if $T_{2}$ values $c_{1}$ or $c_{2}$ at $200,000 and the allocation of the bundle $c_{1}$ , $c_{2}$ in $600,000 then $T_{2}$ wins both bands for the price of $300,000. If company $T_{2}$ does not value taking control of all of the bandwidth available in the region more than b, i.e., $T_{2}$ values the allocation of the bundle $c_{1}$ , $c_{2}$ in $400,000, then despite the fact that company $T_{1}$ might be interested in taking control of all of the available bandwidth for more money than its budget, $T_{1}$ and $T_{2}$ ’s bandwidth allocation will be determined and priced by VCG. Meaning, if $T_{1}$ values $c_{1}$ or $c_{2}$ at $400,000 and the allocation of the bundle $c_{1}$ , $c_{2}$ in $550,000 then $T_{1}$ and $T_{2}$ win each a band for the price of $200,000 and $150,000 respectively. Most interestingly, if company $T_{1}$ would like to acquire any bandwidth in the region and values all such options more than its budget b say $800,000 then $T_{2}$ receives its most beneficial single bandwidth ( $c_{1}$ or $c_{2}$ ) allocation for free, regardless of any high values stated by company $T_{1}$ .

1.3. Paper organization

The paper is organized as follows. Notation and definitions are presented in Section 2. In Section 3 we show the implications of the properties discussed above and prove the uniqueness of VCG pricing. In Section 4 we define and prove our main results – the possibility mechanisms space. The Appendices captures some of the technical proofs.

2. Notation and definitions

We consider combinatorial auction mechanisms with 2 different types of items and 2 players. Let $N = {1, 2}$ be the set of players and $C = {c_{1}, c_{2}}$ be the set of items. Let $B$ be the set of all subsets of items, that is, $B = 2^{C} = {\emptyset, {c_{1}}, {c_{2}}, {c_{1}, c_{2}}}$ .

Each player i has a private value $v_{i} (B) ⩾ 0$ for every bundle $B \in B$ drawn from a valid valuation space $V_{i}$ . We denote the private values of player i by a triple, $V_{i} = (v_{i} (c_{1}), v_{i} (c_{2}), v_{i} (c_{1}, c_{2})) \in V_{i}$ .

Definition 2.1.
We say that $V_{i}$ is a valid valuation space if for every $V_{i} \in V_{i}$ the following two conditions hold:
The valuation of the empty bundle is zero, i.e., $v_{i} (\emptyset) = 0$ and

free disposal, that is for both players the allocation of an extra item cannot reduce their valuation (the usual assumption in combinatorial auctions); i.e., $\forall B, B^{'} \in B$ , $B \subset B^{'} \Rightarrow v_{i} (B) ⩽ v_{i} (B^{'})$ .

In some cases in this paper we further restrict the valuation space to a subset of all the valid valuation spaces.

As players are multi-minded and have different private values for different bundles of the items, a player i may have a separate arbitrary value for each of the four possible outcomes, meaning our valuation space is a multidimensional valuation space and the players have multidimensional valuations.

We assume that player 1 has a limited budget $b_{1}$ while player 2 has an unlimited budget for acquiring the items and these budgets are publicly known information.

Let $G_{i} : V_{i} \to V_{i}$ be the bidding function of player $i \in {1, 2}$ . That is, $G_{i} (V_{i})$ is the reported valuation function.

We use the following notations: $V_{i} = (v_{i} (c_{1}), v_{i} (c_{2}), v_{i} (c_{1}, c_{2}))$ , and $G_{i} (V_{i}) = (g_{i} (c_{1}), g_{i} (c_{2}), g_{i} (c_{1}, c_{2}))$ . $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}) = (B_{1}, B_{2}, p (B_{1}), p (B_{2}))$ is the auction mechanism where $B_{i}$ is the bundle allocated to player i and $p (B_{i})$ is the price of the bundle $B_{i}$ .

We assume that all the prices are nonnegative, i.e., $p (B_{i}) ⩾ 0$ for $i = {1, 2}$ . We also assume that the auction mechanism $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})$ can produce at least three outcomes, i.e., there exist inputs: $(G_{1} (V_{1}), G_{2} (V_{2}), b_{1})$ , $(G_{1}^{'} (V_{1}), G_{2}^{'} (V_{2}), b_{1}^{'})$ and $(G_{1}^{″} (V_{1}), G_{2}^{″} (V_{2}), b_{1}^{″})$ , such that $B_{i} = {c_{1}, c_{2}}$ , $B_{i}^{'} = {c_{j}}$ , and $B_{i}^{″} \neq B_{i}, B_{i}^{'}$ .
Definition 2.2.
The utility of player 1, player 2 and the auctioneer are defined as follows:

Player 1’s utility is: $\begin{matrix} u_{1} (F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})) = \{\begin{matrix} v_{1} (B_{1}) - p (B_{1}) & if p (B_{1}) ⩽ b_{1}, \\ - \infty & otherwise . \end{matrix} \end{matrix}$

Player 2’s utility is $u_{2} (F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})) = v_{2} (B_{2}) - p (B_{2})$ .

The auctioneer’s utility is $u_{a} (F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})) = p (B_{1}) + p (B_{2})$ .

For simplicity of notation we will denote $u_{i} (F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}))$ by $u_{i}$ whenever F, $G_{1} (V_{1})$ , $G_{2} (V_{2})$ , and $b_{1}$ will be clear from the context.
Definition 2.3 (Determinism).

An auction mechanism $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})$ is called deterministic if for every given input it outputs a single outcome.

Definition 2.4 (Dictatorship).

An auction mechanism $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}) = (B_{1}, B_{2} = C - B_{1}, p (B_{1}), p (B_{2}))$ is called dictatorial if there exists a player $i \in {1, 2}$ (the dictator), such that given all the feasible allocations, $\forall (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})$ , $B_{i} \in arg {max}_{all-feasible-allocations} (g_{i} (B_{i}) - p (B_{i}))$ ; that is, F maximizes the reported values utility of player i.

For example if player 2 is the dictator and $v_{2} (c_{1}) = 10$ , $v_{2} (c_{2}) = 5$ , $v_{2} (c_{1}, c_{2}) = 11$ , $G_{2} (V_{2}) = V_{2}$ , $p (B_{2} = {c_{1}}) = 2$ , $p (B_{2} = {c_{2}}) = 0$ , $p (B_{2} = {c_{1}, c_{2}}) = 4$ . Then $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}) = (B_{1} = {c_{2}}, B_{2} = {c_{1}}, p (B_{1}), p (B_{2}))$ , regardless of player 1’s $G_{1} (V_{1})$ .

Definition 2.5 (Trivial pricing mechanism).

We say that a mechanism F is a trivial pricing mechanism if there is an input $(G_{1} (V_{1}), G_{2} (V_{2}), b_{1})$ , such that $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}) = (B_{1}, B_{2}, p (B_{1}), p (B_{2}))$ and either ( $B_{1} \neq \emptyset$ and $p (B_{1}) = constant$ ) or ( $B_{2} \neq \emptyset$ and $p (B_{2}) = constant$ ). That is, there is a player i who is allocated a nonempty bundle and pays a constant price, i.e., a price that does not depend on the other player’s valuations.

We next define the four properties under which [13]’s impossibility holds: Individual Rationality (IR), Nonarbitrary Hoarding, Pareto Optimality and Truthfulness.

Definition 2.6 (Property 1: Individual Rationality (IR)).

An auction mechanism $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})$ is called individually rational if for every player i, $u_{i} (F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})) ⩾ 0$ , when true values are reported, i.e. $G_{i} (V_{i}) = V_{i}$ for every i. That is, the following must hold:

$v_{1} (B_{1}) - p (B_{1}) ⩾ 0$ and $p (B_{1}) ⩽ b_{1}$ (IR of Player 1).

$v_{2} (B_{2}) - p (B_{2}) ⩾ 0$ (IR of Player 2).

Note that the auctioneer’s utility is nonnegative from our assumption that all the prices are nonnegative.

Definition 2.7 (Property 2: Nonarbitrary hoarding).

We say that an auction mechanism F is nonarbitrary hoarding if the following two conditions hold:

If $B_{2} = {c_{1}, c_{2}}$ then $g_{2} (c_{1}, c_{2}) ⩾ min {b_{1}, g_{1} (c_{1}, c_{2})}$ .

If $B_{1} = {c_{1}, c_{2}}$ then $min {b_{1}, g_{1} (c_{1}, c_{2})} ⩾ g_{2} (c_{1}, c_{2})$ .

Intuitively, a mechanism fulfills nonarbitrary hoarding if whenever both items are allocated to a single player the player is chosen nonarbitrarily, i.e., in accordance to the reported valuations and budget of the two players. Furthermore, the player chosen has to be able to afford the 2-item bundle more than the other player. Note that the property of nonarbitrary hoarding does not imply that a nonarbitrary hoarding mechanism has to allocate the 2-item bundle to one of the players under some valuations and budget.

Definition 2.8 (Property 3: Pareto optimality).

An auction mechanism F is called Pareto optimal if for every input $(G_{1} (V_{1}), G_{2} (V_{2}), b_{1})$ of true valuations, there is no auction mechanism $F^{'}$ such that all the following inequalities hold, with at least one strong inequality:

$u_{1} (F^{'} (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})) ⩾ u_{1} (F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}))$ ,

$u_{2} (F^{'} (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})) ⩾ u_{2} (F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}))$ ,

$u_{a} (F^{'} (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})) ⩾ u_{a} (F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}))$ .

Definition 2.9 (Property 4: Truthfulness).

An auction mechanism $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})$ is called Truthful if none of the two players can increase their own utility by reporting false valuations. That is, given the true valuations $V_{1} \in V_{1}$ and $V_{2} \in V_{2}$ , for every $G_{1} (V_{1}) \in V_{1}$ and $G_{2} (V_{2}) \in V_{2}$ the following hold:

$u_{1} (F (V_{1}, G_{2} (V_{2}), b_{1})) ⩾ u_{1} (F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}))$ ,

$u_{2} (F (G_{1} (V_{1}), V_{2}, b_{1})) ⩾ u_{2} (F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}))$ .

3. The properties’ implications

In this section we derive the price structure of any non-trivial mechanism that satisfies the properties of: IR, Nonarbitrary Hoarding, Pareto optimality and truthfulness. We derive the price structure in the following three steps:

In Definition 3.1 We define and motivate a new property – stability, that imposes a lower bound on the prices.

In Theorem 3.2 we prove that stability holds in any nontrivial pricing mechanism that satisfies the four properties.

In Lemma 3.3 we prove that the prices can not be higher than the lower bound dictated by stability, and therefore they must equal the lower bound.

3.1. Stability

Definition 3.1 (Stability).

An auction mechanism $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}) = (B_{1}, B_{2}, p (B_{1}), p (B_{2}))$ is stable if the following two conditions hold:

$p (B_{2}) ⩾ min {g_{1} (c_{1}, c_{2}) - g_{1} (B_{1}), b_{1} - p (B_{1})}$ (stability of Player 1), and

$p (B_{1}) ⩾ g_{2} (c_{1}, c_{2}) - g_{2} (B_{2})$ (stability of Player 2).

Stability means that if the stated values are the true valuations, i.e., $G (V_{1}) = V_{1}$ and $G (V_{2}) = V_{2}$ , then no player i can collude with the auctioneer (or defect with the auctioneer) against player $\hat{i}$ to receive the 2-item bundle. That is, player i can not simultaneously increase the auctioneer’s utility (by ε side payment) while maintaining a higher utility from the 2-item bundle than the utility from the mechanism’s allocation. The above intuition can be easily derived for player 2 by subtracting $p (B_{2})$ from both sides of player 2’s stability inequality, i.e., $p (B_{1}) ⩾ g_{2} (c_{1}, c_{2}) - g_{2} (B_{2}) \Rightarrow g_{2} (B_{2}) - p (B_{2}) ⩾ g_{2} (c_{1}, c_{2}) - (p (B_{1}) + p (B_{2}))$ . The above intuition can also be derived for player 1 by subtracting $p (B_{1})$ from both sides of player 1’s stability inequality in the case where budget is not a limitation, i.e., $p (B_{2}) ⩾ g_{1} (c_{1}, c_{2}) - g_{1} (B_{1}) \Rightarrow g_{1} (B_{1}) - p (B_{1}) ⩾ g_{1} (c_{1}, c_{2}) - (p (B_{1}) + p (B_{2}))$ . The intuition above also holds for player 1 when budget is his limitation, i.e., $g_{1} (c_{1}, c_{2}) - g_{1} (B_{1}) > b_{1} - P (B_{1}) \Rightarrow p (B_{1}) + p (B_{2}) ⩾ b_{1}$ .

In the next theorem we show that stability holds in any nontrivial pricing mechanism that satisfies the four properties.

Theorem 3.2.
Stability must hold in any nontrivial pricing mechanism that satisfies IR, Pareto optimality, nonarbitrary hoarding and truthfulness.

We prove Theorem 3.2 by considering the four possible allocations. We show for every allocation that if stability does not hold then one of the properties of IR, nonarbitrary hoarding, Pareto optimality, and truthfulness is violated, or the mechanism must be a trivial pricing mechanism. The proof of Theorem 3.2 can be found in Appendix B.
3.2. Determining the prices

In the following lemma we prove the price structure of any nontrivial pricing mechanism that satisfies the four properties. In Theorem 3.2 we proved that any nontrivial pricing mechanism that satisfies the four properties must satisfy stability. In Definition 3.1 (Stability) we stated the prices’ lower bound.4

⁴
In cases of singleton allocations $p (B_{2}) = b_{1} - p (B_{1})$ implies a trivial pricing mechanism.

We now show that the prices can not be higher than the lower bound and therefore they must equal the lower bound. Lemma 3.3.

In any nontrivial pricing mechanism that satisfies the properties of IR, truthfulness, Pareto optimality, and nonarbitrary hoarding, the prices must be as follows:

If $B_{2} = {c_{1}, c_{2}}$ and $B_{1} = \emptyset$ then: $p (B_{2}) = min {b_{1}, g_{1} (c_{1}, c_{2})}$ .

If $B_{1} = {c_{1}, c_{2}}$ and $B_{2} = \emptyset$ then: $p (B_{1}) = g_{2} (c_{1}, c_{2})$ .

If $B_{1} = {c_{1}}$ and $B_{2} = {c_{2}}$ then:

$p (B_{1}) = g_{2} (c_{1}, c_{2}) - g_{2} (c_{2})$ ,

$p (B_{2}) = g_{1} (c_{1}, c_{2}) - g_{1} (c_{1})$ .

If $B_{1} = {c_{2}}$ and $B_{2} = {c_{1}}$ then:

$p (B_{1}) = g_{2} (c_{1}, c_{2}) - g_{2} (c_{1})$ ,

$p (B_{2}) = g_{1} (c_{1}, c_{2}) - g_{1} (c_{2})$ .

Proof of Lemma 3.3.

We show that the prices can not be higher than the lower bound given by stability and therefore they must equal the lower bound. We consider the four possible allocations:

$B_{2} = {c_{1}, c_{2}}$ and $B_{1} = \emptyset$ .

Suppose to the contrary that $p (B_{2}) > min {b_{1}, g_{1} (c_{1}, c_{2})}$ .

Let $p (B_{2}) = min {b_{1}, g_{1} (c_{1}, c_{2})} + 2 \cdot ε$ . From IR of player 2 it must be the case that $v_{2} (c_{1}, c_{2}) ⩾ min {b_{1}, g_{1} (c_{1}, c_{2})} + 2 ε$ We show that such price can not be truthful for player 2. Consider the following deviation for player 2:

$g_{2}^{'} (c_{1}, c_{2}) = min {b_{1}, g_{1} (c_{1}, c_{2})} + ε$ and

$g_{2}^{'} (c_{1}) = g_{2}^{'} (c_{2}) = 0$ .

Then from the property of nonarbitrary hoarding player 1 will not be allocated the 2-item bundle. Suppose that each player is allocated a singleton and without the loss of generality assume that

B_{1}^{'} = {c_{1}}

and

B_{2}^{'} = {c_{2}}

. Then from Theorem 3.2 it follows that

p (B_{1}^{'}) ⩾ g_{2}^{'} (c_{1}, c_{2}) - g_{2}^{'} (c_{2}) = min {b_{1}, g_{1} (c_{1}, c_{2})} + ε

. However, from free disposal

p (B_{1}^{'})

contradicts IR of player 1, whenever player 1 states true valuations. Therefore player 2 must still be allocated the 2-item bundle for a lower price. Thus any price higher than

min {b_{1}, g_{1} (c_{1}, c_{2})}

is not truthful.

$B_{1} = {c_{1}, c_{2}}$ and $B_{2} = \emptyset$ .

From the nonarbitrary hoarding property it follows that $g_{2} (c_{1}, c_{2}) ⩽ min {b_{1}, g_{1} (c_{1}, c_{2})}$ and thus we conclude that $g_{2} (c_{1}, c_{2}) ⩽ b_{1}$ .

Suppose to the contrary that $p (B_{1}) > g_{2} (c_{1}, c_{2})$ .

Also let $p (B_{1}) = g_{2} (c_{1}, c_{2}) + 2 ε$ . From IR of player 1 it must be the case that $v_{1} (c_{1}, c_{2}) ⩾ p (B_{1}) = g_{2} (c_{1}, c_{2}) + 2 ε$ . We show that it can not be truthful for player 1. Consider the following deviation for player 1:

$g_{1}^{'} (c_{1}, c_{2}) = g_{2} (c_{1}, c_{2}) + ε$ and

$g_{1}^{'} (c_{1}) = g_{1}^{'} (c_{2}) = 0$ ,

g_{2} (c_{1}, c_{2}) < g_{1}^{'} (c_{1}, c_{2})

and

g_{2} (c_{1}, c_{2}) ⩽ b_{1}

. Therefore, from the nonarbitrary hoarding property, player 2 can be allocated the 2-item bundle only if

g_{2} (c_{1}, c_{2}) = b_{1}

. However,

b_{1} = g_{2} (c_{1}, c_{2}) < g_{1}^{'} (c_{1}, c_{2})

and therefore the price would be

p_{2} (c_{1}, c_{2}) = min {b_{1}, g_{1}^{'} (c_{1}, c_{2})} = b_{1} = g_{2} (c_{1}, c_{2})

. That is, if player 2 states the true valuations and is allocated the 2-item bundle, then both players’ utility is 0. This allocation is not Pareto optimal as allocating the 2-item bundle to player 1 for the same price

b_{1}

strictly increase player 1’s utility while player 2 and the auctioneer are indifferent.

Suppose that each player is allocated a singleton and without the loss of generality assume that $B_{2}^{'} = {c_{2}}$ and $B_{1}^{'} = {c_{1}}$ . Then from Theorem 3.2 it follows that $p (B_{2}^{'}) ⩾ g_{1}^{'} (c_{1}, c_{2}) - g_{1}^{'} (c_{1}) = g_{2} (c_{1}, c_{2}) + ε$ . However, from free disposal this contradicts IR for player 2. Therefore player 1 must still be allocated the 2-item bundle for a lower price. Thus any price higher than $g_{2} (c_{1}, c_{2})$ is not truthful.

$B_{1} = {c_{1}}$ and $B_{2} = {c_{2}}$ .

Suppose to the contrary that $p (B_{2}) > g_{1} (c_{1}, c_{2}) - g_{1} (c_{1})$ .

Assume that $p (B_{2}) = g_{1} (c_{1}, c_{2}) - g_{1} (c_{1}) + 2 ε$ . From IR of player 2 it must be the case that: $v_{2} (B_{2}) ⩾ p (B_{2}) = g_{1} (c_{1}, c_{2}) - g_{1} (c_{1}) + 2 ε$ . We show that this price can not be truthful for player 2. Consider the following deviation for player 2:

$g_{2}^{'} (c_{2}) = g_{1} (c_{1}, c_{2}) - g_{1} (c_{1}) + ε$ ,

$g_{2}^{'} (c_{1}) = 0$ ,

$g_{2}^{'} (c_{1}, c_{2}) = g_{1} (c_{1}, c_{2}) + \frac{ε}{2}$ .

Allocating both items to player 1 contradicts the nonarbitrary hoarding property as

g_{2}^{'} (c_{1}, c_{2}) > g_{1} (c_{1}, c_{2})

The allocation $B_{1}^{'} = {c_{2}}$ is not IR for player 1 as from Theorem 3.2 and the free disposal assumption it follows that $p (B_{1}^{'}) ⩾ g_{2}^{'} (c_{1}, c_{2}) - g_{2}^{'} (c_{1}) = g_{1} (c_{1}, c_{2}) + \frac{ε}{2} > g_{1} (c_{1}, c_{2}) ⩾ g_{1} (c_{2})$ .

We claim that allocating both items to player 2 is not Pareto optimal. Suppose that $G_{2}^{'} (V_{2})$ is true report of player 2’s valuations. We proved in case 1 above that if player 2 is allocated both items then the price must equal $min {b_{1}, g_{1} (c_{1}, c_{2})}$ . Therefore, if on one hand $g_{1} (c_{1}, c_{2}) ⩽ b_{1}$ then, player 2’s utility from such an allocation is $\frac{ε}{2}$ and player 1’s utility is zero. The allocation $B_{1}^{″} = {c_{1}}$ , $p (B_{1}^{″}) = g_{1} (c_{1})$ , $B_{2}^{″} = {c_{2}}$ and $p (B_{2}^{″}) = g_{1} (c_{1}, c_{2}) - g_{1} (c_{1})$ is strictly better for player 2 as $u_{2}^{″} = g_{2}^{'} (c_{2}) - g_{1} (c_{1}, c_{2}) + g_{1} (c_{1}) = ε > \frac{ε}{2} = u_{2}^{'}$ , while player 1 and the auctioneer are indifferent.

If on the other hand $g_{1} (c_{1}, c_{2}) > b_{1}$ then the utility of player 2 from such an allocation is $v_{1} (c_{1}, c_{2}) + \frac{ε}{2} - b_{1}$ and the utility of player 1 is zero. The allocation $B_{1}^{‴} = {c_{1}}$ , $p (B_{1}^{‴}) = g_{1}^{'} (c_{1})$ , $B_{2}^{‴} = {c_{2}}$ and $p (B_{2}^{‴}) = b_{1} - v_{1} (c_{1})$ is strictly better for player 2 as $u_{2}^{‴} = g_{2}^{'} (c_{2}) - b_{1} + v_{1} (c_{1}) = v_{1} (c_{1}, c_{2}) + ε - b_{1} > v_{1} (c_{1}, c_{2}) + \frac{ε}{2} - b_{1} = u_{2}^{'}$ while player 1 and the auctioneer are indifferent.

Therefore player 2 must still be allocated $B_{2} = {c_{2}}$ for a price lower than $g_{1} (c_{1}, c_{2}) - g_{1} (c_{1}) + 2 ε$ . Thus any price higher than $g_{1} (c_{1}, c_{2}) - g_{1} (c_{1})$ is not truthful for player 2.

Suppose to the contrary that $p (B_{1}) > g_{2} (c_{1}, c_{2}) - g_{2} (c_{2})$ .

Assume that $p (B_{1}) = g_{2} (c_{1}, c_{2}) - g_{2} (c_{2}) + 2 ε$ . From IR of player 1 it must be the case that: $v_{1} (B_{1}) ⩾ p (B_{1}) = g_{2} (c_{1}, c_{2}) - g_{2} (c_{2}) + 2 ε$ . We claim that this scenario is not truthful for player 1. Consider the following deviation for player 1:

$g_{1}^{'} (c_{1}) = g_{2} (c_{1}, c_{2}) - g_{2} (c_{2}) + ε$ ,

$g_{1}^{'} (c_{2}) = 0$ ,

$g_{1}^{'} (c_{1}, c_{2}) = g_{2} (c_{1}, c_{2}) + \frac{ε}{2}$ .

From nonarbitrary hoarding, as

g_{1}^{'} (c_{1}, c_{2}) > g_{2} (c_{1}, c_{2})

, allocating both items to player 2 might satisfy the other properties only if

g_{1}^{'} (c_{1}, c_{2}) > g_{2} (c_{1}, c_{2}) > b_{1}

. However, if this is the case then allocating both items to player 2 is not Pareto optimal. Consider the allocation

B_{1}^{″} = {c_{1}}

p (B_{1}^{″}) = g_{1}^{'} (c_{1})

B_{2}^{″} = {c_{2}}

and

p (B_{2}^{″}) = b_{1} - g_{1}^{'} (c_{1})

. Then if the players state true valuations, then player 1’s utility is 0 as before and the auctioneer’s utility is unchanged. Player 2’s utility is strictly increased as

u_{2}^{″} = g_{2} (c_{2}) - b_{1} + g_{1}^{'} (c_{1}) = g_{2} (c_{2}) - b_{1} + g_{2} (c_{1}, c_{2}) - g_{2} (c_{2}) + ε > g_{2} (c_{1}, c_{2}) - b_{1} = u_{2}^{'}

The allocation $B_{2}^{'} = {c_{1}}$ is not IR for player 2 as from Theorem 3.2 and free disposal assumption it follows that $p (B_{2}^{'}) ⩾ g_{1}^{'} (c_{1}, c_{2}) - g_{1}^{'} (c_{2}) = g_{2} (c_{1}, c_{2}) + \frac{ε}{2} > g_{2} (c_{1}, c_{2}) ⩾ g_{2} (c_{1})$ . Allocating both items to player 1 is not Pareto. We proved in case 2 above that if player 1 is allocated both items then the price must equal $g_{2} (c_{1}, c_{2})$ . Therefore player 1’s utility from such an allocation is $\frac{ε}{2}$ and player 2’s utility is zero. The allocation $B_{1}^{‴} = {c_{1}}$ , $p (B_{1}^{‴}) = g_{2} (c_{1}, c_{2}) - g_{2} (c_{2})$ , $B_{2}^{‴} = {c_{2}}$ and $p (B_{2}^{‴}) = g_{2} (c_{2})$ is strictly better for player 1 as $u_{1}^{‴} = g_{1}^{'} (c_{1}) - g_{2} (c_{1}, c_{2}) + g_{2} (c_{2}) = ε > \frac{ε}{2} = u_{1}^{'}$ . Player 2 and the auctioneer are indifferent. Therefore any mechanism must still allocate $B_{1} = {c_{1}}$ for a price lower than $g_{2} (c_{1}, c_{2}) - g_{2} (c_{2}) + 2 \cdot ε$ . Thus any price higher than $g_{2} (c_{1}, c_{2}) - g_{2} (c_{2})$ is not truthful for player 1.

The proof for the case $B_{1} = {c_{2}}$ and $B_{2} = {c_{1}}$ is equivalent to the proof of the case $B_{1} = {c_{1}}$ and $B_{2} = {c_{2}}$ above. □

3.3. Implications of Pareto optimality

In the next two lemmas we analyze the implications of the Pareto optimality property on the allocations of the 2-item bundle to the different players. In the following section we will use the Pareto optimality implications to show that without assuming any additional public knowledge there is no mechanism $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})$ that satisfies the four properties.

Lemma 3.4.
In any mechanism that satisfies the properties of IR, truthfulness, Pareto optimality, and nonarbitrary hoarding, if $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}) = (B_{1} = \emptyset, B_{2} = {c_{1}, c_{2}}, p (B_{1}) = 0, p (B_{2}))$ , then Pareto optimality implies that: $g_{2} (c_{1}, c_{2}) - g_{2} (c_{2}) ⩾ min {b_{1}, g_{1} (c_{1})}$ and $g_{2} (c_{1}, c_{2}) - g_{2} (c_{1}) ⩾ min {b_{1}, g_{1} (c_{2})}$ .
Proof of Lemma 3.4.
Suppose to the contrary that F satisfies the four properties, $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}) = (B_{1} = \emptyset, B_{2} = {c_{1}, c_{2}}, p (B_{1}) = 0, p (B_{2}))$ ; and $g_{2} (c_{1}, c_{2}) - g_{2} (c_{2}) < min {b_{1}, g_{1} (c_{1})}$ . Then from Lemma 3.3 we know that $p (B_{2}) = min {b_{1}, g_{1} (c_{1}, c_{2})}$ . We show that this allocation is not Pareto Optimal. Suppose that $G_{2} (V_{2})$ are true valuations, then $u_{2} = g_{2} (c_{1}, c_{2}) - min {b_{1}, g_{1} (c_{1}, c_{2})}$ and $u_{1} = 0$ . The allocation $B_{1}^{'} = {c_{1}}$ and $B_{2}^{'} = {c_{2}}$ with the prices $p (B_{1}^{'}) = min {b_{1}, g_{1} (c_{1})}$ and $p (B_{2}^{'}) = min {b_{1}, g_{1} (c_{1}, c_{2})} - min {b_{1}, g_{1} (c_{1})}$ is strictly better for player 2, better or equal for player 1 and equal for the auctioneer as:
$u_{1}^{'} = g_{1} (c_{1}) - min {b_{1}, g_{1} (c_{1})} ⩾ 0 = u_{1}$ .

$u_{2}^{'} = g_{2} (c_{2}) - min {b_{1}, g_{1} (c_{1}, c_{2})} + min {b_{1}, g_{1} (c_{1})}$ . From the assumption that $g_{2} (c_{1}, c_{2}) - g_{2} (c_{2}) < min {b_{1}, g_{1} (c_{1})}$ we conclude that $g_{2} (c_{1}, c_{2}) < g_{2} (c_{2}) + min {b_{1}, g_{1} (c_{1})}$ . Thus, $u_{2}^{'} = g_{2} (c_{2}) - min {b_{1}, g_{1} (c_{1}, c_{2})} + min {b_{1}, g_{1} (c_{1})} > g_{2} (c_{1}, c_{2}) - min {b_{1}, g_{1} (c_{1}, c_{2})} = u_{2}$ .

$p (B_{1}) + p (B_{2}) = p (B_{1}^{'}) + p (B_{2}^{'})$ .
This contradicts the assumption that the allocation is Pareto optimal. The proof that $g_{2} (c_{1}, c_{2}) - g_{2} (c_{1}) ⩾ min {b_{1}, g_{1} (c_{2})}$ is equivalent. □
Lemma 3.5.
In any mechanism F that satisfies the properties of IR, truthfulness, Pareto optimality, and nonarbitrary hoarding, if $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}) = (B_{1} = {c_{1}, c_{2}}, B_{2} = \emptyset, p (B_{1}), p (B_{2}) = 0)$ , then Pareto optimality implies that $g_{1} (c_{1}, c_{2}) - g_{1} (c_{2}) ⩾ g_{2} (c_{1})$ and $g_{1} (c_{1}, c_{2}) - g_{1} (c_{1}) ⩾ g_{2} (c_{2})$ .
Proof of Lemma 3.5.
Suppose to the contrary that a mechanism F satisfies the four properties, $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1}) = (B_{1} = {c_{1}, c_{2}}, B_{2} = \emptyset, p (B_{1}), p (B_{2}) = 0)$ , however $g_{1} (c_{1}, c_{2}) - g_{1} (c_{1}) < g_{2} (c_{2})$ . From Lemma 3.3 we know that $p (B_{1}) = g_{2} (c_{1}, c_{2})$ . We show that Pareto Optimality does not hold. Suppose that $G_{1} (V_{1})$ are true valuations. Then, $u_{1} = g_{1} (c_{1}, c_{2}) - g_{2} (c_{1}, c_{2})$ and $u_{2} = 0$ . The allocation $B_{1}^{'} = {c_{1}}$ and $B_{2}^{'} = {c_{2}}$ with the prices $p (B_{1}^{'}) = g_{2} (c_{1}, c_{2}) - g_{2} (c_{2})$ and $p (B_{2}^{'}) = g_{2} (c_{2})$ is strictly better for player 1 while player 2 and the auctioneer are indifferent as:
$u_{1}^{'} = g_{1} (c_{1}) - g_{2} (c_{1}, c_{2}) + g_{2} (c_{2}) > g_{1} (c_{1}, c_{2}) - g_{2} (c_{1}, c_{2}) = u_{1}$ , follows from the assumption that $g_{1} (c_{1}, c_{2}) - g_{1} (c_{1}) < g_{2} (c_{2})$ .

$u_{2}^{'} = g_{2} (c_{2}) - g_{2} (c_{2}) = 0 = u_{2}$ .

$p (B_{1}) + p (B_{2}) = p (B_{1}^{'}) + p (B_{2}^{'})$ .
This contradicts the assumption that the allocation is Pareto optimal. The proof that $g_{1} (c_{1}, c_{2}) - g_{1} (c_{2}) < g_{2} (c_{1})$ is equivalent. □

4. The possibility space

In this section we define the possibility space; We show that if certain restrictions on the private valuations are publicly known, then there is a unique mechanism or a family of mechanisms that satisfies the properties, IR, truthfulness, Pareto optimality, and nonarbitrary hoarding. We show that these mechanisms are either VCG prices or dictatorship with player 2 as the dictator.

4.1. Mapping the space

We claim that there are two sets of restrictions on the valuation functions. One of them implies VCG families of mechanisms while the other implies dictatorship. We start by mapping under which conditions any mechanism F that satisfies the properties will allocate singletons and be a trivial pricing mechanism. Then we continue by mapping under which conditions any mechanism F that satisfies the properties will allocate singletons and be a VCG mechanism. From the above mapping we then conclude what public knowledge is needed in order to imply VCG mechanism and what public knowledge is needed in order to imply dictatorship mechanism.

Lemma 4.1.
If the following conditions hold:

$g_{2} (c_{1}, c_{2}) - g_{2} (c_{2}) < min {b_{1}, g_{1} (c_{1})}$ and

$g_{1} (c_{1}, c_{2}) - g_{1} (c_{1}) < g_{2} (c_{2})$ and

$g_{2} (c_{1}, c_{2}) - g_{2} (c_{1}) > min {b_{1}, g_{1} (c_{2})}$ and

$b_{1} - g_{2} (c_{1}, c_{2}) + g_{2} (c_{2}) < g_{1} (c_{1}, c_{2}) - g_{1} (c_{1})$
or

$g_{2} (c_{1}, c_{2}) - g_{2} (c_{1}) < min {b_{1}, g_{1} (c_{2})}$ and

$g_{1} (c_{1}, c_{2}) - g_{1} (c_{2}) < g_{2} (c_{1})$ and

$g_{2} (c_{1}, c_{2}) - g_{2} (c_{2}) > min {b_{1}, g_{1} (c_{1})}$ and

$b_{1} - g_{2} (c_{1}, c_{2}) + g_{2} (c_{1}) < g_{1} (c_{1}, c_{2}) - g_{1} (c_{2})$ .
Then any mechanism F that satisfies the properties of IR, truthfulness, Pareto optimality, and nonarbitrary hoarding, must allocate $B_{1} = {c_{1}}$ , $B_{2} = {c_{2}}$ in case 1 or $B_{1} = {c_{2}}$ , $B_{2} = {c_{1}}$ in case 2 and F must be a trivial pricing mechanism.
Proof of Lemma 4.1.
We first show that if all the conditions in 1 hold then any mechanism F that satisfies the four properties must allocate $B_{1} = {c_{1}}$ and $B_{2} = {c_{2}}$ . Assume to the contrary that F is a nontrivial pricing mechanism. From Lemma 3.4 we conclude that condition 1.1 implies that there is no mechanism that satisfies the four properties and allocates both items to player 2. From Lemma 3.5 we conclude that condition 1.2 implies that there is no mechanism that satisfies the four properties and allocates both items to player 1. From Lemma 3.3 and condition 1.4 it follows that allocating $B_{1} = {c_{2}}$ is not IR for player 1. Therefore the allocation must be $B_{2} = {c_{2}}$ and $B_{1} = {c_{1}}$ .

From Lemma 3.3 we know that $p (B_{1}) = g_{2} (c_{1}, c_{2}) - g_{2} (c_{2})$ and $p (B_{2}) = g_{1} (c_{1}, c_{2}) - g_{1} (c_{1})$ . From condition 1.4 it follows that, if the reported values are true valuations, then $u_{2} = g_{2} (c_{2}) - g_{1} (c_{1}, c_{2}) + g_{1} (c_{1}) < g_{2} (c_{1}, c_{2}) - b_{1}$ . Therefore player 2 will be better off deviating to be allocated the 2-item bundle even for the highest price of $b_{1}$ . Note that in any nontrivial pricing mechanism if $B_{2} = {c_{1}, c_{2}}$ then Lemma 3.3 implies that $p (B_{2}) ⩽ b_{1}$ . Thus F must be a trivial pricing mechanism.

Similarly, it is easy to show that if all the conditions in 2 hold then any mechanism that satisfies the four properties must be a trivial pricing mechanism that allocates $B_{1} = {c_{2}}$ and $B_{2} = {c_{1}}$ . □
Lemma 4.2.
If the following conditions hold:

$g_{2} (c_{1}, c_{2}) - g_{2} (c_{2}) < min {b_{1}, g_{1} (c_{1})}$ and

$g_{1} (c_{1}, c_{2}) - g_{1} (c_{1}) < g_{2} (c_{2})$ and

$g_{2} (c_{1}, c_{2}) - g_{2} (c_{1}) > min {b_{1}, g_{1} (c_{2})}$ and

$b_{1} - g_{2} (c_{1}, c_{2}) + g_{2} (c_{2}) > g_{1} (c_{1}, c_{2}) - g_{1} (c_{1})$
or

$g_{2} (c_{1}, c_{2}) - g_{2} (c_{1}) < min {b_{1}, g_{1} (c_{2})}$ and

$g_{1} (c_{1}, c_{2}) - g_{1} (c_{2}) < g_{2} (c_{1})$ and

$g_{2} (c_{1}, c_{2}) - g_{2} (c_{2}) > min {b_{1}, g_{1} (c_{1})}$ and

$b_{1} - g_{2} (c_{1}, c_{2}) + g_{2} (c_{1}) > g_{1} (c_{1}, c_{2}) - g_{1} (c_{2})$ .
Then any mechanism F that satisfies the properties of IR, truthfulness, Pareto optimality, and nonarbitrary hoarding, must allocate $B_{1} = {c_{1}}$ and $B_{2} = {c_{2}}$ with VCG prices in case 1 or $B_{1} = {c_{2}}$ and $B_{2} = {c_{1}}$ with VCG prices in case 2 .
Proof of Lemma 4.2.
In Lemma 4.1 we showed that if conditions 1.1–1.4 hold then any mechanism that satisfies the four properties must allocate $B_{1} = {c_{1}}$ and $B_{2} = {c_{2}}$ . In Theorem 3.2 we showed that if the inequality in 1.4 holds then the mechanism is a nontrivial pricing mechanism. From Lemma 3.3 we conclude that the prices must be VCG prices.

Similarly, it is easy to show that if all the conditions in 2 hold, then any mechanism that satisfies the four properties must allocate $B_{1} = {c_{2}}$ and $B_{2} = {c_{1}}$ , with VCG prices. □
Conclusion 1.
From Lemma 4.1 and Lemma 4.2 we conclude that if it is publicly known that the conditions of Lemma 4.1 do not hold, then there is a mechanism that satisfies the properties and in any such mechanism the prices are VCG prices.
Conclusion 2.
From Conclusion 1 we further conclude that if it is publicly known that the following restrictions (R1 or R2) hold, then there is a mechanism that satisfies the properties and in any such mechanism the prices are VCG prices:
$v_{1} (c_{1}, c_{2}) ⩽ b_{1}$ 5
⁵
Note that under this restriction ¬1.4 and ¬4.4 in Lemma 4.1 hold.

or

$v_{1} (c_{1}, c_{2}) > b_{1}$ and $v_{2} (c_{1}, c_{2}) ⩽ b_{1}$ .6
⁶
Note that condition 1.2 in Lemma 4.1 with restriction R2 imply ¬1.4. Similarly, condition 2.2 in Lemma 4.1 with restriction R2 imply ¬2.4.

4.2. VCG mechanism – Possibility space

We show that if restrictions R1 and R2 are public knowledge (and thus $G_{i} (V_{i})$ functions are restricted accordingly) then VCG with prices $p (B_{i}) = g_{\hat{i}} (c_{1}, c_{2}) - g_{\hat{i}} (B_{\hat{i}})$ for every $i, \hat{i} \in {1, 2}$ , is the unique mechanism that satisfies the four properties.

Theorem 4.3.
If one of the above restrictions is public knowledge, that is:
$v_{1} (c_{1}, c_{2}) ⩽ b_{1}$ or

$v_{1} (c_{1}, c_{2}) > b_{1}$ and $v_{2} (c_{1}, c_{2}) ⩽ b_{1}$
then there is a unique auction mechanism $F (G_{1} (V_{1}), G_{2} (V_{2}), b_{1})$ that implies VCG prices and satisfies the properties of IR, truthfulness, Pareto optimality, and nonarbitrary hoarding. That is, the following mechanism is the only mechanism that satisfies the four properties: 7
⁷
Note that the cases of equality can be randomly chosen. In all cases of equality the players are indifferent to the alternative allocations. The only exceptions are cases 3.1 and 4.1 with restriction R2, that is, when allocation 1 is not feasible.

8
⁸
Note that if restriction R2 holds than the first allocation is never applied.

If the following conditions hold:
$g_{2} (c_{1}, c_{2}) ⩾ g_{1} (c_{1}, c_{2})$ ,

$g_{1} (c_{1}) < g_{2} (c_{1}, c_{2}) - g_{2} (c_{2})$ ,

$g_{1} (c_{2}) < g_{2} (c_{1}, c_{2}) - g_{2} (c_{1})$
then $B_{2} = {c_{1}, c_{2}}$ , $B_{1} = \emptyset$ , $p (B_{1}) = 0$ , and $p (B_{2}) = g_{1} (c_{1}, c_{2})$ .

If the following conditions hold:
$g_{1} (c_{1}, c_{2}) > g_{2} (c_{1}, c_{2})$ ,

$g_{2} (c_{1}) ⩽ g_{1} (c_{1}, c_{2}) - g_{1} (c_{2})$ ,

$g_{2} (c_{2}) ⩽ g_{1} (c_{1}, c_{2}) - g_{1} (c_{1})$
then $B_{1} = {c_{1}, c_{2}}$ , $B_{2} = \emptyset$ , $p (B_{1}) = g_{2} (c_{1}, c_{2})$ , and $p (B_{2}) = 0$ .

If the following conditions hold
$g_{2} (c_{1}, c_{2}) - g_{2} (c_{2}) ⩽ g_{1} (c_{1})$ ,

$g_{1} (c_{1}, c_{2}) - g_{1} (c_{1}) < g_{2} (c_{2})$ ,

$g_{2} (c_{1}) - g_{2} (c_{2}) ⩽ g_{1} (c_{1}) - g_{1} (c_{2})$
then $B_{1} = {c_{1}}$ , $B_{2} = {c_{2}}$ , $p (B_{1}) = g_{2} (c_{1}, c_{2}) - g_{2} (c_{2})$ , and $p (B_{2}) = g_{1} (c_{1}, c_{2}) - g_{1} (c_{1})$ .

If the following conditions hold
$g_{2} (c_{1}, c_{2}) - g_{2} (c_{1}) ⩽ g_{1} (c_{2})$ ,

$g_{1} (c_{1}, c_{2}) - g_{1} (c_{2}) < g_{2} (c_{1})$ ,

$g_{2} (c_{2}) - g_{2} (c_{1}) < g_{1} (c_{2}) - g_{1} (c_{1})$
then $B_{1} = {c_{2}}$ , $B_{2} = {c_{1}}$ , $p (B_{2}) = g_{1} (c_{1}, c_{2}) - g_{1} (c_{2})$ , and $p (B_{1}) = g_{2} (c_{1}, c_{2}) - g_{2} (c_{1})$ .

We divide the proof of Theorem 4.3 into two parts, one part is the sufficient side and the other part is the necessary side. Each part is divided to two subparts that refer to the two different public knowledge restrictions [R1] and [R2]. The sufficient part of the proof for restriction [R1] shows that if it is publicly known that $v_{1} (c_{1}, c_{2}) ⩽ b_{1}$ then the suggested mechanism satisfies the four properties. The sufficient part of the proof for restriction [R2] shows that if it is publicly known that ( $v_{1} (c_{1}, c_{2}) > b_{1}$ and $v_{2} (c_{1}, c_{2}) ⩽ b_{1}$ ) then the suggested mechanism satisfies the four properties. The necessary part of the proof for restriction [R1] shows that if it is publicly known that $v_{1} (c_{1}, c_{2}) ⩽ b_{1}$ then there is no other mechanism that satisfies the four properties and allocates differently. The necessary part of the proof for restriction [R2] shows that if it is publicly known that ( $v_{1} (c_{1}, c_{2}) > b_{1}$ and $v_{2} (c_{1}, c_{2}) ⩽ b_{1}$ ) then there is no other mechanism that satisfies the four properties and allocates differently.

We prove the second part (the necessity part) in two steps. We first show that if it is publicly known that restriction [R1] or [R2] holds, then any mechanism that satisfies the properties must adopt VCG prices. This part is directly implied from conclusion 2. To complete the uniqueness proof we show that if it is publicly known that either restriction [R1] or [R2] holds, then any pricing mechanism that satisfies the four properties and uses the VCG prices must satisfy all the conditions of each allocation.

The proof of Theorem 4.3 can be found in Appendix C.
4.3. Dictatorial mechanism – Possibility space

Theorem 4.3 proved that if R1 or R2 is publicly known then VCG is the only mechanism that satisfies the four properties. In this subsection we claim that if the following restriction is public knowledge:

$v_{1} (c_{1}, c_{2}) ⩾ b_{1}$ and $v_{1} (c_{1}) ⩾ b_{1}$ and $v_{1} (c_{2}) ⩾ b_{1}$

then there exists a unique family of dictatorial mechanisms that satisfies the four properties.

Theorem 4.4.
If R3 is publicly known, that is, $\forall B_{1} \neq \emptyset$ , $v_{1} (B_{1}) ⩾ b_{1}$ and $G_{1} (V_{1})$ is restricted correspondingly, then there is a unique dictatorial family with at least three outcomes, that satisfies the properties of IR, truthfulness, Pareto optimality, and nonarbitrary hoarding. In this dictatorial family, player 2 must be the dictator. The mechanisms in the family are differentiated by a price parameters, $b_{1} ⩾ y ⩾ 0$ , that determines the price paid by player 1 for any nonempty bundle. That is, the following family of mechanisms are the only mechanisms that satisfy the four properties: $\begin{array}{l} p (B_{1}) = \{\begin{matrix} 0 & if B_{1} = \emptyset, \\ y & otherwise, \end{matrix} \\ p (B_{2}) = \{\begin{matrix} b_{1} & if B_{2} = {c_{1}, c_{2}}, \\ 0 & otherwise . \end{matrix} \end{array}$

We use the following notation:
${Best}_{2} = {B \in arg {max}_{B_{2} \in B} (g_{2} (B_{2}) - p (B_{2}))}$ ,

${Best}_{1} = {B \in arg {max}_{C - B_{1} \in {Best}_{2}} (g_{1} (B_{1}) - p (B_{1}))}$ .

Then the allocation rule is to chose an allocation, $(B_{1}, B_{2} = C - B_{1}, p (B_{1}), p (B_{2}))$ , such that $B_{1} \in {Best}_{1}$ .

The proof of Theorem 4.4 is divided into two parts. In the first part we prove that if restriction [R3] is public knowledge then the suggested family of mechanisms satisfies the four properties. In the second part we prove that if it is publicly known that $\forall B_{1} \neq \emptyset$ , $v_{1} (B_{1}) ⩾ b_{1}$ , then there is no other dictatorial mechanism with at least three outputs that satisfies the four properties and allocates differently.

We prove the second part in several steps:

We show that from nonarbitrary hoarding and the dictatorship Definition 2.4 it follows that player 2 is the only possible dictator.

We show that player 2 must pay 0 for any singleton in any mechanism that satisfies the properties IR, Pareto optimality and truthfulness.

We show that player 2 will not pay more than $b_{1}$ for the 2-item bundle.

We show that from nonarbitrary hoarding and player 2’s truthfulness it follows that player 2 will not pay less than $b_{1}$ for the 2-item bundle.

We show that from player 1’s truthfulness it follows that the prices of player 1’s nonempty bundles must be identical. The price y paid by player 1 is derived directly from player 1’s IR.

Theorem 4.4’s proof can be found in Appendix D.
4.4. Take home point example – Revisited

Recall our take hope point example in Section 1.2. Two telecommunications companies $T_{1}$ and $T_{2}$ are competing over bandwidth in a region with two distinct broadcast bands $c_{1}$ and $c_{2}$ . Company $T_{1}$ has a limited budget b of $500,000 to spend on bandwidth. On the other hand company $T_{2}$ is a large telecommunications company with practically unlimited funds to spend on the discussed region. If company $T_{1}$ does not value taking control of all the bandwidth available in the region more than b, i.e., $v_{T_{1}} (c_{1}, c_{2}) = 300000 ⩽ 500000 = b$ , then $T_{1}$ and $T_{2}$ ’s bandwidth allocation will be determined and priced by VCG. Meaning, if $v_{T_{2}} (c_{1}) = 200000$ or $v_{T_{2}} (c_{2}) = 200000$ and $v_{T_{2}} (c_{1}, c_{2}) = 600000$ then $B_{T_{2}} = {c_{1}, c_{2}}$ and $p (B_{T_{2}}) = 300000$ . If company $T_{2}$ does not value taking control of all of the bandwidth available in the region more than b, i.e., $v_{T_{2}} (c_{1}, c_{2}) = 400000 ⩽ 500000 = b$ , then despite the fact that company $T_{1}$ might be interested in taking control of all of the available bandwidth for more money than its budget, $T_{1}$ and $T_{2}$ ’s bandwidth allocation will be determined and priced by VCG. Meaning, if $v_{T_{1}} (c_{1}) = 400000$ or $v_{T_{1}} (c_{2}) = 400000$ and $v_{T_{1}} (c_{1}, c_{2}) = 550000$ then $B_{T_{1}} = {c_{1}}$ or $B_{T_{1}} = {c_{2}}$ and $p (B_{T_{1}}) = 200000$ and $B_{T_{2}} = {c_{1}}$ or $B_{T_{2}} = {c_{2}}$ and $p (B_{T_{2}}) = 50000$ . Most interestingly, if company $T_{1}$ would like to acquire any bandwidth in the region and values all such options more than its budget b, i.e., $v_{T_{1}} (c_{1}, c_{2}) = 800000 > 500000 = b$ then $T_{2}$ becomes the dictator and receives its most beneficial single bandwidth allocation for free, i.e., $B_{T_{2}} = {c_{1}}$ if $v_{T_{2}} (c_{1}) > v_{T_{2}} (c_{2})$ and $B_{T_{2}} = {c_{2}}$ if $v_{T_{2}} (c_{1}) < v_{T_{2}} (c_{2})$ and $p (B_{T_{2}}) = 0$ , regardless of any high values stated by company $T_{1}$ .

5. Conclusions

Indeed there may be a gap between the 2 × 2 model and a model with more than two players or items, i.e., with more possible outcomes. However, the literature tends to indicate that a four outcome model can capture the complexity of the n player, m items outcome model (for any finite n and m) of the multidimensional combinatorial auction possibility space, as indicated by Roberts’ characterization of the complete preference domain space, [25].

In Roberts’ result a three outcome model captures the complexity of the whole n outcome possibility space of the preference multidimensional space for any finite n. Hence, we believe that extending our model to more players and more items will not introduce new types of possible mechanisms to the space. We leave the extension of our proof for future research.

Footnotes

Prior literature

In recent years several papers studied budget-constrained combinatorial auctions. [21] characterized some of the space of deterministic, dominant-strategy incentive compatible, individually rational, and Pareto optimal budget-constrained combinatorial auctions and showed that the space studied essentially includes one type of mechanisms that behave dictatorially. [9] showed that there does not exist a deterministic auction that is individually rational, dominant-strategy incentive compatible, and Pareto optimal with potentially negative prices and privately known budgets, even when players are one-dimensional types. [11] showed that the same impossibility holds for one-dimensional types with different items and publicly known multi-item demand. [19] also showed the same impossibility with publicly known budgets if multidimensional types (two identical items with three outcomes) are considered.

[9,11,19] allow negative prices to exist, i.e., some players are paid for participation in the auction either by the mechanism or by the other players. Practical auction implementations such as the FCC bandwidth auction usually can not afford or are unwilling to consider paying bidders (telecommunications companies) for their participation nor are they interested in encouraging side payments among the participants. Therefore similar to [22]’s model we chose to assume that all prices are nonnegative. The assumption that all prices are nonnegative narrows down the domain of possible allocations in comparison with the potential negative prices model with multidimensional types. Nevertheless some of the mechanisms which fulfill the three properties of dominant strategy incentive compatible, individually rational, and Pareto optimal in the nonnegative price model are not included in the mechanism space that fulfills the same properties in the negative price model. The reason for the above is the property of Pareto optimality. Since the nonnegative prices model has a smaller set of possible allocations there exist situations where a mechanism does not fulfill the Pareto optimal property in the model with negative prices but does fulfill the Pareto optimal property in the nonnegative price model.

[9] also characterizes the possibility space of dominant-strategy incentive compatibility and Pareto optimal budget-constrained combinatorial auction mechanisms, [9]’s characterization is restricted to one-dimensional types and therefore their possibility space characterization does not imply the possibility space in our model with multidimensional types. More specifically, [9] showed that for multi-unit demand and identical items, Ausubel’s clinching auction, which assumes public budgets and additive valuations, uniquely satisfies the properties (described above). In a similar model with small randomized modification [5] showed that [9]’s result can be obtained with private budgets. Similarly Ausubel’s clinching auction was concluded by [11] for one-dimensional types with different items and publicly known multi-item demand. For unit-demand players with private values and budget constraints in the one-dimensional types model there are several deterministic mechanisms that fulfill the properties of incentive compatible and Pareto optimality (see [2]). In nondeterministic mechanisms with a one-dimensional types model (one indivisible unit) [22] characterizes constrained-efficiency mechanisms, which are mechanisms that maximize the expected social welfare under Bayesian incentive compatibility and budget constraints in a nonnegative price model.

There are few other works that focus on revenue maximization under budget constraints. [4,7] analyzes how budgets change the classic results on “standard” auction formats, showing for example that first-price auctions raise more revenue than second-price auctions when bidders are budget-constrained, and that the revenue of a sequential auction is higher than the revenue of a simultaneous ascending auction. [18,24] constructs single-item auctions that maximize the seller’s revenue.

Proof of Theorem 3.2

Proof of Theorem 4.3

Proof of Theorem 4.4

References

K.J.

Arrow, A difficulty in the concept of social welfare, J. Polit. Econ. 58(4) (1950), 328–346. doi:10.1086/256963.

Ashlagi,

Braverman,

Hassidim,

Lavi and

Tennenholtz, Position auctions with budgets: Existence and uniqueness, The B.E. Journal of Theoretical Economics (Advances) 10(1) (2010).

Bartal,

Gonen and

Nisan, Incentive compatible multi-unit combinatorial auctions, in: Proc. of TARK, 2003, pp. 72–87. doi:10.1145/846241.846250.

J.P.

Benoit and

Krishna, Multiple object auctions with budget constrained bidders, Review of Economic Studies 68(1) (2001), 155–179. doi:10.1111/1467-937X.00164.

Bhattacharya,

Conitzer,

Munagala and

Xiax, Incentive compatible budget elicitation in multi-unit auctions, in: Proc. of SODA, 2010.

Budish and

Cantillon, The multi-unit assignment problem: Theory and evidence from course allocation at Harvard, American Economic Review 102(5) (2012), 2237–2271. doi:10.1257/aer.102.5.2237.

Y.K.

Che and

Gale, Standard auctions with financially constrained bidders, Review of Economic Studies 65, 1–21. doi:10.1111/1467-937X.00033.

E.H.

Clarke, Multipart pricing of public goods, in: Journal Public Choice, Vol. 2, 1971, pp. 17–33.

Dobzinski,

Lavi and

Nisan, Multi-unit auctions with budget limits, Games Econ. Behav. 74 (2012), 486–503. doi:10.1016/j.geb.2011.08.003.

10.

Dobzinski and

Nisan, Multi-unit auctions: Beyond Roberts, in: Proc. of EC’11, 1971, pp. 233–242.

11.

Fiat,

Leonardi,

Saia and

Sankowski, Combinatorial auctions with budgets, in: Proc. of EC’11, 2011.

12.

Gibbard, Manipulation of voting schemes: A general result, J. Econometrica 41 (1973), 587–601. doi:10.2307/1914083.

13.

Gonen and

Lerner, The incompatibility of Pareto optimality and incentive compatibility in quasi-linear settings with anonymous and budget constrained players, Games 4 (2013), 690–710. doi:10.3390/g4040690.

14.

Green and

Laffont, Characterization of satisfactory mechanisms for the revelation of preferences for public goods, J. Econometrica 45 (1977), 427–438. doi:10.2307/1911219.

15.

Groves, Incentives in teams, J. Econometrica 41 (1973), 617–631. doi:10.2307/1914085.

16.

J.W.

Hatfield, Strategy-proof, efficient, and non bossy quota allocations, Soc. Choice Welfare 33 (2009), 505–515. doi:10.1007/s00355-009-0376-6.

17.

Holmstrom, Groves’ scheme on restricted domains, J. Econometrica 47 (1979), 1137–1144. doi:10.2307/1911954.

18.

J.J.

Laffont and

Robert, Optimal auction with financially constrained buyers, Economics Letters 52(2) (1996), 181–186. doi:10.1016/S0165-1765(96)00849-X.

19.

Lavi and

May, A note on the incompatibility of strategy-proofness and Pareto-optimality in quasi-linear settings with public budgets, Econ. Lett. 115 (2012), 100–103. doi:10.1016/j.econlet.2011.11.043.

20.

Lehmann,

L.I.

O’Callaghan and

Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of ACM 49(5) (2002), 577–602. doi:10.1145/585265.585266.

21.

Lerner and

Gonen, Dictatorial mechanisms in constrained combinatorial auctions, The B.E. Journal of Theoretical Economics 13(1) (2013).

22.

E.S.

Maskin, Auctions, development and privatization: Efficient auctions with liquidity-constrained buyers, European Economic Review 44(4–6) (2000), 667–681. doi:10.1016/S0014-2921(00)00057-X.

23.

Nisan and

Ronen, Computationally feasible VCG-based mechanisms, Journal of Artificial Intelligence Research 29 (2007), 19–47.

24.

M.M.

Pai and

Vohra, Optimal auctions with financially constrained bidders, Working paper.

25.

Roberts, The characterization of implementable choice rules, in: Aggregation and Revelation of Preferences,

J.-J.

Laffont, ed., 1979.

26.

Satterthwaite, Strategy-proofness and arrow’s condition: Existence and correspondence theorems for voting procedures and social welfare functions, Journal of Economic Theory 10(2) (1975), 187–217.

27.

Vickrey, Counterspeculation, auctions and competitive sealed tenders, Journal of Finance 16 (1961), 8–37.

Characterizing incentive compatible,Pareto optimal and sufficiently anonymous constrained combinatorial mechanisms – Two players case

Abstract

Keywords

1. Introduction

1 Multidimensional types, meaning that a player may have a separate arbitrary value for each of the four possible outcomes.

1.2. Take home point and example

1.3. Paper organization

2. Notation and definitions

Definition 2.4 (Dictatorship).

Definition 2.5 (Trivial pricing mechanism).

Definition 2.6 (Property 1: Individual Rationality (IR)).

Definition 2.7 (Property 2: Nonarbitrary hoarding).

Definition 2.8 (Property 3: Pareto optimality).

Definition 2.9 (Property 4: Truthfulness).

3. The properties’ implications

3.1. Stability

Definition 3.1 (Stability).

4 In cases of singleton allocations p ( B 2 ) = b 1 − p ( B 1 ) implies a trivial pricing mechanism.

4.1. Mapping the space

5. Conclusions

Footnotes

Prior literature

Proof of Theorem 3.2

Proof of Theorem 4.3

Proof of Theorem 4.4

References

¹
Multidimensional types, meaning that a player may have a separate arbitrary value for each of the four possible outcomes.

⁴
In cases of singleton allocations $p (B_{2}) = b_{1} - p (B_{1})$ implies a trivial pricing mechanism.