<p>Suppose that we want to find a socially-optimal allocation in the following setting:</p>

<ul>
<li>There are $n$ firms and $m$ workers. </li>
<li>Each firm $i$ needs one worker and has value $v_i$ for having a worker (any worker).</li>
<li>Each worker $j$ needs one job and has value $v_j$ for having a job (at any firm).</li>
</ul>

<p>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:</p>

<ul>
<li>there are 5 firms with values are 5,4,3,2,1</li>
<li>there are 4 workers with values 4,3,2,1</li>
</ul>

<p>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.</p>

<p>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. </p>

<p>My question is: in what other cases is it possible to modify the VCG mechanism like that, by adding a "minimum payment"?</p>

CC BY-SA 3.0
2017-08-27T12:44:25.900Z
By "what other cases" you mean that the parameters $m$, $n$ and the utility values can vary, right?
Giskard
CC BY-SA 3.0
2017-08-27T15:56:43.347Z
In any standard economic theory the workers' wages should rise so as to match supply and demand.  A mechanism which prevents that is unlikely to be efficient in the long term
Henry
<reference-request><mechanism-design>
VCG mechanism with a minimum payment threshold
Erel Segal-Halevi
# VCG mechanism with a minimum payment threshold

(Asked by: username_0 on 2017-08-27)

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"?

**Tags:** reference-request, mechanism-design

> **Comments:**
> **username_1**: By "what other cases" you mean that the parameters $m$, $n$ and the utility values can vary, right?  
> **username_2**: In any standard economic theory the workers' wages should rise so as to match supply and demand.  A mechanism which prevents that is unlikely to be efficient in the long term  

---

## 0 answers

