Separating the communication complexity of truthful and non-truthful combinatorial auctions

Sepehr Assadi; Hrishikesh Khandeparkar; Raghuvansh R. Saxena; S. Matthew Weinberg

doi:10.1145/3357713.3384267

Separating the communication complexity of truthful and non-truthful combinatorial auctions

Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Scopus citations

Abstract

We prove the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any truthful auction guaranteeing a (34-1240+")-approximation for two buyers with XOS valuations over m items requires exp(ω(ϵ² · m)) communication whereas a non-truthful auction by Feige [J. Comput. 2009] is already known to achieve a 34-approximation in (m) communication. We obtain our lower bound for truthful auctions by proving that any simultaneous auction (not necessarily truthful) which guarantees a (34-1240+ϵ)-approximation requires communication exp(ω(ϵ² · m)), and then apply the taxation complexity framework of Dobzinski [FOCS 2016] to extend the lower bound to all truthful auctions (including interactive truthful auctions).

Original language	English (US)
Title of host publication	STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
Editors	Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
Publisher	Association for Computing Machinery
Pages	1073-1085
Number of pages	13
ISBN (Electronic)	9781450369794
DOIs	https://doi.org/10.1145/3357713.3384267
State	Published - Jun 8 2020
Event	52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, United States Duration: Jun 22 2020 → Jun 26 2020

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Conference

Conference	52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
Country/Territory	United States
City	Chicago
Period	6/22/20 → 6/26/20

All Science Journal Classification (ASJC) codes

Software

Keywords

Combinatorial Auctions
Lower Bounds
Simultaneous Communication

Access to Document

10.1145/3357713.3384267

Cite this

Assadi, S., Khandeparkar, H., Saxena, R. R., & Weinberg, S. M. (2020). Separating the communication complexity of truthful and non-truthful combinatorial auctions. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, & J. Chuzhoy (Eds.), STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (pp. 1073-1085). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3357713.3384267

Assadi, Sepehr ; Khandeparkar, Hrishikesh ; Saxena, Raghuvansh R. et al. / Separating the communication complexity of truthful and non-truthful combinatorial auctions. STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. editor / Konstantin Makarychev ; Yury Makarychev ; Madhur Tulsiani ; Gautam Kamath ; Julia Chuzhoy. Association for Computing Machinery, 2020. pp. 1073-1085 (Proceedings of the Annual ACM Symposium on Theory of Computing).

@inproceedings{d72fa6d126d24de38d4d6ad45053b0eb,

title = "Separating the communication complexity of truthful and non-truthful combinatorial auctions",

abstract = "We prove the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any truthful auction guaranteeing a (34-1240+{"})-approximation for two buyers with XOS valuations over m items requires exp(ω(ϵ2 · m)) communication whereas a non-truthful auction by Feige [J. Comput. 2009] is already known to achieve a 34-approximation in (m) communication. We obtain our lower bound for truthful auctions by proving that any simultaneous auction (not necessarily truthful) which guarantees a (34-1240+ϵ)-approximation requires communication exp(ω(ϵ2 · m)), and then apply the taxation complexity framework of Dobzinski [FOCS 2016] to extend the lower bound to all truthful auctions (including interactive truthful auctions).",

keywords = "Combinatorial Auctions, Lower Bounds, Simultaneous Communication",

author = "Sepehr Assadi and Hrishikesh Khandeparkar and Saxena, {Raghuvansh R.} and Weinberg, {S. Matthew}",

note = "Publisher Copyright: {\textcopyright} 2020 ACM.; 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 ; Conference date: 22-06-2020 Through 26-06-2020",

year = "2020",

month = jun,

day = "8",

doi = "10.1145/3357713.3384267",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "1073--1085",

editor = "Konstantin Makarychev and Yury Makarychev and Madhur Tulsiani and Gautam Kamath and Julia Chuzhoy",

booktitle = "STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing",

}

Assadi, S, Khandeparkar, H, Saxena, RR & Weinberg, SM 2020, Separating the communication complexity of truthful and non-truthful combinatorial auctions. in K Makarychev, Y Makarychev, M Tulsiani, G Kamath & J Chuzhoy (eds), STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 1073-1085, 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, United States, 6/22/20. https://doi.org/10.1145/3357713.3384267

Separating the communication complexity of truthful and non-truthful combinatorial auctions. / Assadi, Sepehr; Khandeparkar, Hrishikesh; Saxena, Raghuvansh R. et al.
STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. ed. / Konstantin Makarychev; Yury Makarychev; Madhur Tulsiani; Gautam Kamath; Julia Chuzhoy. Association for Computing Machinery, 2020. p. 1073-1085 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Separating the communication complexity of truthful and non-truthful combinatorial auctions

AU - Assadi, Sepehr

AU - Khandeparkar, Hrishikesh

AU - Saxena, Raghuvansh R.

AU - Weinberg, S. Matthew

PY - 2020/6/8

Y1 - 2020/6/8

N2 - We prove the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any truthful auction guaranteeing a (34-1240+")-approximation for two buyers with XOS valuations over m items requires exp(ω(ϵ2 · m)) communication whereas a non-truthful auction by Feige [J. Comput. 2009] is already known to achieve a 34-approximation in (m) communication. We obtain our lower bound for truthful auctions by proving that any simultaneous auction (not necessarily truthful) which guarantees a (34-1240+ϵ)-approximation requires communication exp(ω(ϵ2 · m)), and then apply the taxation complexity framework of Dobzinski [FOCS 2016] to extend the lower bound to all truthful auctions (including interactive truthful auctions).

AB - We prove the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any truthful auction guaranteeing a (34-1240+")-approximation for two buyers with XOS valuations over m items requires exp(ω(ϵ2 · m)) communication whereas a non-truthful auction by Feige [J. Comput. 2009] is already known to achieve a 34-approximation in (m) communication. We obtain our lower bound for truthful auctions by proving that any simultaneous auction (not necessarily truthful) which guarantees a (34-1240+ϵ)-approximation requires communication exp(ω(ϵ2 · m)), and then apply the taxation complexity framework of Dobzinski [FOCS 2016] to extend the lower bound to all truthful auctions (including interactive truthful auctions).

KW - Combinatorial Auctions

KW - Lower Bounds

KW - Simultaneous Communication

UR - http://www.scopus.com/inward/record.url?scp=85086757472&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85086757472&partnerID=8YFLogxK

U2 - 10.1145/3357713.3384267

DO - 10.1145/3357713.3384267

M3 - Conference contribution

AN - SCOPUS:85086757472

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1073

EP - 1085

BT - STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Makarychev, Konstantin

A2 - Makarychev, Yury

A2 - Tulsiani, Madhur

A2 - Kamath, Gautam

A2 - Chuzhoy, Julia

PB - Association for Computing Machinery

T2 - 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020

Y2 - 22 June 2020 through 26 June 2020

ER -

Assadi S, Khandeparkar H, Saxena RR, Weinberg SM. Separating the communication complexity of truthful and non-truthful combinatorial auctions. In Makarychev K, Makarychev Y, Tulsiani M, Kamath G, Chuzhoy J, editors, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2020. p. 1073-1085. (Proceedings of the Annual ACM Symposium on Theory of Computing). doi: 10.1145/3357713.3384267

Separating the communication complexity of truthful and non-truthful combinatorial auctions

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this