Auctions are nothing but solving Allocation problems. Other than matching buyers to sellers, the important aspect of an auction is to determine the price of the object, which in turn determines profits of buyers and sellers. The allocation problem aims at maximizing the profit of both buyer and seller: the total profit of both parties are sometimes also called 'System Profit'.

Before going into LP models of different types of auctions, let us have a look at the concept of Vickrey price. Vickrey prices, or more generally, prices determined by VCG mechanisms (Vickrey-Clarke-Groves Mechanism) induce truthtelling by paying such that each agent's profit is equal to the its' own marginal contribution to the system (i.e. the value it adds to the system). So if V(N) is the total maximum system profit with N bidders(agents) and V(N\j) is the total max system profit without the agent 'j', then j is paid (V(N)-V(N\j)). Prices in English auction and Second price sealed-bid auction are Vickrey prices.

Now let us look at different kind of auctions and their corresponding LP formulations:

A. MULTIPLE (HETEROGENEOUS) ITEMS, MULTIPLE BUYERS, SINGLE-ITEM DEMAND

Setting: There are M objects i=1...M, and N bidders j=1...N. Each bidder wants maximum of one item. Each bidder has got valuation v_ij on the i-th object. We note here that the reserve prices of seller's are zero. LP: This is the simple assignment model. Let x_ij=1 if i-th object goes to j-th bidder, and x_ij=0 otherwise. Then the LP is: Max V(N)=sum((i,j), v_ij * x_ij) s.t. sum(i, x_ij) <= 1 for all j (Dual: t_j) sum(j, x_ij) <= 1 for all i (Dual: p_i) x_ij >= 0 for all i,j [The solutions of this LP are integers if v_ij's are integer]. The dual of this problem, with the dual variables as defined above, is: Min z'=sum(i, p_i) + sum(j, t_j) s.t. p_i + t_j >= v_ij for all i,j

Solving the primal LP gives us the allocation of objects, whereas solving the dual LP gives us price of objects and the profits each buyer will make. Dual variable corresponing to the constraint of each object gives us the price, and those corresponding to the constraints of each bidder give us the profit of the bidder.

Now, here comes the interesting part: Solution space of this dual LP corresponds to all possible Competitive Equilibrium prices and this forms a lattice. A particular fomulation of the dual problem gives the minimal competitive equilibrium price (the one that minimizes sum of prices) and another formulation gives the maximal equilibrium price (the one that maximizes sum of prices). The formulations are: Minimal CE: Maximal CE: Min z'= sum(i, p_i) Max z'= sum(i, p_i) s.t. s.t. sum(i, p_i) + sum(j, t_j) = V(N) sum(i, p_i) + sum(j, t_j) = V(N) p_i + t_j >= v_ij for all i,j p_i + t_j >= v_ij for all i,j

Minimal CE: Prices obtained from (exact) ascending auction algorithm proposed by Demange et. al. for multi-item auctions converge to minimum competitive equilibrium price. This algorithm is an implementation of the Primal-Dual Algorithm (Papadimitriou et. al.). The algorithm involves starting with a dual fisible solution, maintain complementarity slackness conditions throughout the algorithm and reach primal feasibility (and hence optimality). This can be seen as follows: in this mechanism, auction can start with lowest possible price when all things are in everybody's demand set. This is primal infeasible, because each item can be assigned to more than one buyer (thus violating sum(i, x_ij) <= 1) and each buyer can be assigned to more than one item (thus violating sum(j, x_ij <=1). But this is dual feasible, beacuse in this situation, for each object-bidder pair, sum of price of the object and profit of bidder is at least (i.e. greater than) the bidder's valuation for that object.

Ex: Let's consider two objects and two bidders. Sellers' valuations are u_j's and buyers' valuations are v_ij Object: 1 2 u_j: $0 $0 v_ij: 1: $4 $3 2: $2 $0 It's not so clear who gets what, as both prefers object 1 to object 2. Solving the primal LP will show that, 1 gets object 2 and 2 gets object 1.

Primal LP for the above problem: Max V(N)= 4*x_11 + 3*x_12 + 2*x_21 + 0*x_22 s.t. x_11 + x_21 <= 1 (p1) x_12 + x_22 <= 1 (p2) x_11 + x_12 <= 1 (t1) x_21 + x_22 <= 1 (t2)

Solution to this LP is (x_11=0, x_12=1, x_21=1, x_22=0, V(N)=5). Dual of this problem, along with the Complementarity Slackness (CS) conditions will give us all the equilibrium price, and hence the lattice. If the dual variables are as shown above, then the dual is: Min z'= t1 + t2 + p1 + p2 s.t. p1 + t1 >= 4 p2 + t1 >= 3 p1 + t2 >= 2 p2 + t2 >= 0 One solution to the dual LP is (p1=1, p2=0, t1=3, t2=1, z'=5). [Min CE] Another solution is: (p1=2, p2=1, t1=2, t2=0, z'=5). [Max CE] Minimum equilibrium price is (1,0) and maximum equilibrium price is (2,1). Other equilibrium prices can be found out by considering all possible price combinations between these two prices [eg., (1,0), (1,1), (2,0) ...], and checking which are indeed equilibrium (this requires finding out the demand set at each price vector and check if an assignment is possible).

Another way is to use the Complementarity Conditions and plot the lattice. We note, CS conditions are: x_11 * (p1 + t1 - 4) = 0 x_12 * (p2 + t1 - 3) = 0 x_21 * (p1 + t2 - 2) = 0 x_22 * (p2 + t2 - 0) = 0

For optimal assignment, x_12 = x_21 = 1, so (p2 + t1 = 3) and (p1 + t2 = 2). Using this and the dual constraints, we get: 1 <= p1 - p2 <= 2 Alongwith p1, p2 >=0, we can draw the pattice of all equilibrium prices.