You are currently browsing the category archive for the ‘Auctions’ category.

Over a rabelaisian feast with convivial company, conversation turned to a twitter contretemps between economic theorists known to us at table. Its proximate cause was the design of the incentive auction for radio spectrum. The curious can dig around on twitter for the cut and thrust. A summary of the salient economic issues might be helpful for those following the matter.

Three years ago, in the cruelest of months, the FCC conducted an auction to reallocate radio spectrum. It had a procurement phase in which spectrum would be purchased from current holders and a second phase in which it was resold to others. The goal was to shift spectrum, where appropriate, from current holders to others who might use this scarce resource more efficiently.

It is the procurement phase that concerns us. The precise details of the auction in this phase will not matter. Its design is rooted in Ausubel’s clinching auction by way of Bikhchandani et al (2011) culminating in Milgrom and Segal (2019).

The pricing rule of the procurement auction was chosen under the assumption that each seller owned a single license. If invalid, it allows a seller with multiple licenses to engage in what is known as supply reduction to push up the price. Even if each seller initially owned a single license, a subset of sellers could benefit from merging their assets and coordinating their bids (or an outsider could come in and aggregate some sellers prior to the auction). A recent paper by my colleagues Doraszelski, Seim, Sinkinson and Wang offers estimates of how much sellers might have gained from strategic supply reduction.

Was the choice of price rule a design flaw? I say, compared to what? How about the VCG mechanism? It would award a seller owning multiple licenses the marginal product associated with their set of licenses. In general, if the assets held by sellers are substitutes for each other, the marginal product of a set will exceed the sum of the marginal products of its individual elements. Thus, the VCG auction would have left the seller with higher surplus than they would have obtained under the procurement auction assuming no supply reduction. As noted in Paul Milgrom’s  book, when goods are substitutes, the VCG auction creates an incentive for mergers. This is formalized in Sher (2010). The pricing rule of the procurement auction could be modified to account for multiple ownership (see Bikhchandani et al (2011)) but it would have the same qualitative effect. A seller would earn a higher surplus than they would have obtained under the procurement auction assuming no supply reduction. A second point of comparison would be to an auction that was explicitly designed to discourage mergers of this kind. If memory serves, this reduces the auction to a posted price mechanism.

Was there anything that could have been done to discourage  mergers? The auction did have reserve prices, so an upper limit was set on how much would be paid for licenses. Legal action is a possibility but its not clear whether that could have been pursued without delaying the auction.

Stepping back, one might ask a more basic question: should the reallocation of spectrum have been done by auction? Why not follow Coase and let the market sort it out? The orthodox answer is no because of hold-up and transaction costs. However, as Thomas Hazlett has argued, there are transaction costs on the auction side as well.

 

Apparently, it is quite the rage to festoon one’s slides with company logos, particularly of the  frightful five. At present this is done for free. It suggests a new business. A platform that matches advertisers to faculty. Faculty can offer up their slides and advertisers can bid for the right to place their logos on the slides.

When analyzing a mechanism it is convenient to assume that it is direct. The revelation principle allows one to argue that this restriction is without loss of generality. Yet, there are cases where one prefers to implement the indirect version of a mechanism rather than its direct counterpart. The clock version of the English ascending auction and the sealed bid second price auction are the most well known example (one hopes not the only). There are few (i.e. I could not immediately recall any) theorems that uniquely characterize a particular indirect mechanism. It would be nice to have more. What might such a characterization depend upon?

1) Direct mechanisms require that agents report their types. A concern for privacy could be used to `kill’ off a direct mechanism. However, one would first have to rule out the use of trusted third parties (either human or computers implementing cryptographic protocols).

2) Indirect mechanism can sometimes be thought of as an extensive form game and one might look for refinements of solution concepts for extensive form games that have no counterpart in the direct version of the mechanism. The notion of obviously dominant strategy-proof that appears here is an example. However, indirect mechanisms may introduce equilibria, absent in the direct counterpart, that are compelling for the agents but unattractive for the designers purposes.

3) One feature of observed indirect mechanisms is that they use simple message spaces, but compensate by using multiple rounds of communication. Thus a constraint on message spaces would be needed in a characterization but coupled with a constraint on the rounds of communication.

Because I have white hair and that so sparse as to resemble the Soviet harvest of 1963, I am asked for advice. Just recently I was asked about `hot’ research topics in the sharing economy. `You mean a pure exchange economy?, said I in reply.  Because I have white hair etc, I sometimes forget to bite my tongue.

Returning to topic, the Economist piece I linked to above, gets it about right. With a fall in certain transaction costs, trades that were otherwise infeasible, are realized. At a high level there is nothing more to be said beyond what we know already about exchange economies.

A closer looks suggests something of interest in the role of the mediator (eBay, Uber) responsible for the reduction in transaction costs. They are not indifferent Walrasian auctioneers but self interested ones. eBay and Uber provide an interesting contrast in `intrusiveness’. The first reduces the costs with respect to search, alleviates the lemons problem and moral hazard by providing information and managing payments. It does not, however, set prices. These are left to participants to decide. In sum, eBay it appears,  tries to eliminate the textbook obstacles to a perfectly competitive market. Uber, also does these things but more. It chooses prices and the supplier who will meet the reported demand. One might think eBay does not because of the multitude of products it would have to track. The same is true for Uber. A product on Uber is a triple of origin, destination and time of day.    The rider and driver may not be thinking about things in this way, but Uber certainly must in deciding prices and which supplier will be chosen to meet the demand. Why doesn’t Uber allow riders to post bids and drivers to post asks?

Fox News and CNN have been in knots recently about how to allocate scarce debate slots to the many Republican pretenders to the oval office. Should Poll numbers be the criteria? What about gender, race, state office etc. etc. There is a simple and transparent way to allocate the slots: an auction. Neither CNN or Fox are charities. If the debates are a public good, there is no reason why Fox and CNN alone should forgo profits to host them. They should, instead auction off the rights to participate in the debates.

What design questions would have to be answered? First, how much time to allocate to the debate, i.e., what is the supply of the resource to be allocated? Second, should one auction slots or time. For example, should it be 10 slots of equal time lengths in a 2 hour time period? Or, should one allow the bidders to bid on the actual amount of time they would get in the 2 hour period? Are candidates the only ones allowed to bid, or can anyone submit bids on their behalf? Can one bid to deny time to the candidates? Actually, as these are not debates at all, but parallel news conference, perhaps one should auction off the right to answer questions. In real time. That would be entertainment!

According to the NY Times,  some Californians

would have to cut their water consumption by 35 percent under the terms of a preliminary plan issued by state officials on Tuesday to meet a 25 percent mandatory statewide reduction in urban water use.

There is an obvious way to achieve this, raise the price of water. If its obvious why isn’t it the first thing California did some years back when it was clear that water was scarce? In some cases the hands of the state are tied by water rights allocated for commercial purposes, so lets focus on household consumption.

We know that the first tool the state reaches for is regulation. See, for example, the following memo from the California State water board. Interestingly, it begins by noting that the state is in the 4th year of a drought! Eventually, it is clear that regulation is insufficient and then, price increases are considered. In fact, the water reduction targets quoted from the NY Times above come from a report by the Governor of the state that also urges the use of

rate structures and other pricing mechanisms

to achieve reductions. Again, why is price last rather first? Is this because the state must maintain a credible reputation for not exploiting its monopoly power with water?

If one is going reduce consumption by raising prices, should it be an across the board price increase? Note that consumption is metered so the exact amount that is purchased by a household is known to the provider. The state also has access to other information: location, home size, family size and income. In principle, the state could price discriminate. Here is an example from the Irvine Ranch Water district. Each household is given an initial `allotment’ that depends on household size and area that is landscaped. Exceed the allotment and the price of water rises. For more details and the impact on consumption see the following paper. Is it obvious that this is the `correct’ mechanism?

 

 

Penn state runs auctions to license its intellectual property. For each license on the block there is a brief description of what the relevant technology is and an opening bid which I interpret as a reserve price. It also notes whether the license is exclusive or not. Thus, the license is sold for a single upfront fee. No royalties or other form of contingent payment. As far as I can tell the design is an open ascending auction.

In an earlier pair of posts I discussed a class of combinatorial auctions when agents have binary quadratic valuations. To formulate the problem of finding a welfare maximizing allocation let {x^k_j = 1} if object {j \in M} is given to agent {k \in N} and zero otherwise. Denote the utility of agent {k \in N} from consuming bundle {S \subseteq M} by

\displaystyle u_k(S) = \sum_{i \in S}u^k_i + \sum_{i, j \in S}w^k_{ij}.

The problem of maximizing total welfare is

\displaystyle \max \sum_{k \in N}\sum_{i \in M}u^k_ix^k_i + \sum_{k \in N}\sum_{i \neq j}w^k_{ij}x^k_ix^k_j

subject to

\displaystyle \sum_{k \in N}x^k_i \leq 1\,\, \forall i \in M

\displaystyle x^k_i \in \{0,1\}\,\, \forall i \in M, k \in N

I remarked that Candogan, Ozdaglar and Parrilo (2013) identified a solvable instance of the welfare maximization problem. They impose two conditions. The first is called sign consistency. For each {i,j \in M}, the sign of {w^k_{ij} } and {w^r_{ij}} for any {k, r \in N} is the same. Furthermore, this applies to all pairs {i, j \in M}.

Let {G^w} be a graph with vertex set {M} and for any {i,j \in M} such that {w^k_{ij} \neq 0} introduce an edge {(i,j)}. Because of the sign consistency condition we can label the edges of {G^w} as being positive or negative depending on the sign of {w^k_{ij}}. Let {E^+ = \{(i,j): w^k_{ij} \geq 0\}} and {E^- = \{(i,j): w^k_{ij} < 0\}}. The second condition is that {G^w} be a tree.

The following is the relaxation that they consider:

\displaystyle \max \sum_{k \in N}\sum_{i \in M}u^k_ix^k_i + \sum_{k \in N}\sum_{(i,j) \in E^+ \cup E^-}w^k_{ij}z^k_{ij}

subject to

\displaystyle \sum_{k \in N}x^k_i \leq 1\,\, \forall i \in M

\displaystyle z^k_{ij} \leq x^k_i, x^k_j\,\, \forall k \in N, (i,j) \in E^+

\displaystyle z^k_{ij} \geq x^k_i + x^k_j - 1\,\, \forall k \in N, (i,j) \in E^-

\displaystyle x^k_i, z^k_{ij} \in \{0,1\}\,\, \forall i \in M, k \in N

Denote by {P} the polyhedron of feasible solutions to the last program. I give a new proof of the fact that the extreme points of {P} are integral. My thanks to Ozan Candogan for (1) patiently going through a number of failed proofs and (2) being kind enough not to say :“why the bleep don’t you just read the proof we have.”

Let {{\cal C}} be the maximal connected components of {G^w} after deletion of the edges in {E^-} (call this {G^+}). The proof will be by induction on {|{\cal C}|}. The case {|{\cal C}| = 1} follows from total unimodularity. I prove this later.

Suppose {|{\cal C}| > 1}. Let {({\bar z}, {\bar x})} be an optimal solution to our linear program. We can choose {({\bar z}, {\bar x})} to be an extreme point of {P}. As {G^w} is a tree, there must exist a {C \in {\cal C}} incident to exactly one negative edge, say {(p,q)}. Denote by {P'} the polyhedron {P} restricted to just the vertices of {C} and by {Q} the polyhedron {P} restricted to just the vertices in the complement of {C}. By the induction hypothesis, both {P'} and {Q} are integral polyhedrons. Each extreme point of {P'} ({Q}) assigns a vertex of {C} (the complement of {C}) to a particular agent. Let {X_1, X_2, \ldots, X_a} be the set of extreme points of {P'}. If in extreme point {X_r}, vertex {p} is assigned to agent {k} we write {X_{rk} = 1} and zero otherwise. Similarly with the extreme points {Y_1, Y_2, \ldots, Y_b} of {Q}. Thus, {Y_{rk} = 1} is {Y_r} assigns vertex {q} to agent {k}. Let {v(X_{r})} be the objective function value of the assignment {X_r}, similarly with {v(Y_{rk})}.

Now {({\bar z}, {\bar x})} restricted to {P'} can be expressed as {\sum_r\lambda_{r}X_{r}}. Similarly, {({\bar z}, {\bar x})} restricted to {Q} can be expressed as {\sum_r\mu_{r}Y_{r}}. We can now reformulate our linear program as follows:

\displaystyle \max \sum_r\lambda_{r}v(X_{r}) + \sum_r\mu_{r}v(Y_{r}) -\sum_{k \in N} |w^k_{pq}|y^k_{pq}

subject to

\displaystyle -\sum_r\lambda_{rk} = -1

\displaystyle -\sum_r\mu_{rk} = -1

\displaystyle \sum_{r: X_{rk} = 1}\lambda_{r}X_{r} + \sum_{r: Y_{rk} = 1}\mu_{r}Y_{r} \leq y^k_{pq} + 1\,\, \forall k \in N

\displaystyle \lambda_{r}, \mu_{r}, y^k_{pq} \geq 0\,\, \forall r, k

The constraint matrix of this last program is totally unimodular. This follows from the fact that each variable appears in at most two constraints with coefficients of opposite sign and absolute value 1 (this is because {X_{rk}} and {X_{rk'}} cannot both be 1, similarly with the {Y}‘s). Total unimodularity implies that the last program has integral optimal solution and we are done. In fact, I believe the argument can be easily modified to to the case where in {G^w} every cycle must contain a positive even number of negative edges.

Return to the case {|{\cal C}| = 1}. Consider the polyhedron {P} restricted to just one {C \in {\cal C}}. It will have the form:

\displaystyle \sum_{k \in N}x^k_i \leq 1\,\, \forall i \in C

\displaystyle z^k_{ij} \leq x^k_i, x^k_j\,\, \forall k \in N, (i,j) \in E^+ \cap C

\displaystyle x^k_i, z^k_{ij} \in \{0,1\}\,\, \forall i \in C, k \in N

Notice the absence of negative edges. To establish total unimodularity we use the Ghouila-Houri (GH) theorem. Fix any subset, {S}, of rows/constraints. The goal is to partition them into two sets {L} and {R} so that column by column the difference in the sum of the non-zero entries in {L} and and the sum of the nonzero entries in {R} differ by at most one.

Observe that the rows associated with constraints {\sum_{k \in N}x^k_i \leq 1} are disjoint, so we are free to partition them in any way we like. Fix a partition of these rows. We must show to partition the remaining rows to satisfy the GH theorem. If {y^k_{ij} - x^k_i \leq 0} is present in {S} but {y^k_{ij} -x^k_j \leq 0} is absent (or vice-versa), we are free to assign the row associated with {y^k_{ij} - x^k_i \leq 0} in any way to satisfy the GH theorem. The difficulty will arise when both {y^k_{ij}}, {x^k_i} and {x^k_j} are present in {S}. To ensure that the GH theorem is satisfied we may have to ensure that the rows associated with {y^k_{ij} - x^k_i \leq 0} and {y^k_{ij} -x^k_j \leq 0} be separated.

When {S} is the set of all constraints we show how to find a partition that satisfies the GH theorem. We build this partition by sequentially assigning rows to {L} and {R} making sure that after each assignment the conditions of the GH theorem are satisfied for the rows that have been assigned. It will be clear that this procedure can also be applied when only a subset of constraints are present (indeed, satisfying the GH theorem will be easier in this case).

Fix an agent {k \in N}. The following procedure will be repeated for each agent in turn. Pick an arbitrary vertex in {C} (which is a tree) to be a root and direct all edges `away’ from the root (when {S} is a subset of the constraints we delete from {C} any edge {(i,j)} in which at most one from the pair {y^k_{ij} - x^k_i \leq 0} and {y^k_{ij} -x^k_j \leq 0} appears in {S}) . Label the root {L}. Label all its neighbors {R}, label the neighbors of the neighbors {L} and so on. If vertex {i \in C} was labeled {L} assign the row {\sum_{k \in N}x^k_i \leq 1} to the set {L} otherwise to the row {R}. This produces a partition of the constraints of the form {\sum_{k \in N}x^k_i \leq 1} satisfying GH.

Initially, all leaves and edges of {C} are unmarked. Trace out a path from the root to one of the leaves of {C} and mark that leaf. Each unmarked directed edge {(i,j)} on this path corresponds to the pair {y^k_{ij} - x^k_i \leq 0} and {y^k_{ij} -x^k_j \leq 0}. Assign {y^k_{ij} - x^k_i \leq 0} to the same set that is the label of {i}. Assign {y^k_{ij} - x^k_j \leq 0} to the same set that is the label of vertex {j}. Notice that in making this assignment the conditions of the GH theorem continues to satisfied. Mark the edge {(i,j)}. If we repeat this procedure again with another path from the root to an unmarked leaf, we will violate the GH theorem. To see why suppose the tree contains edge {(i,j)} as well as {(i,t)}. Suppose {i} was labeled {L} on the first iteration and {(i,j)} was marked. This means {y^k_{ij} - x^k_{i} \leq 0} was assigned to {L}. Subsequently {y^k_{it} - x^k_i \leq 0} will also be assigned to {L} which will produce a partition that violates the GH theorem. We can avoid this problem by flipping the labels on all the vertices before repeating the path tracing procedure.

What is the institutional detail that makes electricity special? Its in the physics that I will summarize with a model of DC current in a resistive network. Note that other sources, like Wikipedia give other reasons, for why electricity is special:

Electricity is by its nature difficult to store and has to be available on demand. Consequently, unlike other products, it is not possible, under normal operating conditions, to keep it in stock, ration it or have customers queue for it. Furthermore, demand and supply vary continuously. There is therefore a physical requirement for a controlling agency, the transmission system operator, to coordinate the dispatch of generating units to meet the expected demand of the system across the transmission grid.

I’m skeptical. To see why, replace electricity by air travel.

Let {V} be the set of vertices and {E^*} the set of edges a the network. It will be convenient in what follows to assign (arbitrarily) an orientation to each edge in {E^*}. Let {E} be the set of directed arcs that result. Hence, {(i,j) \in E} mens that the edge {(i,j)} is directed from {i} to {j}. Notice, if {(i,j) \in E}, then {(i,j) \not \in E}.

Associated with each {(i,j) \in E} is a number {x_{ij}} that we interpret as a flow of electricity. If {x_{ij} > 0} we interpret this to be a flow from {i} to {j}. If {x_{ij} < 0} we interpret this as a flow from {j} to {i}.

  1. Let {\rho_{ij}} is the resistance on link {(i,j)}.
  2. {c_i} unit cost of injecting current into node {i}.
  3. {v_i} marginal value of current consumed at node {i}.
  4. {d_i} amount of current consumed at node {i}.
  5. {s_i} amount of current injected at node {i}.
  6. {K_{ij}} capacity of link {(i,j)}.

Current must satisfy two conditions. The first is conservation of flow at each node:

\displaystyle s_i + \sum_{k: (k,i) \in E}x_{ji} = \sum_{j: (i,j) \in E}x_{ij} + d_i\,\, \forall i \in V

The second is Ohm’s law. There exist node potentials {\{\phi_i\}_{i \in V}} such that

\displaystyle \rho_{ij}x_{ij} = \phi_i - \phi_j\,\, \forall (i,j) \in E.

Using this systems equations one can derive the school boy rules for computing the resistance of a network (add them in series, add the reciprocals in parallel). At the end of this post is a digression that shows how to formulate the problem of finding a flow that satisfies Ohm’s law as an optimization problem. Its not relevant for the economics, but charming nonetheless.

At each node {i \in V} there is a power supplier with constant marginal cost of production of {c_i} upto {S_i} units. At each {i \in V} there is a consumer with constant marginal value of {v_i} upto {D_i} units. A natural optimization problem to consider is

\displaystyle \max \sum_{i \in V}[v_id_i - c_is_i]

subject to

\displaystyle \sum_{j: (i,j) \in E}x_{ij} -\sum_{j: (j,i) \in E}x_{ji} - s_i + d_i= 0\,\, \forall i \in V

\displaystyle \rho_{ij}x_{ij} = \mu_i - \mu_j\,\, \forall (i,j) \in E

\displaystyle -K_{ij} \leq x_{ij} \leq K_{ij}\,\, \forall (i,j) \in E

\displaystyle 0 \leq s_i \leq S_i\,\, \forall i \in V

\displaystyle 0 \leq d_i \leq D_i\,\, \forall i \in V

This is the problem of finding a flow that maximizes surplus.

Let {{\cal C}} be the set of cycles in {(V, E^*)}. Observe that each {C \in {\cal C}} corresponds to a cycle in {(V, E)} if we ignore the orientation of the edges. For each cycle {C \in {\cal C}}, let {C^+} denote the edges in {E} that are traversed in accordance with their orientation. Let {C^-} be the set of edges in {C} that are traversed in the opposing orientation.

We can project out the {\phi} variables and reformulate as

\displaystyle \max \sum_{i \in V}[v_id_i - c_is_i]

subject to

\displaystyle \sum_{j: (i,j) \in E}x_{ij} -\sum_{j: (j,i) \in E}x_{ji} - s_i + d_i= 0\,\, \forall i \in V

\displaystyle \sum_{(i,j) \in C^+}\rho_{ij}x_{ij} - \sum_{(i,j) \in C^-}\rho_{ij}x_{ij} = 0\,\, \forall \,\, C \in {\cal C}

\displaystyle -K_{ij} \leq x_{ij} \leq K_{ij}\,\, \forall (i,j) \in E

\displaystyle 0 \leq s_i \leq S_i\,\, \forall i \in V

\displaystyle 0 \leq d_i \leq D_i\,\, \forall i \in V

Recall the scenario we ended with in part 1. Let {V = \{1, 2, 3\}}, {E = \{(1,3), (1,2), (2,3)\}} and in addition suppose {\rho_{ij} =1} for all {(i,j)}. Only {(1,3)} has a capacity constraint of 600. Let {D_1 = D_2 = 0} and {S_3 = 0}. Also {c_1 = 20} and {c_2 = 40} and each have unlimited capacity. At node 3, the marginal value is {V > 40} upto 1500 units and zero thereafter. The optimization problem is

\displaystyle \max Vd_3 - 20s_1 - 40 s_2

subject to

\displaystyle x_{12} + x_{13} - s_1 = 0

\displaystyle x_{23} - s_2 - x_{12} = 0

\displaystyle d_3 - x_{13} - x_{23} = 0

\displaystyle x_{13} - x_{23} - x_{12} = 0

\displaystyle -600 \leq x_{13} \leq 600

\displaystyle 0 \leq d_3 \leq 1500

Notice, for every unit of flow sent along {(1,3)}, half a unit of flow must be sent along {(1,2)} and {(2,3)} as well to satisfy the cycle flow constraint.

The solution to this problem is {x_{13} = 600}, {x_{12} = -300}, {x_{23} = 900}, {s_1 = 300}, {s_2 = 1200} and {d_3 = 1500}. What is remarkable about this not all of customer 3’s demand is met by the lowest cost producer even though that producer has unlimited capacity. Why is this? The intuitive solution would have been send 600 units along {(1,3)} and 900 units along {(1,2) \rightarrow (2,3)}. This flow violates the cycle constraint.

In this example, when generator 1 injects electricity into the network to serve customer 3’s demand, a positive amount of that electricity must flow along every path from 1 to 3 in specific proportions. The same is true for generator 2. Thus, generator 1 is unable to supply all of customer 3’s demands. However, to accommodate generator 2, it must actually reduce its flow! Hence, customer 3 cannot contract with generators 1 and 2 independently to supply power. The shared infrastructure requires that they co-ordinate what they inject into the system. This need for coordination is the argument for a clearing house not just to manage the network but to match supply with demand. This is the argument for why electricity markets must be designed.

The externalities caused by electricity flows is not a proof that a clearing house is needed. After all, we know that if we price the externalities properly we should be able to implement the efficient outcome. Let us examine what prices might be needed by looking at the dual to the surplus maximization problem.

Let {y_i} be the dual variable associated with the flow balance constraint. Let {\lambda_C} be associated with the cycle constraints. Let {\nu_i} and {\theta_i} be associated with link capacity constraints. Let {\mu_i} and {\sigma_i} be associated with the remaining tow constraints. These can be interpreted as the profit of supplier {i} and the surplus of customer {i} respectively. For completeness the dual would be:

\displaystyle \min \sum_{(i,j) \in E}[\nu_{ij} + \theta_{ij}]K_{ij} + \sum_{i \in V}[S_i \mu_i + D_i \sigma_i]

subject to

\displaystyle -\theta_{ij} + \nu_{ij} + \rho_{ij}\sum_{C^+ \ni (i,j)}\lambda_C - \rho_{ij}\sum_{C^- \ni (i,j)}\lambda_C + y_i - y_j = 0\,\, \forall (i,j) \in E

\displaystyle \mu_i - y_i \geq -c_i\,\, \forall i \in V

\displaystyle \sigma_i + y_i \geq v_i\,\, \forall i \in V

\displaystyle \nu_{ij}, \theta_{ij}, \mu_i, \sigma_i \geq 0\,\, \forall i \in V,\,\,\forall (i,j) \in E

Now {y_i} has a natural interpretation as a price to be paid for consumption at node {i} for supply injected at node {i}. {\mu_i} and {\nu_i} can be interpreted as the price of capacity. However, {\lambda_C} is trickier, price for flow around a cycle? It would seem that one would have to assign ownership of each link as well as ownership of cycles in order to have a market to generate these prices.

In part two, as promised, I turn to the welfare maximization problem. To formulate the problem of finding a welfare maximizing allocation let {x^k_j = 1} if object {j \in M} is given to agent {k \in N} and zero otherwise. Denote the utility of agent {k \in N} from consuming bundle {S \subseteq M} by

\displaystyle u_k(S) = \sum_{i \in S}u^k_i + \sum_{i, j \in S}w^k_{ij}.

The problem of maximizing total welfare is

\displaystyle \max \sum_{k \in N}\sum_{i \in M}u^k_ix^k_i + \sum_{k \in N}\sum_{i \neq j}w^k_{ij}x^k_ix^k_j

subject to

\displaystyle \sum_{k \in N}x^k_i \leq 1\,\, \forall i \in M

\displaystyle x^k_i \in \{0,1\}\,\, \forall i \in M, k \in N

Welfare maximization with BQP preferences is in general NP-hard. One proof relies on a reduction to the multi-way cut problem. Given a graph {G=(V,E)} with edge weight {c_{ij}} for each {(i,j) \in E}, and a set of terminal vertices {T = \{v_1, v_2, \ldots, v_n\}}, a multiway cut is a set of edges whose removal disconnects every pair of terminal vertices. The problem of finding the multiway cut of minimum total weight is called the multiway cut problem. When {T} consists of only two terminals ({k = 2}) the problem reduces to the well known minimum cut problem. For {k \geq 3}, it is known that the problem is {NP-}hard even on planar graphs.

We can obtain the multiway cut problem by setting {u^k_i = 0} for all {k \in N} and {i \in M} and {w^k_{ij} = c_{ij}} for all {k \in N} and {(i,j) \in E}. Any pair {(i,j)} such that {x^k_ix^r_j = 1} for {k \neq r} will be part of a multi-way cut. This reduction implies that welfare maximization when {w^k_{ij} \geq 0} for all {k \in N} and {i,j \in M} is NP-hard. This is in contrast to the case of surplus maximization.

,Candogan, Ozdaglar and Parrilo (2013), the paper that prompted this post, identify a solvable instance of the welfare maximization problem. They impose two conditions. The first is called sign consistency. For each {i,j \in M} the sign of {w^k_{ij} } and {w^r_{ij}} for any {k, r \in N} is the same. Furthermore, this applies to all pairs {i, j \in M}. Sign consistency by itself is not sufficient to obtain a solvable instance. Another condition is needed. Let {G^w} be a graph with vertex set {M} and for any {i,j \in M} such that {w^k_{ij} \neq 0} introduce an edge {(i,j)}. The second condition is that {G^w} be a tree. Interestingly, Erdos and Sz\'{e}kely (1995) show that a generalization of the multiway cut problem which corresponds to welfare maximization under sign consistency and {u^k_i = 0} for all {k \in N} and {i \in M}, is polynomially solvable when the underlying graph {G} is a tree. The Candogan, Ozdaglar and Parrilo (COP) proof is based on a dynamic programming argument similar to the one used in Erdos and Sz\'{e}kely (1994).

The key result in COP is the following natural linearization of the welfare maximization problem admits an integral optimal solution.

\displaystyle \max \sum_{k \in N}\sum_{i \in M}u^k_ix^k_i + \sum_{k \in N}\sum_{i \neq j}w^k_{ij}y^k_{ij}

subject to

\displaystyle \sum_{k \in N}x^k_i \leq 1\,\, \forall i \in M

\displaystyle y^k_{ij} \leq \{x^k_i, x^k_j\}^-\,\, \forall w^k_{ij} > 0

\displaystyle y^k_{ij} \geq x^k_i + x^k_j -1\,\, \forall w^k_{ij} < 0

\displaystyle x^k_i \in \{0,1\}\,\, \forall i \in M, k \in N

There is a connection between the welfare maximization problem and packing subtrees into trees that I want to highlight. It suggests a possible avenue by which one might enlarge the class of preferences COP consider.

Because of the sign consistency condition we can label the edges of {G^w} as being positive or negative depending on the sign of {w^k_{ij}}. Let {E^+ = \{(i,j): w^k_{ij} \geq 0\}} and {E^- = \{(i,j): w^k_{ij} < 0\}}. Let {{\cal C}} be the maximal connected components of {G^w} after deletion of the edges in {E^-} (call this {G^+}). For any {C \in {\cal C}} and {S \subseteq C} let

\displaystyle v_k(S) = \sum_{i \in S}u^k_i + \sum_{i,j \in S}w^k_{ij}.

By the way, for each {C \in {\cal C}} and {k \in N}, {v_k} is supermodular over the subsets of {C}. Let {z_k(S) = 1} if {S \subseteq C} is assigned to agent {k} and zero otherwise. The problem of finding a welfare maximizing allocation can be expressed as follows:

\displaystyle \max \sum_{k \in N}\sum_{C \in {\cal C}}\sum_{S \subseteq C}v_k(S)z_k(S) - \sum_{k \in N}\sum_{(i,j) \in E^-}|w^k_{ij}|y^k_{ij}

subject to

\displaystyle \sum_{S \ni i}\sum_{k \in N}z_k(S) \leq 1\,\, \forall i \in M,\,\, S \subseteq C \in {\cal C}

\displaystyle y^k_{ij} \geq \sum_{S \ni i}z_k(S) + \sum_{S \ni j}z_k(S) - 1\,\, \forall k \in N, (i,j) \in E^-

\displaystyle z_k(S) \in \{0,1\}\,\, \forall k \in N, S \subseteq C \in {\cal C}

\displaystyle y^k_{ij} \in \{0,1\}\,\, \forall k \in N, (i,j) \in E^-

In the above program, we can, without loss, restrict attention to subsets {S} that a subtrees (connected subgraphs) of {E^+}. To see why, suppose in that in some optimal solution to the above integer program, {z_k(S) = 1} where {S} is not a subtree. Then, we can write {S = A \cup B} where both {A} and {B} are in the same component of {C} as {S} is. Furthermore, it must be the the case that there is no edge {(i,j) \in E^+} such that {i \in A} and {j \in B}. Therefore, {v_k(S) = v_k(A) + v_k(B)}. That means we can construct a new optimal solution by setting {z_k(S) = 0} and raising {z_k(A)} and {z_k(B)} to 1. Note, in the original solution {z_k(A), z_k(B) =0} by virtue of the first constraint. As long as {S} is not a subtree we can repeat this argument.

Hence, if we let {{\cal T}} be the set of subtrees of {G^+}, the welfare maximization problem can be expressed as follows:

\displaystyle \max \sum_{k \in N}\sum_{T \in {\cal T}}v_k(T)z_k(T) - \sum_{k \in N}\sum_{(i,j) \in E^-}|w^k_{ij}|y^k_{ij}

subject to

\displaystyle \sum_{T \in {\cal T}}\sum_{T \ni i}\sum_{k \in N}z_k(T) \leq 1\,\, \forall i \in M,

\displaystyle y^k_{ij} \geq \sum_{T \ni i}z_k(T) + \sum_{S \ni j}z_k(S) - 1\,\, \forall k \in N, (i,j) \in E^-

\displaystyle z_k(S) \in \{0,1\}\,\, \forall k \in N, T \in {\cal T}

\displaystyle y^k_{ij} \in \{0,1\}\,\, \forall k \in N, (i,j) \in E^-

Its important to emphasize that no {T \in {\cal T}} contains a negative edge.

Were it not for the second set of the constraints, integrality would follow from Barany, Edmonds and Wolsey (1986). I’m not aware of this variation of the tree packing problem having been considered. A follow up paper by Aghezzaf and Wolsey (1994) comes close in the sense of allowing for a piecewise linear concave objective function.

Kellogg faculty blogroll