In this thesis, we concentrate on two hot topics, advertising auction (belongs to the scope of mechanisms with monetary transfer) and facility location (belongs to the scope of mechanisms without money). In each topic, aiming to achieve multiple goals, we work on designing the optimal (approximate) mechanisms and compare the simple mechanisms with the optimal mechanism.

In the first work, we focus on the advertising auction. Advertising becomes one of the most popular ways of monetizing an online transaction platform. Usually, sponsored advertisements are posted on the most attractive positions to enhance the number of clicks. However, multiple e-commerce platforms are aware that this action may hurt the search experience of users, even though it can bring more incomes. To balance the...[ Read more ]

In this thesis, we concentrate on two hot topics, advertising auction (belongs to the scope of mechanisms with monetary transfer) and facility location (belongs to the scope of mechanisms without money). In each topic, aiming to achieve multiple goals, we work on designing the optimal (approximate) mechanisms and compare the simple mechanisms with the optimal mechanism.

In the first work, we focus on the advertising auction. Advertising becomes one of the most popular ways of monetizing an online transaction platform. Usually, sponsored advertisements are posted on the most attractive positions to enhance the number of clicks. However, multiple e-commerce platforms are aware that this action may hurt the search experience of users, even though it can bring more incomes. To balance the advertising revenue and the user experience loss caused by advertisements, different from these common rules of treating the allocation of ads separately (from the arrangements of the organic searched items), in this work we build up an integrated system with mixed arrangements of advertisements and organic items. We focus on the design of truthful mechanisms to properly list the advertisements and organic items and optimally trade off the instant revenue and the user experience. Furthermore, for different settings and practical requirements, we extend our optimal truthful allocation mechanisms to cater for these realistic conditions. Finally, with the aid of the real data, our experimental results verify the good performance of our mechanisms

In the second work, we focus on a canonical Bayesian mechanism design setting: a seller wants to sell a single item to n bidders, whose values are drawn i.i.d. from a monotone-hazard-rate distribution. In the literature, three mechanisms receive particular attention: the revenue-optimal mechanism Myerson Auction (OPT), the welfare-optimal mechanism Second-Price Auction (SPA), and the most widely-used mechanism Anonymous Pricing (AP). In terms of revenue, we investigate how well the later two mechanisms can approximate Myerson Auction. OPT vs. AP: over all n ∈ N _≥1, the supremum ratio is 1.27, and the worst-case distribution is exponential-like. OPT vs. SPA: for each n ≥ 2, this ratio is upper-bounded by (1 – (1 – 1/e)^{n – 1})^–1 = 1 + 2^–O(n); an asymptotically matching lower bound can be reached by a truncated exponential distribution.

The third work studies the topic of facility location. In this work, we study a new model where one or two facilities are to be located in a plaza to serve nearby residents. The plaza is geometrically modeled as a square, crossing which located a street. A number of residents (agents) live on this street with actual positions being their private information. Our goal is to design strategyproof mechanisms to elicit the agents' true positions and decide the locations to build facilities such that the social welfare is (approximately) maximized. We study several settings, where the facilities can be favorable or obnoxious, and the agents' distance metrics can be Manhattan or Euclidean. Interestingly, for Manhattan distances, all of our mechanisms achieve the optimal algorithmic social welfare. For Euclidean distances, however, we prove that the optimal algorithms are not strategyproof. Accordingly, for each model we design strategyproof mechanisms that guarantee constant approximations of the optimal social welfare.