[go: up one dir, main page]

WO2009044229A1 - Procédé pour allouer des ressources interdépendantes par un ensemble de participants - Google Patents

Procédé pour allouer des ressources interdépendantes par un ensemble de participants Download PDF

Info

Publication number
WO2009044229A1
WO2009044229A1 PCT/IB2007/053984 IB2007053984W WO2009044229A1 WO 2009044229 A1 WO2009044229 A1 WO 2009044229A1 IB 2007053984 W IB2007053984 W IB 2007053984W WO 2009044229 A1 WO2009044229 A1 WO 2009044229A1
Authority
WO
WIPO (PCT)
Prior art keywords
participant
allocation
resource
preference value
value
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/IB2007/053984
Other languages
English (en)
Inventor
Boi Faltings
Thomas Leaute
Adrian Petcu
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Ecole Polytechnique Federale de Lausanne EPFL
Original Assignee
Ecole Polytechnique Federale de Lausanne EPFL
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Ecole Polytechnique Federale de Lausanne EPFL filed Critical Ecole Polytechnique Federale de Lausanne EPFL
Priority to PCT/IB2007/053984 priority Critical patent/WO2009044229A1/fr
Publication of WO2009044229A1 publication Critical patent/WO2009044229A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Definitions

  • 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.
  • resources in particular infrastructure resources
  • airlines share the capacity of airports
  • shipping companies share the capacity of storage facilities at ports
  • oil and gas companies share pipelines
  • communications companies share radio spectrum and transmitters.
  • the design and operation of such resources must include devices for controlling the access to ensure safe and efficient operation.
  • access to resources might have to be coordinated among multiple agents. For example, participants might want to set up meetings in such a way that each of the participant's time resources is allocated to at most one meeting. Similarly, in commercial procurement, different departments may consider buying from the same supplier to obtain additional discounts or other advantages.
  • the different orders are resources that need to be allocated to unique suppliers in a coordinated fashion.
  • a supplier might have capacity limitations and only be able to deliver one of the orders it is bidding for. In this case, supplier capacity is the resource that needs to be allocated to a unique buyer.
  • access control devices receive requests for access to each resource and perform an optimization to decide on the most efficient way to allocate the resource among the requests. Often, there are dependencies between different resources, for example:
  • the object of the present invention is a method whereby the agents can obtain the optimal joint decision while keeping the information about their preferences almost completely private.
  • the method consists of a distributed optimization protocol where agents exchange messages that encode their preferences.
  • the information can be encrypted so that agents only find out about the aggregated result of other agents' preferences, protecting agents' specific preferences. They also do not find out what other agents are present in the solving process, beyond those that they have constraints with.
  • the method preserves the required privacy in each of the applications described in more detail below:
  • agents In meeting scheduling, agents only find out about the aggregated preferences of unknown subsets of other agents for each possible meeting time, but they do not find out what other agents have meetings together nor what a specific agent's preferences for a meeting are.
  • 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.
  • 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.
  • the present invention can use symmetric cryptography where decryption can be carried out locally and privacy is achieved by the fact that computation is distributed. With respect to schemes based on secure multiparty computation, slightly more information is revealed, but in many applications this information would become known anyway. Furthermore, the present invention does not rely on public-key cryptography and thus provides stronger security guarantees.
  • FIG. 1 a illustrates a combinatorial auction involving two airlines interested in the combination of two slots managed by two airports
  • Figure 4 illustrates a constraint graph corresponding to Figure Ib
  • FIG. 7 illustrate an algorithm to build a DFS tree.
  • Figure 1 a shows the first and second participants offering each one takeoff/landing slot (referred to as Si and S2), and the third participant is an airline Ai interested in the combination of the two slots.
  • Figure 1 also shows a fourth participant, airline A2, which is also interested in the combination of the two same slots.
  • Steps a and b of the method airline Ai sends one request to each airport, announcing its interest in slots Si and S 2 .
  • airline Ai and the corresponding airport then agree on at least one of a pair of keys, the keys being secret random numbers (r 15 r ⁇ ) that will be used to obfuscate the airline's preference values related to the allocation/non-allocation of the slot.
  • the keys being secret random numbers (r 15 r ⁇ ) that will be used to obfuscate the airline's preference values related to the allocation/non-allocation of the slot.
  • Airline Ai and the airport managing slot Si agree on two random numbers: - Ti 12345 corresponding to the non-allocation of Si to Ai;
  • Airline Ai and the airport managing slot S2 agree on two random numbers:
  • airline Ai defines at least one among a set of four preference values describing its interest in combinations of allocations/non-allocations of the two slots.
  • Table 1 illustrates four possible such preference values, corresponding to the case when the airline assigns a preference value of 5 to being assigned only slot Si, of 2 for only slot S 2 , and of 11 for combination of the two.
  • Table 1 Possible preference values for airline Ai describing its interest in combinations of allocations/non- allocations of slots Si and S 2 .
  • Step d obfuscating step.
  • One or more of the airline's preference values in Table 1 are meant to be sent to the two airports in charge of slots Si and S 2 ; however, as will be illustrated later, the messages containing these preference values will possibly be relayed by third-party participants, who should not be able to read these preferences m clear text.
  • the messages will be relayed by airline A 2 , which is a competitor of airline Ai for the allocation of the two slots.
  • airline Ai obfuscating airline Ai 's preference values guarantees that these preferences are not revealed to a competitor.
  • Airline Ai therefore uses the secret keys agreed upon with the two airports in order to obfuscate his preference values, such that only the two airports can de-obfuscate them.
  • Table 2 Airline Ai's obfuscated preference values.
  • step e airline Ai transmits one or more of the obfuscated preference values in Table 2 to the airport in charge of slot S 2 .
  • the message containing these preference values might be relayed by third-party participants before it reaches the airport; however, since they are obfuscated, third parties do not have access to them.
  • De-obfuscation step f When the airport in charge of slot S 2 eventually receives the obfuscated preference values, it de-obfuscates them using the secret keys (r 2 , r' 2 ) that it agreed on with the airline. The resulting preference values are presented in Table 3.
  • Table 3 Airline Ai's de-obfuscated preference values, after subtracting the keys (r 2 , r' 2 ) from the columns.
  • the method of the invention further comprises the steps of :
  • the airport in charge of slot Sl Upon reception, the airport in charge of slot Sl is able to de-obfuscate the preference values using its keys (ri, r'i), by subtracting the random number ri from all preference values corresponding to the non-allocation of the slot to airline Ai, and subtracting r'i from those corresponding to the allocation of slot Si to airline Ai.
  • the resulting de-obfuscated preference values are presented in Table 5.
  • Table 5 De-obfuscated preference values received by the airport in charge of slot Si. In case that more than three participants are involved and in case of indirect transmission of the de-obfuscated first preference value, this method further comprises the steps of.
  • the message transmitted by the airport in charge of slot S 2 to the airport in charge of slot Si may be relayed by one or more third parties.
  • the message transits through a fourth participant, airline A 2 , that competes with airline Ai for the allocation of the two slots.
  • airline A 2 the airport in charge of slot S 2 itself
  • the fourth participant might modify it by aggregating other preference values.
  • these other preference values correspond to their preferences with respect to the allocation of the slots.
  • the airport in charge of slot S 2 has preference values on the combined allocations/non-allocations of the slot to the two airlines; these preferences correspond to the constraint that the slot cannot be allocated to both airlines simultaneously.
  • This constraint translates to the preference values presented in Table 6.
  • Table 7 Preference values resulting of the aggregation of the preference values in Tables 3 and 6.
  • Table 8 Preference values from Table 7, without the sub-optimal preference values.
  • airline A 2 When it receives these preferences, airline A 2 first aggregates them with its own preference values related to the allocation of the two slots, before transmitting (in this example, directly) the resulting aggregated preference values to the airport in charge of slot Si. Airline A 2 's own preference values are presented in Table 9.
  • Table 11 Preference values from Table 10, without the sub-optimal preferences.
  • Table 12 De-obfuscated preference values from Table 1
  • the second participant uses the de-obfuscated first preference value to make a decision to allocate or not allocate the second resource to the third participant.
  • the first participant uses 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.
  • the airport in charge of slot Si can infer the preferable decision to make with respect to the allocation of the slot.
  • Table 5 comparing the two preference values yields that the optimal decision is to allocate the slot to airline A L (11 > 2).
  • the maximum preference value of 11 is reached by deciding to allocate the slot to airline Ai.
  • the aggregation is made by summation of the numbers representing the original preference values, and choosing the maximum in order to find the solution with the best overall utility to the participants. Nevertheless, minor modifications allow the implementation of other aggregation methods such as:
  • the best solution is the one that minimizes the overall cost. In this case, the aggregation is made again by summation of the costs, but then choosing the minimal cost alternatives.
  • the aggregation can be made by multiplication instead of summation, and again by choosing the alternatives with the maximal probability.
  • the claimed method further comprises the steps:
  • the definition of the first preference value by the third participant is based on at least one previous decision to allocate or not allocate a resource to said third participant.
  • airline Ai sends a message comprising at least one preference value, but needs not send all of its preference values simultaneously.
  • it can send preference values as responses to requests from other participants, where the requests take the form of decisions to allocate/not allocate a slot to airline Ai, which replies by sending one or more preference values corresponding to these decisions.
  • the main method further comprises the agreement between the first participant and the third participant on a codenanie defining the allocation/non-allocation of the first resource to the third participant.
  • Preference values are not the only information that airline Ai could be willing to hide from possible competitors through which its messages might be relayed. It could desire to also keep its requests for time slots secret, because they are part of its business strategy.
  • the obfuscated preference values that airline Ai transmits refer to combinations of allocations/non-allocations of slots, referred to by the [S 1 A] identifiers.
  • the presence of the [Si, Ai] identifier in clear text in messages sent by the airline could reveal the existence of its request for slot Si to a competitor, if the messages are relayed by this competitor.
  • the main method further comprises computing by the first participant a payment which is requested from the third participant for the allocation of the first resource.
  • each resource owner requests from the recipient of its resource to specify its preference values for the non-allocation of the resource.
  • both slots are allocated to Ai.
  • the process thus begins with the airport controlling the slot Si requesting from airline Ai to specify its preference value for the non-allocation of slot Si to Ai.
  • a I replies with its preference value for not obtaining slot Si, but obtaining slot S 2 as was determined to be the case in the optimal solution.
  • This preference value is in this example equal to 2, as seen in Table 1.
  • S 2 aggregates the received preference value with its own preference value for this context (which is 0 in this case).
  • S 2 further sends the aggregated preference value to A 2 , which again aggregates it with its own preference value for this context (i.e. when A 2 gets nothing, which is 0, as seen in Table 9).
  • the preference value of Ai not getting Si but getting S 2 reaches Si, and it equals 2 (after de-obfuscation).
  • the claimed method further comprises computing by the second participant a payment which is requested from the third participant for the allocation of the second resource.
  • S 2 proceeds to compute the payment it should claim from Ai for allocating it the slot S 2 .
  • S 2 requests from airline Ai to specify its preference value for the case where neither slot Si or slot S 2 are allocated to Ai.
  • the sum of payments that Ai makes is 9+2, which equals its valuation for the bundle of items ⁇ Si, S 2 ) (see Table 1).
  • this establishment comprising the following steps:
  • defining, for each participant, a participant identifier this step is easily implemented by assigning for example a number from 0 to n - 1 to each participant, where n is the number of participants.
  • any method can be used to choose one of the participants as a preliminary leader, for example by choosing the participant with the highest ID. In our example, this is A 2 , whose ID is 3.
  • any existing DFS construction protocol can be used, such as the one described below.
  • a possible DFS obtained from such a protocol would be the chain A 2 — S 2 -Ai —Si.
  • each participant chooses a random number.
  • the computation performed by the cryptographic circuit tells each participant whether the sum of the random numbers modulo n equals its ID or not. If it does, then the participant knows that it was chosen as the leader, otherwise not. Assume in our example that the participants have chosen as random numbers 1, 2, 1, 0. This yields the sum equal to 4, which modulo 4 means that the chosen ID is 0, i.e. Si has been chosen as leader. Again, it is important to note that this is only known to Si. 5. propagating a token by the participants, said token propagation being initiated by the leader with the purpose of visiting all participants: this step is further described below.
  • the propagation of the token is achieved through the following steps. Once the leader has been elected, it starts the propagation of the token which results in visiting each participant in the problem. Assume that Si has been elected as the leader. Si has two neighbors: Ai and A 2 . Si chooses (in any fashion) one of its neighbors, for example A 2 . It then sends a token to A 2 and marks it as its child. A 2 receives the token, and since this is the first token it has received, it marks the sender (Si) as its parent. Note that the only information available to A 2 after receiving this token is that Si is its parent. A 2 for example does not know if there are any other participants above Si, in other subtrees of Si, nor how many other participants have already been visited, or their identities.
  • a 2 has another unvisited neighbor, S 2 .
  • a 2 sends a token to S 2 and marks it as its child.
  • S 2 receives the token, and since this is the first token it has received, it marks the sender (A 2 ) as its parent.
  • S 2 has another unvisited neighbor, Ai.
  • S 2 sends a token to Ai and marks it as its child.
  • Ai receives the token, and since this is the first token it has received, it marks the sender (S 2 ) as its parent.
  • Ai is a neighbor of Si. Si has already been visited (it is in fact the leader, thus the first participant to have been visited), but this is not known to Ai. Therefore, as far as Ai knows, Si can be its child, so it sends the token to Si.
  • Si does know that it was already visited, and it replies with a special token that can be interpreted as "already- visited”. This informs Ai that Si was already visited, and it is therefore an ancestor to Ai, and not a child.
  • Ai sends back the token to its parent, S 2 .
  • S 2 does not gain any knowledge from this token as to whether there were any other participants visited below Ai, how many of them, or their identities. In particular, S 2 also does not find at this point about the fact that Ai and Si are neighbors. S 2 then returns the token to its parent A 2 , which returns it to Si.
  • decisions on the allocation/non-allocation of resources are made so as to eliminate the need for announcing the optimal allocations to the participants lower in the hierarchy.
  • the enabler to this procedure is that the leading participant (the root of the hierarchy) receives from all the other participants (aggregated) preference values, which, once aggregated, lead to the root being able to find its optimal decision.
  • the first iteration of this procedure is like described in the main method of the invention: one of the participants takes the role of the root, preference values are transmitted and aggregated by the participants, until the root receives all required (aggregated) preference values. The root then chooses the decision that corresponds to the best aggregated preference value, and stores it as its optimal decision, but does not announce it to other participants.
  • Si will only consider the case when it allocates itself to Ai while propagating and aggregating preference values. This ensures that the participant at the top obtains a coherent view of the aggregated preference values, and that the assignment it determines to be optimal is consistent with the value that would have otherwise been determined in the first round.
  • the method that is the object of this invention allows agents to combine their preferences regarding a certain decision in an obfuscated or encrypted form such that they can be decrypted only by the agent that has to make this decision. In this way, the privacy of an agent's preferences is entirely protected.
  • the method of this invention finds a value for each decision variable such that as many constraints between them are satisfied as possible, and the sum of the utilities expressed by the individual agents is as large as possible.
  • the decisions are found by a sequence of message exchanges between agents.
  • Another object of this invention is to use codenames for decisions and decision values as well as anonymous leader election and DFS construction protocols that ensure that no agent can determine any of the following information: 1. The identity of other agents in the problem except for those that control decisions that it has a preference for or that directly constrain its own decisions;
  • the method of this invention also shows protocols for determining the payments that each agent should make or receive.
  • the invention can be applied to a variety of scenarios, such as the following scheduling meetings between agents, combinatorial auctions consisting of several individual auctions, allocating landing slots among airlines, sharing transmission time on a transmitting facility, etc.
  • scenarios such as the following scheduling meetings between agents, combinatorial auctions consisting of several individual auctions, allocating landing slots among airlines, sharing transmission time on a transmitting facility, etc.
  • combinatorial auctions consisting of several individual auctions
  • allocating landing slots among airlines such as the following scheduling meetings between agents, combinatorial auctions consisting of several individual auctions, allocating landing slots among airlines, sharing transmission time on a transmitting facility, etc.
  • the following sections provide more details about these scenarios.
  • each meeting corresponds to a va ⁇ able which models the time slot allocated to the meeting, the values for each va ⁇ able are the possible time slots for the corresponding meeting
  • the agents can express preferences by placing constraints/relations directly on the corresponding variables
  • This model of a meeting scheduling problem as a DCOP corresponds to the model in [I].
  • Auctions are a popular way to allocate resources or tasks to agents in a multiagent system. Essentially, bidders express bids for obtaining a good (getting a task in reverse auctions). Usually, the highest bidder (lowest one in reverse auctions) gets the good (task in reverse auctions), for a price that is either his bid (first price auctions) or the second highest bid (second price, or Vickrey auctions).
  • CA Combinatorial auctions
  • a combinatorial auction can be defined as follows.
  • CA Combinatorial Auction
  • B ⁇ bi, ..., bk ⁇ is a set of bids; a bid b(k, ⁇ ) expressed by an agent A 1 is a tuple
  • a feasible allocation is a mapping S: B — > ⁇ true, false ⁇ that assigns true or false to all bids b(k, ⁇ ) (where true means that agent A 1 wins its bid b(k, ⁇ )), such that ⁇ /b(k, ⁇ ),b(l,m), if 3z 7 e / s t i j G b(k, ⁇ ) A i j G b(l,m), then at least one of b(k, ⁇ ), b(l, m) is assigned false.
  • Figure Ib shows an example consisting of three items ij, 12, 13 for sale in separate, parallel, sealed-bid auctions, and three bidders bi, b2, bs interested in acquiring some or all of the items
  • bidder bi bids for items ii and 12, bidder b2 for all three items, and hi for i 2 and 13.
  • airports allocate takeoff and landing slots to different airlines and need to coordinate these allocations so that airlines have corresponding slots for their flights
  • the airports and airlines are agents, airports decide which airlines to allocate available slots to, while airlines decide which flights to operate. These decisions must be coordinated so that for every flight the airline has the required slots for its takeoffs and landings.
  • Section 5 1 presents a centralized model, which assumes a center that collects the bids and solves the problem in a centralized fashion
  • the privacy loss to the center is complete
  • Section 5 2 presents a distributed model which does not assume the existence of a center, and preserves privacy to a great extent 5.1
  • Centralized Model for CAs
  • This centralized model is a simple model where each item is associated with a variable which models the winner of the item. Bids from the agents are modeled as relations between the items present in the bid. A graph is thus formed with nodes being the variables, and (hyper)edges being the bids.
  • Figure 3 (a) shows the centralized model that corresponds to the auction problem from Figure l(b).
  • This section presents a decentralized model of the CA problem which allows the agents to execute a distributed protocol to solve the problem, and additionally provides better privacy guarantees.
  • This model eliminates the need for a center to collect the bids, and allows the agents to execute a distributed optimization protocol for deciding the allocation. It also provides some privacy guarantees, in that agents which do not share any item of common interest do not have to learn about each other.
  • Each item can only be sold to at most one bidder, which translates to the following constraint, for each item i, :
  • Each bidder b ⁇ has a utility function U 1 that creates interactions between auctions: for instance bi might be interested in getting only ii or 1 2 , but not both; or b 2 might be willing to pay for all three items more than the sum of its bids for each single item.
  • variable x(i,j) is owned by the auctioneer for item i, while variable x'(ij) is owned by bidder b,.
  • Private constraints hence become proper to their corresponding agents, as illustrated in the constraint graph in Figure 4.
  • Each seller of any item ii upon receiving a buyer b k 's expression of interest in its item, will create internally a variable x(k,l) that models the decision of awarding the item to bk.
  • the seller creates such a variable for each buyer who expressed interest in its item. It then models internally the fact that it can award the item to at most one buyer as a constraint on its internal variables.
  • each variable x'(k,l) of a seller agent of an item ii is connected with exactly one corresponding variable x(k,l) of a buyer agent b k ; we call these variables peers.
  • the goods are offered by the bidders, which can hence be called suppliers.
  • the constraint graph would then be exactly the same as the one for auctions in Figure 4, except that, since the aim is no longer to assign the task to the bidder offering the highest bid, but rather to the bidder offering the lowest bid, the bidders' private utilities U 1 would be encoded with negative numbers. This way, maximizing the total, aggregated sum of negative bids corresponds to minimizing the total, aggregated sum of bids.
  • the resulting model would be founded upon the assumption that each seller only puts one task for auction. This assumption can be removed by adding constraints coupling different tasks, expressing one auctioneer's coupled preferences with respect to its tasks.
  • DFS traversal of the problem graph is initiated. This phase has the goal to generate a depth-first traversal (DFS) of the problem graph in a distributed manner.
  • This DFS tree is subsequently used as a communication structure for our algorithms: nodes exchange messages with their ancestors and descendants in the DFS tree, but not with any siblings.
  • Definition 2 DFS tree
  • a DFS arrangement of a graph G is a rooted tree with the same nodes and edges as G and the property that adjacent nodes from the original graph fall in the same branch of the tree (e.g. b 2 and i 3 in Figure 6).
  • Figure 6 shows an example of a DFS tree.
  • tree edges corresponding to parent-child relationships (e.g. u - b2)
  • back edges corresponding to pairs of neighboring agents that are not directly linked by a parent-child relationship (e.g. b 2 - i 3 ).
  • TN 1 are the tree neighbors OfX 1 (nodes linked to X 1 via tree edges).
  • TN 1 P 1 u Ci.
  • DFS-traversal algorithm used in [2] has several drawbacks, especially in terms of privacy: agents may gather sensitive information about the structure of the constraint graph, and hence about their competitors in auctions in which they take part.
  • the DFS generation protocol starts from a node which is designated as the root of the DFS tree. To choose such a node, we require an anonymous leader election protocol, with the following desirable properties:
  • the leader has a way to prove it is the leader if necessary (e.g. if another agent tries to pretend it is the leader). 3. In cases where the problem is initially disconnected, any leader election algorithm, when executed by all agents in the problem will elect exactly as many leaders as there are connected components.
  • the agents need to first establish a circular communication structure. To do this, they construct an initial DFS tree in the following way.
  • Each agent has a unique ID, and knows an upper bound n on the number of agents in the problem.
  • Each agent creates a local variable i and iteratively sets it to the maximum of its own ID and the value of i of any of its neighbors, where a neighbor is an agent that it shares a constraint with. After n iterations, each agent compares the value of i with its ID. The agent for which the two values are equal starts the DFS tree construction as described below.
  • the root starts the construction a DFS ordering by using any DFS traversal algorithm, such as the one described in Section 5.4.2.
  • Every agent i selects a random X 1 (between 1 and q - 1) as its secret key.
  • Every agent A 1 creates a vector W 1 of n random numbers ⁇ [1..q - I]. It sets the element at its own position, w ⁇ i), to 1. It encrypts every element w t (k) into two numbers u ⁇ k) and v ⁇ k) using El-gamal encryption:
  • Every agent A 1 picks a random shift S 1 e [O..n — I]. It shifts the vectors V 1 and U 1 circularly to the left by S 1 positions and sends this vector to the neighbor. Every agent A, who receives vectors U 1 and V 1 from its neighbor A 1 generates newly randomized vectors
  • Vj (k) v,(k) y(k)
  • Uj (k) u,(k) y(k) where the y(k) are again distinct random numbers. It then shifts both vectors circularly to the left by S j positions and sends them to its neighbor. This step repeats until every agent receives its (transformed) original vector back. 6.
  • an agent i takes the first element of vector v, and sends it to the next agent (mod n).
  • the next agent, A 3 raises it to its secret power, x,, and sends it to the next agent (mod n).
  • DFS tree generation is described in Algorithm 1 (see Figure 7).
  • multiple DFS trees are generated for disconnected problems, by simply initiating DFS token passing processes from each leader elected in Section 5.4.1.
  • Each agent maintains a label for each one of its neighbors, which is initially unvisited.
  • the leader agent sends a token to one of its neighbors.
  • a token is simply an empty message, which has the purpose of ensuring that the DFS traversal of the graph happens in a synchronous, sequential manner.
  • agents wait for the token to be sent to them, and pass it on to their neighbors.
  • an agent receives a token from a neighbor, it labels the sender as visited.
  • an agent A 1 receives the token for the first time, it also marks the sender as its parent. Then, it sends the token to one of its unvisited neighbors; let this be agent A 3 , which is marked now as A 1 ' s child.
  • a 1 waits for the token to return. The token thus circulates through the graph, and eventually returns to agent A 1 . If it returns from agent A 3 , then A 1 repeats the process by sending it to another unvisited neighbor.
  • Example 1 Let us follow the execution of Algorithm 1 on the auction example in Figure 4. Assume that agent ii was chosen as the root by the secure leader election protocol. Being the root, agent ii goes on to execute Token Passing, while all other agents execute Handle incoming tokens, i.e. they wait for incoming tokens (line 9).
  • Agent ii's neighbors are the two bidders interested in item ii: bi and b 2 . Both bi and b 2 were marked as unvisited (line 1). Let us assume that agent ii decides to visit first its neighbor b 2 . It does so by sending it a DFS token (an empty message). Agent b2 receives the token and marks ii as visited (lines 9 and 10). As this is the first token that b2 received so far, b2 also marks il as its parent (line 11). Agent b2 then goes on to explore its own neighbors (lines 3-5). It has 2 neighbors that are not yet visited: 1 2 and 1 3 . Assume it chooses 1 2 to visit next, thus it sends the DFS token to agent i ⁇ .
  • DFS token an empty message
  • Agent i 2 receives the token and marks b 2 as its parent. i 2 has 2 neighbors that are not yet visited: bi and b 3 . Assume it chooses bi to visit next, thus it sends the DFS token to agent bi.
  • Agent bi receives the token and marks i2 as its parent, bi has one neighbor that is not yet visited: ii, therefore it can only send the DFS token to ii.
  • this approach creates one by logically adding the missing (dummy) corresponding edges in the local problem graph.
  • This approach has the advantage that all variables of an agent are grouped together. However, it may artificially increase the complexity of the solving algorithm, as the induced width of the constraint graph may increase.
  • variable-level DFS tree Each agent internally treats its local variables individually, DFS-traverses connected components, and continues the DFS traversal by visiting other agents before returning to its other connected components. This approach does not guarantee that all variables of an agent will appear in a single block in the DFS tree, which means that an agent may be present in several places in the tree. It has the advantage that the complexity of the solving algorithm is not artificially increased by creating dummy edges in the constraint graph
  • the UTIL propagation starts bottom-up from the leaves and propagates upwards only through tree edges, from children to parents.
  • a UTIL message sent by X 1 to its parent X informs X 1 how much utility u* Xl (v(j, k)) each one of its values v(j, k) gives to the whole subtree rooted at X 1 in the optimal solution.
  • To compute the UTIL message for its parent X, has to join the messages it received from all its children, and the relations it has with its parent and pseudoparents. Afterwards, it projects itself out of the join and sends the result to its parent.
  • the result of the projection is in fact the set of optimal utilities that can be obtained by the subtree rooted at this node, plus the relations it has with its parent/pseudoparents, for each combination of values of the parent/pseudoparents (see [2]).
  • Table 14 UTIL message UTIL b i ⁇ l2 eencrypted with respect to x( 1,1) by adding the random
  • the UTIL message UTIL b i ⁇ l2 that bidder bi sends to the auctioneer for item I 2 would be of the form presented in Table 13.
  • the auctioneer only needs to choose r x (l, 1) and send it to bidder bi through a secure channel; bi then encrypts its UTIL message with this secret random vector.
  • Intermediate computations on the UTIL message performed by other agents then operate on the encrypted valuations, without the need to decrypt them.
  • the auctioneer for item i L eventually receives the result of these computations, it simply subtracts r x (l, 1) in order to decrypt the message.
  • the encrypted UTIL message corresponding to the example in Table 13 is presented in Table 14.
  • This encryption scheme provides one important improvement with respect to sending an unencrypted message: the auctioneer for item 1 2 no longer has access to the exact valuations that bi assigns to item ii.
  • the auctioneer for item ii also sends a secret codename v that bi should use in lieu and place of x(l,l) in its UTIL message.
  • the resulting encrypted message is presented in Table 15.
  • the auctioneer for item 1 2 Upon receiving the encrypted message in Table 15, the auctioneer for item 1 2 is still able to infer that bi's valuations with respect to i 2 depend on the result of some other auction, but it is unable to know which one, since this auction is identified by a secret codename v. This secret auction might not even involve bidder bi itself.
  • This section descnbes the guarantees provided by the method with respect to protected the agents' private information.
  • Each item ii can obviously be sold to a single bidder, hence at most one of the variables x(l,k) which model the interest of bidders b k may take value 1 (see Section 5.2.1).
  • This type of constraint can lead to potential privacy losses, as a bidder could infer that there are other bidders interested in the same items.
  • Table 16 shows the constraint that x(2,3) and x(3,3) cannot take both value 1 : this combination is forbidden by the large negative valuation — M.
  • the message i 3 sends to b 3 has to carry this information, such that during the VALUE propagation phase, at most one "1" is chosen for x(2,3) and x(3,3).
  • bidder bi encrypts its UTIL message in order to obfuscate information about item ii to the auctioneer for item i 2
  • the auctioneer for item i 3 must also hide the information about bidder b 2 's participation to the auction from bidder b 3 . This is illustrated in Tables 4 and 5.
  • agents choose their codenames according to the following procedure, which can be seen as a new phase between the pseudo-tree generation phase and the UTIL propagation phase.
  • This procedure is a top-down propagation procedure, during which CODE messages, containing codenames already taken, are exchanged.
  • each agent When receiving a CODE message, each agent chooses codenames for the variables it needs to encrypt (if any) such that they are not contained in the incoming CODE message. It then adds its codenames to the message and passes it on to its child agent, after sharing the codenames with its corresponding pseudo-children over secure channels.
  • the auctioneer for item ii chooses the codename v for its variable x(l,l) (with v £ CODE ⁇ lL ). It sends this codename to bidder bi over a secure channel, and sends to bidder b 2 the following new CODE message:
  • bidder b 2 upon reception of the CODE message CODE ll ⁇ b2 , bidder b 2 chooses a codename ⁇ for variable x'(2,3) that is not contained in the message, communicates this secret codename to the auctioneer for item i 3 over a secure channel, and sends to its child agent the following CODE message:
  • the auctioneer for item i 2 has no variable to encrypt and is not the leaf of any backedge, therefore it simply passes on the incoming CODE message unchanged to its child agents.
  • the left branch containing bidder bi does not need to know about the existence of codename ⁇ , since no overlapping with the ⁇ -backedge would be possible, so that any agent in that branch can safely choose ⁇ again as a codename without risking a codename clash.
  • the auctioneer for item i 2 only needs to send codename ⁇ to the right branch.
  • Table 18 Internal, plaintext utility matrix representing Ws private valuations
  • bidder b 3 Upon receiving the encrypted UTIL message UTIL l3 ⁇ b3 (Table 17), bidder b 3 needs to merge it with its internal utility matrix representing its valuations with respect to the two auctions it is taking part in. This plaintext matrix is introduced in Table 18. In order to join the encrypted UTIL message UTIL l3 ⁇ b3 (Table 17) with the plaintext matrix in Table 18, bidder b 3 simply needs to sum up the columns in x'(3,3), without the need to decrypt the first message. The result is presented in Table 19. The message, which would normally be a 3-dimensional hypercube, is represented as a 2-dimensional table, with 2 merged dimensions for the rows.
  • Table 20 Encrypted UTIL message U ⁇ L b3 ⁇ l2 that bidder b 3 sends to the auctioneer for item
  • Table 22 Internal UTIL message UTIL x(1, 2) ⁇ x(3;2) obtained after projecting out x(l,2) in Table 21
  • Table 23 Intermediate UTIL message obtained by joining UTIL x ( 1 2 ) ⁇ x ⁇ 2 ) (Table 22) with UTILb 3 ⁇ l2 (Table 20)
  • the UTIL message UTIL 12 ⁇ b2 (Table 24) that bidder b 2 receives from the auctioneer for auction I 2 contains variable ⁇ , which is the codename for variable x'(2,3), owned by b 2 . To be able to project this variable out in the process of computing the UTIL message to be sent to its parent, b 2 needs to decrypt the message with respect to ⁇ To do this, it applies the inverse transformations of the two encryption schemes that b 3 applied to encrypt its message.
  • the first step of the decryption process hence consists in replacing the codename ⁇ by its true variable name x'(2,3)
  • the resulting version of UTIL message UTIL i2 ⁇ b2 decrypted with respect to x'(2,3), is given in Table 25.
  • the next step in the process of computing the UTIL message UTIL b2 ⁇ ;i consists in joining UTIL; 2 ⁇ b2 (Table 25) with b 2 's combined utilities with respect to all three items (Table 26). Note that there is no use for b 2 to encrypt these utilities, since there is no third agent between itself and auctioneer ii that could eavesdrop over a potential back-edge.
  • the resulting join is given in Table 15.
  • Tables 28 and 29 show the results of projecting out x'(2,2) and x'(2,3), successively. Replacing x'(2,l) with x(2,l), Table 29 then corresponds to the UTIL message UTILbwi.
  • the auctioneer for item ii decrypts the message with respect to v, which is the codename for x(l,l) that bidder bi initially used to encrypt its UTIL message.
  • v is the codename for x(l,l) that bidder bi initially used to encrypt its UTIL message.
  • the very last step in the UTIL propagation phase consists, for the auctioneer for ii, in joining its incoming UTIL message UTIL b2 ⁇ ii (Table 30) with the hard constraint x(l,l) + x(2,l) ⁇ 1, which produces the final internal message in Table 31.
  • Table 27 Intermediate message resulting from the join of UTIL 12 ⁇ 2 (Table 13) with b 2 's combined utilities (Table 26)
  • Table 29 Encrypted UTIL message UTIL b2 ⁇ 1 i after projecting x'(2,3) out of the message in Table 28 and replacing x'(2,l) with x(2,l)
  • VALUE ll ⁇ b2 ⁇ v ⁇ - 1 , x(2,l) ⁇ - 0 ⁇ .
  • bidder b 2 who lost the auction, only knows the fact that it lost it; it does not know the identity of the winner. More generally, for any auction, this scheme guarantees that only the auctioneer and the winner know who acquired the item.
  • Bidder b 2 subsequently generates the VALUE message:
  • VALUE b2 ⁇ ⁇ 2 ⁇ v ⁇ - ⁇ , x' ⁇ 2, T) ⁇ - 0, x'(2,3) that it sends to the auctioneer for item i 2 .
  • b 2 encrypts its VALUE message with respect to variable x'(2,3) using the same variable codename as the one used during the UTIL propagation phase; the resulting VALUE message is the following:
  • VALUE b2 ⁇ l2 ⁇ v ⁇ - ⁇ , x'(2, 2) ⁇ - 0, ⁇ ⁇ - 0 ⁇ .
  • VALUE ⁇ bl ⁇ v ⁇ - ⁇ , x(l , 2) ⁇ - l ⁇
  • VALUE l2 ⁇ b3 ⁇ ⁇ - 0, x(3,2) «- 0 ⁇ .
  • the auctioneer When it receives this VALUE message, the auctioneer immediately discovers that bidder b 3 has won the auction. Decrypting ⁇ ⁇ — 0 is not even necessary since it would only tell it that bidder b 2 was not assigned the item.
  • Sections 5.5 and 5.6 only described a protocol to determine the winner of each auction, based on how much utility each bidder assigned to the items it is interested in acquiring. The prices at which bidders then acquire the items they won still remain to be fixed. In this section, we describe a protocol to compute the payments that winning bidders should send to auctioneers to pay for the items they were awarded.
  • the UTIL messages exchanged between agents during the UTIL propagation phase in Section 5.5 could be interpreted as bids that participants place on items or on bundles of items.
  • bi's utility matrix with respect to items ii and i 2 (Table 13).
  • the utilities assigned by the bidder to each item simply correspond to how much it values them, i.e. how much it is willing to pay for them. Its bid for item ii is therefore 5, for item i 2 , it is of 2, and bi is willing to pay 11 for the combination of both items. It is however still unclear, in case it wins both items, how this combined payment of 11 will be split among the two corresponding auctioneers. This will be described in Section 5.7.3.
  • the auctioneer for item i 2 receives the encrypted version of bi's utility matrix
  • the auctioneer however does not know this fact: it only knows that the UTIL message it receives is an aggregation of the utilities of all agents below itself in the pseudo-tree. Not knowing the structure of the subtree rooted at bi, it cannot reliably infer that the marginal utilities in the message correspond only to bi's, or are the result of the aggregation of the utilities from several agents and/or for several items.
  • An example that illustrates this difference is given by the (decrypted) UTIL message UTIL h2 ⁇ i that bidder b2 sends to the auctioneer for item u (Table 30).
  • This case corresponds to awarding the item to its direct child b2 in the tree for a price of 4, which is somewhat compatible with b2 5 s private utilities in Table 26, according to which b 2 5 s marginal utility with respect to item il is between 3 and 5 (depending on the result of other auctions).
  • this aggregated bid obviously does not correspond to b 2 's private preferences, otherwise it would mean that b 2 is willing to pay 6 in order not to get the item.
  • bidder bi gets assigned both items ii and 12, and item i 3 is sold to bidder b3. This generates a total, aggregated utility of 13, as given in Table 30.
  • the auctioneer for item ii compares this utility with the total, aggregated utility of 7 corresponding to not selling its item. However, not selling its item would trigger a reallocation of item i 2 , which would then go to bidder b 3 . This would generate an additional utility corresponding to the surplus in bs's combined bid for the bundle involving items i 2 and i 3 .
  • agent a In order to compute this marginal utility, agent a explicitly sends a request for its subtrees to "freeze" all decisions, and return the total aggregated utility that they would get if only its own decisions changed. More formally, each agent a executes the following protocol.
  • Agent a maintains a list A of assignments to variables, which is initialized with the assignments contained in the VALUE message received during the VALUE propagation phase, augmented with the optimal assignments to the variables it owns. It also maintains a variable w(A) that is initialized to the (possibly encrypted) total, aggregated utility that the assignments in A generate for its subtrees and itself.
  • agent a For each of its variables x(b,i) (or x'(b,i)) whose currently assigned value is 1, agent a then changes its assignment to 0 in its list A, and sends the updated list in the form of ASSIGN messages to its children. • When receiving an ASSIGN message, each agent updates its own list A, whose relevant assignments it sends to its children. If the agent is a leaf, then it responds by starting a new UTIL propagation phase, during which all variables are set to the values specified in the agents' lists A, and agents update their variables u(A) according to the UTIL messages they receive.
  • agent a When receiving the resulting single-entry UTIL messages from its children, agent a joins them all together with its personal utilities in order to compute the total, aggregated utility that would incur from setting variable x(b,i) to 0 rather than 1. Subtracting this utility from u(A) yields the payment that bidder b should send to the auctioneer for item i. Note that since a owns variable x(b,i) (resp. x'(b,i)), a is the auctioneer for item i (resp. bidder b). Agent a then finally updates its variable u(A).
  • Section 5.7.3 illustrates this general payment protocol on the example used in the previous sections.
  • ASSIGN b2 ⁇ l2 ⁇ v ⁇ O, x(2,l) ⁇ - 0 ⁇ in which it replaced variables by their codenames when necessary to protect private information.
  • the ASSIGN message is therefore the following:
  • ASSIGN b2 ⁇ 2 ⁇ v «- 0, ⁇ ⁇ - 0, x'(2, 2) ⁇ - 0 ⁇ where x'(2,3) was replaced by its codename ⁇ .
  • ASSIGN ⁇ 2 ⁇ bl ⁇ v ⁇ - 0, x(l, 2) ⁇ - 1 ⁇
  • ASSIGN l2 ⁇ hi ⁇ ⁇ - 0, x(3,2) ⁇ - 0 ⁇ .
  • This value in sent to its parent through a single-entry UTIL message: UTIL bl ⁇ 2 ⁇ 12347 ⁇ using the same random vector as in previous phases to encrypt its true valuation.
  • UTIL b2 ⁇ ll ⁇ 12349 ⁇ .
  • the agent picks a variable it owns whose current assignment is 1 and sets it to 0 instead. The only such variable in this case is x(l,2).
  • the agent first sets variable x'(3,3) to 0, updates its list A b3 , and sends the following message to its child:
  • ASSIGN b3 ⁇ l3 ⁇ ⁇ - 0, x'(3,3) «- 0 ⁇ .
  • UTIL ⁇ 3 ⁇ b3 ⁇ 34567 ⁇ .
  • I 1 E L.m. m has to be much larger than n, the actual number of agents in the system, and the ID's have to be randomly distributed in the interval l..m. To see why this is important, consider the case where all ID's are numbers from 1 to n (n is the number of agents). Since the protocol always chooses the node with the smallest ID, it is obvious to all agents that always agent 1 will be chosen as the root.
  • Every node encodes their number in a vector of k t 1 's followed by (m - k,) ⁇ 's, where a is some other number different from 0 and 1. It encodes each element of the vector in a homomorphic encryption scheme and sends it to all its neighbors. El Gamal encryption is such a protocol. To run this, we either need a third party that manages the keys, or we can run this cooperatively by doing every encryption/decryption through a message exchange that goes through all agents.
  • Every node multiplies its (encrypted) vector element- wise with the (encrypted) vectors received from its neighbors, and makes this its new vector. This propagation is repeated at least d times, where d is the length of the longest path between any two nodes. This computes the minimum of all the numbers.
  • DPOP is an algorithm based on dynamic programming, which proved very efficient for solving distributed optimization problems.
  • the dAOBB algorithm works on a pseudotree/DFS ordering as DPOP does.
  • dAOBB works by performing search on the tree in a top-to-bottom fashion.
  • EVAL and UTIL messages circulate on the tree, top-down and bottom-up respectively.
  • Agents use EVAL messages to announce their decisions to their subtrees; the agents in the subtrees reply with UTIL messages to inform their parents about the utility they can achieve given these decisions.
  • agents can revise their decisions and try different ones.
  • agents obtain accurate information about how much utility each one of their decisions can bring to their subtrees (similar to DPOP), given the decisions of their ancestors. The process stops when all agents have decided on their optimal values.
  • dAOBB (or any search algorithm for that matter) can be modified to work in the context of the method we describe here, i.e. with variable code names, and obfuscation/encryption. It is all a matter of replacing the real variables names in the EVAL messages with their corresponding codenames (see Section 5.5.1.2), and adding the random numbers in the VALUE messages (see
  • UTIL values can be combined following a similar method as the one used to compute the join of UTIL messages in Section 5.5.2.
  • search algorithms have the advantage that they require only linear memory, as opposed to exponential for DPOP.
  • search algorithms have two drawbacks: first, they require in general an exponential number of small messages; this produces a large networking overhead which negatively influences performance.
  • a caching mechanism allows agents to remember their decisions they previously took in different contexts of their ancestors' assignments, such that when these contexts appear again in the search process, they can simply retrieve them from the cache instead of performing search again to obtain them. This method has experimentally been proven to greatly increase the efficiency of search.
  • agents first construct an anonymous DFS tree as described in Section 5.4.2. They turn this DFS tree into a circular order. Agents communicate with their successors/predecessors either directly or through the links in the underlying DFS tree when they are not direct neighbours. A constraint is added between the root agent and the last agent in the ordering.
  • the root starts the UTIL propagation by encoding the utility of each of its values as a vector, as described above. It encrypts each element of the vector using El Gamal encryption with its own key. It sends a message containing this vector for each of its own values to the last agent in the order. It also sends its public El Gamal key to all agents.
  • Each agent in the order performs the following operations: • For each value in the message it received and each combination of backedge values, it adds its own utility ⁇ by shifting the vector by ⁇ places, and then randomizing all values according to the El Gamal scheme. This is the same propagation as in Section 5.5, except that a linear ordering is used so that messages never need to be joined, and that all utilities are encoded as vectors using the El Gamal scheme.
  • this agent decrypts the utilities for each of its values and picks a value with the highest utility for itself.
  • the protocol In order to assign values to all variables, the protocol iterates with each agent being the root of the tree. The orderings are generated according to the protocol described in Section 5.4.2. Agents that have already been assigned a value behave differently in the propagation and forward directly the UTIL values corresponding to their chosen values without projecting their variables out.
  • This protocol still leaks some information about utilities as the root agent finds out about the total utilities for each of its values.
  • complete privacy can be provided by the following modification: the agent just below the root agent sends the root agent not the actual UTIL message, but already carries out partial projections of all values whose i-th bit is 1 as well as those whose i-th bit is 0. The root agent can then compare the projections and learn the bits that identify its optimal value, but never finds out the utility values themselves.
  • Section 5.7.2 presents a possible implementation of a protocol to compute the payments that bidders should make to the auctioneers in case they are awarded items.
  • the method presented is not limited to this particular payment protocol; computing the payments could be done in a number of other ways, for example according to the division of the surplus by the Shapley values.

Landscapes

  • Engineering & Computer Science (AREA)
  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Strategic Management (AREA)
  • Economics (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Educational Administration (AREA)
  • Game Theory and Decision Science (AREA)
  • Development Economics (AREA)
  • Marketing (AREA)
  • Operations Research (AREA)
  • Quality & Reliability (AREA)
  • Tourism & Hospitality (AREA)
  • Physics & Mathematics (AREA)
  • General Business, Economics & Management (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Storage Device Security (AREA)

Abstract

La présente invention concerne un procédé qui permet à un groupe de participants indépendants de coordonner des décisions concernant l'allocation de ressources interdépendantes, sous réserve de certaines garanties de confidentialité. La présente invention concerne un procédé d'allocation de ressources interdépendantes par un ensemble d'au moins trois participants, ce procédé comprenant les étapes suivantes : (a) réception par un premier participant d'une requête pour une première ressource émanant d'un troisième participant, et accord entre le premier participant et le troisième participant sur au moins l'une d'une paire de clés d'allocation/non-allocation pour la première ressource, la clé d'allocation étant liée à l'allocation de la ressource et la clé de non-allocation étant liée à la non-allocation de la ressource; (b) réception par un second participant d'une requête pour une seconde ressource par le troisième participant, et accord entre le second participant et le troisième participant sur au moins l'une d'une paire de clés d'allocation/non-allocation pour la seconde ressource, la clé d'allocation étant liée à l'allocation de la ressource et la clé de non-allocation étant liée à la non-allocation de la ressource; (c) définition par le troisième participant d'au moins une première valeur de préférence définissant son intérêt dans une première combinaison d'allocation ou de non-allocation des première et seconde ressources; (d) obscurcissement par le troisième participant de ladite première valeur de préférence à l'aide des deux clés correspondant à la première combinaison d'allocation et de non-allocation des première et seconde ressources; (e) transmission de la première valeur obscurcie directement ou indirectement au second participant; (f) désobscurcissement par le second participant de la valeur de préférence reçue à l'aide des clés d'allocation/non-allocation correspondantes.
PCT/IB2007/053984 2007-10-01 2007-10-01 Procédé pour allouer des ressources interdépendantes par un ensemble de participants Ceased WO2009044229A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
PCT/IB2007/053984 WO2009044229A1 (fr) 2007-10-01 2007-10-01 Procédé pour allouer des ressources interdépendantes par un ensemble de participants

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/IB2007/053984 WO2009044229A1 (fr) 2007-10-01 2007-10-01 Procédé pour allouer des ressources interdépendantes par un ensemble de participants

Publications (1)

Publication Number Publication Date
WO2009044229A1 true WO2009044229A1 (fr) 2009-04-09

Family

ID=39471986

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/IB2007/053984 Ceased WO2009044229A1 (fr) 2007-10-01 2007-10-01 Procédé pour allouer des ressources interdépendantes par un ensemble de participants

Country Status (1)

Country Link
WO (1) WO2009044229A1 (fr)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8667062B2 (en) 2011-02-22 2014-03-04 Nokia Corporation Method and apparatus for preserving privacy for appointment scheduling
WO2018134602A1 (fr) * 2017-01-23 2018-07-26 Chaddenwych Services Limited Procédé d'attribution de ressources dans un réseau de services utilitaires

Non-Patent Citations (7)

* Cited by examiner, † Cited by third party
Title
FALTINGS B., LÉAUTÉ T., PETCU A.: "Privacy Guarantees through Distributed Constraint Satisfaction", 8 April 2008 (2008-04-08), Swiss Federal Institute of Technology in Lausanne (EPFL), pages 1 - 15, XP002483980, Retrieved from the Internet <URL:http://liawww.epfl.ch/Publications/Archive/Faltings2008.pdf> [retrieved on 20080609] *
FEUERSTEIN S., PRIBYL B.: "Oracle PL/SQL Programming, Fourth Edition", 2005, O'REILLY, ISBN: 0-596-00977-1, XP002483982 *
GREENSTADT R., GROSZ B., SMITH M. D.: "SSDPOP: improving the privacy of DCOP with secret sharing", PROCEEDINGS OF THE 6TH INTERNATIONAL JOINT CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS, 18 May 2007 (2007-05-18), pages 1098 - 1100, XP002483978, ISBN: 978-81-904262-7-5, Retrieved from the Internet <URL:http://doi.acm.org/10.1145/1329125.1329333> [retrieved on 20080612] *
MAHESWARAN R T ET AL: "Taking DCOP to the real world: efficient complete solutions for distributed multi-event scheduling", AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS, 2004. AAMAS 2004. PROCEEDING S OF THE THIRD INTERNATIONAL JOINT CONFERENCE ON NEW YORK, NY, USA 19-23 JULY 2004, PISCATAWAY, NJ, USA,IEEE, 19 July 2004 (2004-07-19), pages 310 - 317, XP010753849, ISBN: 978-1-58113-864-1 *
PETCU A., FALTINGS B., PARKES D.C.: "MDPOP: faithful distributed implementation of efficient social choice problems", PROCEEDINGS OF THE FIFTH INTERNATIONAL JOINT CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS, 2006, pages 1397 - 1404, XP002483979, ISBN: 1-59593-303-4, Retrieved from the Internet <URL:http://doi.acm.org/10.1145/1160633.1160895> [retrieved on 20080612] *
PETCU A., FALTINGS B.: "DPOP: A scalable method for multiagent constraint optimization", PROCEEDINGS OF THE 19TH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI-05, 2005, pages 266 - 271, XP002483977, Retrieved from the Internet <URL:http://www.ijcai.org/papers/0445.pdf> [retrieved on 20080612] *
PETCU A.: "Recent Advances in Dynamic, Distributed Constraint Optimization", LIA-REPORT, no. 2006-006, 2006, Swiss Federal Institute of Technology in Lausanne (EPFL), XP002483981, Retrieved from the Internet <URL:http://liawww.epfl.ch/Research/dcr/dcop_advances.pdf> [retrieved on 20080612] *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8667062B2 (en) 2011-02-22 2014-03-04 Nokia Corporation Method and apparatus for preserving privacy for appointment scheduling
WO2018134602A1 (fr) * 2017-01-23 2018-07-26 Chaddenwych Services Limited Procédé d'attribution de ressources dans un réseau de services utilitaires

Similar Documents

Publication Publication Date Title
US20090089789A1 (en) Method to allocate inter-dependent resources by a set of participants
Léauté et al. Protecting privacy through distributed computation in multi-agent decision making
Zhu et al. Privacy-aware double auction with time-dependent valuation for blockchain-based dynamic spectrum sharing in IoT systems
Petcu A class of algorithms for distributed constraint optimization
CN111753324B (zh) 私有数据的处理方法、计算方法及所适用的设备
Archetti et al. The split delivery capacitated team orienteering problem
US11538070B2 (en) Blockchain-based system and method for peer-to-peer online advertising auction
Montakhabi et al. Sharing economy in future peer-to-peer electricity trading markets: Security and privacy analysis
Barkataki et al. On achieving secure collaboration in supply chains
Erdayandi et al. Privacy-friendly peer-to-peer energy trading: A game theoretical approach
Sun et al. Holistic roadmap of trends in radio access network slicing: A survey
Lin et al. The enhancement of solving the distributed constraint satisfaction problem for cooperative supply chains using multi-agent systems
Li et al. PR-OppCL: Privacy-preserving reputation-based opportunistic federated learning in intelligent transportation system
Bansal et al. Iterative combinatorial auctions for managing product transitions in semiconductor manufacturing
Babel et al. Human-centric digital product passports: Enabling verifiable information sharing for sustainable consumption through wallet-based identity management and zero-knowledge proofs
WO2009044229A1 (fr) Procédé pour allouer des ressources interdépendantes par un ensemble de participants
Cheng et al. A secure and fair double auction framework for cloud virtual machines
Hong Privacy-preserving collaborative optimization
Erdayandi et al. Towards privacy preserving local energy markets
Radonjic-Simic Reference Model and Architecture for the Post-Platform Economy
Lima et al. Auction-based resource allocation using a layer-2 blockchain
Zhang et al. Meta-level coordination for solving distributed negotiation chains in semi-cooperative multi-agent systems
Hafezalkotob et al. Cooperative network flow problem with pricing decisions and allocation of benefits: A game theory approach
Rizk et al. Brokerless inter-domain virtual network embedding: A blockchain-based approach
Ehsanfar et al. Mechanism design for exchanging resources in federated networks

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 07826608

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 07826608

Country of ref document: EP

Kind code of ref document: A1