Prompt mechanism for ad placement over time

摘要: Consider video ad placement into commercial breaks in a television channel. The ads arrive online over time and each has an expiration date. are typically of some uniform duration; however, the may have arbitrary size. Each private value should be posted break at most once by its player who own gets her if had been broadcasted ad's date (obviously, after arrival date), zero otherwise. Arranging while maximizing players' profit is classical problem subject to capacity constraint that solved truthfully. However, we interested not only truthfulness but also prompt mechanism where payment determined for agent very moment broadcast. promptness crucial requirement our algorithm, since it allows process without any redundant relation between auctioneer players. An inability resolve this could even prevent application such mechanisms real marketing process. We design 6-approximation problem. Previously Cole et al considered special case all same size which equal duration. For particular they achieved 2-approximation mechanism. general with considerably more involved requires designing new call Gravity Algorithm.