Papers

A recent report of Littmann [Commun. ACM '21] outlines the existence and the fatal impact of collusion rings in academic peer reviewing. We introduce and analyze the problem Cycle-Free Reviewing that aims at finding a review assignment without the following kind of collusion ring: A sequence of reviewers each reviewing a paper authored by the next reviewer in the sequence (with the last reviewer reviewing a paper of the first), thus creating a review cycle where each reviewer gives favorable reviews. As a result, all papers in that cycle have a high chance of acceptance independent of their respective scientific merit. We observe that review assignments computed using a standard Linear Programming approach typically admit many short review cycles. On the negative side, we show that Cycle-Free Reviewing is NP-hard in various restricted cases (i.e., when every author is qualified to review all papers and one wants to prevent that authors review each other's or their own papers or when every author has only one paper and is only qualified to review few papers). On the positive side, among others, we show that, in some realistic settings, an assignment without any review cycles of small length always exists. This result also gives rise to an efficient heuristic for computing (weighted) cycle-free review assignments, which we show to be of excellent quality in practice.

poster session 1 @ blue 6, poster session 12 @ blue 6, poster session 1, poster session 12

Artificial Intelligence has aimed to give the systems or agents, the ability to learn, perceive, recognize, plan, reason and act. Affective Computing has brought into focus the importance of giving AI systems, the capability to perceive, detect, utilize and generate emotion, affect, sentiment or feelings. To have a meaningful human-computer interaction, we need to design and develop a more socially intelligent and affective AI. My doctoral research goal is to delve deeper into some of these aspects, firstly by surveying computational models implemented in AI that uses emotion in decision-making or behaviour; secondly, by creating new model to predict social event context and affect in group videos; thirdly, to predict the social identities in visual scenes; and lastly to combine information about context, identities, behaviour and emotion in a social interaction scene to predict social incoherence and to recommend appropriate behaviour.

poster session 1 @ blue 6, poster session 2 @ blue 6, poster session 1, poster session 2

Correlated Equilibrium is a solution concept that is more general than Nash Equilibrium (NE) and can lead to outcomes with better social welfare. However, its natural extension to the sequential setting, the Extensive Form Correlated Equilibrium (EFCE), requires a quadratic amount of space to solve, even in restricted settings without randomness in nature. To alleviate these concerns, we apply subgame resolving, a technique extremely successful in finding NE in zero-sum games to solving general-sum EFCEs. Subgame resolving refines a correlation plan in an online manner: instead of solving for the full game upfront, it only solves for strategies in subgames that are reached in actual play, resulting in significant computational gains. In this paper, we (i) lay out the foundations to quantify the quality of a refined strategy, in terms of the social welfare and exploitability of correlation plans, (ii) show that EFCEs possess a sufficient amount of independence between subgames to perform resolving efficiently, and (iii) provide two algorithms for resolving, one using linear programming and the other based on regret minimization. Both methods guarantee safety, i.e., they will never be counterproductive. Our methods are the first time an online method has been applied to the correlated, general-sum setting.

poster session 1 @ blue 6, poster session 12 @ blue 6, oral session 12 @ blue 6, poster session 1, poster session 12, oral session 12

We study fair and efficient allocation of divisible goods, in an online manner, among n agents. The goods arrive online in a sequence of T time periods. The agents' values for a good are revealed only after its arrival, and the online algorithm needs to fractionally allocate the good, immediately and irrevocably, among the agents. Towards a unifying treatment of fairness and economic efficiency objectives, we develop an algorithmic framework for finding online allocations to maximize the generalized mean of the values received by the agents. In particular, working with the assumption that each agent's value for the grand bundle of goods is appropriately scaled, we address online maximization of p-mean welfare. Parameterized by an exponent term p in (-infinity, 1], these means encapsulate a range of welfare functions, including social welfare (p=1), egalitarian welfare (p to -infinity), and Nash social welfare (p to 0). We present a simple algorithmic template that takes a threshold as input and, with judicious choices for this threshold, leads to both universal and tailored competitive guarantees. First, we show that one can compute online a single allocation that O (n^{1/2} log n)-approximates the optimal p-mean welfare for all p<=1. The existence of such a universal allocation is interesting in and of itself. Moreover, this universal guarantee achieves essentially tight competitive ratios for specific values of p. Next, we obtain improved competitive ratios for different ranges of p by executing our algorithm with p-specific thresholds, e.g., we provide O(log^3 n)-competitive ratio for all p in (-1/log 2n, 1). We complement our positive results by establishing lower bounds to show that our guarantees are essentially tight for a wide range of the exponent parameter.

poster session 1 @ blue 6, poster session 12 @ blue 6, oral session 1 @ blue 6, poster session 1, poster session 12, oral session 1

We study a multi-leader single-follower congestion game where multiple users (leaders) choose one resource out of a set of resources and, after observing the realized loads, an adversary (single-follower) attacks the resources with maximum loads causing additional costs for the leaders. For the resulting strategic game among the leaders, we show that pure Nash equilibria fail to exist and therefore, we consider approximate equilibria instead. As our first main result, we show that the existence of a K-approximate equilibrium can always be guaranteed, where K (approximately equal to 1.1974) is the unique solution of a cubic polynomial equation. To this end, we give a polynomial time combinatorial algorithm which computes a K-approximate equilibrium. The factor K is tight, meaning that there is an instance that does not admit an A-approximate equilibrium for any A < K. Thus A = K is the smallest possible value of A such that the existence of an A-approximate equilibrium can be guaranteed for any instance of the considered game. Secondly, we focus on approximate equilibria of a given fixed instance. We show how to compute efficiently a best approximate equilibrium, that is, with smallest possible A among all A-approximate equilibria of the given instance.

poster session 1 @ blue 6, poster session 12 @ blue 6, oral session 12 @ blue 6, poster session 1, poster session 12, oral session 12

My dissertation investigates the computation of Bayes-Nash equilibria in auctions via multiagent learning. A particular focus lies on the game-theoretic analysis of learned gradient dynamics in such markets. This requires overcoming several technical challenges like non-differentiable utility functions and infinite-dimensional strategy spaces. Positive results may open the door for wide-ranging applications in Market Design and the economic sciences.

poster session 3 @ blue 6, poster session 1 @ blue 6, poster session 3, poster session 1

We consider the problem of maximizing the Nash social welfare when allocating a set $\calG$ of indivisible goods to a set $\calN$ of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent $i \in \calN$ for every good $j \in \calG$ is $v_{ij} \in \{p,q\}$, for $p,q \in \NN$, $p \le q$. In this work, we design an algorithm to compute an optimal allocation in polynomial time if $p$ divides $q$, i.e., when $p=1$ and $q \in \NN$ after appropriate scaling. The problem is \classNP-hard whenever $p$ and $q$ are coprime and $p \ge 3$. In terms of approximation, we present positive and negative results for general $p$ and $q$. We show that our algorithm obtains an approximation ratio of at most 1.0345. Moreover, we prove that the problem is \classAPX-hard, with a lower bound of $1.000015$ achieved at $p/q = 4/5$.

poster session 1 @ blue 6, poster session 12 @ blue 6, oral session 12 @ blue 6, poster session 1, poster session 12, oral session 12

My work studies the problem of generating scenarios to evaluate interaction between humans and robots. I expect these interactions to grow in complexity as robots become more intelligent and enter our daily lives. However, evaluating such interactions only through user studies, which are the de facto evaluation method in human-robot interaction, will quickly become infeasible as the number of possible scenarios grows exponentially with scenario complexity. Therefore, I propose automatically generating scenarios in simulation to explore the diverse possibility space of scenarios to better understand interaction and avoid costly failures in real world settings.

poster session 1 @ blue 6, poster session 2 @ blue 6, poster session 1, poster session 2

The entertainment industry, as well as the field of Computer Graphics, frequently faces the issue of creating large virtual crowds that would populate a scene. One of the ways to achieve that, particularly with modern rendering techniques, is by using simulation -- this, however, is nontrivial to design and control. The main goal of my PhD work is working towards the creation of a tool enabling the creation of virtual crowds that one can interact with, and we believe the best way to that is through Multiagent Reinforcement Learning techniques. These animated crowds can then be used both in movies and video games. Especially for the latter, it is highly desirable that both the crowd as a whole, as well as the individual characters, can react to the user's input in real time.

poster session 3 @ blue 6, poster session 1 @ blue 6, poster session 3, poster session 1

In hedonic games, a set of $n$ agents, having preferences over all possible coalition structures, needs to agree on a stable outcome. In this work, we initiate the study of hedonic games with fixed-size coalitions, where the set of possible coalition structures is restricted as follows: there are $k$ coalitions, each coalition has a fixed size, and the sum of the sizes of all coalitions equals $n$. We focus on the basic model of additively separable hedonic games with symmetric preferences, where an agent's preference is captured by a utility function which sums up a contribution due to any other agent in the same coalition. In this setting, an outcome is stable if no pair of agents can exchange coalitions and improve their utilities. Conditioned on the definition of improvement, three stability notions arise: {\em swap stability under transferable utilities}, which requires to improve the sum of the utilities of both agents, {\em swap stability}, which requires to improve the utility of one agent without decreasing the utility of the other one, and {\em strict swap stability}, requiring to improve the utilities of both agents simultaneously. We analyse the fundamental questions of existence, complexity and efficiency of stable outcomes, and that of complexity of a social optimum.

poster session 1 @ blue 6, poster session 12 @ blue 6, poster session 1, poster session 12

We consider a setting where a large number of agents are all interested in attending some public resource of limited capacity. Attendance is thus allotted by lottery. If agents arrive individually, then randomly choosing the agents – one by one - is a natural, fair and efficient solution. We consider the case where agents are organized in groups (e.g. families, friends), the members of each of which must all be admitted together. We study the question of how best to design such lotteries. We first establish the desired properties of such lotteries, in terms of fairness and efficiency, and define the appropriate notions of strategy proofness (providing that agents cannot gain by misrepresenting the true groups, e.g. joining or splitting groups). We establish inter-relationships between the different properties, proving properties that cannot be fulfilled simultaneously (e.g. leximin optimality and strong group stratagy proofness). Our main contribution is a polynomial mechanism for the problem, which guarantees many of the desired properties, including: leximin optimality, Pareto-optimality, anonymity, group strategy proofness, and adjunctive strategy proofness (which provides that no benefit can be obtained by registering additional - uninterested or bogus - individuals). The mechanism approximates the utilitarian optimum to within a factor of 2, which, we prove, is optimal for any mechanism that guarantees any one of the following properties: egalitarian welfare optimality, leximin optimality, envyfreeness, and adjunctive strategy proofness.

poster session 1 @ blue 6, poster session 12 @ blue 6, poster session 1, poster session 12

We study a dynamic traffic assignment model, where agents base their instantaneous routing decisions on real-time delay predictions. We formulate a mathematically concise model and derive properties of the predictors that ensure a dynamic prediction equilibrium exists. We demonstrate the versatility of our framework by showing that it subsumes the well-known full information and instantaneous information models, in addition to admitting further realistic predictors as special cases. We complement our theoretical analysis by an experimental study, in which we systematically compare the induced average travel times of different predictors, including a machine-learning model trained on data gained from previously computed equilibrium flows, both on a synthetic and a real road network.

poster session 1 @ blue 6, poster session 12 @ blue 6, poster session 1, poster session 12

We study a participatory budgeting problem, where a set of strategic agents wish to split a divisible budget among different projects, by aggregating their proposals on a single division. Unfortunately, the straight-forward rule that divides the budget proportionally is susceptible to manipulation. In a recent work, (Freeman et al.,2021) proposed a class of truthful mechanisms, called moving phantom mechanisms. Among others, they propose a proportional mechanism, in the sense that in the extreme case where all agents prefer a single project to receive the whole amount, the budget is assigned proportionally. While proportionality is a naturally desired property, it is defined over a limited type of preference profiles. To address this, we expand the notion of proportionality, by proposing a quantitative framework which evaluates a budget aggregation mechanism according to its worst-case distance from the proportional allocation. Crucially, this is defined for every preference profile. We study this measure on the class of moving phantom mechanisms, and we provide approximation guarantees. For two projects, we show that the Uniform Phantom mechanism is the optimal among all truthful mechanisms. For three projects, we propose a new, proportional mechanism which is optimal among all moving phantom mechanisms. Finally, we provide impossibility results regarding the approximability of moving phantom mechanisms.

poster session 1 @ blue 6, poster session 12 @ blue 6, poster session 1, poster session 12

We study the problem of allocating indivisible goods among strategic agents. We focus on settings wherein monetary transfers are not available and each agent's private valuation is a submodular function with binary marginals, i.e., the agents' valuations are matroid-rank functions. In this setup, we establish a notable dichotomy between two of the most well-studied fairness notions in discrete fair division; specifically, between envy-freeness up to one good (EF1) and maximin shares (MMS). First, we show that a Pareto-efficient mechanism of Babaioff et al. (2021) is group strategy-proof for finding EF1 allocations, under matroid-rank valuations. The group strategy-proofness guarantee strengthens the result of Babaioff et al. (2021), that establishes truthfulness (individually for each agent) in the same context. Our result also generalizes a work of Halpern et al. (2020), from binary additive valuations to the matroid-rank case. Next, we establish that an analogous positive result cannot be achieved for MMS, even when considering truthfulness on an individual level. Specifically, we prove that, for matroid-rank valuations, there does not exist a truthful mechanism that is index oblivious, Pareto efficient, and maximin fair. For establishing our results, we develop a characterization of truthful mechanisms for matroid-rank functions. This characterization in fact holds for a broader class of valuations (specifically, holds for binary XOS functions) and might be of independent interest.

poster session 1 @ blue 6, poster session 12 @ blue 6, oral session 1 @ blue 6, poster session 1, poster session 12, oral session 1

We study the computational complexity of computing solutions for the straight-cut and square-cut pizza sharing problems. We show that finding an approximate solution is PPA-hard for the straight-cut problem, and PPA-complete for the square-cut problem, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. Our PPA-hardness results apply even when all mass distributions are unions of non-overlapping squares, and our FIXP-hardness result applies even when all mass distributions are unions of weighted squares and right-angled triangles. We also prove that decision variants of the square-cut problem are hard: the approximate problem is NP-complete, and the exact problem is ETR-complete.

poster session 1 @ blue 6, poster session 12 @ blue 6, poster session 1, poster session 12

We initiate the study of the heterogeneous facility location problem with limited resources. We mainly focus on the fundamental case where a set of agents are positioned in the line segment $[0,1]$ and have approval preferences over two available facilities. A mechanism takes as input the positions and the preferences of the agents, and chooses to locate a single facility based on this information. We study mechanisms that aim to maximize the social welfare (the total utility the agents derive from facilities they approve), under the constraint of incentivizing the agents to truthfully report their positions and preferences. We consider three different settings depending on the level of agent-related information that is public or private. For each setting, we design deterministic and randomized strategyproof mechanisms that achieve a good approximation of the optimal social welfare, and complement these with nearly-tight impossibility results.

poster session 1 @ blue 6, poster session 12 @ blue 6, poster session 1, poster session 12

In this work, we study the maximin share fairness notion for allocation of indivisible goods in the subadditive and fractionally subadditive settings. While previous work refutes the possibility of obtaining an allocation which is better than $1/2$-\textsf{MMS}, the only positive result for the subadditive setting states that when the number of items is equal to $m$, there always exists an $\Omega(1/\log m)$-\textsf{MMS} allocation. Since the number of items may be larger than the number of agents ($n$), such a bound can only imply a weak bound of $\Omega(\frac{1}{n \log n})$-\textsf{MMS} allocation in general. In this work, we improve this gap exponentially to an $\Omega(\frac{1}{\log n \log \log n})$-\textsf{MMS} guarantee. In addition to this, we prove that when the valuation functions are fractionally subadditive, a $1/4.6$-\textsf{MMS} allocation is guaranteed to exist. This also improves upon the previous bound of $1/5$-\textsf{MMS} guarantee for the fractionally subadditive setting.

poster session 1 @ blue 6, poster session 12 @ blue 6, poster session 1, poster session 12

Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where a resource may be shared by two neighbors in a social network and each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and tree-like (hierarchical) social networks.

poster session 1 @ blue 6, poster session 12 @ blue 6, oral session 1 @ blue 6, poster session 1, poster session 12, oral session 1

My PhD research focus is to produce a critical review of literature in Algorithmic Impact Assessment (AIA) and to develop an AIA tool that can be used to evaluate potential unintended impact of AI systems.

poster session 3 @ blue 6, poster session 1 @ blue 6, poster session 3, poster session 1

Broadly speaking, I hope to dedicate my PhD to improving our understanding of algorithmic economics with the ultimate goal of building welfare improving decentralized technology for markets. In the following pages, I describe how my past work has built on the existing literature to get closer to the goal of creating such technologies, and describe what research paths this work opens up for the rest of my PhD. I believe that my research has the potential to provide algorithmic solutions to problems in machine learning, optimization, and game theory, and can be used to improve the efficiency of online marketplaces.

poster session 1 @ blue 6, poster session 2 @ blue 6, poster session 1, poster session 2

Collaborative robots (i.e., "cobots") and machine learning-based virtual agents are increasingly entering the human workspace with the aim of increasing productivity, enhancing safety, and improving the quality of our lives. These agents will dynamically interact with a wide variety of people in dynamic and novel contexts, increasing the prevalence of human-machine teams in healthcare, manufacturing, and search-and-rescue. In this research, we enhance the mutual understanding within a human-machine team by enabling cobots to understand heterogeneous teammates via person-specific embeddings, identifying contexts in which xAI methods can help improve team mental model alignment, and enabling cobots to effectively communicate information that supports high-performance human-machine teaming.

poster session 1 @ blue 6, poster session 2 @ blue 6, poster session 1, poster session 2

In recent times, the social credit systems (SCS) and similar AI-driven mass surveillance systems have been deployed by the Chinese government in various regions. However, the discussions around the SCS are ambiguous: some people call them very controversial and a breach of human rights, while other people say that the SCS are very similar in structure to the company rankings or background checks on individuals in the United States. In reality, though, there is no monolith and there are different forms of SCS deployed in different regions of China. In this paper, I review the different models of the Chinese SCS. Then, I compare how the different systems are upholding or breaching China’s own AI Ethics guidelines.

poster session 3 @ blue 6, poster session 1 @ blue 6, poster session 3, poster session 1