Suppose that we want to find a socially-optimal allocation in the following setting:
- There are $n$ firms and $m$ workers.
- Each firm $i$ needs one worker and has value $v_i$ for having a worker (any worker).
- Each worker $j$ needs one job and has value $v_j$ for having a job (at any firm).
The values are private and we look for a truthful mechanism. The first attempt is VCG, however, it might run a deficit. For example, if:
- there are 5 firms with values are 5,4,3,2,1
- there are 4 workers with values 4,3,2,1
then VCG says that the 4 high-value firms are matched to the 4 workers, each firm pays 1 (its externality on the 5th firm) and each worker pays -2 (his externality on the 4th firm). So we have a deficit of 4.
A simple solution here is to declare that there will be no negative payments. Apparently the mechanism is truthful: if there are more firms than workers then all firms pay a positive price and all workers pay 0, and vice versa if there are more workers than firms.
My question is: in what other cases is it possible to modify the VCG mechanism like that, by adding a "minimum payment"?
