Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Artificial Intelligence Lab Friday, January 11, 2013: Stochastic Mechanisms for Truthfulness and Budget Balance in Computational Social Choice
2 views
Skip to first unread message
wlr...@uwaterloo.ca
Nov 26, 2012, 3:59:09 PM11/26/12
to
A new Artificial Intelligence Lab event has been scheduled:
Stochastic Mechanisms for Truthfulness and Budget Balance in Computational Social Choice
In this thesis, we examine stochastic techniques for
overcoming game theoretic and computational issues in the collective
decision making process of self-interested individuals. In
particular, we examine truthful, stochastic mechanisms, for settings
with a strong budget balance constraint (there is no net flow of money
into or away from the agents). We characterize social choice
functions that are implementable in truthful mechanisms for the
setting of heterogeneous item allocation with unit demand agents, both
with and without the strong budget balance constraint. These
characterizations reveal impossibility results and poor worst-case
performance that motivates us to examine stochastic solutions. To
adequately compare stochastic mechanisms, we introduce and discuss
measures that capture the behaviour of stochastic mechanisms, based on
techniques used in stochastic algorithm design. We observe that
mechanisms can (and typically must) achieve truthfulness and strong
budget balance using one of two techniques: labelling a subset of
agents as ``auctioneers\'\' who cannot affect the outcome, but collect
any surplus; and partitioning agents into disjoint groups, such that
each partition solves a subproblem of the overall decision making
process. In addition to item allocation, we apply these techniques to
the room assignment-rent division, and public good problems.
Communication and computational complexity are two other important
concerns of computational social choice. Both the random-auctioneer
and random-partition approaches offer a flexible trade-off between low
complexity of the mechanism, and high overall outcome quality
measured, for example, by total agent utility. They enable truthful
and feasible solutions to be incrementally improved on as the
mechanism receives more information or is allowed more processing
time. Our main results are based on optimizing worst-case
performance, and we complement these results through empirical,
average-case analyses on our mechanisms.
Date: Friday, January 11, 2013
Time: 13:00
Please look on WebCalendar to view this appointment.
http://www.cs.uwaterloo.ca/odyssey/event/1632
Stochastic Mechanisms for Truthfulness and Budget Balance in Computational Social Choice
In this thesis, we examine stochastic techniques for
overcoming game theoretic and computational issues in the collective
decision making process of self-interested individuals. In
particular, we examine truthful, stochastic mechanisms, for settings
with a strong budget balance constraint (there is no net flow of money
into or away from the agents). We characterize social choice
functions that are implementable in truthful mechanisms for the
setting of heterogeneous item allocation with unit demand agents, both
with and without the strong budget balance constraint. These
characterizations reveal impossibility results and poor worst-case
performance that motivates us to examine stochastic solutions. To
adequately compare stochastic mechanisms, we introduce and discuss
measures that capture the behaviour of stochastic mechanisms, based on
techniques used in stochastic algorithm design. We observe that
mechanisms can (and typically must) achieve truthfulness and strong
budget balance using one of two techniques: labelling a subset of
agents as ``auctioneers\'\' who cannot affect the outcome, but collect
any surplus; and partitioning agents into disjoint groups, such that
each partition solves a subproblem of the overall decision making
process. In addition to item allocation, we apply these techniques to
the room assignment-rent division, and public good problems.
Communication and computational complexity are two other important
concerns of computational social choice. Both the random-auctioneer
and random-partition approaches offer a flexible trade-off between low
complexity of the mechanism, and high overall outcome quality
measured, for example, by total agent utility. They enable truthful
and feasible solutions to be incrementally improved on as the
mechanism receives more information or is allowed more processing
time. Our main results are based on optimizing worst-case
performance, and we complement these results through empirical,
average-case analyses on our mechanisms.
Date: Friday, January 11, 2013
Time: 13:00
Please look on WebCalendar to view this appointment.
http://www.cs.uwaterloo.ca/odyssey/event/1632
0 new messages