Transcript Paper Presentation

GENERALIZED AGENTMEDIATED PROCUREMENT
AUCTIONS
PAPER BY: BONATTI, FAELLA, GALDI, SAURO
MARK KARLE
WHAT??
• Procurement Auctions
•
Auctioneer needs a service
•
Bidders offer it at their own conditions
• Agents acting on behalf of humans
• Partial preferences
•
Cannot have complete total order because of incomparability
•
Pick A, pick B, flip a coin, or wait for a decision later
•
Agents find shortlist which user picks from
• Do not allow null utility
PREFERENCE INCOMPLETENESS SCENARIO
• Alice is planning a trip and is looking for an online service
•
Either ticket booking, hotel booking, or both
•
Travel time 8-24 hours
•
Prices between $1000 and $2500
• Agent can accept constraints
• Alice favors 3-star hotel, prefers fast travels and flights, hates ads, and being contacted for marketing
COMPLICATED DESIRES
• Package 1
•
8 hour flight
•
3 star hotel
• Package 2
•
12 hour flight
•
5 star hotel
•
Costs $150 more per night
• Alice prefers Package 1 to Package 2
• If Package 3 and 4 differ by less than $20
•
Alice will prefer the shorter flight
• No options have null utility and being selected is never indifferent to not being selected
NOTATION (SORRY)
• a - Auctioneer
• N = {1,…,n} - Set of bidders
• A - Set of possible contracts auctioneer can stipulate with a bidder
• ≤𝑎 - preorder over A
•
b < b’ and b ~ b’ act as normal
•
𝑏 ⋈𝑎 𝑏′ means they are incomparable
• 𝐴𝑎 ⊆ 𝐴 – set of contracts that are admissible
•
Inadmissible means the agent incurs a loss
•
Any contract which does not incur a loss is strictly preferred to one that does
• 𝜑 𝐴 → 𝐴 – choice function which chooses final outcome after filtering by partial preference
•
𝐵1, … , 𝐵𝑛 - where Bi is the bid of bidder i
•
Masked vector B-i is obtained by replacing Bi with ?
•
(Bi, B-i) = B
MULTI-ITEM A-AUCTION
• Function A from bid vectors to pairs (x, c) where x is a Boolean allocation vector (xi = 1 iff i is a winner)
and c is the vector of contracts stipulated by each bidder
• Single-item A-auctions identify a single winner and single winning contract
•
For all B only one i such that xi = 1 and for all j=/= i, cj = null contract
BIDDER BEHAVIOR
• indifferent losers
• Preference between outcomes is consistent with preference between contracts
• Winning with admissible contract is at least as good as not winning
• Strictly prefer not to win rather than winning with an inadmissible contract
DOMINANCE
• B’ is a dominant strategy iff it dominates all other bids
•
It has highest utility
• Weak dominance if B’ weakly dominates
•
Now includes incomparable bids
DESIRABLE PROPERTIES
• No positive transfer
•
For all bidders i, if xi = 1, ci is in Bi
• Relative optimality
•
For any two bidders, if one wins, then its contract is not dominated by anything in the other’s bid
• Voluntary participation
•
If a bidder loses, its contract is null
• No failure
•
If there is at least one bidder intersecting Aa then there is a winner with a contract in Aa
• Truthfulness
•
Vector B^ = (A1,…,An) is a dominant strategy equilibrium
• Weak Truthfulness
•
B^ is a WDSE
COMPARISON WITH CLASSICAL AUCTIONS
• Standard second-price auctions violate no positive transfer
•
Second best bid might not be admissible for the winner
• An auction mechanism is truthful iff it is equivalent to a bid-independent auction
•
Bid-independent: bidder i is a winner iff bi>= f(B-i). All winners get a copy of the item and pay f(B-i)
•
Vickrey single-item second-price requires one bidder’s offer be strictly better than all others
•
Generalize it to be a winner if f(B-i) is in B
• Assume A has least three contracts. No single-item, bid-independent A-auction satisfies both relative
optimality and no failure.
SINGLE-ITEM AUCTIONS
• No single-item auction satisfies the properties no positive transfer, relative optimality, and weak
truthfulness
• The winner w is the highest priority bidder such that Aa intersect Bi is not empty.
•
w selects an element in the intersection and outputs (w,b)
• This defines a dictatorship
•
Tie-breaking is done by w
•
w is incentivized to maximize the set of admissible choices
•
Not relatively optimal
• Not known if there is a weakly truthful auction different from a dictatorship
MAKING IT RELATIVELY OPTIMAL
• Each bidder submits a bid giving rise to a bid vector.
• Let filter(i,B) be set of contracts offered by i that are admissible and no other bidder has made a strictly
preferable offer
• Select those who submitted a top offer
•
Winner w is highest priority element in this selection
• Transmit w to filter(w, B)
• Reply with a non-empty subset of contracts
• Transmit the subset to the auctioneer
• Auctioneer replies with its choice b
• Output is (w,b) and other bidders are assigned null contract
OUR MECHANISM
• No failure
• No positive transfer
• Relative optimality
• Voluntary participation
STRATEGIC ANALYSIS
• The winner selects the maximum from the filter
•
No other bidder can influence
•
Auction satisfies no failure and no positive transfer
• This auction is not weakly truthful
• Nonetheless, there is some dominance
•
For each bid Bi, Bi U Ai dominates Bi
• If a bidder wins with a truthful bid, then over-bidding does not yield any advantage
• If a truthful bidder is not a candidate winner, then over-bidding is counterproductive
• From point of view of auctioneer, effects of over-bidding are limited
•
It cannot yield a strictly less preferable contract
MULTI-ITEM AUCTIONS
• Bid independent defined as f(B-i) is in B is a winner is naturally multi-agent
• Generalized bid-independent auctions do not satisfy the no-failure property
• Use a variant of the auction mechanism
•
Assign a contract to each winner from the filter
• This satisfies truthfulness
QUESTIONS?