File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/3465456.3467631
- Scopus: eid_2-s2.0-85112019071
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Targeting Makes Sample Efficiency in Auction Design
Title | Targeting Makes Sample Efficiency in Auction Design |
---|---|
Authors | |
Issue Date | 2021 |
Publisher | Association for Computing Machinery. |
Citation | Proceedings of the 22nd ACM Conference on Economics and Computation (EC '21), Budapest, Hungary, 18-23 July 2021, p. 610-629 How to Cite? |
Abstract | This paper introduces the targeted sampling model in optimal auction design. In this model, the seller may specify a quantile interval and sample from a buyer's prior restricted to the interval. This can be interpreted as allowing the seller to, for example, examine the top 40% bids from previous buyers with the same characteristics. The targeting power is quantified with a parameter Δ ∈ [0, 1] which lower bounds how small the quantile intervals could be. When Δ = 1, it degenerates to Cole and Roughgarden's model of i.i.d. samples; when it is the idealized case of Δ = 0, it degenerates to the model studied by [7]. For instance, for n buyers with bounded values in [0, 1], ~O(ε-1) targeted samples suffice while it is known that at least ~Ømega(n ε-2) i.i.d. samples are needed. In other words, targeted sampling with sufficient targeting power allows us to remove the linear dependence in n, and to improve the quadratic dependence in ε-1 to linear. In this work, we introduce new technical ingredients and show that the number of targeted samples sufficient for learning an ε-optimal auction is substantially smaller than the sample complexity of i.i.d. samples for the full spectrum of Δ ∈ [0, 1). Even with only mild targeting power, i.e., whenever Δ = o(1), our targeted sample complexity upper bounds are strictly smaller than the optimal sample complexity of i.i.d. samples. |
Persistent Identifier | http://hdl.handle.net/10722/304340 |
ISBN |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hu, Y | - |
dc.contributor.author | Huang, Z | - |
dc.contributor.author | Shen, Y | - |
dc.contributor.author | Wang, X | - |
dc.date.accessioned | 2021-09-23T08:58:41Z | - |
dc.date.available | 2021-09-23T08:58:41Z | - |
dc.date.issued | 2021 | - |
dc.identifier.citation | Proceedings of the 22nd ACM Conference on Economics and Computation (EC '21), Budapest, Hungary, 18-23 July 2021, p. 610-629 | - |
dc.identifier.isbn | 9781450385541 | - |
dc.identifier.uri | http://hdl.handle.net/10722/304340 | - |
dc.description.abstract | This paper introduces the targeted sampling model in optimal auction design. In this model, the seller may specify a quantile interval and sample from a buyer's prior restricted to the interval. This can be interpreted as allowing the seller to, for example, examine the top 40% bids from previous buyers with the same characteristics. The targeting power is quantified with a parameter Δ ∈ [0, 1] which lower bounds how small the quantile intervals could be. When Δ = 1, it degenerates to Cole and Roughgarden's model of i.i.d. samples; when it is the idealized case of Δ = 0, it degenerates to the model studied by [7]. For instance, for n buyers with bounded values in [0, 1], ~O(ε-1) targeted samples suffice while it is known that at least ~Ømega(n ε-2) i.i.d. samples are needed. In other words, targeted sampling with sufficient targeting power allows us to remove the linear dependence in n, and to improve the quadratic dependence in ε-1 to linear. In this work, we introduce new technical ingredients and show that the number of targeted samples sufficient for learning an ε-optimal auction is substantially smaller than the sample complexity of i.i.d. samples for the full spectrum of Δ ∈ [0, 1). Even with only mild targeting power, i.e., whenever Δ = o(1), our targeted sample complexity upper bounds are strictly smaller than the optimal sample complexity of i.i.d. samples. | - |
dc.language | eng | - |
dc.publisher | Association for Computing Machinery. | - |
dc.relation.ispartof | The 22nd ACM Conference on Economics and Computation (EC) 2021 | - |
dc.rights | The 22nd ACM Conference on Economics and Computation (EC) 2021. Copyright © Association for Computing Machinery. | - |
dc.title | Targeting Makes Sample Efficiency in Auction Design | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Huang, Z: zhiyi@cs.hku.hk | - |
dc.identifier.authority | Huang, Z=rp01804 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/3465456.3467631 | - |
dc.identifier.scopus | eid_2-s2.0-85112019071 | - |
dc.identifier.hkuros | 325108 | - |
dc.identifier.spage | 610 | - |
dc.identifier.epage | 629 | - |
dc.publisher.place | New York, NY | - |