Method to allocate inter-dependent resources by a set of participants

• US 20090089789A1
• Filed: 10/01/2007
• Published: 04/02/2009
• Est. Priority Date: 10/01/2007
• Status: Abandoned Application

• Current Assignee: Ecole polytechnique fãdãrale de lausanne epfl (Schweizerische Eidgenossenschaft)
• Original Assignee: Ecole polytechnique fãdãrale de lausanne epfl (Schweizerische Eidgenossenschaft)
• Inventors: Petcu, Adrian, Leaute, Thomas, Faltings, Boi
• Application Number:
  US11/905,423
• Publication Number:
  US 20090089789A1
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 30/08 Auctions

Abstract

The object of the present invention is a method that allows a group of independent participants to coordinate decisions with respect to the allocation of interdependent resources, while maintaining certain privacy guarantees.

The present invention proposes a method to allocate inter-dependent resources by a set of at least three participants, this method comprising the steps of:

• • a. receiving by a first participant a request for a first resource by a third participant, and agreeing between the first participant and the third participant on at least one of a pair of allocation/non-allocation keys for the first resource, the allocation key being related to the allocation of the resource and the non-allocation key being related to the non-allocation of the resource,
  • b. receiving by a second participant a request for a second resource by the third participant, and agreeing between the second participant and the third participant on at least one of a pair of allocation/non-allocation keys for the second resource, the allocation key being related to the allocation of the resource and the non-allocation key being related to the non-allocation of the resource,
  • c. the third participant defining at least a first preference value defining his interest in a first combination of allocation or non-allocation of the first and second resources,
  • d. the third participant obfuscating said first preference value using the two keys corresponding to the first combination of allocation and non-allocation of the first and second resources,
  • e. transmitting the first obfuscated value directly or indirectly to the second participant,
  • f. de-obfuscating by the second participant the received preference value using the corresponding allocation/non-allocation keys.

Claims

1. Method to allocate inter-dependent resources by a set of at least three participants, this method comprising the steps of:

a. receiving by a first participant a request for a first resource by a third participant, and agreeing between the first participant and the third participant on at least one of a pair of allocation/non-allocation keys for the first resource, the allocation key being related to the allocation of the resource and the non-allocation key being related to the non-allocation of the resource,

b. receiving by a second participant a request for a second resource by the third participant, and agreeing between the second participant and the third participant on at least one of a pair of allocation/non-allocation keys for the second resource, the allocation key being related to the allocation of the resource and the non-allocation key being related to the non-allocation of the resource,

c. the third participant defining at least a first preference value defining his interest in a first combination of allocation or non-allocation of the first and second resources,

d. the third participant obfuscating said first preference value using the two keys corresponding to the first combination of allocation and non-allocation of the first and second resources,

e. transmitting the first obfuscated value directly or indirectly to the second participant,

f. de-obfuscating by the second participant the received preference value using the corresponding allocation/non-allocation keys.

2. Method of claim 1, further comprising the steps of:

a. transmitting directly or indirectly said de-obfuscated first preference value to the first participant,

b. de-obfuscating by the first participant the received preference value using the corresponding allocation/non-allocation keys.

3. Method of claim 2, in which the indirect transmission of said de-obfuscated first preference value further comprises the steps of:

a. receiving by a fourth participant said value, aggregating said value with other preference values,

c. transmitting directly or indirectly by said fourth participant said aggregated value to the first participant.

4. Method of claim 1, further comprising the the second participant using the de-obfuscated first preference value to make a decision to allocate or not allocate the second resource to the third participant.

5. Method of claim 2, further comprising the first participant using the de-obfuscated received preference value or aggregated preference value to make a decision to allocate or not allocate the first resource to the third participant.

6. Method of claim 3, in which the aggregation is obtained by the sum, product, minimum or the maximum of the obfuscated first preference value and at least one other preference value.

7. Method of claim 5, further comprising the steps:

transmitting to the second participant the decision to allocate/not allocate the first resource to the third participant,

deciding by the second participant whether or not to allocate the second resource to the third participant based on the decision made by the first participant and the received preference values.

8. Method of claim 1, in which the definition of the first preference value by the third participant is based on at least one previous decision to allocate or not allocate the first resource to said third participant.

9. Method of claim 1, further comprising the agreement between the first participant and the third participant on a codename defining the allocation/non-allocation of the first resource to the third participant.

10. Method of claim 1, in which the third participant has been allocated the first resource and the first preference value sent to the first participant was defined for the allocation of the first resource to the third participant, this method further comprising the steps of:

requesting by the first participant from the third participant to define his preference value corresponding to the non-allocation of the first resource to the third participant,

defining by the third participant the preference value corresponding to the combination of the non-allocation of the first resource to the third participant and the allocation/non-allocation of the second resource to the third participant, and obfuscating said preference value with the corresponding keys,

transmitting by the third participant said obfuscated preference value directly or indirectly to the second participant,

de-obfuscating by the second participant the received preference value using the corresponding allocation/non-allocation keys,

transmitting by the second participant the resulting de-obfuscated preference value directly or indirectly to the first participant,

de-obfuscating by the first participant the received preference value using the keys corresponding to the non-allocation of the first resource,

using by the first participant the resulting de-obfuscated preference value to define a payment to be requested from the third participant.

11. Method of claim 10, in which the third participant has been allocated the second resource and the first preference value sent to the second participant was defined for the allocation of the second resource to the third participant, this method further comprising the steps of:

requesting by the second participant from the third participant to define his preference value corresponding to the non-allocation of the second resource to the third participant,

defining by the third participant the preference value corresponding to the combination of the non-allocation of the first resource to the third participant and the non-allocation of the second resource to the third participant, and obfuscating said preference value with the corresponding keys,

transmitting by the third participant said obfuscated preference value directly or indirectly to the second participant,

de-obfuscating by the second participant the received preference value using the keys corresponding to the non-allocation of the second resource,

using by the second participant the resulting de-obfuscated preference value to define a payment to be requested from the third participant.

12. Method of claim 1, further comprising the step of establishing a hierarchy among the participants in an anonymous fashion, this establishment comprising the following steps:

a) defining for each participant a participant'"'"'s identifier,

b) choosing among the participants a preliminary leader

c) constructing a depth-first search arrangement of all the participants, starting from the chosen preliminary leader and using any depth-first traversal method

d) executing by the participants, in depth-first order according to the depth-first arrangement from point c), an encrypted computation that results in each participant computing a function that evaluates to true if the participant is the chosen leader, and to false otherwise

e) propagating a token by the participants, said token propagation being initiated by the leader with the purpose of visiting all participants

13. Method of claim 12, in which the propagation of the token comprises the steps of:

initiating a first token propagation by the chosen leader,

the leader choosing one of its neighbors, and sending the first token to this neighbor,

relaying the first token by each participant when receiving the first token from another participant, to a selected unvisited participant,

replying with a second token when receiving the first token for at least a second time, from another participant different from the participant to which the first token was last sent,

when no other unvisited neighbor participant is found, returning the first token by each participant to the first sender participant that has for the first time sent the first token.

14. Method of claim 12 for sequential decision making, further comprising the steps of:

a) participants taking turns at being the first participant

b) receiving by first participant aggregate preference values as in claim 1

c) using by the first participant the received aggregated preference values to make a decision about allocation/non-allocation of its resources

d) in subsequent runs, participants which have already taken the role of the first participant, aggregate and transmit preference values only taking into account their decisions taken while being the leader.