東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Linked to FindBook

Google Book

Amazon

博客來

Mechanism Design for Variants of Advertising Auction and Facility Location.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Mechanism Design for Variants of Advertising Auction and Facility Location./
Author:	Li, Weian.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2021,
Description:	104 p.
Notes:	Source: Dissertations Abstracts International, Volume: 83-11, Section: A.
Contained By:	Dissertations Abstracts International83-11A.
Subject:	Sparsity. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=29057126
ISBN:	9798426864948

Mechanism Design for Variants of Advertising Auction and Facility Location.
Li, Weian.

Mechanism Design for Variants of Advertising Auction and Facility Location. - Ann Arbor : ProQuest Dissertations & Theses, 2021 - 104 p.

Source: Dissertations Abstracts International, Volume: 83-11, Section: A.

Thesis (Ph.D.)--Hong Kong University of Science and Technology (Hong Kong), 2021.

This item must not be sold to any third party vendors.

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 workon designing the optimal (approximate) mechanisms and compare the simple mechanismswith 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, sponsoredadvertisements are posted on the most attractive positions to enhance the number ofclicks. However, multiple e-commerce platforms are aware that this action may hurtthe search experience of users, even though it can bring more incomes. To balance theadvertising revenue and the user experience loss caused by advertisements, different fromthese common rules of treating the allocation of ads separately (from the arrangementsof the organic searched items), in this work we build up an integrated system with mixedarrangements of advertisements and organic items. We focus on the design of truthfulmechanisms to properly list the advertisements and organic items and optimally trade off the instant revenue and the user experience. Furthermore, for different settings andpractical requirements, we extend our optimal truthful allocation mechanisms to cater forthese realistic conditions. Finally, with the aid of the real data, our experimental resultsverify the good performance of our mechanismsIn the second work, we focus on a canonical Bayesian mechanism design setting: aseller 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 particularattention: the revenue-optimal mechanism Myerson Auction (OPT), the welfare-optimal mechanism Second-Price Auction (SPA), and the most widely-used mechanism AnonymousPricing (AP). In terms of revenue, we investigate how well the later two mechanisms canapproximate 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, thisratio is upper-bounded by (1 - (1 - 1/e)n - 1)-1 = 1 + 2-O(n); an asymptotically matchinglower bound can be reached by a truncated exponential distribution.The third work studies the topic of facility location. In this work, we study a newmodel 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 numberof 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 positionsand 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 Manhattandistances, 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 guaranteeconstant approximations of the optimal social welfare.

ISBN: 9798426864948Subjects--Topical Terms:

3680690
Sparsity.

Mechanism Design for Variants of Advertising Auction and Facility Location.
LDR:04478nmm a2200325 4500 001 2348948
005 20220920134629.5
008 241004s2021 ||||||||||||||||| ||eng d
020 $a 9798426864948
035 $a (MiAaPQ)AAI29057126
035 $a (MiAaPQ)HongKongSciTech_991012985999403412
035 $a AAI29057126
040 $a MiAaPQ $c MiAaPQ
100 1 $a Li, Weian. $3 3688330
245 1 0 $a Mechanism Design for Variants of Advertising Auction and Facility Location.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2021
300 $a 104 p.
500 $a Source: Dissertations Abstracts International, Volume: 83-11, Section: A.
500 $a Advisor: Qi, Qi.
502 $a Thesis (Ph.D.)--Hong Kong University of Science and Technology (Hong Kong), 2021.
506 $a This item must not be sold to any third party vendors.
520 $a 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 workon designing the optimal (approximate) mechanisms and compare the simple mechanismswith 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, sponsoredadvertisements are posted on the most attractive positions to enhance the number ofclicks. However, multiple e-commerce platforms are aware that this action may hurtthe search experience of users, even though it can bring more incomes. To balance theadvertising revenue and the user experience loss caused by advertisements, different fromthese common rules of treating the allocation of ads separately (from the arrangementsof the organic searched items), in this work we build up an integrated system with mixedarrangements of advertisements and organic items. We focus on the design of truthfulmechanisms to properly list the advertisements and organic items and optimally trade off the instant revenue and the user experience. Furthermore, for different settings andpractical requirements, we extend our optimal truthful allocation mechanisms to cater forthese realistic conditions. Finally, with the aid of the real data, our experimental resultsverify the good performance of our mechanismsIn the second work, we focus on a canonical Bayesian mechanism design setting: aseller 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 particularattention: the revenue-optimal mechanism Myerson Auction (OPT), the welfare-optimal mechanism Second-Price Auction (SPA), and the most widely-used mechanism AnonymousPricing (AP). In terms of revenue, we investigate how well the later two mechanisms canapproximate 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, thisratio is upper-bounded by (1 - (1 - 1/e)n - 1)-1 = 1 + 2-O(n); an asymptotically matchinglower bound can be reached by a truncated exponential distribution.The third work studies the topic of facility location. In this work, we study a newmodel 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 numberof 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 positionsand 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 Manhattandistances, 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 guaranteeconstant approximations of the optimal social welfare.
590 $a School code: 1223.
650 4 $a Sparsity. $3 3680690
650 4 $a Game theory. $3 532607
650 4 $a Design. $3 518875
650 4 $a Cellular telephones. $3 607843
650 4 $a User experience. $3 3543994
650 4 $a Bids. $3 3561817
690 $a 0389
690 $a 0505
690 $a 0338
710 2 $a Hong Kong University of Science and Technology (Hong Kong). $3 1022235
773 0 $t Dissertations Abstracts International $g 83-11A.
790 $a 1223
791 $a Ph.D.
792 $a 2021
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=29057126