Mechanism Design: Online Auction or Packet Scheduling Online auction of a reusable good (packet slots) Agents types: (arrival, departure, value) Agents can lie about value Agents can lie about arrival & departure Restrict to later arrival, earlier departure Goals Maximize value of agents who receive good Maximize revenue generated by auctioneer Reminder of previous results
Upper bound of 2 Lower bound of = (5 + 1)/2 1.618 Upper bound of 2 Greedy: Always send feasible packet with maximum value Greedy is 2-competitive Come up with a 2 packet instance which gives lower bound of 2 (3,2) (3,3)
(2,3) (4,4) Time: 1, packet (4,4) sent Lower Bound: = (5 + 1)/2 Figures from Online Scheduling with Partial Job Values: Does Timesharing or Randomization Help? by Chin and Fung, Algorithmica, 37, 149-164, 2003. Mechanism Design Bounds Agents can lie about values, arrival time, and departure time
Unbounded Can create 3-competitive mechanism using Set Nash concept Agents can lie about values, arrival time, and early departure time How could we enforce such a mechanism? Bound of 2 exactly General Lower Bound Lavi and Nisan (SODA 2005) Must have restriction on deadline or else cannot guarantee bounded competitive ratio
Key observation: Consider price pi(b-i) faced by agent i at time 1 Suppose v(i) < pi(b-i). Can agent i ever get item i? Suppose v(i) > pi(b-i) but doesnt win item 1 Now have M agents all arrive at time 1 with deadlines M and values in the range of (1, 1+).). Only one agent wins item in first time slot Optimal allocation is all agents win an item in some slot M can be arbitarily large so no bound on competitive ratio Restricted lower bound of 2
Hajiaghayi, Kleinberg, Mahdian, Parkes (EC 2005) and no 2-). mechanism Describe what happens in the following scenarios 1. 2. 3. 4. 5. (1,1,infinity) and (1,2,1) (ar, dep, value).
(1,1,1+) and (1,2,1) (what about price?) (1,2,1+) and (1,2,1) and (2,2,infinity) (1,2,1+) and (1,1,1) and (2,2,infinity) (1,2,1+) and (1,1,1) Restricted upper bound of 2 Based on greedy 2-competitive algorithm Allocation: In each time slot, give item to highest bidder Price computation Second price auction Price can drop in later rounds if it could have gotten the
item cheaper in a later round Example (1,2,2), (1,1, 2-).), (2,2,1) Variations k copies of each item available in each time slot Basically the same except the k top bidders in each time slot get the item Asynchronous time slots Item is needed for 1 unit of time but not all arrivals/deadlines are at integer time points
5 competitive mechanism Weight currently running agents value by extra 2 where is how long it has run for Set Nash Idea Identify a set of recommended strategies for all players Set-Nash Equilibria: A best response to all other agents playing a recommended strategy is to employ some recommended strategy Truthful mechanism: set of strategies is 1, truthfulness Not as powerful as truthful strategy is best response to ANY combination of strategies from other agents
Any game: set could be all strategies and then this is trivially true Application Japanese auction: tradition incremental auction (i.e. bids raise by ). until there is a winner) Sequential Japanese auction: use Japanese auction at each time t Players observe dropouts Myopic strategy Drop out when price reaches v(i) or when there are exactly d(i)-t players that did not drop yet
Semi-myopic strategy Drop no later than when price reaches v(i) and, satisfying first condition, no earlier than when only d(i)-t players did not drop yet If all players employ a semi-myopic strategy, 3-approximation Set-Nash Equilibria: The set of semi-myopic strategies forms a set Nash equilibrium
