Author name cluster

Oren Dean

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.

2 papers

2 author rows

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