Speakers: Michael Zuckerman, Reshef Meir, Ilan Nehama, Hebrew University
Date: Wednesday, 30 November 2011
Time: 1pm
Place: Ross 201

=======

"An NTU Cooperative Game Theoretic View of Manipulating Elections"

Speaker: Michael Zuckerman

Abstract:

Social choice theory and cooperative (coalitional) game theory have
become important foundations for the design and analysis of multiagent
systems. In this paper, we use cooperative game theory tools in order
to explore the coalition formation process in the coalitional
manipulation problem. Unlike earlier work on a
cooperative-game-theoretic approach to the manipulation problem, we
consider a model where utilities are not transferable. We investigate
the issue of stability in coalitional manipulation voting games; we
define two notions of the core in these domains, the $\alpha$-core and
the $\beta$-core. For each type of core, we investigate how hard it is
to determine whether a given candidate is in the core. We prove that
for both types of core, this determination is at least as hard as the
coalitional manipulation problem. On the other hand, we show that for
some voting rules, the $\alpha$- and the $\beta$-core problems are no
harder than the coalitional manipulation problem. We also show that
some prominent voting rules, when applied to the truthful preferences
of voters, may produce an outcome not in the core, even when the core
is not empty.

Joint work with Piotr Faliszewski, Vincent Conitzer, and Jeff Rosenschein.

=======

"Revenue Enhancement in Ad Auctions"

Speaker: Reshef Meir

Abstract:

We consider the revenue of the Generalized Second Price (GSP) auction,
which is one of the most widely used mechanisms for ad auctions. While
the standard model of ad auctions implies that the revenue of GSP in
equilibrium is at least as high as the revenue of VCG, the literature
suggests that it is not strictly higher due to the selection of a
natural equilibrium that coincides with the VCG outcome. We propose a
randomized modification of the GSP mechanism, which eliminates the
low-revenue equilibria of the GSP mechanism under some natural
restrictions. The proposed mechanism leads to a higher revenue to the
seller.

Joint work with Michal Feldman and Moshe Tennenholtz.

=========

"Approximate Judgment Aggregation"

Speaker: Ilan Nehama

Abstract:

In this work we analyze judgement aggregation problems in which a
group of agents independently votes on a set of complex propositions
that has some interdependency constraint between them (e.g.,
transitivity when describing preferences). We generalize the previous
results by studying approximate judgement aggregation. We relax the
main two constraints assumed in the current literature, Consistency
and Independence and consider mechanisms that only approximately
satisfy these constraints, that is, satisfy them up to a small portion
of the inputs. The main question we raise is whether the relaxation of
these notions significantly alters the class of satisfying aggregation
mechanisms. The recent works for preference aggregation of Kalai and
Mossel ?t into this framework. The main result of this work is that,
as in the case of preference aggregation, in the case of a subclass of
a natural class of aggregation problems termed `premise-conclusion
agendas', the set of satisfying aggregation mechanisms does not extend
non-trivially when relaxing the constraints.

=========