QUESTION
Facebook has all sorts of personal information and thus, can entice advertisers by promising they can deliver ads targeted to specific demographic groups. Advertisers are drooling and ready to fork over some big bucks. Now Facebook is trying to figure out an efficient method to deliver targeted ads to as many users as possible.
The first step in this process is to classify people into demographic groups. On Facebook these classifications might be based on things such as geographic location, age, interest in a type of music, college major. We'll assume this step is taken care of by the data mining group and they have identified k demographic groups G_1, G_2, ..., G_k. Note that these groups can overlap; G_1 could be people who live in Bellingham, G_2 could be people who like pizza, G_3 could be students majoring in computer science.
The marketing department at Facebook is forging contracts with m different advertisers to show a certain number of ads to users of the site. Here's what a contract with the ith advertiser looks like:
For a subset of the demographic groups, X_i = {G_1, G_2, ..., G_k}, advertiser i will have its ads shown only to users who belong to at least one of the demographic groups in X_i
For a number r_i, the advertiser will have its ads shown to at least r_i users each minute
Now consider the problem of showing ads for a single minute. Specifically, you want to create a way to show no more than one ad to each user at this minute to satisfy as many of the advertising contracts as possible. Suppose at a given minute there are n users on the site and we we know that user j belongs to a particular subset of the demographic groups.
Can you phrase the problem as a maximum flow problem and explain how to determine if it's possible to show a single ad to each user at this minute so that the Facebook's advertising contracts with each of the m advertisers are satisfied? If it is possible, you should explain how to pair users with advertisements to satisfy the contracts.
Note : Please give structure of graph(what nodes and edges are), capacity of those edges, and the source and sink when describing how to make this a maximum flow problem.
My Confusion: I am really struggling on where to even start with this problem.
For sure it seems like the source should be the ads, with outgoing edges pointing to each person with a capacity of 1. (This is single ad to each user at this minute)
This also seems like there might be a Bipartite Matching graph structure with people pointing to the categories they are in.
However, I am confused about have multiple different advisors fit into all this.
However, all my ideas above could be wrong, I am really struggling with this.
This can be solved with the generalization of a maximum flow: minimum cost flow. I do not believe this can be solved with a vanilla maximum flow because of this sentence in the problem statement,
Specifically, you want to create a way to show no more than one ad to each user at this minute to satisfy as many of the advertising contracts as possible.
To satisfy this statement, a minimum capacity would be required on each edge connected to advertisers in the maximum flow problem (which in some texts [1] is still considered a small variation on the maxflow problem.) That said, even if it can be solved as a maxflow, the MCF formulation is a more natural and simpler tool to apply as you can easily extend it to include (integer) values of each contract and, thus, maximizing profit each minute.
The MCF that solves this problem is a simple layer graph:
s -> A -> G -> U -> t
where s is the source, t is the sink, A is the layer of advertisers, G is the layer of demographic groups, and U is the layer of users. The -> symbol indicates there are directed nodes from the preceding layer to the next layer. Unless otherwise stated, each edge has a cost of 0 and a capacity of 1.
Place edges from s -> A_i with capacity r_i and some large negative constant M for the cost. Also add an edge from s -> A_i with cost 0 and and infinite capacity. These sets of edges ensure that we satisfy as many contracts as possible, by rewarding each contract with a value of -M > 0 (cost of M < 0). Note, a natural extension is to us a M_i per contract that is reflective of its actual value to Facebook.
Place edges from A_i -> G_j if A_i is interested in the demographic group. Set each edges capacity to infinite and weight/cost to 0.
Place edges from G_j -> u_k if user u_k belongs to demographic group G_j. Set capacity to 1 and cost to 0.
Places edges from u_k -> t with capacity 1 and cost 0 to ensure that each user sees only one advertisement.
Solve this network flow problem using any Minimum Cost Flow algorithm, and use the flow to directly tell you how many contracts can be satisfied given the constraints.
[1] https://courses.engr.illinois.edu/cs498dl1/sp2015/notes/25-maxflowext.pdf