A Proposed Auction System for Public Housing

Following on from the counterfactual public housing system I previously wrote about, I would like to flesh out the auction system used to allocate HDB flats.

[Edit: But before moving on, I would like to state that I do understand that when supply can be manipulated, prices will naturally shoot up. Thus, it is important that this be executed only once there is a buffer stock of flats and only if there is explicit policy to maintain that buffer stock.]

The allocation of HDB flats will be done through the conduct of regular VCG-based auctions of all available flats in Singapore by HDB, with a reserve price on each flat set to a reasonable value reflective of cost or cost-plus. Interested buyers would first register with HDB and then be issued with accounts to bid for flats. They would then place bids for each flat they are interested in.

In what follows, I intend to recapitulate my description of the auction mechanism and how it works. Then, I will describing the kinds of outcomes generated by the auction through graphs generated from numerical experiments. Some of this will be repeated material (for which I apologize), as it is intended to make this as self-contained as possible.

Auctions and Free-Market Prices
Before moving on, I would like to emphasize that a major aim of using such an auction is to get at the true free market values of flats. I have previously mentioned that personal valuations for flats take into account both economic, relational and personal factors that are mostly unaccounted for in “independent valuations”. Furthermore, the phenomenon of substitution throws another wrench into the work of arriving at an accurate valuation. A household may be willing to consider 3-room, 4-room or 5-room flats. If valuers do not account for this, they will double (or triple) count demand, leading to artificially high values. (This insight was obtained from viewing allocation and pricing output from the auction based on various scenarios.)

While I concede that valuers may have some knowledge of substitution patterns, difficult as they might be to measure, there is little incentive to use it. Furthermore, it is a "forgivable mistake", noting the simplistic "price is determined by intersecting supply and demand" image that many have of economics.

Eliminating Dilemmas
It is, perhaps, underemphasized that potential buyers face dilemmas when flat issues are conducted in “unfortunate orders”. One’s second choice location might be up first, followed by one’s first choice. One then faces the dilemma of whether or not to apply in the first issue. The associated “what if” questions are a needless hassle. Furthermore, it stands to reason that clearing a national public housing auction is likely to increase allocative efficiency.

Characteristics of the Proposed VCG-based Auction
By allocating all available flats (old and new) through a VCG-based auction mechanism where bidders articulate their valuations for the (multiple) flat types they desire in their bids (and revise them periodically until the auction closes), the following will be achieved:

(i) information about multiple flat types is integrated in the pricing and allocation outcome, (ii) a truly free-market allocation is arrived at, (iii) allocated flats are priced at the lowest possible bid which could have been made without changing the outcome, and (iv) each bidder gains a better picture of his/her preferences as the auction progresses.

It would certainly be agreeable that these are desirable socio-economic outcomes.

Having hopefully motivated the use of an auction mechanism to allocate flats, I would like to sketch the mechanics of the auction. Firstly, this auction mechanism will stand up easily to scrutiny because it is based on a well-known (and well-studied) family of mechanisms called Vickrey-Clarke-Groves (VCG) Mechanisms. In the auction, each bid price is intended to be the maximum amount the relevant bidder is willing to pay for a flat of a particular type in a particular location. Bidders will make bids for every type of flat they are interested in.

The outcome of the auction will be the socially optimal allocation based on the bids made and subject to allocation constraints that HDB has such as reserved quantities for first timers and the Ethnic Integration Policy (EIP). This leads to the achievement of (i).

Furthermore, it may be said that only preferences of buyers and the constraints of the (non-profit seeking) HDB are incorporated into the allocation. As such, the input of external parties seeking to profit off the outcome of the auction is minimized, in all it is arguable that this leads to (ii).

The pricing of each allocated flat is done via externality pricing. That is to say, for each winning bidder, the maximum social welfare of all bidders is computed again with the winning bidder removed. Necessarily, this new number is never larger than the maximum social welfare when all bidders are included. Call the difference between these numbers w. The price that bidder pays is his bid less w. With some thought, it would be clear that had he bid anything more that the price he paid, allocating him that flat would certainly remain part of the optimal allocation, and had he bid less, allocating him that flat would no longer be part of the optimal allocation. For mechanism design neophytes, it may require a bit more time to understand this argument, but it explains (iii). From a different perspective, it stands to reason that the optimal bidding strategy is for a bidder to truthfully bid the actual maximum value he is willing to pay for a flat, and the auction mechanism will not use this information to extract additional revenue from him.

This leads to a major criticism of the VCG Mechanism by academics and auction practitioners: revenue from VCG-based auctions compares poorly to that from other auction forms. This arises as VCG enforces the property of truthfulness by charging winning bidders the lowest amount they could have bid and been allocated a flat, an amount typically much lower than the amount bid, as mentioned in the explanation of (iii). However, having less revenue extracted from winning bidders turns out to be a strength for allocating public housing. Since the mission of HDB is to "provide affordable homes of quality and value", it may be said that selling flats at the reserve price is a mark of successfully meeting housing demand in an affordable fashion and low revenue from the auction is not, in fact, a problem.

Consider conducting the auction in manner where the tentative outcome for one’s bids and the tentative prices for flats in each category are made available at regular intervals, and bidders are able to update their bids in response to tentative outcomes. It cannot be assumed that people have full clarity on the real value of a flat to them. By viewing a tentative outcome, they may realize that they are willing to pay more for a flat of a particular type, or that they have overvalued a flat of a particular type. This explains (iv). It is suggested that prior to the close of the auction, there be a (long) period where results are no longer updated to reduce the incentive of last minute “sniping”.

The Allocation Model for our VCG-based Auction
The Allocation Model is basically defines the characteristics of the socially optimal allocation, expressing it as a mixed-integer linear optimization problem, the objective of which is to pick an allocation which maximizes the total sum of the bids corresponding to allocated flats. Note, however, that the price of the flat is at most the bid price and usually strictly lower.

The parameters that define the problem are:

v_ij: Bid price of bidder i for a flat of category j
m_j: Number of available flats in category j
o_jr: Maximum of available flats in category j that members of racial group r may buy

... and the variables that define the allocation:
x_ij: Boolean variable defining whether bidder i was allocated a flat in category j (for the bidder representing HDB, this is a not a boolean variable, but rather a non-negative integer variable)

So, the following optimization problem is to be solved using linear optimization software: (I know I said that this is an integer program, but the linear relaxation is equivalent. This can be easily shown by an appeal to the Ghouila-Houri characterization of Total Unimodularity, which proves that optimizing any linear objective over the above feasible set can be done efficiently.)

maximize Sum[over bidders i and flat categories j] v_ij x_ij
subject to:

Sum[over flat categories j] x_ij ≤ 1 for each bidder i except HDB (1)

Sum[over bidders i] x_ij = m_j for each flat category j (2)

Sum[over bidders i in racial group r] x_ij ≤ o_jr for each flat category j and racial group r (4)

Note that HDB bids the reserve price for each category. Also, bidders not bidding for a flat category bid zero.

The set of constraints (1) mean that each bidder (other than HDB) may be allocated at most 1 flat. The set of constraints (2) mean that all flats are allocated. The set of constraints (3) serves to reserve some fraction of flats for first timers. This in turn results in higher prices on second timers due to the higher externality they will impose on other second timers when allocated flats. The set of constraints (4) reflects the government's “Ethnic Integration Policy” (EIP). The inclusion of (4) will probably translate the previous time to sell/time to buy difference for different ethnic groups to a price difference. With this constraint, it would really pay to be among more of those of other races.

One can prove that if the bid prices (other than HDB's) are all not equal (and other non-equal "difference" conditions hold), this integer optimization problem can be relaxed to an equivalent linear optimization problem. (This can be easily engineered and implies big computational savings, which will be necessary for quickly producing an allocation and pricing the allocated flats.) Such a scenario can be engineered by requiring minimal bid increments (of say $100) and incorporating random tie breaking by doctoring bids by random values smaller than the bid increment. This practical measure is similar to allocating flats by ballot, but differs in that it first takes allocative efficiency into account.

Examples
Having outlined the characteristics of the auction, allow me to provide some concrete (albeit simple) examples of bids and outcomes. If only 800 bidders compete for an issue of 1000 "identical" flats, regardless of how wildly high some bidders might bid, all bidders bidding at least the reserve price pay just the reserve price for their flat. In contrast, if 1800 bidders compete for an issue of 1000 "identical" flats, all bidding more than the reserve price, the 1000 winning bidders would end up paying the 1001-st highest bid price. In the setting of auctioning identical items, the VCG auction reduces to the k-th price auction.

One might visualize the results by using bid prices to describe "demand" and relating it to the quantity of the respective type of flat supplied. Notably, this auction tends to see winning bidders paying less than the price determined by the point where the (assumed vertical) supply curve intersects the "demand curve". This is due to substitution effects, as HDB flats of different types are related goods. This is true for all bidders when no first timer and EIP constraints are included, when those constraints are included this would still typically be true for the first timers.

Now let us look at some auction results. The graphs that follow will depict demand for a type of flat (bid prices), fulfillment (allocation of flats at some price), flat supply for this type of flat, and the reserve price for this type of flat. I've neglected to label the axes, but the vertical axis denotes price and the horizontal axis denotes quantity.

The first example (Figure 1) is a fairly pedestrian one. This particular instance reflects supply exceeding demand for this type of flat, so all demand is satisfied at the reserve price.

Figure 1: Supply exceeds demand

The next examples (Figure 2 and Figure 3) are part of a small-medium sized example with 2000 bidders (1712 of whom made at least 1 bid) competing for 521 flats in 10 categories. (Data was randomly generated.) About 40% of the bidders are second timers and for each flat category, at most 15% to 30% of the flats may be allocated to second timers. The EIP constraints were not imposed.

In Figure 2, one sees that 13 bidders paid 146 for their flats while the other 44 paid 115. The former group were all second timers, while the latter were all first timers. This illustrates the effect of restricting the number of flats available to a certain group. A similar effect is visible in Figure 3, from the same example. In general, with k "groups" with different constraints on each, one would expect to see k price levels in the fulfillment curve.

Figure 2: Flat Category C0 from a Small-Medium Sized Example

Figure 3: Flat Category C4 from a Small-Medium Sized Example

The next examples (Figure 4 and Figure 5) are part of a small-medium sized example with 2000 bidders (1476 of whom made at least 1 bid) competing for 297 flats in 10 categories. (Again, data was randomly generated.) About 40% of the bidders are second timers and for each flat category, at most 15% to 30% of the flats may be allocated to second timers. Each flat category was restricted to 70% Chinese buyers, 15% Malay buyers and 10% Indian buyers. However, 80% of the bidders were Chinese, 5% were Malay and 10% were Indian.

In Figures 4 and 5, one sees multiple price levels, corresponding to different subsets of bidders, with each group facing different forms of restriction that increase, in varying degrees, the level of competition for flats between bidders in the respective subsets. In both figures, the highest prices are paid by the second timer ethnic Chinese buyers, due to the restrictions placed on them and the higher competition for available flats within their ethnic group.

Figure 4: Flat Category C0 from a Small Example with EIP Constraints and Unbalanced Demand from Ethnic Groups

Figure 5: Flat Category C1 from a Small Example with EIP Constraints and Unbalanced Demand from Ethnic Groups

Hopefully the above examples have been helpful in illustrating how the auction behaves. While some of the examples suggest that prices can get high, I would like to assure the reader that they only get high in the event that supply is inadequate. The fact is, examples with adequate supply are boring, probably with all flats selling at or near the reserve price, these were constructed to exhibit "interesting behavior".

The small-medium example of Figures 2-3 took about 5 sec to solve per optimization problem using an open source solver (GLPK). With about 500 allocations, it actually took just under 50 min to compute the pricing decisions for each flat allocated. A more realistic example with about 15000 bidders competing for about 5000 flats takes about 5 min to solve. However, to generate tentative prices in the auction prices for each and every flat allocated need not be computed. With parallization, much larger instances could be solved to allow tentative results to be refreshed every hour. Commercial software (CPLEX/Gurobi/Xpress MP) might be used if they're found to be much faster.

Closing Remarks
In my assessment, this auction mechanism is technically feasible and produces sensible results. I think this is worthy of exploration as a means for allocating flats in our public housing system.

In presenting this and advocating for it I do bear in mind a certain cautionary note, as so well put by Malcolm Gladwell, against the "infatuation with the things we make". We all have our blinders. With that in mind, I would like to receive comments on this especially those that point out what I've missed.