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

STOC Conference 2024 Conference Paper

Fair Division via Quantile Shares

Yakov Babichenko
Michal Feldman
Ron Holzman
Vishnu V. Narayan

We consider the problem of fair division, where a set of indivisible goods should be distributed fairly among a set of agents with combinatorial valuations. To capture fairness, we adopt the notion of shares, where each agent is entitled to a fair share, based on some fairness criterion, and an allocation is considered fair if the value of every agent (weakly) exceeds her fair share. A share-based notion is considered universally feasible if it admits a fair allocation for every profile of monotone valuations. A major question arises: is there a non-trivial share-based notion that is universally feasible? The most well-known share-based notions, namely the proportional share and the maximin share, are not universally feasible, nor are any constant approximations of them. We propose a novel share notion, where an agent assesses the fairness of a bundle by comparing it to her valuation in a random allocation. In this framework, a bundle is considered q -quantile fair, for q ∈[0,1], if it is at least as good as a bundle obtained in a uniformly random allocation with probability at least q . Our main question is whether there exists a constant value of q for which the q -quantile share is universally feasible. Our main result establishes a strong connection between the feasibility of quantile shares and the classical Erdős Matching Conjecture. Specifically, we show that if a version of this conjecture is true, then the 1/2 e -quantile share is universally feasible. Furthermore, we provide unconditional feasibility results for additive, unit-demand and matroid-rank valuations for constant values of q . Finally, we discuss the implications of our results for other share notions.

Details

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

TCS Journal 2021 Journal Article

Golden games

Urban Larsson
Yakov Babichenko

We consider extensive form 2-player win-lose games, with alternating moves, of perfect and complete information. The games are played over a complete binary-tree of depth n, where 0/1 payoffs in the leaves are drawn according to an i. i. d. Bernoulli distribution with probability p. Whenever p differs from the golden ratio, asymptotically as n → ∞, the winner of the game is determined. In the case where p equals the golden ratio, we call such a random game a golden game. In golden games the winner is the player that acts first with probability equal to the golden ratio. We suggest the notion of fragility as a measure for “fairness” of a game's rules. Fragility counts how many leaves' payoffs should be flipped in order to convert the identity of the winning player. Our main result provides a recursive formula for asymptotic fragility of golden games. Surprisingly, golden games are extremely fragile. For instance, with probability ≈0. 77 a losing player could flip a single payoff (out of 2 n ) and become a winner. With probability ≈0. 999 a losing player could flip 3 payoffs and become the winner.

Details DOI

STOC Conference 2021 Conference Paper

Settling the complexity of Nash equilibrium in congestion games

Yakov Babichenko
Aviad Rubinstein

We consider (i) the problem of finding a (possibly mixed) Nash equilibrium in congestion games, and (ii) the problem of finding an (exponential precision) fixed point of the gradient descent dynamics of a smooth function f :[0,1] n → ℝ. We prove that these problems are equivalent. Our result holds for various explicit descriptions of f , ranging from (almost general) arithmetic circuits, to degree-5 polynomials. By a very recent result of [Fearnley et al., STOC 2021], this implies that these problems are PPAD ∩ PLS -complete. As a corollary, we also obtain the following equivalence of complexity classes:

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 classiﬁcation of agents in a network according to their reviews of each other. In the α-classiﬁcation 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 classiﬁcation of an IC mechanism and the ideal α-classiﬁcation. 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 ﬁnd 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

STOC Conference 2019 Conference Paper

The communication complexity of local search

Yakov Babichenko
Shahar Dobzinski
Noam Nisan

We study a communication variant of local search. There is some fixed, commonly known graph G . Alice holds f A and Bob holds f B , both are functions that specify a value for each vertex. The goal is to find a local maximum of f A + f B with respect to G , i.e., a vertex v for which ( f A + f B )( v )≥ ( f A + f B )( u ) for each neighbor u of v .

Details

STOC Conference 2017 Conference Paper

Communication complexity of approximate Nash equilibria

Yakov Babichenko
Aviad Rubinstein

For a constant ϵ, we prove a ( N ) lower bound on the (randomized) communication complexity of ϵ-Nash equilibrium in two-player N x N games. For n -player binary-action games we prove an exp( n ) lower bound for the (randomized) communication complexity of (ϵ,ϵ)-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least (1-ϵ)-fraction of the players are ϵ-best replying.

Details

STOC Conference 2014 Conference Paper

Query complexity of approximate nash equilibria

Yakov Babichenko

We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players n and a constant number of actions m . Our main result states that even for constant ε , the query complexity of an ε -well-supported Nash equilibrium is exponential in n .

Details