slides - Stanford University

Stable Invitations
‘Haden’ Hooyeon Lee
Stanford University
Joint work with Yoav Shoham
Jan 29, 2015
‘Haden’ Hooyeon Lee (Stanford)
Stable Invitations
Jan 29, 2015
1 / 11
Motivation
Motivation: Group Scheduling Problems
Event organizer is trying to invite agents to social event – fundraiser.
Agents may have some constraints and preferences.
Agent may be willing to attend only if her closest friends also attend.
Another agent may be unwilling if her business competitor attends.
Agents have preferences ( ) over the number of attendees (∈ [1, n]).
Organizer wants to invite as many agents as possible subject to
Individual Rationality (IR)
Every invited agent prefers attending.
No Exclusion-regret with addition (a-ER)
No uninvited agent wishes to be added to the invitation list.
No Exclusion-regret with replacement (r-ER)
No uninvited agent wishes to replace another invited agent.
‘Haden’ Hooyeon Lee (Stanford)
Stable Invitations
Jan 29, 2015
2 / 11
Stable Invitation Problem
Anonymous Stable Invitation Problem (ASIP)
An instance of ASIP is a pair (N, P = (P1 , P2 , . . . , Pn )) where
N = {a1 , a2 , . . . , an } is a set of agents
Pi is preference ordering on outcomes, X = {1, . . . , n} ∪ {0}
x ∈ [1, n] is an outcome of attending with x attendees (including
oneself)
0 is a special outcome (an outside option) of not attending or not
invited.
An invitation S is a subset of N:
S satisfies IR (individually rationality)
if ∀ai ∈ S, |S| i 0
S satisfies a-ER (no exclusion-regret with addition)
if ∀aj ∈ S, 0 j (|S| + 1)
S is a-stable if it satisfies IR and a-ER.
‘Haden’ Hooyeon Lee (Stanford)
Stable Invitations
Jan 29, 2015
3 / 11
Stable Invitation Problem
Examples of ASIP
Example 1: Stable invitations may not exist.
P1 : 1
0
2,
P2 : 2
0
1
∅ violates ER due to a1 (1 1 0 and thus a1 wishes to be added).
{a1 } violates ER due to a2 (2 2 0 and thus a2 wishes to be added).
{a2 } violates IR due to a2 (0 2 1)
{a1 , a2 } violates IR due to a1 (0 1 2)
‘Haden’ Hooyeon Lee (Stanford)
Stable Invitations
Jan 29, 2015
4 / 11
Stable Invitation Problem
Examples of ASIP
Example 2: Stable invitations are not unique.
P1 : 1
0
2,
P2 : 1
0
2
Two stable invitations: S1 = {a1 } and S2 = {a2 }
∅ violates ER and {a1 , a2 } violates IR
‘Haden’ Hooyeon Lee (Stanford)
Stable Invitations
Jan 29, 2015
5 / 11
Stable Invitation Problem
Technical Results for ASIP
Technical Results for ASIP
Given an instance (N, P) of ASIP (and non-strategic agents),
Can we efficiently decide whether a stable invitation exists? Yes.
If yes, can we also efficiently find a maximum stable invitation? Yes.1
Given an instance (N, P) of ASIP (and strategic agents),
Can we design a non-trivial strategy-proof mechanism?
No, in general.
Yes, in special cases.
1
Also see ‘Group Activity Selection Problem’ by Darmann et al. WINE 2012.
‘Haden’ Hooyeon Lee (Stanford)
Stable Invitations
Jan 29, 2015
6 / 11
Stable Invitation Problem
Proof of Impossibility
Proof Sketch of Impossibility in Strategic Setting
Consider two agents from Example 2:
P1 : 1 0 2,
P2 : 1 0 2
There are two stable invitations: S1 = {a1 } and S2 = {a2 }.
If mechanism chooses S1 given (P1 , P2 ), then a2 has an incentive to
misreport:
If a2 reports (Pˆ2 : 1 2 0) instead of P2
Then S2 becomes the only stable invitation, given (P1 , Pˆ2 ).
If mechanism chooses S2 given (P1 , P2 ), then a1 has an incentive (by
symmetry).
No strategy-proof mechanism is able to find a stable invitation.
(Intuition?)
‘Haden’ Hooyeon Lee (Stanford)
Stable Invitations
Jan 29, 2015
7 / 11
Stable Invitation Problem
Strategy-proof Mechanism
Strategy-proof Mechanism for INC-ASIP
Agent ai is said to have an increasing preference (INC):
If ai prefers more attendees than fewer.
In other words, there is some threshold li > 0 such that
n (n − 1) · · · (li + 1) li 0 · · · .
If ai happens to prefer 0 the most, we can set li = n + 1.
In case of INC-ASIP (all agents have INC-preferences)
Simply inviting everyone (i.e., S = N) may violate IR (Why?).
Optimal, strategy-proof mechanisms exist!
Idea: Check whether stable invitation of size k exists for all k in greedy
manner.
‘Haden’ Hooyeon Lee (Stanford)
Stable Invitations
Jan 29, 2015
8 / 11
Stable Invitation Problem
Recap
Recap and Extension
Anonymous Stable Invitation Problem (ASIP):
Agents have anonymous preferences P over sizes of invitations.
Objective is to find a maximum, stable invitation (if any).
Agents may or may not act strategically.
Technical Results:
We can find a maximum stable invitation in poly-time.
Strategy-proof mechanisms cannot find a stable invitation.
Yet optimal, strategy-proof mechanisms exist in special cases such as
INC-ASIP.
General Stable Invitation Problem (GSIP)
Some agent would attend only if her closest friends also attend
Some agent would not attend if her business competitor attends
Agents have preferences ( ) over the number of attendees (∈ [1, n])
Please see paper for definitions and technical results.
‘Haden’ Hooyeon Lee (Stanford)
Stable Invitations
Jan 29, 2015
9 / 11
Stable Invitation Problem
Related Work
Related Work
Group Activity Selection Problem (GASP) [Darmann et al. (2012)]
ASIP is a special subclass of GASP (with a single activity).
Strategic agents vs. Truthful agents
Identities vs. Anonymity (in preferences)
GASP only considers a-ER (addition), but ASIP/GSIP also consider
r-ER (replacement) in addition to a-ER.
Related work in hedonic games
Hedonic Coalitions: Optimality and Stability [DG 1980]
The Stability of Hedonic Coalition Structures [BJ 2002]
Computational Complexity of Hedonic Games [Ballester 2004]
NP-hardness results for hedonic games and anonymous hedonic games
‘Haden’ Hooyeon Lee (Stanford)
Stable Invitations
Jan 29, 2015
10 / 11
Questions
Questions?
Presenter: ‘Haden’ Hooyeon Lee
Website: Google my name with ‘Stanford’ keyword.
‘Haden’ Hooyeon Lee (Stanford)
Stable Invitations
Jan 29, 2015
11 / 11

Download Report