In the first setting, we don抰 consider strategic behaviors of merchants. Given the information of each deal, we study how to dynamically allocate the user traffic of a GS website to different deals to maximize its revenue. We first consider a simple scenario in which the GS website shows one deal to each visitor. We derive an algorithm to find an optimal allocation. We then consider the scenario of showing multiple deals to each visitors, and make discussions with different settings of the deals. We derive an algorithm which can achieve a 1/4 approximation of the optimal allocation in the worst case.
We consider the strategic behaviors of merchants in the second setting and a GS website runs auctions allocate its traffic to deals. We formally study this kind of auctions, which are named as Groupon-style (GS) auctions. In GS auctions, a GS website is the auctioneer; merchants are bidders, and they submit bids about their deals (e.g., discounted price, revenue share ratio, purchase limit, etc.); an auction mechanism determines which subset of the deals to show to the consumers and how to charge merchants. We focus on mechanism design problems for social welfare maximization and revenue optimization.