Skip to main content

VCG Principle and Expert Networks

There are many expert networks or question and answer sites on the Internet such as Quora and Yahoo Answers. These sites crowd-source answers to questions posted and rely on a community of experts to answer questions. However, the answers tend to be of varying quality and responses to questions may not be in real-time. An on-demand expert network named Fountain was created to solve this problem. It matches users to experts in the relevant query category in real-time using a database of experts. All experts in this database are interviewed to ensure high quality expertise.

Fountain takes in a natural language query from a user, matches that user to multiple experts suited to answering that query and contacts all these experts simultaneously. The expert who first confirms he/she can answer the query is then put in contact with the user. The current pricing model is 5 dollars per consultation where the consultation time varies across categories. This model is not very scalable and fails to allocate experts to users efficiently. Imagine if the system had millions of users and only thousands of experts. In this scenario, experts would be overwhelmed with requests to answer queries. The price of a consultation in a particular category (such as gardening) should go up with increasing demand from users. The experts are a scarce resource and should be allocated to the users with the highest willingness to pay. Furthermore, the current pricing model does not take into account the quality of each expert.

To solve the problem of poor resource allocation, we can use the VCG (Vickrey-Clarke-Groves) principle to hold a second price auction for multiple experts in a particular category. If each consultation has a fixed duration, we can hold VCG auctions for each category in real-time for the currently available experts in that category. Assume that we know the quality of each expert because we track user satisfaction on-site via feedback forms and each expert has an expert quality score in an interval of 1 to 5 on the real line. Each user has an unknown query value in dollars. Since the dominant strategy in VCG is to bid your true value, each user bids his true query value. The expert quality score is used as a multiplier on the query bid to determine the value of a particular expert to a user.

Consider a situation where we have 3 experts (a, b, c) and 3 users (x, y, z). Note that in a scenario where there are more users than experts, we simply create fictional experts with an expert quality score of 0 such that the number of users equals the number of experts. Expert a has a quality score of 5, expert b has a quality score of 3 and expert c has a quality score of 2. User x values an answer to his garden gnome query at 10 dollars, user y is willing to pay 5 dollars to consult an expert about water fountains in his garden and user z would pay 3 dollars for advice on pest-proofing his carrot patch.

In the first step of the VCG procedure, we ask each user to announce values or bids. Since the dominant strategy in VCG is to bid your true value, each user bids his true query value. The second step of VCG is to create a matching that maximises total valuation. In the matching with maximum total valuation, expert a is assigned to user x, expert b is assigned to user y and expert c is assigned to user z. This matching has a total valuation of 50 + 15 + 6 = 71. The third step of VCG is to charge each user a price that is equal to the harm that each user inflicts on other users by taking his assigned expert. The price Pij of user j taking expert i is equal to the maximum total valuation of the assignment of users to experts with user j omitted, minus the maximum total valuation of the assignment of users to experts with user j and expert i omitted. This is equivalent to the harm that user j inflicts on other users by taking his assigned expert i.

Expert Quality Score Expert User Query Value (dollars) Query Bid (dollars) Value of a Value of b Value of c
5 a x 10 10 50 30 20
3 b y 5 5 25 15 10
2 c z 3 3 15 9 6


We will now calculate the VCG prices using the procedure described above. Please consult the above table for reference. The price paid by user x for expert a is Pax = (25 + 9) – (15 + 6) = 13 dollars. The price paid by user y for expert b is Pby = (50 + 9) – (50 + 6) = 3 dollars. The price paid by user z for expert c is Pcz = (50 + 15) – (50 + 15) = 0 dollars. In this case, we can simply charge a reserve price of a few dollars instead of giving away expert advice for free! The VCG mechanism results in a more efficient allocation of users to experts. The users who are willing to pay the most will be allocated experts and among these users, the users who bid higher will get better quality experts. The calculated prices seem reasonable for around 5 minutes of consultation.

The VCG mechanism may solve the problem of poor resource allocation in Fountain’s model but there are still scalability problems. In the main article, Richard Socher states that “you might need multiple experts to answer a single question” when dealing with more complex questions that span multiple topics/categories. All the models discussed above allocate at most one expert to each user. It is hard to develop a pricing model that allocates multiple experts to a particular user and still preserves efficiency in allocating resources. A successful on-demand expert network must address this problem – otherwise it will not be able to scale to millions of users.

Main article:

Relevant sources:

Easley, David, and Jon Kleinberg. Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press, 2010.


Leave a Reply

Blogging Calendar

October 2014