Journal of Economic Theory 107, 377–406 (2002)doi:10.1006/jeth.2001.2957
The Package Assignment Model1
1 We are grateful to Louis Makowski, John Mamer, Uzi Segal, participants at variousseminars, and the referee and associate editor for helpful comments.
Sushil Bikhchandani
Anderson School of Management, University of California, Los Angeles, California [email protected]
and
Joseph M. Ostroy
Department of Economics, University of California, Los Angeles, California [email protected]
To better understand the properties of models with multiple indivisibleobjects, we consider them as extensions of the canonical standard assign-ment model in which each buyer and seller is restricted to trade at most oneobject (Koopmans and Beckman [16], Gale [12], Shapley and Shubik[23]). When there is only one seller, the standard assignment model is thesetting for the well-known single-object auction (Vickrey [24]). We areespecially interested in those extensions which, when specialized to a singleseller, lead to models of multi-object auctions.
The standard assignment model exhibits a generalization of Vickrey’ssealed bid single object auction that is truth-telling for buyers (or sellers,but not typically both) and an ascending (descending) price auction that isincentive compatible for buyers (sellers) (Crawford and Knoer [7],Leonard [17], Demange and Gale [9], Demange et al. [10], and Gretskyet al. [13]).2
2 Asymmetry with respect to incentive compatibility is frequently built into auction theoryby regarding the single seller as, for example, a government with less self-interested motivesthan the buyers.
Linear programming has been applied to the standard assignment model,with the following remarkable results (see references in previous para-graphs):
There is a linear programming characterization of the standardassignment model yielding optimal solutions to the underlying integer pro-gramming problem.
The primal and dual solutions of the linear program coincide withprice-taking Walrasian equilibrium and with the core. Moreover, these dual(=core) solutions form a lattice.
A corner of the lattice/core corresponds to those allocations, calledthe Vickrey payoff point below, at which buyers would have the incentiveto truthfully represent their characteristics in a sealed bid auction or in anascending price auction.
We extend the price characterization of efficient allocations in the standardassignment problem to the package assignment model. These characteriza-tions will be based on linear programming. Then, from the perspective ofthe package assignment model, we address the problem of incentive com-patibility in the single seller case, where we derive a necessary and sufficientcondition under which the Vickrey payoff point can be implemented as atruth-telling price equilibrium.
The package assignment model was first investigated by Kelso andCrawford [15], who obtained sufficient conditions for existence of Walra-sian equilibrium. Gul and Stacchetti [14] obtained equivalent sufficientconditions for existence of equilibrium and showed that under this condi-tion the core has the lattice property. Bikhchandani and Mamer [4] gave alinear programming characterization of the package assignment model.These papers made the usual assumption that the prices of packages are thesum of the prices of the objects contained in it, i.e., linear prices. The pointof departure in our paper is to consider pricing functions which are non-additive over objects and also possibly non-anonymous.
At first glance this non-linearity may appear incompatible with linearprogramming. A package of objects, however, may be regarded as an
378 BIKHCHANDANI AND OSTROY
‘‘activity’’ whose valuation need not be the sum of its component activities.Similarly, non-linearity may appear incompatible with Walrasian equilib-rium which normally presumes that pricing is linear. We broaden the defi-nition to include non-linear and non-anonymous pricing schemes. In thisrespect, we follow Makowski [19]. We shall use the term pricing equilib-rium to describe such schemes.
The need for non-linear pricing, both for characterizing efficiency andfor establishing incentive compatibility, originates from the small numbersof participants. Otherwise, the ‘‘convexifying effect of large numbers’’implies that price characterizations of efficiency would lead to linearitydespite the presence of indivisibilities (non-convexities). Similarly, as eachbuyer may purchase a non-negligible number of objects when the numberof other buyers is small, the opportunity cost principle underlying Vickreypayments results in non-linear pricing. Because our attention is limited toproblems posed by small numbers and the absence of perfect competition,we do not confine ourselves to linear price models.
A summary of the results comparing the package to the standardassignment model are described below. As in the standard assignmentmodel:
• Pricing equilibrium in the package asignment model exists if andonly if the associated primal linear programming problem has an integer-valued solution (in which case the dual solutions form the set of pricingequilibria).
In line with the different notion of pricing:
• The prices of packages may be non-linear (i.e., non-additive withrespect to the prices of the objects they contain) or non-anonymous (i.e.,depend on the pair of traders). There are package assignment models forwhich only non-linear and non-anonymous price equilibria exist.
But without further restrictions, a dual solution compatible with an integer-valued solution to the primal (pricing equilibrium) need not exist; indeed,the core may be empty. Moreover, when pricing equilibria do exist, the setof pricing equilibria is contained in the core, but the set of pricing equi-libria may not fill out the core. Further, these prices need not form alattice.
By considering a class of linear programming problems whose dualspermit non-linearities with respect to objects, a pricing equilibrium is notguaranteed but the class of models for which there exist price characteriza-tions of optimal solutions is enlarged and we move closer to the pricingschemes underlying demand revelation.
PACKAGE ASSIGNMENT MODEL 379
When the package model is restricted to one seller, the setting for themulti-object auction, stronger results emerge:
• Pricing equilibria always exist. Moreover, they fill out the core.
Even though the core is priced in the single seller model, the Vickrey payoffpoint may lie outside; hence all such pricing(=core) equilibria may bemanipulable. The following condition is critical to the placement of theVickrey point. Say that buyers are substitutes if the change in the gainsfrom trade resulting from the withdrawal of a group of buyers is at least aslarge as the sum of the changes caused by the withdrawal of the individualbuyers in the group. Shapley [22] demonstrated that the standard assign-ment model has this property. Our main incentive compatibility result is:
• The Vickrey payoff point is a pricing equilibrium if and only ifbuyers are substitutes.
Consequently, when buyers are substitutes there exists a pricing equilib-rium which is the outcome of a non-manipulable sealed-bid auction for thesingle seller package assignment model.
It is well-known that an ascending price auction for a single objectimplements the smallest Walrasian price. In the single seller model withhomogeneous objects, we show that the ascending price auction in Ausubel[1] implements a smallest pricing equilibrium. This generalization fromascending price auctions for single objects to multiple identical objectsrequires a generalization of Walrasian equilibrium which permits non-linear and non-anonymous prices.
Non-linearity can, of course, impose unreasonable computationaldemands. For example, if there are 100 objects, a ‘‘complete markets’’ listof package prices would contain 2100 items. With a small number of parti-cipants, however, an efficient allocation would require only a minute frac-tion of these packages. Therefore, it would be uneconomical to priceeverything; hence, the question of how to implement a non-linear scheme.The linear programming formulation will be used to describe computatio-nal issues and to suggest a practical implementation.
In Section 2, we describe four versions of the package assignment modeland define corresponding versions of pricing equilibrium. In Section 3 weestablish an equivalence between the existence of pricing equilibrium ineach of the four versions of the package assignment model and the exis-tence of integer optimal solutions to the corresponding linear programmingproblems. Section 4 describes the relation between the core and pricingequilibrium. In Section 5 we focus on the single seller model, and in Sec-tion 6 we provide necessary and sufficient conditions for the single sellermodel to exhibit truth-telling price equilibrium. Examples are giventhroughout to illustrate our results or to show why they cannot be
380 BIKHCHANDANI AND OSTROY
extended. Concluding remarks are contained in Section 7. Proofs are givenin an Appendix.
2. THE PACKAGE MODEL(S)
Buyers b=1, 2, ..., B are interested in purchasing packages of indivisibleobjects k=1, ..., K from sellers s=1, 2, ..., S. Let Z+ denote the set ofnonnegative integers. The initial endowment of indivisible objects withseller s is
Ws=(W1s, W2s, ..., Wks, ..., WKs) ¥ZK+.
The aggregate endowment in the economy is W=;Ss=1 Ws.
Buyers have utility over packages z and (divisible) money, m ¥R. Buyerb’s utility function is
Wb(z, m)=ub(z)+m, -z ¥ZK+,
where ub(z) is buyer b’s reservation value for z. Assume ub(0)=0 and ub( · )is weakly increasing. Buyer b has no endowment of the non-money com-modities but a large enough quantity of the money commodity ( > ub(W))to purchase any z [ W. It is convenient to assume that the buyer’s initialendowment of the money commodity is normalized to be zero and that thebuyer can supply any (negative) quantity required. Hence the utility of notrade for the buyer isWb(0, 0)=ub(0)+0=0.
Seller s’s utility function over the bundle (y, m), 0 [ y [ Ws, m ¥R, is
Ws(y, m)=m,
where y is the amounts of the K objects sold and m is the money receivedin exchange.3 The seller has no endowment of the money commodity and
3 The assumption that the sellers have zero reservation values for the objects may berelaxed. The results in this paper easily generalize to the case where seller’s reservation valuesare nonnegative and additive, i.e., Ws(y, m)=m−;K
k=1 ck yk.
therefore the utility of no trade for the seller is Ws(0, 0)=0.Rather than qualifying the domains on which sellers’ utility functions are
defined, we adopt the following convention which extends Ws( · , m) fromWs to ZK
+:
us(y) — ˛0 if y [ Ws,−. otherwise
Ws(y, m)=us(y)+m.
Let this economy be E(ub, -b, us, -s).
PACKAGE ASSIGNMENT MODEL 381
2.1. Resale Restrictions
The features of an equilibrium pricing system depend on resale restric-tions on buyers and on substitution possibilities among sellers. Withoutrestrictions on resale it would be difficult for a seller to price discriminate;but even with such restrictions, substitution possibilities among sellers maypreclude discriminatory pricing. Substitution possibilities are (implicitly)described by the tastes and endowments in an economy E. Each economyis further defined by its resale restrictions, Ej, that will range from ‘‘none’’to ‘‘complete’’ with two possibilities in between.
Each buyer buys S packages, one from each seller. (Since null packagesare allowed, the fact that a buyer must purchase a package from each selleris not a restriction.) Let zbs ¥ZK
+ denote a package that buyer b requestsfrom seller s and let Zb=(zb1, ..., zbS) denote a collection of such packages.Each seller brings B packages to the market, one for each buyer. Letybs ¥ZK
+ denote a package that seller s earmarks for buyer b and letYs=(y1s, ..., yBs) denote a collection of such packages.
Let Z=(Zb) denote the buyers’ collections of packages requested fromsellers and let Y=(Ys) denote the sellers’ collections of packages ear-marked for buyers. A necessary condition for the pair (Z, Y) to be feasibleis that each seller can supply his packages from his endowments, i.e., foreach s, Ys=(ybs) satisfies ; b ybs [ Ws.
To model resale restrictions in a static model, we consider more than oneway to describe the remaining condition for a feasible assignment, namelythat demand is (less than or) equal to supply. Think of the demands forand supplies of packages as arriving at a central clearinghouse. The differ-ent roles below that a clearinghouse might play in establishing feasibilitywill be interpreted as removing or enforcing restrictions on resale.4
4 Resale restrictions may be enforced by sellers or may arise naturally. An example of thelatter is the spot market portion of the California Power Exchange, a double auction in whichpower producers sell electricity to distribution companies. Heterogeneity is introduced by thetime and place (on the transmission grid) at which electricity is injected (by sellers) orwithdrawn (by buyers). There is the Day Ahead auction which is a futures market and theHour Ahead auction which is a spot market. As electricity cannot be stored easily, there arelimited resale opportunities after the Hour Ahead auction, whereas contracts traded in theDay Ahead auction could re-traded in subsequent auctions. (See Chao and Wilson [6].)
The pair (Z, Y) is a first order assignment if
Cw
1 C{bs: zbs=w}
zbs 2 [Cw
1 C{bs: ybs=w}
ybs 2 .
Note that ;w (; {bs: zbs=w} zbs) is simply another way to write ; b ; s zbs;similarly, ;w (; {bs: ybs=w} ybs) is the same as ; s ; b ybs. For a first orderassignment, the clearinghouse takes the most active role bundling and
382 BIKHCHANDANI AND OSTROY
unbundling the objects in the packages supplied to meet the demands.Therefore, the available supply of packages need only be sufficient in termsof the total number of objects ; s ; b ybs they contain so that they can berepackaged, if necessary, to satisfy the total requirements for objects; b ; s zbs contained in the demands for packages by buyers.
The pair (Z, Y) is a second order assignment if for every w
C{bs: zbs=w}
zbs [ C{bs: ybs=w}
ybs.
With a second order assignment, the clearinghouse takes a less active role.It is as if each package from a supplier arrives in a separate crate. Cratescannot be opened in the clearinghouse, as they can with a first orderassignment. But crates can be reassigned in the sense that a crate ear-marked by seller s for buyer b in Y can be reassigned as a package from s −
to b − to satisfy the demand in Z.The pair (Z, Y) is a third order assignment if for every b and every w
C{s: zbs=w}
zbs [ C{s: ybs=w}
ybs.
This is like a second order assignment in that packages supplied by sellerscannot be unbundled in the clearinghouse to satisfy the demands of buyers.Moreover, a crate assigned to buyer b has a lock which only b can open.But a ‘‘crate’’ earmarked by seller s for buyer b in Y may be reassigned as acrate from seller sŒ to the same buyer b to satisfy the demand in Z. Thus, athird order assignment is seller-anonymous.
The pair (Z, Y) is a fourth order assignment if for every b and s
zbs=ybs or 0.
Here, the clearinghouse takes the least active role: No reassembly or reas-signment of packages is permitted.5
5 One other type of assignment lying between second and fourth order assignments is: forevery s and every w, ; {b: zbs=w} zbs [; {b: ybs=w} ybs. This buyer-anonymous assignment, whichis the counter-part of third order assignment, does not add much to the four versions con-sidered above.
The more the clearing house intervenes in disassembling and reassembl-ing packages, the more it mimics removal of resale restrictions. And themore it intervenes, the easier it is to satisfy these inequalities: If (Z, Y) is aj order assignment, it is a j−1 order assignment, j=4, 3, 2.
The environment Ej is the conjunction of E with resale restrictions j.Below, we will sometimes refer to E without j, but only when the results donot depend on resale restrictions.
PACKAGE ASSIGNMENT MODEL 383
It will be convenient to extend the definition of utilities for packages toutilities for assignments by letting
Ub(Zb)=ub 1Cszbs 2 and Us(Ys)=us 1C
bybs 2 .
The utility of an assignment for a buyer is based on the total package thebuyer obtains after collecting the packages purchased from each of thesellers. For example, if the buyer purchases half of the books in a matchedcollection from one seller and the other half from another seller, the utilityis the same as if the entire collection were purchased from a single seller.The utility of an assignment for the seller is either zero or −.; althoughassignments that yield −. utility are unattainable by a seller, we do notexplicitly exclude these from the model.
A pair (Z, Y) is a j(=1, 2, 3, 4) order feasible assignment if it is a j orderassignment and Us(Ys)=0, -s. Thus, if (Z, Y) is j order feasible then; b ybs [ Ws, -s.
An efficient assignment of the non-money commodities in a model withquasilinear preferences is obtained by maximizing the sum total of utilitiesfor the non-money commodities. In the present case, efficiency in Ej isachieved by
v(Ej)=max(Z, Y)
3CbUb(Zb)+C
sUs(Ys)4 ,
subject to the constraint that (Z, Y) is a j order assignment.The assignments (Z, Y) and (Z −, Y −) are utility equivalent if Ub(Zb)=Ub(Z
−
b) for all b and Us(Ys)=Us(Y−
s) for all s. Even though the higher theorder, the smaller the set of feasible assignments, the added constraintsused to define second, third, and fourth order feasibility are not binding interms of their utility equivalents in reaching any final allocation. In otherwords, resale restrictions do not preclude any final allocations.
Lemma 2.1. If (Z, Y) is j order feasible, there is a utility equivalentassignment (Z −, Y −) that is j+1 order feasible, j=1, 2, 3.
To illustrate, for any first order feasible assignment one can construct autility equivalent fourth order feasible assignment by showing that eachbuyer’s total allocation in the first order asignment may be broken up intoS-packages, one from each seller.
Therefore,
v(E)=v(Ej), j=1, 2, 3, 4
384 BIKHCHANDANI AND OSTROY
is the maximum gains from an efficient allocation from the package modelEj no matter which definition of feasibility/resale restrictions is employed.
2.2. Pricing with Resale Restrictions
The different orders of feasibility have different implications not only forthe meaning of ‘‘demand=supply’’ but also for the role of prices. Letpbs(w) \ 0 be the amount of money that buyer b pays seller s for thepackage w (the amount of money seller s receives from buyer b for w).Thus, in the most general case, prices may be non-linear and depend on theidentities of the seller and the buyer. A pricing system is denoted by(Pb, Ps) where Pb(Zb)=; s pbs(zbs) is the cost to buyer b of the assignmentZb=(zbs) and Ps(Ys)=; b pbs(ybs) is the revenue to seller s of the assign-ment Ys=(ybs).
In parallel with the four orders of assignments in the previous section weshall define four types of price systems. In the usual one, prices of packagesare based on prices of the objects pk, k=1, 2, ..., K in the vector p=(pk)such that
pbs(w)=p·w,
Pb(Zb)=p· Cs ¥ Szbs, Ps(Ys)=p· C
b ¥ Bybs.
(1)
That is, the pricing function is linear. We call this a first order pricing func-tion. Kelso and Crawford [15], Gul and Stacchetti [14], Bikhchandani andMamer [4], and Ma [18] established conditions for existence of first orderpricing equilibria.
A second order pricing function is defined by
pbs(w)=p(w),
Pb(Zb)=Cs ¥ Sp(zbs), Ps(Ys)=C
b ¥ Bp(ybs),
(2)
which permits non-linearity in pricing. That is, we may have p(w+wŒ) ]p(w)+p(wŒ). With second order pricing, all costs and revenues are basedon prices p(w) for all w ¥ZK
+. Second order pricing will be associated withan equilibrium of demand and supply with respect to crates.
A third order pricing function is of the form
pbs(w)=pb(w),
Pb(Zb)=Cs ¥ Spb(zbs), Ps(Ys)=C
b ¥ Bpb(ybs).
(3)
PACKAGE ASSIGNMENT MODEL 385
The primitive prices are pb(w), for all w ¥ZK+, for all b. The price paid or
received for a package (crate) is non-linear and depends on the identity ofthe buyer.
A fourth order pricing function is of the form
pbs(w)=pbs(w),
Pb(Zb)=Cs ¥ Spbs(zbs), Ps(Ys)=C
b ¥ Bpbs(ybs).
(4)
The primitive prices are pbs(w), for all w ¥ZK+, for all s, b. This version of
pricing may be non-linear and completely non-anonymous in that pricesmay depend on the identities of the buyer and the seller between whom atransaction occurs.6
6 Another pricing function, analogous to third order pricing, is one where prices are non-linear and depend on the identity of the seller (but not the buyer).
To rationalize the non-linear, non-anonymous pricing in j order equi-libria (j > 1), we emphasize that the trade restrictions in Ej stipulate:
B1. Although each buyer can deal with many sellers and each sellerwith many buyers, a buyer/seller pair can exchange at most one package.
B2. Buyers may not resell packages to each other after buying fromsellers.
B1 implies that prices may be superadditive.7 Without B2, equilibrium
7 Specifically, for (pbs( · )), a j > 1 order pricing system, it is possible that pbs(w)+pbs(w −) <pbs(w+w −), where (w+w −) [ Ws. If B1 does not hold and pbs(w)+pbs(w −) < pbs(w+w −) then abuyer wishing to buy w+w − will buy the two packages w, w − separately from seller s.
prices cannot be buyer dependent, i.e., B2 permits third and fourth orderpricing. Further, B2 implies that second order prices may be subadditive.8
8 That is, p(w)+p(w −) > p(w+w −) for some (w+w −) [ Ws is possible. Suppose that for agiven set of prices, buyers b and b − wish to buy packages w and w − respectively from seller s. IfB2 does not hold and p(w)+p(w −) > p(w+w −), then b may purchase w+w − and resell wŒ tobuyer bŒ later.
A (parametric) pricing equilibrium is an assignment and prices such thatconsumers maximize utility, producers maximize profits and markets clear.The package assignment model is an exchange economy (there is no pro-duction), but the buyers and sellers resemble households and firms, respec-tively. As households, buyers maximize utility subject to the budget con-straint Pb(Zb)+mb=0. With quasilinear preferences, maximization ofutility subject to the budget constraint is equivalent to the objective
Ub6 (Pb)=maxZb{Ub(Zb)−Pb(Zb)}.
386 BIKHCHANDANI AND OSTROY
As firms, sellers choose packages from among their feasible sets to maxi-mize profits. Given our conventions with respect to Us, profit maximizationis equivalent to
Us6 (Ps)=maxYs{Us(Ys)+Ps(Ys)}.
Ub6 and Us6 are the indirect utility functions.
Definition 2.1. A pricing equilibrium for the package assignmentproblem Ej is a [(Zg, Yg), (Pg
b , Pgs )] such that
• (Zg, Yg) is a j order feasible assignment,• buyers maximize utilities: for all b, Ub(Z
gb )−P
gb (Z
gb )=Ub6 (P
gb )
• sellers maximize profits: for all s, Us(Ygs )+P
gs (Y
gs )=Us6 (P
gs )
• ; b Pgb (Z
gb )=; s P
gs (Y
gs ).
The last condition that total money payments equals total receipts impliesthat the prices of packages in excess supply must be zero.
3. LP CHARACTERIZATIONS OF PRICING EQUILIBRIA
In this section we show that pricing equilibria for Ej are equivalent tointeger-valued solutions to a corresponding linear programming problem.9
9 An LP characterization of first order pricing equilibria also holds when commodities aredivisible (Makowski and Ostroy [21]).
Regard each Zb and Ys as an ‘‘activity’’ operated at unit level. If theseactivities are operated at levels xb(Zb) \ 0 and xs(Ys) \ 0, their payoffs areUb(Zb) xb(Zb) and Us(Ys) xs(Ys). Recalling our convention, for each s thereare only a finite number of (individually feasible) activities yielding Usgreater than −..
Let IP(Ej) denote the integer programming problem defined by packagemodel Ej, i.e.,
v(IP(Ej))=max Cb
CZb
Ub(Zb) xb(Zb)+Cs
CYs
Us(Ys) xs(Ys),
subject to the constraints,
CZb
xb(Zb) [ 1, -b (5)
CYs
xs(Ys) [ 1, -s (6)
PACKAGE ASSIGNMENT MODEL 387
A jx [ 0
xb(Zb), xs(Ys) ¥ {0, 1},
where A j is the matrix of coefficients of the linear inequalities distinguish-ing IP(Ej) and x=(xb(Zb), xs(Ys)). The feasible set of IP(Ej) will coincidewith the set of j order feasible assignments; and the optimal solution set toIP(Ej) will be the set of (j order) efficient assignments. Thus, v(IP(Ej))=v(E).
Let Fbs(w)={Zb: zbs=w} denote those Zb in which buyer b requestspackage w from seller s. Similarly, Gbs(w)={Ys: ybs=w} are those Ys inwhich seller s earmarks package w for buyer b. Then, the linear inequalitiesfor A1 are
Cw
1Cbs
CZb ¥ F
bs(w)
xb(Zb)−Cbs
CYs ¥ G
bs(w)
xs(Ys)2 w [ 0.
When xb( · ) ¥ {0, 1}, ; bs ;Zb ¥ Fbs(w) xb(Zb) counts the number of packages
of type w requested by buyers. When xs( · ) ¥ {0, 1}, ; bs ;Ys ¥ Gbs(w) xs(Ys)
counts the number of packages of type w earmarked for buyers. Since eachw ¥ZK
+ is defined by the number and kinds of objects in it, the inequalitiesfor A1 restate the conditions for a first order assignment. For example,
Cw
1Cbs
CZb ¥ F
bs(w)
xb(Zb)2 w=Cw
C{bs: zbs=w}
zbs=Cb
Cszbs
is the total demand for objects contained in the packages demanded in Z.The linear inequalities for A2 are
Cbs
CZb ¥ F
bs(w)
xb(Zb)−Cbs
CYs ¥ G
bs(w)
xs(Ys) [ 0, -w.
These inequalities require that the total number of packages of type wsupplied by sellers are at least as large as the total number requested bybuyers; hence, it is equivalent to a second order assignment.
The linear inequalities for A3 are
Cs
CZb ¥ F
bs(w)
xb(Zb)−Cs
CYs ¥ G
bs(w)
xs(Ys) [ 0, -b, w.
These inequalities, which are equivalent to third order assignments, requirethat the total number of packages of type w supplied by sellers to a buyer bare at least as large as the total number requested by b from sellers.
388 BIKHCHANDANI AND OSTROY
The linear inequalities for A4 are
CZb ¥ F
bs(w)
xb(Zb)− CYs ¥ G
bs(w)
xs(Ys) [ 0, -b, s, w.
When xb( · ), xs( · ) ¥ {0, 1}, the inequalities for A4 are equivalent to zbs=ybsor 0, -b, s, the condition for fourth order assignments.
Let LP(Ej) denote the linear programming problem defined by changingthe integer constraints xb( · ), xs( · ) ¥ {0, 1} in IP(Ej) to xb( · ), xs( · ) \ 0.10
10 The restrictions xb( · ), xs( · ) [ 1 are unnecessary as they are implied by ;Zb xb(Zb) [ 1and ;Ys xs(Ys) [ 1.
Let DLP(Ej) be the dual of LP(Ej). The first two constraints in each LP(Ej)are the same. Since these two constraints are the only ones with non-zeroright-hand side terms, they determine the objective functions for theirduals. Hence, the form of the objective function for each DLP(Ej) is thesame, namely,
v(DLP(Ej))=min Cbpb+C
sps,
where pb and ps are the ‘‘prices’’ of buyer b and seller s respectively, i.e., pbis buyer b’s surplus and ps is seller s’s profit. As the remaining constraintsfor the LP(Ej) differ, so do their dual constraints.
The constraints for DLP(Ej) are
pb+Cspbs(zbs) \ Ub(Zb), -Zb=(zbs), -b, (7)
ps−Cbpbs(ybs) \ Us(Ys), -Ys=(ybs), -s, (8)
pb, ps, pbs(w) \ 0, -b, s, w.
Inspection of the primal constraints reveals that the specification of thedual variables in DLP(Ej), j=1−4, is given by the corresponding pricingfunctions in Eqs. (1)–(4): for DLP(E1), pbs(w)=p·w; for DLP(E2), pbs(w)=p(w); for DLP(E3), pbs(w)=pb(w); while for DLP(E4), the pricing functionis pbs(w).
To summarize, the problem for DLP(Ej) is to find pricing functions oforder j (or less) which minimize the total gains to the buyers and sellers,while the problem for LP(Ej) is to find assignments of order j whichmaximize those gains.
The following is the main result for the multi-seller model. A special caseof Theorem 3.1—for pricing equilibrium in E1—was proved in Bikhchandaniand Mamer [4].
PACKAGE ASSIGNMENT MODEL 389
Theorem 3.1. [(Zg, Yg), (Pgb , P
gs )] is a pricing equilibrium for Ej,
j=1, 2, 3, 4, if and only if the integer-valued assignment (Zg, Yg) is anoptimal solution to LP(Ej) and (P
gb ,P
gs , P
gb , P
gs ), where p
gb=Ub6 (P
gb ) and
pgs=Us6 (P
gs ) for all b and s, is an optimal solution to DLP(Ej). That is,
v(LP(Ej))=CbUb(Z
gb )+C
sUs(Y
gs )=v(E)=C
bpgb+C
spgs=v(DLP(Ej)).
The following is immediate from the LP characterization of pricingequilibria.
Corollary 3.1. If [(Zg, Yg), (Pgb , P
gs )] is a pricing equilibrium for Ej,
j=1, 2, 3, 4, then [Zg, Yg] is efficient, i.e., ; b Ub(Zgb )+; s Us(Y
gs )=v(E).
If [(Zg, Yg), (Pgb , P
gs )] is a pricing equilibrium for Ej, then (Zg, Yg) is a
feasible solution to IP(Ej). Moreover, by Corollary 1, [Zg, Yg] is an effi-cient assignment and therefore it is an optimal solution to IP(Ej).Theorem 3.1 says that [(Zg, Yg), (Pg
b , Pgs )] is a pricing equilibrium for Ej if
and only if [Zg, Yg] is an optimal solution to LP(Ej). Consequently, thecritical condition for existence of pricing equilibrium of order j is theequality
v(IP(Ej))=v(LP(Ej)).
Because of the evident inequality
v(IP(Ej)) [ v(LP(Ej)), (9)
existence is in general problematic. The following explains why appeal tomore general (i.e., higher order) pricing functions can enlarge the domainof existence.
As j increases, the constraints in LP(Ej) become more restrictive (a jorder assignment is a j−1 order assignment) and the constraints inDLP(Ej) become less restrictive (first order pricing is a special case ofsecond order pricing, etc.). Therefore,
where the equalities are guaranteed by the Basic Theorem of Linear Pro-gramming.
Denote by P(Ej) the set of equilibrium price systems associated with Ej.If v(LP(E1)) > v(IP(Ej))[=v(E)], P(E1)=”. Nevertheless, if the restric-tions imposed by j > 1 order equilibria are sufficiently binding thatv(LP(Ej))=v(IP(Ej)) for j=2, 3, or 4, then P(Ej) ]”.
The following example from Kelso and Crawford [15] (who use it toshow nonexistence of first order prices) shows that pricing equilibria maynot exist in E2; but in this example pricing equilibria do exist in E3.
Example 3.1. [P(Ej)=”, j=1, 2, P(E3) ]”] There is one sellerendowed with (1, 1, 1). The reservation values of the two buyers are inTable I.
Let YŒ=((1, 1, 0), (0, 0, 1)) and Yœ=((0, 1, 0), (1, 0, 1)) denote twofeasible sales. Let Z −1=(1, 1, 0) and Z'1=(0, 0, 1) be two feasible packagesbuyer 1 might request. Similarly, Z −2=(0, 1, 0) and Z'2=(1, 0, 1) arepackages buyer 2 might request. The optimal solution to LP(E2) is:
(i) xs(YŒ)=xs(Yœ)=0.5, and xs(Y)=0, -Y ] YŒ, Yœ,(ii) xb1 (Z
−
1)=xb1 (Z'
1 )=0.5, and xb1 (Z1)=0, -Z1 ] Z−
1, Z'
1 ,(iii) xb2 (Z
−
2)=xb2 (Z−
2Œ)=0.5, and xb2 (Z2)=0, -Z2 ] Z−
2, Z'
2 .
At this optimal solution, v(LP(E2))=11.75. An efficient assignment isZ=Y=((0, 1, 0), (1, 0, 1)) implying that v(IP(E))=11.5. As v(LP(E2)) >v(E), Theorem 3.1 implies P(E2)=f.
However, P(E3) ] f. Table II shows order 3 pricing equilibrium, pb( · ),b=1, 2. The only assignments that these prices support are the two effi-cient assignments.
Nevertheless, as the next example shows, an appeal to E4 need not implyexistence.
Example 3.2. [P(Ej)=”, j=1, 2, 3, 4.] There are three buyers, a, b,and c, and three sellers, 1, 2, and 3. There are three distinct commoditiesand seller s(=1, 2, 3) is endowed with one unit of commodity s. The threebuyers’ reservation value functions are shown in Table III.
Each seller s has four feasible sales. Let Ys(b) be the sale in which seller sassigns his commodity to buyer b. Ys(f) denotes no sale. As each seller hasa distinct commodity, we will denote Zb by ; s zbs. Thus at Za=(1, 1, 0),buyer a requests one unit of commodity 1 from seller 1, a unit of commo-dity 2 from seller 2, and nothing from seller 3. The following is an optimalsolution to LP(E4).
(iii) x3(Y3(b))=x3(Y3(c))=0.5, x3(Y3(a))=x3(Y3(f))=0.(iv) xa(1, 1, 0)=0.5, xa(Za)=0 for all Za ] (1, 1, 0).(v) xb(1, 0, 1)=0.5, xb(Zb)=0 for all Zb ] (1, 0, 1).
(vi) xc(0, 1, 1)=0.5, xc(Zc)=0 for all Zc ] (0, 1, 1).
At this optimal solution v(LP(E4))=4.5. In any efficient assignment, allthree commodities are assigned to the same buyer; this yields v(E)=4.Theorem 3.1 implies that P(E4)=f.
Remark on lotteries. It might appear that lotteries can be used here toaddress indivisibilities. For example, it is tempting to re-interpretxb(Zb) \ 0 and xs(Ys) \ 0 as probabilities (rather than fractions) of Zb andYs respectively.11 To see that such an interpretation is problematic, consider
11 Since probabilities must sum to 1, the constraint corresponding to (5) in LP(Ej) would bereplaced by xb(0)+;Zb xb(Zb)=1 with xb(0) representing the probability of the null alloca-tion. A similar modification to (6) would be necessary.
Example 3.2. At the ‘‘lottery’’ optimal solution xa(1, 1, 0)=0.5,xb(1, 0, 1)=0.5, and xc(0, 1, 1)=0.5 the probabilities add up to 1.5 as theallocations of (1, 1, 0) to a, of (1, 0, 1) to b, and of (0, 1, 1) to c aremutually exclusive events.
Lotteries can be applied to this model, but the results are disappointing.Let F be the set of feasible assignments (Z, Y) (of any order) for theeconomy E and consider the lottery LP problem:
v(LLP(E))=max C(Z, Y) ¥F
c(Z, Y) x(Z, Y),
392 BIKHCHANDANI AND OSTROY
where c(Z, Y)=; b ub(Zb)+; s us(Ys), subject to the constraint
C(Z, Y) ¥F
x(Z, Y)=1, x(Z, Y) \ 0.
Lotteries are useful when they expand utility possibilities. But here it isreadily seen that v(LLP(E))=v(IP(E)). Moreover, the dual of LLP(E) isdeprived of any useful notion of pricing.
4. THE CORE
In this section we show that, in addition to efficiency (Corollary 3.1),another well-known property of first order price equilibrium (i.e., the usualnotion of Walrasian equilibrium) is also shared by higher order pricing.
The set of players is denoted by N — {1, 2, ..., B} 2 {1, 2, ..., S}. For anysubset T ıN, let TB — T 5 {1, 2, ..., B} be the set of buyers in T and letTS — T 5 {1, 2, ..., S} be the set of sellers in T.
Recall that v(E) is the maximum gains available in the economy E.Regard E ’N and let
V(N) — v(E).
Similarly, let V(T) be the maximum gains in the economy consisting ofthose buyers and sellers in T. Let (Z(T), Y(T)) be any j order assignmentsuch that zbs=0 for all b ¥ TB and s ¨ TS, and ybs=0 for all b ¨ TB ands ¥ TS. That is, at (Z(T), Y(T)) buyers and sellers in T trade only amongthemselves. Lemma 2.1 assures us that regardless of j,
V(T) — maxZ(T), Y(T)
3 Cb ¥ TB
Ub(Zb(T))+ Cs ¥ TSUs(Ys(T))4 ; (10)
hence, V(T) is insensitive to resale restrictions.Note that (i) if TB=f or TS=f then V(T)=0; (ii) If T1 … T2 thenV(T1) [ V(T2); and (iii) V is superadditive, i.e., if T1 5 T2=f thenV(T1)+V(T2) [ V(T1 2 T2).
Definition 4.1. Let PB=(pb) ¥RB+ and PS=(ps) ¥RS
+. Then (PB,PS)is in the core of the game defined by E, denoted (PB,PS) ¥ core(E), if
Cb ¥ TB
pb+ Cs ¥ TSps \ V(T), -T ıN
CB
b=1pb+C
S
s=1ps=V(N).
PACKAGE ASSIGNMENT MODEL 393
The next theorem says that pricing equilibrium payoffs for Ej are in thecore.
12 A proof of Theorem 4.1, which follows from the optimality properties of Theorem 3.1, is inBikhchandani and Ostroy [5].
Example 4.1 below shows that, unlike the standard assignment model,the converse of Theorem 4.1 is not true in the package assignment model.
Example 4.1. [P(E4) is not utility equivalent to core(E)] Let thebuyers and the aggregate endowment be as in Example 3.1. There are twosellers, h and l. Seller h’s initial endowment is (1, 0, 0) and seller l’s initialendowment is (0, 1, 1). It may be verified that P(E4) is empty and that thecore is nonempty.13
13 The core consists of the convex hull of points (2.5, 2.5, 2, 4.5), (1, 1, 3, 6.5),(1.5, 1.5, 3, 5.5), and (2.5, 2.5, 1.5, 5).
5. THE SINGLE SELLER MODEL
Denote the package assignment model with a single seller by E[1]. Weshow that in E3[1] the core can be priced and P(E3[1]) is nonempty.14 If
14 In this model, there is no difference between equilibria of order 3 and 4.
an assumption of ‘‘buyers are substitutes’’ is satisfied, then the core has alattice property with respect to buyers’ payoffs.
Theorem 5.1. (PB, ps) ¥ core(E[1]) if and only if there exists a pricingequilibrium defined by (Pb, Ps) ¥ P(E3[1]) such that ps=Us6 (Ps) and for allb, pb=Ub6 (Pb).
It follows from the fact that V(T)=0 whenever s ¨ T, thatcore(E[1]) ]”. Thus,
Corollary 5.1. P(E3[1]) ]”.
Example 3.1 implies that Corollary 5.1 is not true for P(Ej[1]) whenj < 3.
In E3[1], each Zb=zb is a bundle in ZK+. Let s denote the single seller.
Thus DLP(E3[1]) simplifies to
minpb, ps
CB
b=1pb+ps
394 BIKHCHANDANI AND OSTROY
subject to
pb+pb(zb) \ ub(zb), -zb, -b
ps−Cbpb(ybs) \ Us(Ys), -Ys=(ybs)
pb, ps, pb(w) \ 0, -b, w.
Theorem 3.1 and Corollary 5.1 imply that P(E3[1]) is utility equivalentto the optimal solution set of DLP(E3[1]). This, together withTheorem 5.1, implies:
Corollary 5.2. The optimal solution set of DLP(E3[1]) coincides withthe core in E[1].
For any two points (PB, ps), (PB, ps) ¥ core(E[1]) we define two addi-tional points, one of which is preferred by the buyers and the other by theseller:
pb — max{pb, pb}, -b, p¯s — V(N)−C
bpb=v(E[1])−C
bpb
p¯b — min{pb, pb}, -b, ps — V(N)−C
bp¯b=v(E[1])−C
bp¯b.
(11)
We say that the core has the lattice property with respect to buyers if forany two points (PB, ps), (PB, ps) ¥ core(E[1]) we have (PB, p
¯s), (P¯B, ps) ¥
core(E[1]). The qualification ‘‘with respect to buyers’’ is important: if(PB, ps), (PB, ps) ¥ core(E[1]), the minimum and maximum of thesevectors will typically not even add to V(N).
The next example shows that, in general, core(E[1]) does not have thislattice property.
Example 5.1. There are three identical buyers, labeled b=1, 2, 3, andone seller, s, endowed with three identical units of an object. The reserva-tion value function of the buyers is: u(1)=7, u(2)=8, and u(3)=10.Thus, for any T ı {s, 1, 2, 3},
V(T)=˛10, if s ¥ T, |T|=2
15, if s ¥ T, |T|=3
21, if s ¥ T, |T|=4
0, otherwise.
PACKAGE ASSIGNMENT MODEL 395
The core consists of points (pb, b=1, 2, 3, ps) \ 0 such that pb [ 6,pb+pbΠ[ 11, p1+p2+p3+ps=21. Thus, the points (6, 5, 5, 5) and(5, 6, 5, 5) lie in the core but the point (6, 6, 5, 4) does not.
The lattice property of the core in the standard assignment model isrelated to an individual’s marginal product. Buyer b’s marginal product,MPb, is the increase in the gains from trade due to b. That is,
MPb — V(N)−V(N0{b}), -b.
Similarly, MPT, the marginal product of a subset of buyers T is15
15 Because they depend only on the characteristic function V, (10) implies that MPT andMPb are determined by E alone, and are insensitive to resale restrictions Ej.
MPT — V(N)−V(N0T), T ı {1, 2, ..., b, ..., B}.
If for all T ı {1, 2, ..., b, ..., B}
MPT \ Cb ¥ T
MPb. (12)
then we say, following Shapley [22], that buyers are substitutes in E[1].16
16 The inequality is required only with respect to the individual members of T, not for alldisjoint subsets.
Such a condition underlies, for example, the belief that workers are betteroff forming a union rather than bargain individually with management. Wefind this to be a plausible restriction. Shapley [22] shows that (12) alwaysholds for the standard assignment model; nevertheless, as Example 5.1illustrates, the condition need not hold beyond that case.
The proof of the next proposition is related to a result in Shapley andShubik [23].
Proposition 5.1. When buyers are substitutes the core(E[1]) has thelattice property with respect to buyers.17
17 In the 1997 version of this paper we referred to a stronger condition as buyers exhibitdecreasing marginal products.
Combined with Theorem 5.1, Proposition 5.1 assures us that the corepoint (PB, p
¯s), which is most preferred by all buyers and least preferred by
the seller, can be priced by an element of P(E3[1]).
396 BIKHCHANDANI AND OSTROY
Corollary 5.3. When buyers are substitutes there exist points(PB, p
¯s), (P¯B, ps) ¥ core(E[1]) such that for any (PB, ps, ) ¥ core(E[1]),
pb \ pb \ p¯b, -b
p¯s [ ps [ ps.
Remark on the lattice property. That the core can be priced in thestandard assignment model is associated with the fact that the core has thelattice property: this, in turn, translates directly to the lattice property ofequilibrium prices. In E[1], even though the core can be priced, it may notbe a lattice. Further, when the core is a lattice with respect to buyers, thelattice property does not translate either to the seller’s core payoffs or toprices in P(E3[1]).
6. PRICING VICKREY PAYMENTS
E[1] is the setting for a multi-object auction. In this section we applyour previous results to demonstrate incentive compatibility in the singleseller model.
A feasible allocation (Zg, Yg) in Ej[1] is efficient if ; b ub(zgb )+Us(Y
g)=V(N). It is well-known from Vickrey–Clarke–Groves mechanism theorythat a necessary and sufficient condition for an efficient mechanism(auction) to guarantee truth-telling for buyer b is the following: in additionto the utility ub(z
gb ) that the buyer receives from his part of the efficient
assignment (Zg, Yg), the money payment mgb must be such that the buyer’s
total utility is equal to his marginal product,
ub(zgb )−m
gb=MPb — V(N)−V(N0{b}),
plus possibly a lump sum. (See, for example, Makowski and Ostroy [20].)As V(N)=; bŒ ubŒ(z
gbŒ), the above equation implies that
mgb=V(N0{b})− C
b Œ ] bubŒ(z
gbŒ) \ 0.
The inequality follows because (zg1 , zg2 , ..., z
gb−1, z
gb+1, ..., z
gB) is a feasible
allocation in E ’ b[1], the economy without buyer b. Thus, the moneypayment paid by buyer b should just compensate the rest of the economyfor any change in their total welfare as a consequence of the presence of b.Call this charge the Vickrey payment, i.e., the amount of money that allows
PACKAGE ASSIGNMENT MODEL 397
buyer b to receive his marginal product. Let R¯ s
be the amount that theseller receives when each buyer receives his marginal product, i.e.,
R¯ s=V(N)−C
bMPb=C
bmb \ 0.
Call the point (MP1,MP2, ...,MPb, ...,MPB, R¯ s) the Vickrey payoff point
(VPP).It is an obvious consequence of the definition of the core that a buyer’s
marginal product is an upper bound of the set of possible core payoffs thebuyer can receive. In the present case, if (PB, ps) ¥ core(E[1]), then
pb [ MPb, -b, and ps \ R¯ s(13)
If (PB, ps) ¥ core(E[1]), then Theorem 5.1 implies that (PB, ps) is utilityequivalent to the indirect utilities from an element of P(E3[1]). Hence, ifVPP ¥ core(E[1]) then (i) this point can be priced and (ii) (13) implies thatthe VPP is the core point most preferred by all buyers and least preferredby the seller that was identified in Corollary 5.3. The money paymentsestablished by the prices in P(E3[1]) which yield the VPP coincide withVickrey payments.
Example 5.1 shows, however, that VPP may lie outside the core. In thisexample, the VPP is (6, 6, 6, 3): 3 to the seller and 6 to each of the buyers.This point is not in the core as 6+3 < V({s, 1})=10. Buyers are not sub-stitutes as the marginal product of a coalition of any two buyers is 11whereas the marginal product of a single buyer is 6, violating (12).
A P¯
¥ P(E3[1]) is smallest if at this equilibrium the buyers’ payoffs arenot less than and the seller’s payoffs are not greater than at any otherP ¥ P(E3[1]).
Theorem 5.1 and Corollaries 5.2 and 5.3 imply that a smallest P¯
exists inP(E3[1]) when buyers are substitutes.18 This leads to the main result of the
18 There may be multiple smallest P¯
; these differ only in prices of buyer-packages that arenot in any efficient allocation.
single seller model.
Theorem 6.1. The following are equivalent:
(i) Buyers are substitutes in E[1].(ii) The Vickrey payoff point is in the core of E[1].
(iii) Vickrey payments are priced by any smallest P¯
¥ P(E3[1]). Thatis, if buyers’ Vickrey allocations and payments are (zg1 , z
g2 , ..., z
gb , ..., z
gB) and
(mg1 , m
g2 , ..., m
gb , ..., m
gB) respectively and P
¯=(p¯b(zb), -zb, -b), then
mgb=p¯b(z
gb ) for all b.
398 BIKHCHANDANI AND OSTROY
TABLE IV
z 1 2 3 4
ua(z) 4 7 9 9ub(z) 4 7 9 10
The example below shows that pricing functions in P(Ej[1]), j < 3, maynot price the VPP (when buyers are substitutes).
Example 6.1. One seller, s, owns four identical units of an object.There are two buyers, a and b, for the objects with reservation values as inTable IV.
The characteristic function of this economy is V({s, a})=9,V({s, b})=10, V({s, a, b}) =14, and V(T)=0 for all other T … {s, a, b}.The VPP is (MPa=4,MPb=5, R¯ s
=5). As buyers are substitutes,Theorem 6.1 implies that the VPP is in the core and that a price inP(E3[1]) yields this point. At this pricing equilibrium, each buyer obtainstwo units but buyer a pays 3, and buyer b pays 2. Therefore, althoughpricing equilibrium of order 2 exists in this example (i.e., P(E2[1]) ] f),there is no pricing equilibrium of order less than 3 which yields the VPP.
6.1. Implementation and Computation of Vickrey Payments
6.1.1. Sealed Bid Vickrey Auction. The rules of the Vickrey auctionrequire that between 2 and B+1 integer programming problems, where Bis the number of buyers, have to be solved in order to implement theauction. A solution to the integer programming problem IP(Ej[1]) yieldsan efficient allocation, (zg1 , z
g2 , ..., z
gb , ..., z
gB), and the total gains from trade
V(N). In addition, for each buyer b who wins a subset (i.e., zgb > 0) theinteger programming problem IP(E ’ b
j [1]) is solved in order to computeV(N0{b}). The solutions to these integer programming problems yieldeach buyer b’s Vickrey allocation zgb , and his Vickrey payment mg
b=V(N)−V(N0{b}). This imposes a huge computational burden on theseller, rendering the Vickrey auction impractical for selling more than ahandful of objects.
An implication of Theorems 3.1 and 5.1 is that the Vickrey auctioneerneed solve LP(E3[1]) instead of IP(Ej[1]), and LP(E ’ b
3 [1]) instead ofIP(E ’ b
j [1]).19 Consequently, the computational requirements of the
19 Integer solutions to LP(E3[1]) may be obtained by using a primal-dual algorithm. Alter-natively, an efficient allocation, i.e., an integer solution to LP(E3[1]), may be obtained by (i)finding a solution to DLP(E3[1]) and (ii) computing the (integer) demand sets of buyers at theprices in the DLP(E3[1]) solution; an efficient allocation from these demand sets is feasible.
PACKAGE ASSIGNMENT MODEL 399
Vickrey auction decrease considerably in that the seller need only solvelinear programming relaxations of integer programming problems.20
20 Integer programming problems are usually much more difficult to solve than linear pro-gramming problems. Often, it is computationally infeasible to obtain an optimal solution tomoderate-sized integer programming problems whereas optimal solutions to the correspondinglinear program relaxation (which ignores the integer restrictions) are computationally feasible.
When buyers are substitutes, the dual characterization of Vickrey pay-ments results in a further reduction of computational complexity in thatsolutions to a single linear programming problem LP(E3[1]) and a variantof its dual, DLP(E3[1]), yield Vickrey allocations and payments. Thisimplementation of the Vickrey auction is as follows. After eliciting reser-vation values, the seller solves LP(E3[1]). The solution yields an efficient(therefore, Vickrey) allocation, (zg1 , z
g2 , ..., z
gb , ..., z
gB), and also the value of
V(N). Next, the seller solves the following variant of DLP(E3[1])—denoted by VDLP(E3[1]):
min pssubject to
pb+pb(zb) \ ub(zb), -zb, -b
ps−Cbpb(ybs) \ Us(Ys), -Ys=(ybs)
ps+Cbpb=V(N) (14)
pb, ps, pb(w) \ 0, -b, w,
where ub(·) are the bids submitted by buyer b. The linear program VDLP(E3[1])differs from DLP(E3[1]) in that (i) the objective function is min ps instead ofmin ps+;b pb and (ii) the constraint (14) is not there in DLP(E3[1]). However,by Corollary 5.2, all optimal solutions to DLP(E3[1]) are in core(E[1]) andtherefore satisfy (14). Further, an optimal solution to VDLP(E3[1]) is alsooptimal in DLP(E3[1]) and therefore belongs to core(E[1]).
By Theorem 6.1, if buyers are substitutes then VDLP(E3[1]) has aunique optimal solution ((pg
b ), pgs ) which is the VPP in E[1]. That is,
((pgb ), p
gs )=(MP1,MP2, ...,MPb, ...,MPB, R¯ s
). Hence, the Vickrey pay-ments are mg
b=ub(zgb )−p
gb .21
21 As to the practicality of solving the linear programming problems above, suppose thereare N objects and B bidders. The linear programming formulation would solve for 2N×Bpersonalized packages and their prices. As N increases, however, most of the solution valuesfor the primal variables will be zero as each buyer receives only one package. Assume that ifeach buyer were limited to placing bids on anyM (whereM ’ O(N)) of the 2N packages, thiswould not be a binding restriction on the information needed to obtain an efficient allocation.In this case, the only variables considered are the package/buyer pairs for which bids havebeen submitted (=M×B) and a price for each; a solution to the LP formulation of theproblem is computationally feasible.
400 BIKHCHANDANI AND OSTROY
6.1.2. Ascending Price Vickrey Auction. Ausubel [1] proposes anascending price auction for homogeneous objects which implements a VPP.Assume, as Ausubel does, that all buyers have decreasing marginal utility.It can be shown that buyers are substitutes in this setting (see Proposition 4in Bikhchandani and Ostroy [5]). Hence, by Theorem 6.1, the VPPimplemented by Ausubel’s ascending price auction is also attainable by anysmallest pricing equilibrium in P(E3[1]).
It is well-known that an ascending price auction for a single objectimplements the smallest equilibrium price (and also implements the VPP).In Ausubel’s setting, a first order pricing equilibrium exists; but such anequilibrium will typically fail to implement the VPP (see Example 6.1, forinstance). Thus, the generalization from ascending price auctions for singleobjects to multiple homogeneous units requires an appropriate generaliza-tion (i.e., order 3) of Walrasian equilibrium.
7. CONCLUDING REMARKS
Our strategy has been to formulate the problem of resource allocationwith multiple indivisible commodities as an extension of the standardassignment model. A key feature of our analysis is that even when utilityfunctions are non-additive, the problem of achieving an efficient allocationhas a linear structure in which the pricing functions expressing duality maybe non-linear in the objects constituting the packages. This led us to estab-lish the interconnections among linear programming, a broadening of theconcept of Walrasian equilibrium, and the core. The notable existence andequivalence among all three of these concepts in the standard assignmentmodel is not preserved in the package version, but important traces, suchas the equivalence of linear programming solutions and pricing equilib-rium, remain. Nevertheless, existence of pricing equilibrium is problematic.
When there is a single seller, however, existence is guaranteed. Moreover,another feature of the standard assignment model—the equivalence ofpricing equilibrium with the core—re-emerges. Here, pricing equilibriumincludes non-linear and non-anonymous pricing. In single seller models,that kind of pricing is normally associated with the monopolist’s efforts toextract more surplus from buyers than is possible under simple monopoly.If the seller were to succeed in capturing all the surplus, i.e., in extractingher marginal product, the outcome would be efficient. Such perfectlydiscriminatory pricing presupposes considerable knowledge by the seller ofbuyers’ tastes, as well as restrictions on resale. The Vickrey approach toefficient auctions goes in the opposite direction, rewarding the buyers with
PACKAGE ASSIGNMENT MODEL 401
their marginal products to induce them to report their valuations truth-fully. In the single seller model, if buyers are substitutes, two additionalproperties of the standard assignment model reappear: the core has a latticeproperty and there is a price equilibrium at which buyers receive theirVickrey payoffs.
There is a trade-off between simplicity (i.e., practicality) and efficiency ofmulti-object auctions. Many commonly used multi-object auctions areinefficient (see, for example, Ausubel and Cramton [2], Engelbrecht-Wiggans and Kahn [11], and Bikhchandani [3]). Efficient multi-objectauctions, such as the Vickrey auction and the auction proposed inDasgupta and Maskin [8], are computationally complex to implement.However, our results imply that a considerable reduction in the computa-tional requirements of the Vickrey auction is possible in that only the linearprogramming relaxations of certain integer programming problems need tobe solved.
APPENDIX
Proof of Theorem 3.1. We give a proof for pricing equilibrium in E4; theproof for Ej, j=1, 2, 3, is similar.Sufficiency. Suppose that LP(E4) has an integer optimal solution,(Zg, Yg). Let (pgb , p
gs , P
gb , P
gs ) be an optimal solution to DLP(E4). The
complementary slackness conditions satisfied by these optimal solutionsare:
51−CZb
xgb (Zb)6 pgb=0, -b (A.1)
51−CYs
xgs (Ys)6 pgs=0, -s (A.2)
5 CZb ¥ F
bs(w)
xgb (Zb)− CYs ¥ G
bs(w)
xgs (Ys)6 pgbs(w)=0, -b, -s, -w (A.3)
5pgb+C
spgbs(zbs)−Ub(Zb)6 xg
b (Zb)=0, -Zb=(zbs), -b (A.4)
5pgs −C
bpgbs(ybs)−Us(Ys)6 xg
s (Ys)=0, -Ys=(ybs), -s (A.5)
where xgb (Zb) is 1 if Zb=Zgb and 0 otherwise. Similarly, xg
s (Ys) is 1 ifYs=Y
gs and 0 otherwise.
402 BIKHCHANDANI AND OSTROY
Thus, (A.4) and the buyer maximization constraints in DLP(E4)(inequality 7) imply that
Ub(Zgb )−C
spgbs(z
gbs)=p
gb \ Ub(Zb)−C
spgbs(zbs), -Zb=(zbs), -b.
Similarly, (A.5) and the seller maximization constraints in DLP(E4)(inequality 8) imply that
Us(Ygs )+C
bpgbs(y
gbs)=p
gs \ Us(Ys)+C
bpgbs(ybs), -Ys=(ybs), -s.
As (Zg, Yg) is LP(E4) feasible, it is a fourth order assignment. As (Pgb , P
gs )
is DLP(E4) feasible, it is a fourth order pricing function. Further, (A.3)implies that if a package w is assigned by seller s to buyer b in Yg but not inZg (i.e., yg
bs=w but zgbs=0) then pgbs(w)=0. Therefore, ; b Pgb (Z
gb )=
; s Pgs (Y
gs ). Hence, [(Zg, Yg), (Pg
b , Pgs )] is a pricing equilibrium in E4.22
22 The complementary slackness condition (A.1) [(A.2)] states the obvious fact that a buyer[seller] who does not buy [sell] anything makes zero profit.
Necessity. Let [(Zg, Yg), (Pgb , P
gs )] be a pricing equilibrium in E4.
Therefore,
pgb — Ub(Zgb )−P
gb (Z
gb ) \ Ub(Zb)−P
gb (Zb), -Zb, -b
pgs — Us(Y
gs )+P
gs (Y
gs ) \ Us(Ys)+P
gs (Ys), -Ys, -s.
(A.6)
Let xgb (Zgb )=1 and xgb (Z
gb )=0 if Zb ] Z
gb . Similarly, xg
s (Ygs )=1 and
xgs (Y
gs )=0 if Ys ] Y
gs . As (Zg, Yg) is a fourth order assignment,
(xgb ( · ), xgs ( · )) is a feasible solution to LP(E4). Similarly, DLP(E4) feasi-
bility of (pgb , p
gs , P
gb , P
gs ) is implied by (A.6) and the fact that (Pg
b , Pgs ) is a
fourth order pricing function. Therefore,
v(LP(E4))=v(DLP(E4))
[Cbpgb+C
spgs
=Cb[Ub(Z
gb )−P
gb (Z
gb )]+C
s[Us(Y
gs )+P
gs (Y
gs )]
=CbUb(Z
gb )+C
sUs(Y
gs )
[ v(IP(E4))
[ v(LP(E4)),
where the first inequality follows from DLP(E4) feasibility of (pgb , p
gs ), the
second inequality from the fact that (Zg, Yg) is a fourth order assignment
PACKAGE ASSIGNMENT MODEL 403
and therefore in the feasible set of IP(E4), the third inequality from (9), thesecond equality follows from (A.6), and the third equality from the factthat ; b P
gb (Z
gb )=; s P
gs (Y
gs ) at a pricing equilibrium. L
Proof of Theorem 5.1. In view of Theorem 4.1, we only need to showthat any point in the core can be priced by a pricing equilibrium in E3[1].
Suppose that (PB, ps) ¥ core(E[1]). Let (Zg, Zg) be an efficient thirdorder assignment, i.e., ;b ub(z
gb )+Us(Z
g)=;b ub(zgb )=;b pb+ps=V(N).
Define
pb(w) — max{ub(w)−pb, 0}, -w.
The core inequalities imply that for each buyer b,
ub(zgb )=C
B
a=1ua(z
ga )− C
a ] bua(z
ga )
\ V(N)−V(N0{b})
\ 5 CB
a=1pa+ps6−5 C
a ] bpa+ps6
=pb.
Thus, ub(zgb )−pb \ 0 for all b and pb(z
gb )=ub(z
gb )−pb for all b and
; b pb(zgb )=ps. Hence, ub(z
gb )−pb(z
gb )=pb \ ub(zb)−pb(zb) for all zb,
where the inequality follows from the definition of pb( · ). Therefore, buyersmaximize utility at these prices.
For any other feasible assignment (Z, Y), let B1={b | ub(yb) \ pb)}.Thus, pb(yb)=0 for b ¨ B1. Then,
CB
b=1pb(yb)=C
B
b=1[max{ub(yb)−pb, 0}]
= Cb ¥ B1
ub(yb)− Cb ¥ B1
pb
[ V({s} 2 B1)− Cb ¥ B1
pb
[ ps+ Cb ¥ B1
pb− Cb ¥ B1
pb
=CB
b=1pb(z
gb ),
where the first inequality follows from the definition of V( · ) and thesecond inequality from (PB, ps) ¥ core(E[1]). Thus, the seller also maxi-
404 BIKHCHANDANI AND OSTROY
mizes utility at prices (Pb, Ps). Consequently, ((Zg, Zg), pb( · )) is a pricingequilibrium in E3[1] which yields the payoffs (PB, ps). L
Proof of Proposition 5.1. Suppose that (PB, ps) and (PB, ps) are twopoints in core(E[1]). Let (PB, p
¯s), and (P
¯B, ps) be as in (11).
By definition p¯s+; b pb=V(N). Take any T …N. If s ¨ T then V(T)=0
and (PB, p¯s) clearly satisfy the core inequality for T. Therefore, suppose
that s ¥ T. Note that
V(N) \ V(T)+ Cb ¨ TB[V(N)−V(N0{b}] \ V(T)+ C
b ¨ TBmax{pb, pb}, (A.7)
where the the first inequality follows from (12) and the second inequalityfrom (13). Therefore, using (A.7),
Cb ¥ TB
pb+p¯s= C
b ¥ TBmax{pb, pb}+V(N)− C
B
b=1max{pb, pb}
=V(N)− Cb ¨ TB
max{pb, pb}
\ V(T).
Thus, (PB, p¯s) ¥ core(E[1]). A similar proof implies that (P
¯B, ps) ¥
core(E[1]). L
Proof of Theorem 6.1. (i) Z (ii): Take any coalition T. If s ¨ T thenV(T)=0 and the core inequality is satisfied by the Vickrey payoff point(VPP). Therefore, suppose that s ¥ T. Then
R¯ s+Cb ¥ T
MPb=V(N)− CB
b=1[V(N)−V(N0{b})]+C
b ¥ T[V(N)−V(N0{b})]
=V(N)− Cb ¥N0T
[V(N)−V(N0{b})]
\ V(N)−[V(N)−V(T)]
=V(T),
where the inequality holds for all T if and only if buyers are substitutes.Thus, VPP ¥ core(E[1]) if and only if buyers are substitutes.
(ii) Z (iii): Note that if VPP ¨ core(E[1]) then no pricing equilibriumin E3[1] can price it. If, instead, VPP ¥ core(E[1]) then by Theorem 5.1,there exists a pricing equilibrium in E3[1] which gives agents their payoffsin VPP. By (13) and Theorem 5.1 the payoffs at any other pricing equilib-rium must be no greater for the buyers and no lower for the seller. Hence,any pricing equilibrium which yields the VPP is a smallest pricing equilib-rium in E3[1]. L
PACKAGE ASSIGNMENT MODEL 405
REFERENCES
1. L. M. Ausubel, An efficient ascending-bid auction for multiple objects, working paper,University of Maryland, 1997.
2. L. M. Ausubel and P. C. Cramton, Demand reduction and inefficiency in mult-unit auc-tions, working paper, University of Maryland, 1995.
3. S. Bikhchandani, Auctions of heterogeneous objects, Games Econ. Behav. 26 (1999),193–220.
4. S. Bikhchandani and J. W. Mamer, Competitive equilibrium in an exchange economywith indivisibilities, J. Econ. Theory 74 (1997), 385–413.
5. S. Bikhchandani and J. M. Ostroy, The package assignment model, working paper,UCLA, 2001. (First version June 1997)
6. H.-P. Chao and R. B. Wilson, Design of wholesale electricity markets, working paper,Stanford University, 1999.
7. V. P. Crawford and E. M. Knoer, Job matching with heterogeneous firms and workers,Econometrica 49 (1981), 437–450.
8. P. Dasgupta and E. Maskin, Notes on efficient auctions, working paper, Harvard Uni-versity, 1998.
9. G. Demange and D. Gale, The strategy structure of two-sided matching markets, Econo-metrica 53 (1985), 873–883.
10. G. Demange, D. Gale, and M. Sotomayor, Multi-item auctions, J. Polit. Economy 94(1986), 863–872.
11. R. Engelbrecht-Wiggans and C. M. Kahn, Multi-unit auctions with uniform prices,working paper, University of Illinois, 1995.
12. D. Gale, ‘‘The Theory of Linear Economic Models,’’ University of Chicago Press,Chicago, 1960.
13. N. Gretsky, J. M. Ostroy, and W. Zame, Perfect competition in the continuous assign-ment model, J. Econ. Theory 88 (1999), 60–118.
14. F. Gul and E. Stacchetti, Walrasian equilibrium with gross substitutes, J. Econ. Theory 87(1999), 96–124.
15. A. Kelso and V. P. Crawford, Job-matching, coalition formation, and gross substitutes,Econometrica 50 (1982), 1483–1504.
16. T. Koopmans and M. Beckman, Assignment problems and the location of economicactivities, Econometrica 25 (1957), 53–76.
17. H. B. Leonard, Elicitation of honest preferences for the assignment of individuals to posi-tions, J. Polit. Economy 91 (1983), 461–479.
18. J. Ma, Competitive equilibrium with indivisibilities, J. Econ. Theory 82 (1998), 458–468.19. L. Makowski, Value theory with personalized trading, J. Econ. Theory 20 (1979), 194–212.20. L. Makowski and J. M. Ostroy, Vickrey–Clarke–Groves mechanisms and perfect compe-
tition, J. Econ. Theory 42 (1987), 244–261.21. L. Makowski and J. M. Ostroy, General equilibrium and linear programming, working
paper, UCLA, 1996.22. L. Shapley, Complements and substitutes in the optimal assignment problem, Naval Res.Logist. Quart. 9 (1962), 45–48.
23. L. Shapley and M. Shubik, The assignment game I: The core, Int. J. Game Theory 1(1972), 111–130.
24. W. Vickrey, Counterspeculation, auctions and competitive sealed tenders, J. Finance 16(1961), 1–17.
