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 finding an invitation of given size for either concept is NP-complete. In this work, we study the complexity of SIP on a finer 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 finding an individually rational invitation of size k is W[1]-complete, yet finding a stable invitation is W[2]-complete.Moreover, when all friend and enemy relations are symmetric, finding a solution of either of the concepts becomes fixed-parameter tractable unless agents have unbounded number(s) of enemies.

We consider the situation in which an organizer is trying to convenean 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 eventand possibly also who the attendees should be.This induces a stability requirement: All invited agents should preferattending to not attending, and all the other agents should not regretbeing 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.

We study the complexity of the maximum coverage problem, restricted to set systems of bounded VC-dimension. Our main result is a fixed-parameter tractable approximation scheme: an algorithm that outputs a (1-ε)-approximation to the maximum-cardinality union of k sets, in running time $O(f(ε,k,d)⋅ poly(n)) where n is the problem size, d is the VC-dimension of the set system, and f(ε,k,d) is exponential in (kd/ε)c for some constant c. We complement this positive result by showing that the function f(ε,k,d) in the running-time bound cannot be replaced by a function depending only on (ε,d) or on (k,d), under standard complexity assumptions. We also present an improved upper bound on the approximation ratio of the greedy algorithm in special cases of the problem, including when the sets have bounded cardinality and when they are two-dimensional halfspaces. Complementing these positive results, we show that when the sets are four-dimensional halfspaces neither the greedy algorithm nor local search is capable of improving the worst-case approximation ratio of 1-1/e that the greedy algorithm achieves on arbitrary instances of maximum coverage.

We propose to demonstrate SGL, a language and system for writing computer games using data management techniques. We will demonstrate a complete game built using the system, and show how complex game behavior can be expressed in a declarative scripting language. The demo will also illustrate the workflow necessary to modify a game and include a visualization of the relational operations that are executed as the game runs.