4. Suppose n companies (n >= 3) each make a bid on a project, but the value of e

Question

4. Suppose n companies (n >= 3) each make a bid on a project, but the value of each bid is supposed
to remain secret; i.e., each company knows its own bid, and nobody else is allowed to know it until all
the bids are opened up together. Let the n bids be represented by positive integers b1, ... , bn. We
can assume that b1 + ... + bn < N for some known number N.
Now suppose that all the companies want to know the average value (b1 + ... + bn)=n of the
n bids. Devise a procedure (protocol) by which the n companies, among themselves, compute this
average bids while keeping each bid secret; nobody else besides the n companies can participate in this
protocol (no third party, etc.). Assume that in the exchange of information, only correct information
is given (i.e., correct with respect to the agreed-upon protocol).
[The answer is fairly short, but not obvious.]

Explain the answer in words, equations, and logic , no coding

Explanation / Answer

Thing to note here is that nobody can disclose their individual bids but they can share modified numbers by which their bid can't be predicted.
So taking advantage of this info here is the strategy that we can make :

Let's assume there are 3 bidders A,B,C and their bids are b1,b2,b3

1. A adds random number r1 to it's bid b1 and shares it with B (B will receive b1 + r1)
2. B adds random number r2 to it's bid b2 , adds it to the number received by A and shares the sum with C (C will receive b1 + r1 + b2 + r2)
3. C adds random number r3 to it's bid b3 , adds it to the number received by B and shares the sum with A (A will receive b1 + r1 + b2 + r2 + b3 + r3)
4. A removes it's random number r1 from the sum and shares it with B (B will receive b1 + b2 + r2 + b3 + r3)
5. B removes it's random number r2 from the sum and shares it with C (C will receive b1 + b2 + b3 + r3)
6. C removes it's random number r3 from the sum and shares it with everyone ( Now everyone receives b1 + b2 + b3)
7. Now average can be computed by dividing the sum by 3.

Same approach can be extended for n bidders where one by one (from b1 to bn) everyone adds some random number to their bids and to the sum , after this one by one (from b1 to bn) everyone will subtract their random number from the sum which ultimately provides us with the sum of all the bids which we can be be divided by n to get the answer.

**If you have any query , please feel free to comment with details.
**Happy leaning :)

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.