Arrow Research search

Author name cluster

Yakov Babichenko

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
2 author rows

Possible papers

10

AAAI Conference 2021 Conference Paper

Bayesian Persuasion under Ex Ante and Ex Post Constraints

  • Yakov Babichenko
  • Inbal Talgam-Cohen
  • Konstantin Zabarnyi

Bayesian persuasion, as introduced by Kamenica and Gentzkow in 2011, is the study of information sharing policies among strategic agents. A prime example is signaling in online ad auctions: what information should a platform signal to an advertiser regarding a user when selling the opportunity to advertise to her? Practical considerations such as preventing discrimination, protecting privacy or acknowledging limited attention of the information receiver impose constraints on information sharing. We propose a simple way to mathematically model such constraints as restrictions on Receiver’s admissible posterior beliefs. We consider two families of constraints – ex ante and ex post; the latter limits each instance of Sender-Receiver communication, while the former more general family can also pose restrictions in expectation. For the ex ante family, a result of Doval and Skreta (2018) establishes the existence of an optimal signaling scheme with a small number of signals – at most the number of constraints plus the number of states of nature – and we show this result is tight. For the ex post family, we tighten the previous bound of Vølund (2018), showing that the required number of signals is at most the number of states of nature, as in the original Kamenica-Gentzkow setting. As our main algorithmic result, we provide an additive bi-criteria FPTAS for an optimal constrained signaling scheme assuming a constant number of states of nature; we improve the approximation to singlecriteria under a Slater-like regularity condition. The FPTAS holds under standard assumptions, and more relaxed assumptions yield a PTAS. We then establish a bound on the ratio between Sender’s optimal utility under convex ex ante constraints and the corresponding ex post constraints. We demonstrate how this result can be applied to find an approximately welfare-maximizing constrained signaling scheme in ad auctions.

PDF Details

FOCS Conference 2020 Conference Paper

Communication complexity of Nash equilibrium in potential games (extended abstract)

  • Yakov Babichenko
  • Aviad Rubinstein

We prove communication complexity lower bounds for (possibly mixed) Nash equilibrium in potential games. In particular, we show that finding a Nash equilibrium requires poly(N) communication in two-player N×N potential games, and 2 poly(n) communication in n-player two-action games. To the best of our knowledge, these are the first results to demonstrate hardness in any model of (possibly mixed) Nash equilibrium in potential games.

Details

AAAI Conference 2020 Conference Paper

Incentive-Compatible Classification

  • Yakov Babichenko
  • Oren Dean
  • Moshe Tennenholtz

We investigate the possibility of an incentive-compatible (IC, a. k. a. strategy-proof) mechanism for the classification of agents in a network according to their reviews of each other. In the α-classification problem we are interested in selecting the top α fraction of users. We give upper bounds (impossibilities) and lower bounds (mechanisms) on the worst-case coincidence between the classification of an IC mechanism and the ideal α-classification. We prove bounds which depend on α and on the maximal number of reviews given by a single agent, Δ. Our results show that it is harder to find a good mechanism when α is smaller and Δ is larger. In particular, if Δ is unbounded, then the best mechanism is trivial (that is, it does not take into account the reviews). On the other hand, when Δ is sublinear in the number of agents, we give a simple, natural mechanism, with a coincidence ratio of α.

PDF Details

TARK Conference 2019 Conference Paper

Sequential Voting with Confirmation Network

  • Yakov Babichenko
  • Oren Dean
  • Moshe Tennenholtz

We discuss voting scenarios in which the set of voters (agents) and the set of alternatives are the same; that is, voters select a single representative from among themselves. Such a scenario happens, for instance, when a committee selects a chairperson, or when peer researchers select a prize winner. Our model assumes that each voter either renders worthy (confirms) or unworthy any other agent. We further assume that the prime goal of any agent is to be selected himself. Only if that is not feasible, will he try to get one of those he confirms selected. In this paper we investigate the open-sequential ballot system in the above model. We consider both plurality (where each voter has one vote) and approval (where a voter may vote for any subset). Our results show that it is possible to find scenarios in which the selected agent is much less popular than the optimal (most popular) agent. We prove, however, that in the case of approval voting, the ratio between their popularity is always bounded from above by 2. In the case of plurality voting, we show that there are cases in which some of the equilibria give an unbounded ratio, but there always exists at least one equilibrium with ratio 2 at most.

Details DOI