The answers are in boldface.

1. What is a common value auction?

   • One where the value an agent places on the item depends solely on the value the other agents place on the item.
   • One of the most commonly used auction types: English or Dutch.
   • One where the agents have an incentive to reveal their true valuations of the item.
   • One that does not have a coalition-proof incentive-compatible dominant strategy.
   • One where we are trying to maximize the sum of the valuations received by the agents.

2. What is the dominant strategy for a buyer in the English (first-price sealed-bid) auction?

   • There is none.
   • Bid his true valuation.
   • Start bidding from the beginning.
   • Do not bid until the last possible instance.
   • Bid up to twice his true valuation.

3. What is the main advantage of the Dutch auction over the first-price sealed-bid auction?

   • It is real-time efficient.
   • It generates more expected revenue for the buyer.
   • It generates more expected revenue for the seller.
   • It has a dominant strategy.
   • It can be used to sell tulips.

4. What is a possible way to cheat, as a buyer, on the Vickrey auction?

   • Collude with other buyers so that they bid less.
   • There is no way to cheat. The auction has a dominant strategy of revealing one's true valuation.
   • Submit a bid that is slightly lower than one's true valuation.
   • Submit a bid that is slightly higher than one's true valuation.
   • Try to find out what the others will bid and then bid only slightly higher than the highest bid.

5. Why is it that an item will often sell for more money on Ebay than it does on a regular retail outlet?

   • Because the English auction increases revenue for seller in correlated value auctions.
   • It does not. The expected sale price on Ebay is the same as on a retail store.
   • Because the robots used to place the automated bids at the end of the auction tend to push the price higher.
   • Because of the real-time characteristics of an Ebay auction.
   • Because the auctions have a time limit.

6. When does the winner's curse appear?

   • In common value auctions.
   • In English auctions.
   • In Vickrey auctions.
   • When the buyer buys something that he didn't want.
   • At the end of an auction with very close (similar) valuations.

7. What is the best way to clear the following set of bids so as to be locally efficient and provide a uniform price? This is a double auction. Consider only integer clearing prices.

   Agent	Bid
   Buyer-1	5
   Buyer-2	6
   Buyer-3	4
   Seller-1	3
   Seller-2	1

   • $4, Buyer-3 gets nothing.
   • $4, Buyer-1 gets nothing.
   • $3, Seller-1 gets nothing
   • $5
   • $2

8. Combinatorial auctions are useful because

   • they eliminate the problem of inefficient allocation of correlated goods in successive auctions.
   • they are computationally tractable so it is easy to determine the winner.
   • they allow the players to place bids that are conditional on external events.
   • they combine the power of Vickrey and Dutch auctions.
   • they allow bidders to express their bid values as combinatorial functions.

9. You are asked to implement an algorithm that finds the optimal solution to the mailman problem.

   A set of mailman start at a central location and must deliver a set of letters. At the end each mailman goes home. They incur a cost proportional to the distance traveled and receive a reward for each letter delivered.

   You instantly realized that this problem can be solved using a combinatorial auction where each mailman bids:
   • One bid for each possible subset of letters. The value of each bid the total reward for delivering the letters minus the cost of delivering them.
   • The mailman problem cannot be reduced to a combinatorial auction.
   • His utility for delivering all the letters. That is, the reward for delivering all the letters minus the cost of delivering them.
   • One bid for each letter. The value of each bid the total reward for delivering the letter minus the cost of delivering it.
   • One bid for each letter that is closer to the mailman's home than to any other mailman's home. The value of each bid the total reward for delivering the letter minus the cost of delivering it.

10. If the following bids were entered in a combinatorial auction (taken from the slide used in class, the items for sale are Spyke, Nightcrawler, Storm, ShadowCat, Rogue, Wolverine, Cyclops, Xavier, Jean Grey).

    Bid #	Bid price	Bid items
    1	$5	Wolverine
    2	$4	Cyclops, Jean Grey
    3	$5	Rogue, Wolverine
    4	$7	Cyclops, Storm
    5	$7	Nightcrawler, Storm
    6	$15	All items

    Which set of bids clears this auction while maximizing revenue?

    • 1,2,3,5
    • 6
    • 1,2,3,4,5,6
    • 1,2,3
    • 3,5,6

11. In Sandholm's algorithm for winner determination in combinatorial auctions we construct a search tree where each path from the root to a leaf: (pick best)

    • represents a set of bids where every item is in exactly one bid.
    • represents an allocation of items to agents where each item is allocated to exactly one agent.
    • represents the set of bids from one agent.
    • represents the set of bids for each item.
    • represents a possible allocation of bids to sellers.

12. A possible way to make Sandholm's algorithm for winner determination faster would be to (the choice you pick must be one that the algorithm does not currently implement).

    • order the search tree so that the bids with higher value are near the top.
    • create singleton bids of value 0 for all items.
    • use a better search algorithm, like IDA*.
    • ask the buyers to submit all their bids for all the items.
    • eliminate from consideration any bid that is dominated by another bid.

13. In negotiations, the conflict deal is:

    • the initial allocation.
    • the deal where no one does anything.
    • the deal where one agent does everything.
    • a payment of 0 to every agent.
    • a negative payment to every agent.

14. In the monotonic concession protocol, I terminate when

    • the deal proposed to me by the other guy is better for me than the deal I proposed to him.
    • we reach the conflict deal.
    • the time expires.
    • the deal he proposes has a higher utility for me than his previous offer.
    • the other guy proposes a deal that has lower utility for me than the previous deal he offered.

15. What is the Zeuthen strategy?

    • a way to determine how much to concede on my next offer in a negotiation.
    • a method for determining which of the available Nash equilibrium solutions is best in a negotiation.
    • a way to force the other player in a negotiation to offer his true valuation for the item.
    • a method for cheating in Vickrey auctions.
    • a way to incorporate externalities in a negotiation.

16. An appealing aspect of the Zeuthen strategy is that

    • if I say Im using then the best strategy for the other guy is also Zeuthen.
    • it terminates in one step.
    • it is coalition-proof.
    • it forces the other player in a negotiation to offer his true valuation for the item.
    • it can be used in combinatorial auctions.

    It does not work as is for combinatorial auction, but maybe there is a way to modify it so that it does?

17. What is reflectional symmetry?

    • In voting, if one agent prefers A to B and another B to A, then their votes should cancel each other out.
    • In auctions, if bid A is larger than bid B then bid B should be ignored.
    • In combinatorial auctions, if there is a bid for items A and B and another bid for items B and A, then the highest of the two bids should be considered.
    • In voting, a person can only vote once for each candidate.
    • In auctions, the result should be the same regardless of the order the bids were submitted.

18. Say you prefer Oscar the most, then Elmo, then Rosita, and finally Grouch. You are asked to participate in a Borda count auction to elect the favorite. What should your vote look like?

    • 4 for Oscar, 3 for Elmo, 2 for Rosita, and 1 for Grouch
    • Oscar
    • Oscar then Elmo then Rosita then Grouch
    • Oscar in the first election, then in any succeeding elections vote for my most preferred candidate that is still in the running.
    • 4 for Oscar and 1 for everyone else.

19. What does Arrow's Impossibility Theorem tell us?

    • That there can't be a completely fair voting mechanism.
    • That it is impossible to determine the winner of an election in polynomial time.
    • That it is impossible to determine the winner of a combinatorial auction in polynomial time.
    • That it is impossible to achieve rotational symmetry.
    • That it is impossible to achieve revenue equivalence.

20. Andrew, Bob, and Charles are trying to decide what color outfit to wear. They each have a Red, Blue, and Pink outfits. Andrew will only wear something different from everyone else. Bob will wear Red if Charles wears Blue, otherwise he wears Pink. Charles has decided to wear Pink. If they use the filtering algorithm to solve this problem, what color combination will Andrew, Bob, and Charles wear.

    • The algorithm will not find a solution.
    • Pink, Pink, Red
    • Blue, Red, Red
    • Blue, Blue, Red
    • Pink, Red, Red

21. Given that ¬ (a ∧ b ∧ c) and ¬ (b ∧ a ∧ f) and (a ∨ f), what can you derive from these facts using the hyper-resolution rule?

    • ¬( b ∨ c ∨ a)
    • ¬ b
    • ¬ (b ∧ c)
    • a ∧ f ∧ c
    • f ∨ c ∨ a

22. In the hyper-resolution based consistency algorithm, what information is contained within a nogood?

    • It tells of a particular assignment that violates some constraints.
    • It contains the constraints that are violated by the current assignment.
    • It is sent when the algorithm discovers that there is no solution to the problem.
    • It contains the list of variable assignments that have been tried so far.
    • It contains information about the number of assignments that have failed.

23. In asynchronous backtracking each agent maintains a local-view which contains

    • its beliefs about others' state.
    • the history of all messages received.
    • the current nogood.
    • the nogoods derived using the hyper-resolution rule.
    • its priority ordering of the agents.

24. In asynchronous weak-commitment search an agent will reset its own priority whenever

    • it can't find a value for itself that is consistent with its local view.
    • it receives a nogood from a lower priority agent.
    • it is the lowest priority agent and it resolves a nogood.
    • the current priority ordering does not reflect the fact that it has received more messages than higher priority agents.
    • there is no solution to the problem.

25. What is the problem in distributed constraint optimization?

    • To find the solution that minimizes the cost.
    • To find the solution that does not violate any of the constraints.
    • To distribute a constraint satisfaction problem.
    • To optimize the time that each agent spends computing.
    • To find a good graph coloring.

26. The Adopt algorithm first builds a DFS tree. This DFS tree has the special characteristic that

    • every node has links only to its ancestors or descendants.
    • it is a binary tree.
    • the agents with more constraints are placed near the root of the tree.
    • every path from the root to a leaf represents a possible solution to the problem.
    • all the constraints in the problem are represented as parent-child relationships in the tree.

27. The Adopt algorithm can solve (pick best)

    • distributed constraint optimization problems on problems with binary constraints.
    • distributed constraint optimization problems.
    • graph coloring problems.
    • distributed constraint satisfaction problems.
    • distributed constraint satisfaction problems on graph coloring instances.

28. In the Adopt algorithm each node maintains

    • a context, a lower bound, and an upper bound.
    • the current coloring for the subtree rooted at the node.
    • a history of all the OK? messages received.
    • the lower and upper bound on the cost of the solution for the whole problem.
    • a coloring and list of nogoods.

29. You are using LRTA* to solve the 8-puzzle and I tell you about five specific tile configurations and their respective distance to the goal (that is, how many moves it takes to get from each one to the goal configuration). How can you incorporate this information into your algorithm?

    • Add it to the heuristic function.
    • Eliminate those boards from the search space.
    • Have the agent start from the configuration (of the five) with the lowest distance.
    • Have the algorithm re-start whenever it reaches one of those configurations.
    • This information cannot be used without making significant changes to the code.

30. Does LRTA* always converge to the optimal solution?

    • No
    • Yes

    If it always moves to the min neighbor it can get neglect to explore states that might be better.

31. If you were to use LRTA* to solve the maze problem (that is, have one agent find its way out of a 2-dimensional maze), what would be good heuristic to use?

    • The linear distance to the goal.
    • The linear distance from the start.
    • The number of left turn taken thus far.
    • The linear distance to the start plus the linear distance to the goal.
    • The linear distance to the goal times the number of steps taken.

32. If two players using Fictitious play converge to a solution, what can we say about that solution?

    • It is a Nash equilibrium
    • It dominates all other solutions.
    • It is unstable.
    • It is only a fictitious solution. The real solution might be different.
    • It is the social welfare solution.

33. Under replicator dynamics each agent

    • has a reproduction rate that is proportional to its performance.
    • replicates by merging its "DNA" with that of others.
    • uses the strategy that has been shown to be most effective in the population.
    • creates one identical offspring after each step.
    • determines its best action by exploiting others' past behaviors.

34. An evolutionary stable strategy is one that

    • can overcome the appearance of small number of mutants.
    • is impervious to mutations.
    • only creates offsprings that will receiver higher expected rewards.
    • has a flaw in it.
    • cannot be superinfluenced by the Vickrey-Clarke imperative.

    "superinfluenced". I like making up words.

35. What is the moving target function problem?

    • When an agent's learning changes what another learning has to learn, and viz.
    • When two agents are moving around a field trying to find each other.
    • When the target changes its value.
    • It is the discrepancy between the Bayesian beliefs of the source agent and the Markov reality.
    • It is the lag time between the action and the reward.

    Can we have a Markov reality in a quantum world?

36. In the CLRI theory, the error() captures

    • the probability that the agent will take an incorrect action.
    • the number of incorrect actions taken by the agent.
    • the distance to the initial configuration.
    • the learning rate.
    • the change rate.

37. A 2-level agent

    • models other agents as 1-level.
    • takes actions based on a S->S'->A mapping.
    • is impossible to implement.
    • will always perform better than a 1-level and 0-level agent.
    • is a type of layered architecture.

    We discussed layered architectures in the first part of the semester.

38. The revelation principle in mechanism design states that

    • if a social choice can be implemented by a multi-step protocol then it can be implemented by a one-step protocol.
    • under certain conditions a mechanism will always exist such that the agents' best strategy is to reveal their true type.
    • any multi-step protocol that is Vickrey-Clarke-Groves compliant is also in a Bayesian Nash equilibrium.
    • if the Bayesian Nash equilibrium is strategy-proof then it is also Vickrey-Clarke-Groves compliant.
    • there is no better strategy than to tell the truth.

39. Under the Groves mechanism each agent should receive a payment that is equal to some function h() plus

    • the sum of everyone else's valuations for the given outcome.
    • the sum of all the payments divided by the agent's valuation for the given outcome
    • the agent's valuation for the given outcome.
    • a random number.
    • the payment given to the agent with the next highest (second-best) valuation.

40. What is the purpose of the Groves mechanism in mechanism design?

    • To make the mechanism strategy proof and converge to the social welfare solution.
    • To make the agents individually-rational.
    • To make the mechanism converge to the Bayesian Nash equilibrium.
    • To minimize the problem of revenue equivalence.
    • To make the mechanism tractable so that the agents can compute their bids in a timely manner.