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
- 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
- One that does not have a coalition-proof
incentive-compatible dominant strategy.
where we are trying to maximize the sum of the valuations received
by the agents.
What is the dominant strategy for a buyer in the English
(first-price sealed-bid) auction?
- There is none.
his true valuation.
- Start bidding from the
- Do not bid until the last possible
- Bid up to twice his true
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
- It generates more expected revenue for
- It has a dominant
- It can be used to sell
What is a possible way to cheat, as a buyer, on the Vickrey
- Collude with other buyers so that they
- There is no way to cheat. The auction
has a dominant strategy of revealing one's true
- Submit a bid that is slightly lower
than one's true valuation.
- Submit a bid that is
slightly higher than one's true valuation.
to find out what the others will bid and then bid only slightly
higher than the highest bid.
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.
When does the winner's curse appear?
- In common value auctions.
- In English auctions.
- In Vickrey
- When the buyer buys something that he
- At the end of an auction with very
close (similar) valuations.
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.
- $4, Buyer-3 gets nothing.
- $4, Buyer-1 gets nothing.
- $3, Seller-1 gets nothing
Combinatorial auctions are useful because
- they eliminate the problem of
inefficient allocation of correlated goods in successive
- they are computationally tractable so
it is easy to determine the winner.
- they allow
the players to place bids that are conditional on external
- they combine the power of Vickrey and
- they allow bidders to express
their bid values as combinatorial functions.
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.
mailman problem cannot be reduced to a combinatorial
- 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.
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).
Which set of bids clears this auction while maximizing revenue?
|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
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
- represents a possible allocation of
bids to sellers.
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.
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
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.
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.
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.
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?
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.
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 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.
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.
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
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
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.
In asynchronous backtracking each agent maintains a local-view
- 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.
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.
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.
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.
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.
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.
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.
Does LRTA* always converge to the optimal solution?
If it always moves to the min neighbor it can get neglect to explore states that might be better.
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.
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.
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.
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.
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?
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.
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.
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.
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.
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.