Xem mẫu
Analyzing the Privacy of a Vickrey Auction Mechanism
Figure 1. Example of auction
Bidder 1 Bidder 2 Bidder 3 Bidder 4 Bidder 5 Bidder 6 Bidder 7 Bidder 8 Bidder 9 Bidder 10
Bid 30 18 65 46 47 39 97 58 63 46
1st 425.234 171.33 1683.41 909.87 945.367 678.261 3432.27 1374.45 1592.34 909.87 2nd 6715.23 6461.33 7973.41 7199.87 7235.37 6968.26 9722.27 7664.4 7882.3 7199.87
3rd 3.13306E09 3.0146E09 3.72007E09 3.35917E09 3.37573E09 3.25111E09 4.53602E09 3.57592E09 3.67759E09 3.35917E09 4th 6.64109E17 6.17765E17 9.16682E17 7.569E17 7.63919E17 7.11848E17 1.33002E18 8.5115E17 8.9713E17 7.569E17 5th 4.70011E18 4.65376E18 4.95268E18 4.7929E18 4.79992E18 4.74785E18 5.36602E18 4.88715E18 4.93313E18 4.7929E18 6th 2.2208E25 2.1989 E25 2.34014E25 2.26465E25 2.26796E25 2.24336E25 2.53544E25 2.30918E25 2.3309E25 2.26465E25 7th 1.21115E40 1.19232E40 1.31567E40 1.24918E40 1.25207E40 1.23066E40 1.49347E40 1.28824E40 1.30746E40 1.24918E40 8th 5.08121E43 5.08119E43 5.08132E43 5.08125E43 5.08125E43 5.08123E43 5.08149E43 5.08129E43 5.08131E43 5.08125E43 9th 1.96679E49 1.96679E49 1.96684E49 1.96681E49 1.96681E49 1.9668E49 1.9669E49 1.96682E49 1.96683E49 1.96681E49 10th 2.43639E79 2.43638E79 2.43647E79 2.43642E79 2.43643E79 2.43641E79 2.43661E79 2.43645E79 2.43647E79 2.43642E79
2nd highest 1st 1.96684E49 2nd 5.08132E43 3rd 1.31567E40 4th 2.34014E25 5th 4.95268E18 6th 9.16682E17 7th 3.72007E09 8th 7973.41 9th 1683.41
10th 65 Winner
Then, B1 and B2 communicate the local function of X to B3. With this information, bidder B3 can ¿QGRXWWKHELGRI;$QH[DPSOHRIDQDXFWLRQ is given in Figure 1.
In practice, this kind of collusion is extremely unlikely to occur. Let us suppose that before the auction begins, bidders B1, B2, and B3 make a deal to perform that plan. Let us note that the plan will work only if X sends both the transformation of his or her own bid and the transformation of some other value to bidders in the set {B1, B2, B3}. Recall that after a bidder applies his or her function, he/she freely (e.g., randomly) chooses what bidder will receive his or her transformed value to continue with the transformation. So, bidders B1, B2, and B3 must be really lucky to be positioned in the necessary positions with UHVSHFWWRVRPHVSHFL¿FELGGHU;RUHYHQWRDQ\ RWKHUELGGHU 1 then /* there are more stages */ - p := ChooseRandomly(P \ G);
- Transmit (c, Ø, i-1, G {p}) to bidder p; /* p is first bidder of next stage */ else Broadcast c;
Resolution: Once a value c is broadcasted, do:
Ask for the bidder whose bid was greater than c. Let k be such bidder; Assign item to bidder k at price c;
functions dramatically modify values, we were concerned about modifying values, and the preci-sion of the overall process. This issue is critical because it concerns whether the transformed bids keep their relative order like the original bids. Besides, it also concerns whether the decoding
of a coded bid matches the original value. Even WKRXJK¿YHVWDJHVDUHHQRXJKWRJXDUDQWHHPRVW privacy properties, more stages were used in or-der to maximize numerical errors and study the numerical stability of the algorithm. In particular, we used 10 stages where the kinds of functions
2096
Analyzing the Privacy of a Vickrey Auction Mechanism
cyclically alternated, as we said before. The C-data type used to store values was the standard long double type that provides 80-bit precision ÀRDWLQJSRLQWQXPEHUV
In our experiment, bidders choose a random bid between 1 and 100. Then they select multipli-cative factors between 1 and 10 and exponential factors between 1.01 and 1.1. Regarding additive factors, they choose values whose magnitude is close to that of the values they manipulated in the previous stage. In spite of the fact that the prob-ability of each value is uniformly distributed in our experiment, bidders of a true auction are free to choose their values according to any private criterion. A simulation of the process is depicted in Figure 2.
The winner is depicted in bold face, while the second highest bidder is shown in italics. %RWKWKHFRGL¿FDWLRQDQGWKHGHFRGLQJSKDVHV are depicted. Let us note that the decoding of the second highest value matched perfectly the original second highest bid (65). For the sake of checking precision issues, the rest of the values were decoded as well. It turns out that not only the relative order between bids is kept, but also WKH¿QDOYDOXHVPDWFKSHUIHFWO\ZLWKWKHRULJLQDO bids. That is, all values in any decoding stage i FRLQFLGHWRWKRVHLQWKHFRGL¿FDWLRQVWDJHQL The reason for that numerical precision is that our protocol does not mix different kinds of op-erations in the same stage. That is, in spite that the order in which each exponential function is applied is different for each bid, no single addi-tion or multiplication is performed until all the bids are transformed according to all exponential functions in this stage. A similar argument applies when the kind of function is either multiplicative or additive. This fact minimizes numerical preci-sion problems.
Let us note that if the number of bidders in an auction is high, then the factors used by bidders in their local functions should be constrained by some upper and lower bounds. Otherwise, the size of transformed values could be too high or too
ORZDQGLWFRXOGRYHUÀRZWKHPD[LPDOSUHFLVLRQ allowed by the chosen data types. Alternatively, data types with unlimited precision (and unlimited memory usage) can be constructed and used.
CONCLUSION AND FUTURE WORK
In this paper, we have studied some properties of the protocol presented in López et at. (2004). In that paper, a mechanism to perform a Vickrey auction was presented in such a way that only the VHFRQGKLJKHVWELGDQGWKHLGHQWLW\RIWKH¿UVWELG-der were revealed. Contrarily to some previous works, this is achieved without the necessity of any trusted third part, not even the auctioneer. However, some relevant issues concerning risks against the privacy, with or without collusion, were not considered. Besides, a discussion about practical issues was missing. In this paper, we have addressed all these topics, and some results about a simple implementation have been reported.
Let us note that this protocol requires that all bidders behave conforming to the protocol. That is, they are supposed to follow the behavior described by the protocol. However, the result of the auction could be ruined if one or more bidders cheat. For example, if a bidder applies a different function when a bid is coded and when it is decoded, the published value of the second highest bid could be wrong. Following this line, we are currently developing a mechanism to detect liars in the protocol. It consists of apply-ing a kind of checksumWR¿QGRXWZKHWKHUVRPH ELGGHUPRGL¿HGWKHUHVXOWV,WLVDGLI¿FXOWWDVN because faults in the results must be detected without revealing too much information, which could break the privacy.
ACKNOWLEDGMENT
We would like to thank Felix Brandt for his helpful comments about our auction protocol. This work
2097
Analyzing the Privacy of a Vickrey Auction Mechanism
has been supported in part by the MCYT project MASTER (reference TIC2003-07848-C02-01), and by the JCCLM project PAC-03-001.
REFERENCES
Brandt, F., & Sandholm, T. (2004). (Im)possibility of unconditional privacy preserving auctions. In Proceedings of the 3rd International Joint Con-ference on Autonomous Agents and Multiagent Systems (pp. 810–817). ACM Press.
Lipmaa, H., Asokan, N., & Niemi, V. (2002). Secure Vickrey auctions without threshold trust. In Proceedings of the Annual Conference on Fi-nancial Cryptography, LNCS 2357 (pp. 87–101). Springer.
Systems and Tools, ESPRIT Working Group 9245 (pp.33–42).
Vickrey W. (1961). Counterspeculation, auctions, and competitive sealed tenders. Journal of Fi-nance, 16, 8–37.
ENDNOTES
1 The RET requires, for example, that the ORZHVWELGGHUH[SHFWV]HURSUR¿WWKDWELG-ders are risk-neutral, and that bidders have independent and private values for their items. These properties are rarely met in real e-commerce environments.
2 For instance, if a bidder played the role of an auctioneer in a previous auction where the item being sold was similar, then he could
López, N., Núñez, M., Rodríguez, I., & Rubio, F. (2004). Improving privacy in Vickrey auctions. ACM SIGEcom Exchanges, 5(1), 1–12.
Myerson, R. B. (1981). Optimal auction design. Mathematics of Operations Research, 6, 58–73.
Naor, M., Pinkas, B., & Sumner, R. (1999). Privacy preserving auctions and mechanism design. In Proceedings of the ACM Conference on Electronic Commerce (pp.129–139). ACM Press.
Sandholm, T., & Lesser, V. (1995). On automated contracting in multienterprise manufacturing. In Proceedings of Distributed Enterprise: Advanced
¿QGRXWWKHELGVLQWKHFXUUHQWDXFWLRQ
3 Alternatively, in order to guarantee that the winner (and not the second bidder) buys the item, the price could be raised in any tiny amount μ.
4 In (López et al., 2004) the possibility that a bidder knew two examples of the function was not explicitly considered. However, the global function depended in general on more than two unknowns, since each stage used a different kind of function and introduced a new unknown in the global function.
This work was previously published in International Journal of E-Business Research, Vol. 2, Issue 3, edited by I Lee, pp. 17-27, copyright 2006 by IGI Publishing (an imprint of IGI Global).
2098
...
- tailieumienphi.vn
nguon tai.lieu . vn