Mechanisms for Dynamic EnvironmentsDavid C. ParkesDivision of Engineering and Applied SciencesHarvard UniversityCarnegie Mellon University Nov 6, 2005http://www.eecs.harvard.edu/econcsOutline• Prior-Free Online Auction Design: – Non-reusable Goods, Finite time horizon.• General characterization for truthful online auctions• Prior-Free Online Auction Design: – Reusable Goods, infinite time horizon.• Model-based Online Mechanisms. • Future Directions.Related Papers• Virtual Worlds: Fast and Strategyproof Auctions for Dynamic Resource Allocation. Chaki Ng, David C. Parkes, and Margo Seltzer. In Proc. 4th ACM Conf. on Electronic Commerce(EC'03), pp. 238-239, 2003 (Short paper).• Adaptive Limited-Supply Online Auctions, Mohammad T. Hajiaghayi, Robert Kleinberg, and David C. Parkes. In Proc. ACM Conf. on Electronic Commerce, pp. 71-80, 2004. • Online Auctions with Re-usable Goods, Mohammad Hajiaghayi, Robert Kleinberg, Mohammad Mahdian, and David C. Parkes. In Proc. 6th ACM Conf. on Electronic Commerce(EC'05), pp. 165-174, 2005.• Models for Truthful Online Double Auction. Jonathan Bredin and David C. Parkes. In Proc. 21st Conference on Uncertainty in Artificial Intelligence(UAI'2005), pp. 50-59, 2005.• Pricing WiFi at Starbucks– Issues in Online Mechanism Design, Eric Friedman and David C. Parkes. In Proc. 4th ACM Conf. on Electronic Commerce(EC'03), pp. 240-241, 2003. (Short paper).• An MDP-Based Approach to Online Mechanism Design, David C. Parkes and Satinder Singh. In Proc. 17th Annual Conf. on Neural Information Processing Systems(NIPS'03), 2003.• Approximately Efficient Online Mechanism Design, David C. Parkes, Satinder Singh, and Dimah Yanovsky. In Proc. 18th Annual Conf. on Neural Information Processing Systems(NIPS'04), 2004. Value $100 $80 $60Arrival: 11am 11am 12pmPatience: 2hrs 2hrs 1hrHow should you bid?“Please bid your value and your patience. A decision will be made by the end of your stated patience.”Example 1: Last-Minute TicketsValue $100 $80 $60Arrival: 11am 11am 12pmPatience: 2hrs 2hrs 1hrAuction: sell one ticket ineach hour (given demand),to the highest bidder at second-highest bid price. If truthful, then:{ <1, $80>, <2, $60>}However, bidder 1 could a) reduce bid price to $65{<2, $65>, <1, $60>}b) delay bid until 12pm{<2, $0>, <1, $60>}Dynamic allocation problems…are everywhere in computer science• MoteLab (Berkeley)– distributed sensor network testbed– researchers compete for the right to sense, aggregate and propagate readings• PlanetLab (Princeton)– global overlay network on the Internet– supports network research, long-running services•Grid computing – much of science research is now intensively computational– globally-distributed computational infrastructure• Network resource allocation– e.g. dynamic negotiation for WiFi bandwidthMany systems are simultaneously both computational and economic systems. …are can be found in e-commerce, elsewhere • Sequential auctions on eBay– e.g. auctions for LCDs, each bidder wants one• Expiring goods– e.g. auctions for last-minute ticketsBasic Model for Online Auctions• Valuation θi= (ai, di, wi). Discrete time periods.• Arrival time: ai. Departure time: di.Value, wi• Allocation schedule x∈X. •vi(x) = wi, if xi(t)=1 for some t∈[ai,di]= 0 , otherwise• Quasi-linear utility: ui(x,price) = vi(x) - price• Auction: A=< f, p >, –allocation rule, f : Θn→ X– payment rule, p : Θn→ Rn• Truthful auction: reporting value <ai, di, wi>immediately upon arrival is a dominant strategy equilibrium.• Assume: cannot under-report ai.Prior-Free: Key Variations• Limited-supply (k≥1) of goods, sell in any period before time horizon, T. –single-unit demand– multi-unit demand• Reusable goods, can sell up to k units in each time period. Finite time horizon, T. –single-period demand–multi-period demandPrior-Free Auction Design• c-competitive for efficiency if E[Val(Aucv)] ≥ 1/c EFF(v), for all v• c-competitive for revenue if E[Rev(Aucv)] ≥ 1/c F (2)(v), for all vValue $500 $80 $60Arrival: 11am 11am 12pmPatience: 2hrs 2hrs 1hrv(m)is m-th highest valueEFF: $580OPT: $160EFF(v) = ∑i·kv(i)“efficiency”F (2)(v) = max2· l·k{ l·v(l) } “omniscient revenue”(c.f. Goldberg, Hartline et al.01)(or Vickrey price if 1 item)Limited-Supply Auction• Assume values in [L,U]. k-unit supply. Let φ = (U/L).• Adversarial model: choose values and timing.• Define a “price schedule”: p(j) = L · φ j/k+1, for jthunit.• Sell units while bid value ≥ price.(Lavi & Nisan’00)φ1/k+1φkTruthful. ln(φ)-competitive w.r.t. efficiency and Vickrey revenue, Matching lower-bound, and good average-case performance in simulation.Our model: Fixed, Unknown Distribution• More realistic adversarial model: Lavi & Nisan allowed arbitrary sequencing of arbitrary values• Instead, we model values as i.i.d. from some unknown distribution. • Want good performance whateverthe distribution.• Should lead to an auction with better performance in practice.(Hajiaghayi, Kleinberg, P., ACM’EC04)Aside: The Online Selection Problem• Remove incentives, and specialize to the case of disjoint arrival-departure intervals.7 1,000 325• Remove incentives, and specialize to the case of disjoint arrival-departure intervals.• Reduces to the secretary problem:– interview n job applicants in random order, want to max probof selecting best applicant (told n)–told relative orderingw.r.t. applicants already interviewed, must hire or passAside: The Online Selection Problem7 1,000 325• Remove incentives, and specialize to the case of disjoint arrival-departure intervals.• Reduces to the secretary problem:– interview n job applicants in random order, want to max probof selecting best applicant (told n)–told relative orderingw.r.t. applicants already interviewed, must hire or passAside: The Online Selection Problem7 1,000 3251 1 421usefulinfo•Samples 1…n• Candidate: a sample that is max across seen so far• Want to accept a candidate when Prob(winner | candidate) ≥ Prob(find winner in future with optimal policy)increases decreasesE.g., n=1, s*=1, Pr(succ)=1n=5, s*=3, Pr(succ)=0.433n=10, s*=4, Pr(succ)=0.399n=20, s*=8, Pr(succ)=0.384n=100, s*=38, Pr(succ)=0.371n=1000, s*=369, Pr(succ)=0.368 ≈ 1/eSo, unique round in which start accepting.The Secretary Algorithm• Theorem (Dynkin, 1962): The