Author name cluster

Hooyeon Lee

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.

4 papers

1 author row

AAAI Conference 2017 Conference Paper

Complexity of the Stable Invitations Problem

Hooyeon Lee
Vassilevska Williams

We study the Stable Invitations Problem (SIP) in which an event organizer is to invite a subset of agents (from a group of agents) to an event, subject to certain rationality criteria. In SIP, the agents have friends, enemies, and preferences on the number of attendees at the event; an agent is willing to attend the event if all friends of the agent attend, no enemy of the agent attends, and the number of attendees is acceptable to the agent. We consider two solution concepts: (1) individual rationality (everyone who is invited is willing to attend) and (2) (Nash) stability (no agent wants to deviate from the given invitation). It is known that ﬁnding an invitation of given size for either concept is NP-complete. In this work, we study the complexity of SIP on a ﬁner scale, through the lense of parameterized complexity. For the two solution concepts and the special cases where the number of friends and/or enemies is bounded above by a constant, we show that the problems belong to different complexity classes when parameterized by the size of solutions. For instance ﬁnding an individually rational invitation of size k is W[1]-complete, yet ﬁnding a stable invitation is W[2]-complete. Moreover, when all friend and enemy relations are symmetric, ﬁnding a solution of either of the concepts becomes ﬁxed-parameter tractable unless agents have unbounded number(s) of enemies.

PDF Details

AAMAS Conference 2017 Conference Paper

Parameterized Complexity of Group Activity Selection

Hooyeon Lee
Virginia Vassilevska Williams

We consider the Group Activity Selection Problem (GASP) in which a group of agents need to be assigned to activities, subject to agent preferences and stability conditions. In GASP, the agents announce dichotomic preferences on which (activity, number-of-participant) pairs are acceptable to them. We consider five solution concepts of assignments: (1) individual rationality (everyone who is assigned to an activity is willing to participate), (2) (Nash) stability (no agent wants to deviate from the assignment), (3) envy-freeness (no agent is envious of someone else’s assignment), (4) stability and envyfreeness, and (5) perfection (everyone is assigned and willing to participate). It is known that finding an assignment of a given size with any of these properties is NP-complete. We study the complexity of GASPon a finer scale, through the lens of parameterized complexity. We show that the solution concepts above differ substantially, when parameterized by the size of the solution (the number of assigned agents or the number of used activities). In particular, finding an individually rational assignment is fixed parameter tractable, yet other solutions concepts are less tractable (W[1]- and W[2]-hard) even under very natural restrictions on inputs.

PDF

IJCAI Conference 2016 Conference Paper

Probabilistic Matrix Inspection and Group Scheduling

Hooyeon Lee
Ashish Goel

Consider an event organizer who is trying to schedule a group meeting. Availability of agents is unknown to the organizer a priori, but the organizer may have probability estimates on availability of each agent for each date/time option. The organizer can ask an agent to reveal her availability, but it causes inconvenience for the agent, and thus the organizer wishes to find an agreeable outcome at a minimum number of such queries. Motivated by this example, we study the Probabilistic Matrix Inspection problem in which we are given a matrix of Bernoulli random variables that are mutually independent, and the objective is to determine whether the matrix contains a column consisting only of 1's. We are allowed to inspect an arbitrary entry at unit cost, which reveals the realization of the entry, and we wish to find an inspection policy whose expected number of inspections is minimum. We first show that an intuitive greedy algorithm exists for 1-row and 1-column matrices, and we generalize this to design an algorithm that finds an optimal policy in polynomial time for the general case.

PDF Details

AAAI Conference 2015 Conference Paper

Stable Invitations

Hooyeon Lee
Yoav Shoham

We consider the situation in which an organizer is trying to convene an event, and needs to choose whom out of a given set of agents to invite. Agents have preferences over how many attendees should be at the event and possibly also who the attendees should be. This induces a stability requirement: All invited agents should prefer attending to not attending, and all the other agents should not regret being not invited. The organizer’s objective is to find an invitation of maximum size, subject to the stability requirement. We investigate the computational complexity of finding such an invitation when agents are truthful, as well as the mechanism design problem when agents act strategically.

PDF Details