## November 28th: Nati Linial, HUJI

November 23, 2010 by ilannehama

Title: No justified complaints; on fair sharing of resources

Abstract:

A set of $n$ {\em users} share a system that consists of $m$ different {\em resources}. Each user $U_i$ has his {\em entitlement} $e_i > 0$ with $\sum e_i = 1$. He makes his requests and asks to receive $r_{ij}$ units of resource $j$. We are looking for numbers $1 \ge x_i > 0$ so that $U_i$ actually receives $x_i r_{ij}$ units of resource $j$ for every $j$. There are several conditions that we want to satisfy:

1. We cannot give out more that a total of one unit from any resource (that’s all there is of each resource).

2. (This is the tricky part) No user has grounds for complaints for receiving too little.

We turn to explain what this means: Fix the vector of $x_i$’s. We say that resource $j$ is {\em critical} if we are giving out a whole unit of this resource. The requirement is that for every $i$, either (i) $x_i=1$ (and we can tell the user that he received everything he asked for) or (ii) There is a critical resource $j$ so that $x_i r_{ij} \ge e_i$. (In the latter case we tell him: Resource $j$ is presently critical. You have received from that resources whatever you are entitled for. We cannot increase your $x_i$ without violating condition (1) or without taking away from others).

Main theorem: For every set of $e_i$ and $r_{ij}$ as above, such $x_i$ exist and can be found efficiently. A nice aspect of this work is it brings together ideas from discrete mathematics with

(basic) methods from the theory of ordinary differential equations.

Joint work with Danny Dolev,

### Like this:

Like Loading...

*Related*

## Leave a Reply