Distributed resource allocation

1. A computer-implemented method for allocating M resources subject to L constraints, the method comprising:

receiving data representing L constraints, wherein each of the L constraints corresponds to a subset of M resources and restricts a respective maximum number C of resources to be selected among the subset of the M resources, wherein any subset corresponding to a first constraint out of the L constraints has no common resource with any other subset corresponding to a second constraint out of the L constraints, unless the subset corresponding to the first constraint is a subset of the other subset corresponding to the second constraint;

determining a topological ordering of the L constraints, wherein the topological ordering defines a traversing order of the L constraints;

selecting all the M resources as an initial selection;

removing resources from the initial selection by traversing each constraint in the topological ordering of the L constraints, wherein the removing comprises: for a constraint l of the L constraints corresponding to a subset S l of the M resources and restricting a maximum number C l of resources to be selected out of the subset S l ,

determining currently selected resources in the subset S l , and

unselecting, among the currently selected resources in the subset S l , any resource that is not one of C l resources that have top C l rewards among the currently selected resources in the subset S l ; and

allocating the selected resources after traversing all the L constraints in the topological ordering of the L constraints.

2. The method of claim 1 , wherein:

the data representing the L constraints comprises L index subsets, each of the L index subsets corresponds to a respective one of the L constraints and comprises indexes of a subset of the M resources corresponding to the respective one of the L constraints; and

the subset S l comprises indexes of a subset of the M resources corresponding to the constraint l.

3. The method of claim 1 , wherein the data representing the L constraints comprises data representing each of the L constraints by a node in a directed acyclic graph (DAG) data structure, and an edge of the DAG represents a relationship between two of the L constraints corresponding to two nodes of the edge.

4. The method of claim 1 , further comprising: obtaining data representing M rewards, each reward corresponding to one of the M resources respectively.

5. The method of claim 4 , further comprising:

sorting the M resources in a non-increasing order according to the M rewards corresponding to the M resources before traversing each subset in the L subsets in the topological ordering of the L subsets; and

wherein unselecting, among the currently selected resources in the subset S l , any resource that is not one of C l resources that have top C l rewards among the currently selected resources in the subset S l comprises unselecting the any resource that is not one of C l resources that have top C l rewards among the currently selected resources in the subset S l according to the non-increasing order of the M resources.

6. The method of claim 4 , wherein the M rewards are M cost-adjusted rewards respectively, wherein each of the M cost-adjusted rewards comprises a reward minus a cost if one of the M resources is selected.

7. The method of claim 1 , wherein the method is performed for one of N users in performing resource allocation of the M resources among the N users into K pools subject to K global constraints and the L constraints, wherein each of the L constraints restricts a respective maximum number of resources out of the M resources to be selected by a single user, and each of the K global constraints limits resources allocated for each pool across the N users.

8. A non-transitory, computer-readable storage medium storing one or more instructions executable by a computer system to perform operations for allocating M resources subject to L constraints, the operations comprising:

receiving data representing L constraints, wherein each of the L constraints corresponds to a subset of M resources and restricts a respective maximum number C of resources to be selected among the subset of the M resources, wherein any subset corresponding to a first constraint out of the L constraints has no common resource with any other subset corresponding to a second constraint out of the L constraints, unless the subset corresponding to the first constraint is a subset of the other subset corresponding to the second constraint;

determining a topological ordering of the L constraints, wherein the topological ordering defines a traversing order of the L constraints;

selecting all the M resources as an initial selection;

removing resources from the initial selection by traversing each constraint in the topological ordering of the L constraints, wherein the removing comprises: for a constraint l of the L constraints corresponding to a subset S l of the M resources and restricting a maximum number C l of resources to be selected out of the subset S l ,

determining currently selected resources in the subset S l , and

unselecting, among the currently selected resources in the subset S l , any resource that is not one of C l resources that have top C l rewards among the currently selected resources in the subset S l ; and

allocating the selected resources after traversing all the L constraints in the topological ordering of the L constraints.

9. The non-transitory, computer-readable storage medium of claim 8 , wherein:

the data representing the L constraints comprises L index subsets, each of the L index subsets corresponds to a respective one of the L constraints and comprises indexes of a subset of the M resources corresponding to the respective one of the L constraints; and

the subset S l comprises indexes of a subset of the M resources corresponding to the constraint l.

10. The non-transitory, computer-readable storage medium of claim 8 , wherein the data representing the L constraints comprises data representing each of the L constraints by a node in a directed acyclic graph (DAG) data structure, and an edge of the DAG represents a relationship between two of the L constraints corresponding to two nodes of the edge.

11. The non-transitory, computer-readable storage medium of claim 8 , the operations further comprising: obtaining data representing M rewards, each reward corresponding to one of the M resources respectively.

12. The non-transitory, computer-readable storage medium of claim 11 , the operations further comprising:

sorting the M resources in a non-increasing order according to the M rewards corresponding to the M resources before traversing each subset in the L subsets in the topological ordering of the L subsets; and

wherein unselecting, among the currently selected resources in the subset S l , any resource that is not one of C l resources that have top C l rewards among the currently selected resources in the subset S l comprises unselecting the any resource that is not one of C l resources that have top C l rewards among the currently selected resources in the subset S l according to the non-increasing order of the M resources.

13. The non-transitory, computer-readable storage medium of claim 11 , wherein the M rewards are M cost-adjusted rewards respectively, wherein each of the M cost-adjusted rewards comprises a reward minus a cost if one of the M resources is selected.

14. The non-transitory, computer-readable storage medium of claim 8 , wherein the operations are performed for one of N users in performing resource allocation of the M resources among the N users into K pools subject to K global constraints and the L constraints, wherein each of the L constraints restricts a respective maximum number of resources out of the M resources to be selected by a single user, and each of the K global constraints limits resources allocated for each pool across the N users.

15. A computer-implemented system, comprising:

one or more computers; and

one or more computer memory devices interoperably coupled with the one or more computers and having tangible, non-transitory, machine-readable media storing one or more instructions that, when executed by the one or more computers, perform one or more operations for allocating M resources subject to L constraints, the operations comprising:

receiving data representing L constraints, wherein each of the L constraints corresponds to a subset of M resources and restricts a respective maximum number C of resources to be selected among the subset of the M resources, wherein any subset corresponding to a first constraint out of the L constraints has no common resource with any other subset corresponding to a second constraint out of the L constraints, unless the subset corresponding to the first constraint is a subset of the other subset corresponding to the second constraint;

determining a topological ordering of the L constraints, wherein the topological ordering defines a traversing order of the L constraints;

selecting all the M resources as an initial selection;

removing resources from the initial selection by traversing each constraint in the topological ordering of the L constraints, wherein the removing comprises: for a constraint l of the L constraints corresponding to a subset S l of the M resources and restricting a maximum number C l of resources to be selected out of the subset S l ,

determining currently selected resources in the subset S l , and

unselecting, among the currently selected resources in the subset S l , any resource that is not one of C l resources that have top C l rewards among the currently selected resources in the subset S l ; and

allocating the selected resources after traversing all the L constraints in the topological ordering of the L constraints.

16. The system of claim 15 , wherein:

the data representing the L constraints comprises L index subsets, each of the L index subsets corresponds to a respective one of the L constraints and comprises indexes of a subset of the M resources corresponding to the respective one of the L constraints; and

the subset S l comprises indexes of a subset of the M resources corresponding to the constraint l.

17. The system of claim 15 , wherein the data representing the L constraints comprises data representing each of the L constraints by a node in a directed acyclic graph (DAG) data structure, and an edge of the DAG represents a relationship between two of the L constraints corresponding to two nodes of the edge.

18. The system of claim 15 , the operations further comprising: obtaining data representing M rewards, each reward corresponding to one of the M resources respectively.

19. The system of claim 18 , the operations further comprising:

sorting the M resources in a non-increasing order according to the M rewards corresponding to the M resources before traversing each subset in the L subsets in the topological ordering of the L subsets; and

wherein unselecting, among the currently selected resources in the subset S l , any resource that is not one of C l resources that have top C l rewards among the currently selected resources in the subset S l comprises unselecting the any resource that is not one of C l resources that have top C l rewards among the currently selected resources in the subset S l according to the non-increasing order of the M resources.

20. The system of claim 18 , wherein the M rewards are M cost-adjusted rewards respectively, wherein each of the M cost-adjusted rewards comprises a reward minus a cost if one of the M resources is selected.

21. The system of claim 15 , wherein the operations are performed for one of N users in performing resource allocation of the M resources among the N users into K pools subject to K global constraints and the L constraints, wherein each of the L constraints restricts a respective maximum number of resources out of the M resources to be selected by a single user, and each of the K global constraints limits resources allocated for each pool across the N users.