DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.64

On the Communication Complexity of Finding a King in a Tournament

Authors: Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract

A tournament is a complete directed graph. A source in a tournament is a vertex that has no in-neighbours (every other vertex is reachable from it via a path of length 1), and a king in a tournament is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known that every tournament has at least one king. In particular, a maximum out-degree vertex is a king. The tasks of finding a king and a maximum out-degree vertex in a tournament has been relatively well studied in the context of query complexity. We study the communication complexity of finding a king, of finding a maximum out-degree vertex, and of finding a source (if it exists) in a tournament, where the edges are partitioned between two players. The following are our main results for n-vertex tournaments: - We show that the communication task of finding a source in a tournament is equivalent to the well-studied Clique vs. Independent Set (CIS) problem on undirected graphs. As a result, known bounds on the communication complexity of CIS [Yannakakis, JCSS'91, Göös, Pitassi, Watson, SICOMP'18] imply a bound of Θ̃(log² n) for finding a source (if it exists, or outputting that there is no source) in a tournament. - The deterministic and randomized communication complexities of finding a king are Θ(n). The quantum communication complexity of finding a king is Θ̃(√n). - The deterministic, randomized, and quantum communication complexities of finding a maximum out-degree vertex are Θ(n log n), Θ̃(n) and Θ̃(√n), respectively. Our upper bounds above hold for all partitions of edges, and the lower bounds for a specific partition of the edges. One of our lower bounds uses a fooling-set based argument, and all our other lower bounds follow from carefully-constructed reductions from Set-Disjointness. An interesting point to note here is that while the deterministic query complexity of finding a king has been open for over two decades [Shen, Sheng, Wu, SICOMP'03], we are able to essentially resolve the complexity of this problem in a model (communication complexity) that is usually harder to analyze than query complexity.

Cite as

Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh. On the Communication Complexity of Finding a King in a Tournament. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 64:1-64:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mande_et_al:LIPIcs.APPROX/RANDOM.2024.64,
  author =	{Mande, Nikhil S. and Paraashar, Manaswi and Sanyal, Swagato and Saurabh, Nitin},
  title =	{{On the Communication Complexity of Finding a King in a Tournament}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{64:1--64:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.64},
  URN =		{urn:nbn:de:0030-drops-210571},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.64},
  annote =	{Keywords: Communication complexity, tournaments, query complexity}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.44

Bayesian Calibrated Click-Through Auctions

Authors: Junjie Chen, Minming Li, Haifeng Xu, and Song Zuo

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

We study information design in click-through auctions, in which the bidders/advertisers bid for winning an opportunity to show their ads but only pay for realized clicks. The payment may or may not happen, and its probability is called the click-through rate (CTR). This auction format is widely used in the industry of online advertising. Bidders have private values, whereas the seller has private information about each bidder’s CTRs. We are interested in the seller’s problem of partially revealing CTR information to maximize revenue. Information design in click-through auctions turns out to be intriguingly different from almost all previous studies in this space since any revealed information about CTRs will never affect bidders' bidding behaviors - they will always bid their true value per click - but only affect the auction’s allocation and payment rule. In some sense, this makes information design effectively a constrained mechanism design problem. Our first result is an FPTAS to compute an approximately optimal mechanism under a constant number of bidders. The design of this algorithm leverages Bayesian bidder values which help to "smooth" the seller’s revenue function and lead to better tractability. The design of this FPTAS is complex and primarily algorithmic. Our second main result pursues the design of "simple" mechanisms that are approximately optimal yet more practical. We primarily focus on the two-bidder situation, which is already notoriously challenging as demonstrated in recent works. When bidders' CTR distribution is symmetric, we develop a simple prior-free signaling scheme, whose construction relies on a parameter termed optimal signal ratio. The constructed scheme provably obtains a good approximation as long as the maximum and minimum of bidders' value density functions do not differ much.

Cite as

Junjie Chen, Minming Li, Haifeng Xu, and Song Zuo. Bayesian Calibrated Click-Through Auctions. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2024.44,
  author =	{Chen, Junjie and Li, Minming and Xu, Haifeng and Zuo, Song},
  title =	{{Bayesian Calibrated Click-Through Auctions}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{44:1--44:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.44},
  URN =		{urn:nbn:de:0030-drops-201878},
  doi =		{10.4230/LIPIcs.ICALP.2024.44},
  annote =	{Keywords: information design, ad auctions, online advertising, mechanism design}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2022.11

Multi-Channel Bayesian Persuasion

Authors: Yakov Babichenko, Inbal Talgam-Cohen, Haifeng Xu, and Konstantin Zabarnyi

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

The celebrated Bayesian persuasion model considers strategic communication between an informed agent (the sender) and uninformed decision makers (the receivers). The current rapidly-growing literature assumes a dichotomy: either the sender is powerful enough to communicate separately with each receiver (a.k.a. private persuasion), or she cannot communicate separately at all (a.k.a. public persuasion). We propose a model that smoothly interpolates between the two, by introducing a natural multi-channel communication structure in which each receiver observes a subset of the sender’s communication channels. This captures, e.g., receivers on a network, where information spillover is almost inevitable. Our main result is a complete characterization specifying when one communication structure is better for the sender than another, in the sense of yielding higher optimal expected utility universally over all prior distributions and utility functions. The characterization is based on a simple pairwise relation among receivers - one receiver information-dominates another if he observes at least the same channels. We prove that a communication structure M₁ is (weakly) better than M₂ if and only if every information-dominating pair of receivers in M₁ is also such in M₂. This result holds in the most general model of Bayesian persuasion in which receivers may have externalities - that is, the receivers' actions affect each other. The proof is cryptographic-inspired and it has a close conceptual connection to secret sharing protocols. As a surprising consequence of the main result, the sender can implement private Bayesian persuasion (which is the best communication structure for the sender) for k receivers using only O(log k) communication channels, rather than k channels in the naive implementation. We provide an implementation that matches the information-theoretical lower bound on the number of channels - not only asymptotically, but exactly. Moreover, the main result immediately implies some results of [Kerman and Tenev, 2021] on persuading receivers arranged in a network such that each receiver observes both the signals sent to him and to his neighbours in the network. We further provide an additive FPTAS for an optimal sender’s signaling scheme when the number of states of nature is constant, the sender has an additive utility function and the graph of the information-dominating pairs of receivers is a directed forest. We focus on a constant number of states, as even for the special case of public persuasion and additive sender’s utility, it was shown by [Shaddin Dughmi and Haifeng Xu, 2017] that one can achieve neither an additive PTAS nor a polynomial-time constant-factor optimal sender’s utility approximation (unless P=NP). We leave for future research studying exact tractability of forest communication structures, as well as generalizing our result to more families of sender’s utility functions and communication structures. Finally, we prove that finding an optimal signaling scheme under multi-channel persuasion is computationally hard for a general family of sender’s utility functions - separable supermajority functions, which are specified by choosing a partition of the set of receivers and summing supermajority functions corresponding to different elements of the partition, multiplied by some non-negative constants. Note that one can easily deduce from [Emir Kamenica and Matthew Gentzkow, 2011] and [Itai Arieli and Yakov Babichenko, 2019] that finding an optimal signaling scheme for such utility functions is computationally tractable for both public and private persuasion. This difference illustrates both the conceptual and the computational hardness of general multi-channel persuasion.

Cite as

Yakov Babichenko, Inbal Talgam-Cohen, Haifeng Xu, and Konstantin Zabarnyi. Multi-Channel Bayesian Persuasion. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 11:1-11:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{babichenko_et_al:LIPIcs.ITCS.2022.11,
  author =	{Babichenko, Yakov and Talgam-Cohen, Inbal and Xu, Haifeng and Zabarnyi, Konstantin},
  title =	{{Multi-Channel Bayesian Persuasion}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{11:1--11:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.11},
  URN =		{urn:nbn:de:0030-drops-156072},
  doi =		{10.4230/LIPIcs.ITCS.2022.11},
  annote =	{Keywords: Algorithmic game theory, Bayesian persuasion, Private Bayesian persuasion, Public Bayesian persuasion, Secret sharing, Networks}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2017.34

Algorithmic Aspects of Private Bayesian Persuasion

Authors: Yakov Babichenko and Siddharth Barman

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract

We consider a multi-receivers Bayesian persuasion model where an informed sender tries to persuade a group of receivers to take a certain action. The state of nature is known to the sender, but it is unknown to the receivers. The sender is allowed to commit to a signaling policy where she sends a private signal to every receiver. This work studies the computation aspects of finding a signaling policy that maximizes the sender's revenue. We show that if the sender's utility is a submodular function of the set of receivers that take the desired action, then we can efficiently find a signaling policy whose revenue is at least (1-1/e) times the optimal. We also prove that approximating the sender's optimal revenue by a factor better than (1-1/e) is NP-hard and, hence, the developed approximation guarantee is essentially tight. When the sender's utility is a function of the number of receivers that take the desired action (i.e., the utility function is anonymous), we show that an optimal signaling policy can be computed in polynomial time. Our results are based on an interesting connection between the Bayesian persuasion problem and the evaluation of the concave closure of a set function.

Cite as

Yakov Babichenko and Siddharth Barman. Algorithmic Aspects of Private Bayesian Persuasion. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{babichenko_et_al:LIPIcs.ITCS.2017.34,
  author =	{Babichenko, Yakov and Barman, Siddharth},
  title =	{{Algorithmic Aspects of Private Bayesian Persuasion}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.34},
  URN =		{urn:nbn:de:0030-drops-81502},
  doi =		{10.4230/LIPIcs.ITCS.2017.34},
  annote =	{Keywords: Economics of Information, Bayesian Persuasion, Signaling, Concave Closure}
}

4 Search Results for "Babichenko, Yakov"

On the Communication Complexity of Finding a King in a Tournament

Abstract

Cite as

Bayesian Calibrated Click-Through Auctions

Abstract

Cite as

Multi-Channel Bayesian Persuasion

Abstract

Cite as

Algorithmic Aspects of Private Bayesian Persuasion

Abstract

Cite as

Thanks for your feedback!

Could not send message