Author name cluster

David Kurokawa

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.

7 papers

1 author row

AAAI Conference 2018 Conference Paper

Ranking Wily People Who Rank Each Other

Anson Kahng
Yasmine Kotturi
Chinmay Kulkarni
David Kurokawa
Ariel Procaccia

We study rank aggregation algorithms that take as input the opinions of players over their peers, represented as rankings, and output a social ordering of the players (which reﬂects, e. g. , relative contribution to a project or ﬁt for a job). To prevent strategic behavior, these algorithms must be impartial, i. e. , players should not be able to inﬂuence their own position in the output ranking. We design several randomized algorithms that are impartial and closely emulate given (nonimpartial) rank aggregation rules in a rigorous sense. Experimental results further support the efﬁcacy and practicability of our algorithms.

PDF Details

AAAI Conference 2016 Conference Paper

An Algorithmic Framework for Strategic Fair Division

Simina Brânzei
Ioannis Caragiannis
David Kurokawa
Ariel Procaccia

We study the paradigmatic fair division problem of fairly allocating a divisible good among agents with heterogeneous preferences, commonly known as cake cutting. Classic cake cutting protocols are susceptible to manipulation. Do their strategic outcomes still guarantee fairness? To address this question we adopt a novel algorithmic approach, proposing a concrete computational model and reasoning about the gametheoretic properties of algorithms that operate in this model. Speciﬁcally, we show that each protocol in the class of generalized cut and choose (GCC) protocols — which includes the most important discrete cake cutting protocols — is guaranteed to have approximate subgame perfect Nash equilibria, or even exact equilibria if the protocol’s tie-breaking rule is ﬂexible. We further observe that the (approximate) equilibria of proportional protocols — which guarantee each of the n agents a 1/n-fraction of the cake — must be (approximately) proportional, thereby answering the above question in the positive (at least for one common notion of fairness).

PDF Details

AAAI Conference 2016 Conference Paper

When Can the Maximin Share Guarantee Be Guaranteed?

David Kurokawa
Ariel Procaccia
Junxing Wang

The fairness notion of maximin share (MMS) guarantee underlies a deployed algorithm for allocating indivisible goods under additive valuations. Our goal is to understand when we can expect to be able to give each player his MMS guarantee. Previous work has shown that such an MMS allocation may not exist, but the counterexample requires a number of goods that is exponential in the number of players; we give a new construction that uses only a linear number of goods. On the positive side, we formalize the intuition that these counterexamples are very delicate by designing an algorithm that provably ﬁnds an MMS allocation with high probability when valuations are drawn at random.

PDF Details

IJCAI Conference 2015 Conference Paper

Impartial Peer Review

David Kurokawa
Omer Lev
Jamie Morgenstern
Ariel D. Procaccia

Motivated by a radically new peer review system that the National Science Foundation recently experimented with, we study peer review systems in which proposals are reviewed by PIs who have submitted proposals themselves. An (m, k)-selection mechanism asks each PI to review m proposals, and uses these reviews to select (at most) k proposals. We are interested in impartial mechanisms, which guarantee that the ratings given by a PI to others’ proposals do not affect the likelihood of the PI’s own proposal being selected. We design an impartial mechanism that selects a k-subset of proposals that is nearly as highly rated as the one selected by the non-impartial (abstract version of) the NSF pilot mechanism, even when the latter mechanism has the “unfair” advantage of eliciting honest reviews.

PDF Details

AAAI Conference 2014 Conference Paper

Biased Games

Ioannis Caragiannis
David Kurokawa
Ariel Procaccia

We present a novel extension of normal form games that we call biased games. In these games, a player’s utility is influenced by the distance between his mixed strategy and a given base strategy. We argue that biased games capture important aspects of the interaction between software agents. Our main result is that biased games satisfying certain mild conditions always admit an equilibrium. We also tackle the computation of equilibria in biased games.

PDF Details

AAAI Conference 2014 Conference Paper

Simultaneous Cake Cutting

Eric Balkanski
Simina Brânzei
David Kurokawa
Ariel Procaccia

We introduce the simultaneous model for cake cutting (the fair allocation of a divisible good), in which agents simultaneously send messages containing a sketch of their preferences over the cake. We show that this model enables the computation of divisions that satisfy proportionality — a popular fairness notion — using a protocol that circumvents a standard lower bound via parallel information elicitation. Cake divisions satisfying another prominent fairness notion, envy-freeness, are impossible to compute in the simultaneous model, but admit arbitrarily good approximations.

PDF Details

AAAI Conference 2013 Conference Paper

How to Cut a Cake Before the Party Ends

David Kurokawa
John Lai
Ariel Procaccia

For decades researchers have struggled with the problem of envy-free cake cutting: how to divide a divisible good between multiple agents so that each agent likes his own allocation best. Although an envy-free cake cutting protocol was ultimately devised, it is unbounded, in the sense that the number of operations can be arbitrarily large, depending on the preferences of the agents. We ask whether bounded protocols exist when the agents’ preferences are restricted. Our main result is an envy-free cake cutting protocol for agents with piecewise linear valuations, which requires a number of operations that is polynomial in natural parameters of the given instance.

PDF Details