1) Two companies bid on a project

Subject:Computer SciencePrice: Bought3

Share With

1) Two companies bid on a project. The project work could be apportioned to the two companies. Company A has the following profit function PA = p(xA,xB)xA−cAxA and PB = p(xA,xB)xB−cBxB where xA,xB are the units of work put in by company A and B respectively.
(a) Determine the strategic units of work that the companies contribute at Nash equilibrium, when p(xA,xB)=K−(2x2A+xB). (10pts)
(b) What are the Stackelberg equilibrium strategies if company A determines its strategy first? (15 pts)
2. Recall the local connection game defined by a set of vertices and graph G where edges are to be
added to build connections, suppose the cost to user u (i.e. user at node u) is defined to be Cuαnu +
P pdist(u, v) where nu is the number of edges incident to u, that u purchases (a connection edge v
is only paid for by one user), and dist(u, v) is the shortest distance from u to v. α, β ≥ 0.
Characterize when a star configuration (a center node and every other node connected to it with an edge) graph is a NE and also determine the characterization of an optimal solutions as a function of α.
(20pts)
3. Suppose in non-atomic routing in networks, the delay function on edges is of the form afe3 +be where
fe is the flow on edge e.
Hint: Use Pigou Bound (15 pts)
44/3 Show that P oA ≤ 44/3 − 3 .
4. In a cloud computing environment with m machines, k machines are required (k < m) to complete the task of finding a solution to a physics problem. The machine owners bid to be used as one machine out of k for the job. Let αj be the bid by machine owner j for the job.
(a) Show an incentive compatible method to determine the winners. (5 pts)
1

(b) Suppose you also need to consider the cost of edges that connect to the k nodes to exchange data. There are E edge providers that bid for the connection. Each edge provider e provides a cost bid βe,j for connecting a client to a machine j. Determine an incentive compatible mechanism for this problem (goal is to minimize cost). Tip: Express the answer as an optimization program first. (15 pts)
5. In the Fisher linear market equilibrium model, let M be a market with n traders and m goods, with each trader i having utility uij = vijxij for good j where vij = rjsi ≥ 0, and xij ∈ R+. There is 1 unit of each good. And each trader has 1 unit of money.
Showthatthepricesof2goodsjandj′acquiredbyatraderisintheratiorj/rj′,i.e.pj/pj′ =rj/rj′. Determine an allocation and prices that are at Market equilibrium. (20pts)