E0-239 ELECTRONIC COMMERCE January - April 2005 Problem Set # 4 ------------------------------------------------------------------------ 1. Consider an exchange where a single unit of an item is traded. There are 4 sellers S1, S2, S3, S4 and 3 buyers B1, B2, and B3. Here are the bids from the buyers and the asks from the sellers for the single item. The objective is to maximize the surplus in the exchange. S1: 10 S2: 12 S3: 14 S4: 16 B1: 8 B2: 12 B3: 18 Find a surplus maximizing allocation for this exchange. If now Vickrey pricing is used, will the exchange have budget balance? 2. Suppose there are two units of the item, instead of one in the above example. Repeat the exercise. 3. Rework the GVA truth revelation proof that we discussed in the class for the case of the classical Vickrey auction (second price sealed bid auction). 4. Suppose the Vickrey auction pricing mechanism is used for English auctions. Will it generate more revenue, less revenue, or the same revenue as the classical English auction. Why? 5. Dutch auction and first price sealed bid auction produce the same average revenue even if all the assumptions of the benchmark model (independent private values, symmetry, risk-neutal bidders, prices depend on bids alone) are violated. Is this statement true or false. Justify. 6. Consider first price sealed bid auction under the benchmark model. Let v_i be the valuation of bidder i. Let bidder i conjecture that all other bidders are using a bidding function B to deicide their bids. That is, if v_j is the valuation of bidder j, then bidder j will bid B(v_j). Note that the individual valuations v_j are not known to bidder i. Assume that B is a monotonically increasing function (which guarantees that the inverse of B exists). Compute the probability that bidder i will win with a bid b_i in the above setting. 7. For the benchmark model, it is found that variance of revenue is lower in English or Vickrey auction than in first price sealed bid or Dutch auction. How would a seller and a buyer use this information? 8. Assume that there is perfect competition (infinitely many bidders) and assume the benchmark model. Is this good for the seller or the buyers. What would be the price the winning bidder will pay? 9. Proof of correctness of Sandholm's Algorithm: Given a set of items and a set of bids for some subsets of these, Sandholm's algorithm constructs an allocation tree where children of a node are those bids that (a) include the item with the smallest index among the items that are not yet on the path, and (b) do not include items that are already on the path Show that this algorithm constructs "every" feasible allocation "exactly once." ............................................................................ For the following problems: Note 1: Notation: Znstar = Multiplicative group modulo n of all positive integers less than n and relatively prime to n. Note 2: Read up appropriate sections in the Handbook by Menezes et al. ............................................................................ 10. Study the Extended Euclidean algorithm (Algorithm 2.107 in the Handbook). What is the worst-case computational complexity of this algorithm. 11. Study the repeated square and multiply algorithm for modular exponentiation (Algorithm 2.143 in the Handbook). What is the worst-case computational complexity of this algorithm. 12. What is the worst-case computational complexity of: (a) Key generation in RSA (b) Encryption in RSA (c) decryption in RSA 13. What is the worst-case computational complexity of: (a) Key generation in ElGamal scheme (b) Encryption in ElGamal Scheme (c) decryption in ElGamal Scheme 14. Given Znstar with n = 8, say whether it is cyclic. If cyclic, find out all its generators. 15. Given Znstar with n = 14, say whether it is cyclic. Justify your answer. If cyclic, determine all its generators. 16. RSA: Choose p = 3; q = 5. Choose a public key and private key of this scheme. Let the message be 2. What will be the encrypted message. Show the decryption process also. 17. In an RSA system, you intercept the ciphertext c = 10 sent to a user whose public key is e = 5, n = 35. What do you think is the plaintext m? 18. In an RSA system, the public key of a given user is e = 31, n = 3599. What is the private key of this user. 19. In the RSA scheme, the private key of an entity A is broken, so A has to regenerate a new pair of public key and priavte key. Is it safe to use the same "n" for generating the new keys or should he use a different n altogether? 20. ElGamal: Let p = 7; alpha = 3; a = 4. What is the public key and the private key. If m = 5, then what is the cipher text if k = 4. How is the message recovered. 21. Diffie-Hellman: Assume p = 7; alpha = 5; x_A = 3; x_B = 4. Find the secret key. 22. Diffie-Hellman: Assume p = 7; alpha = 5; secret key = 2. Find x_A and x_B.