Ascending Combinatorial Auctions = a restricted form of preference elicitation in CAsAdvantages of ascending CAsPrice hierarchyCompetitive equilibriumExistence of CE pricesWhen do linear CE prices exist?When do non-linear anonymous prices exist?Minimal CE pricesBuyers are substitutesBuyer-submodularUniversal CE pricesCommunicational complexity lower boundsDesigning ascending CAsPrice-based ascending CAsSlide 17Price update methodsPrimal-dual auction designPrimal-dual example: iBundle(2)Other CA designs used in practiceOpen problemsAscending Combinatorial Auctions = a restricted form of preference elicitation in CAsTuomas SandholmAdvantages of ascending CAs•Same motivation as other multiagent preference elicitation methods•Transparency•Dynamic exchange of information–With correlated values, can lead to increased revenuePrice hierarchy•We consider several classes of pricing functions:1. Linear: pj for each jG, p(S) = ΣjSpj2. Non-linear: p(S) for each bundle S3. Non-linear and non-anonymous: pi(S) for each bundle S and bidder i•3 generalizes 2 generalizes 1Competitive equilibrium•Let agent i’s surplus πi(Si,p) = vi(Si) – pi(Si)•Let ΠS(S,p) = Σi pi(Si)•Prices p and allocation S* are in competitive equilibrium (CE) if:1. πi(Si*, p) = maxS [vi(S) – pi(S), 0] (for all i)2. ΠS(S*, p) = maxS Σi pi(Si) s.t. S feasible•So, a CE (S*,p) is such that S* maximizes the payoff of every bidder and the seller, given the prices•Allocation S* is said to be supported by p in CE•Theorem: Allocation S* is supported in CE iff S* is efficient•CE prices always exist (e.g. pi = vi)Existence of CE prices•Some ascending CAs are designed to output a CE•We just saw that non-linear, non-anonymous prices always exist•But linear and non-linear anonymous prices do not always exist–Under what conditions do they exist? …When do linear CE prices exist?•Theorem If each agent’s valuation function satisfies “goods are substitutes”, then linear CE prices exist•Special cases–Unit-demand valuations–Additive valuations–Downward-sloping valuationsWhen do non-linear anonymous prices exist?•Non-linear anonymous prices exist if1. valuations are supermodular, i.e., increasing returns, or2. bidders are single-minded, or3. bidders have safe valuations (each pair of bundles with positive value share at least one item)Minimal CE prices•Def. Minimal CE prices are CE prices where the seller’s revenue is minimized•For certain valuations, minimal CE prices correspond to VCG payments–Thus, truthful bidding is ex post equilibrium•Since minimal CE prices are a restriction of CE prices, a minimal CE allocation is efficient•Minimal CE prices always provide upper bound on VCG paymentsBuyers are substitutes•Let w(L) for L  I denote the value of the efficient allocation for CAP(L)•Def. A valuation v satisfies the buyers are substitutes (BAS) condition if:w(I) – w(I \ K) ≥ iK [w(I) – w(I \ i)] for all K  I•Thm. BAS holds iff VCG payments are supported in minimal CEBuyer-submodular•Recall: Buyers are substitutes (BAS) if:w(I) – w(I \ K) ≥ iK [w(I) – w(I \ i)] for all K  I•Slightly stronger version: Buyer-submodular (BSM):w(L) – w(L \ K) ≥ iK [w(L) – w(L \ i)] for all K  L, L I•Some ascending CAs require the BSM condition to terminate in a minimal CEUniversal CE prices•BAS does not hold in many practical cases–Then, by the previous theorem, VCG not reachable in minimal CE•We can reach a stronger condition by further restricting the price equilibrium concept•Defn Prices p are universal competitive equilibrium (UCE) prices if p are CE prices and p-i are CE prices for CAP(I \ i)•UCE prices (non-linear, non-anonymos) always exist (e.g. pi = vi)•Minimal CE prices are universal iff BAS holds•VCG outcome and payments determinable from UCE prices–Thm. Let p be UCE with efficient allocation S*. The VCG payment to bidder i is: qi = pi(Si*) – [I*(p) – I\i*(p)]where L*(p) = maxS ∑ pi(Si) for bidders L  I, S feasibleCommunicational complexity lower bounds•Thm Any CA that implements an efficient allocation must compute CE prices•Thm Any CA that implements the VCG outcome must compute UCE pricesDesigning ascending CAs•Timing–Continuous: faster propagation of info, difficult winner determination–Discrete: runs according to planned schedule•Feedback–Prices, bids, provisional allocation–Tradeoff between effective bid guidance and mitigating risk of collusion•Bidding rules–Bid improvement rule–Percentage improvement rule–Activity rules (to avoid sniping)•Termination conditions–Fixed vs. rolling•Bidding language•Proxy agentsPrice-based ascending CAs•Each auction in this family has roughly the same structure–In each round, announce prices and allocation–Receive bids–Update prices and allocation–Stop if termination criterion metPrice-based ascending CAsResults assume truthful biddingName Valuations Price structure Language Price update methodOutcomeKCSubstitutes Non-anon items OR-items Greedy CESAA Substitutes Items OR-items Greedy CEGS Substitutes Items XOR Minimal Min CEAus Substitutes Items Single Greedy VCGiBundle BSM Non-anon bundles XOR Greedy VCGGeneral Min CEdVSV BSM Non-anon bundles XOR Minimal VCGClock-proxy BSM Items (+proxy) XOR Greedy VCGGeneral Min CERAD General Items OR LP-based ????AkBA General Anon bundles XOR LP-based ????iBEA General Non-anon bundles XOR Greedy VCGMP General Non-anon bundles XOR Minimal VCGPrice update methods•Greedy: Price is increased on some set of the over-demanded items/bundles•Minimal: Price is increased on a minimal set of over-demanded items–Or, on the bids from a set of minimally undersupplied bidders•LP (primal-dual)-based: –Formulate CA as an LP with integral optima. Dual should allow convergence to UCE prices (or minimal CE prices in the case of BAS)–Use bidding language that is expressive for straightforward bidding, and formulate a WDP to compute feasible primal solution that minimizes violation of complementary slackness conditions as represented by bids–Terminate when provisional allocation and ask prices satisfy complementary slackness conditions (and thus represent a CE), and also satisfy any additional conditions needed to compute VCG payments (e.g., UCE conditions or minimal CE conditions under BAS) –Otherwise, adjust prices to make progress toward an