Papers

Bayesian persuasion is a model for understanding strategic information revelation: an agent with an informational advantage, called a sender, strategically discloses information by sending signals to another agent, called a receiver. In algorithmic Bayesian persuasion, we are interested in efficiently designing the sender's signaling schemes that lead the receiver to take action in favor of the sender. This paper studies algorithmic Bayesian-persuasion settings where the receiver's feasible actions are specified by combinatorial constraints, e.g., matroids or paths in graphs. We first show that constant-factor approximation is NP-hard even in some special cases of matroids or paths. We then propose a polynomial-time algorithm for general matroids by assuming the number of states of nature to be a constant. We finally consider a relaxed notion of persuasiveness, called CCE-persuasiveness, and present a sufficient condition for polynomial-time approximability.

poster session 2 @ blue 6, poster session 11 @ blue 6, oral session 11 @ blue 6, poster session 2, poster session 11, oral session 11

Counterfactual regret minimization (CFR) is the most commonly used algorithm to approximately solving two-player zero-sum imperfect-information games (IIGs). In recent years, a series of novel CFR variants such as CFR+, Linear CFR, DCFR have been proposed and have significantly improved the convergence rate of the vanilla CFR. However, most of these new variants are hand-designed by researchers through trial and error based on different motivations, which generally requires a tremendous amount of efforts and insights. This work proposes to meta-learn novel CFR algorithms through evolution to ease the burden of manual algorithm design. We first design a search language that is rich enough to represent many existing hand-designed CFR variants. We then exploit a scalable regularized evolution algorithm with a bag of acceleration techniques to efficiently search over the combinatorial space of algorithms defined by this language. The learned novel CFR algorithm can generalize to new IIGs not seen during training and performs on par with or better than existing state-of-the-art CFR variants.

poster session 2 @ blue 6, poster session 11 @ blue 6, oral session 11 @ blue 6, poster session 2, poster session 11, oral session 11

Epistemic social choice aims at unveiling a hidden ground truth given votes, which are interpreted as noisy signals about it. We consider here a simple setting where votes consist of approval ballots: each voter approves a set of alternatives which they believe can possibly be the ground truth. Based on the intuitive idea that more reliable votes contain fewer alternatives, we define several noise models that are approval voting variants of the Mallows model. The likelihood-maximizing alternative is then characterized as the winner of a weighted approval rule, where the weight of a ballot decreases with its cardinality. We have conducted an experiment on three image annotation datasets; they conclude that rules based on our noise model outperform standard approval voting; the best performance is obtained by a variant of the Condorcet noise model.

poster session 2 @ blue 6, poster session 11 @ blue 6, poster session 2, poster session 11

We study online task assignment problem with reusable resources, motivated by practical applications such as ridesharing, crowdsourcing and job hiring. In the problem, we are given a set of offline vertices~(agents), and, at each time, an online vertex~(task) arrives randomly according to a known time-dependent distribution. Upon arrival, we assign the task to agents immediately and irrevocably. The goal of the problem is to maximize the expected total profit produced by completed tasks. The key features of our problem are (1) an agent is reusable, i.e., an agent comes back to the market after completing the assigned task, (2) an agent may reject the assigned task to stay the market, and (3) a task may accommodate multiple agents. The setting generalizes that of existing work in which an online task is assigned to one agent under (1). In this paper, we propose an online algorithm that is $1/2$-competitive for the above setting, which is tight. Moreover, when each agent can reject assigned tasks at most $\Delta$ times, the algorithm is shown to have the competitive ratio $\Delta/(3\Delta-1)\geq 1/3$. We also evaluate our proposed algorithm with numerical experiments.

poster session 2 @ blue 6, poster session 11 @ blue 6, oral session 2 @ blue 6, poster session 2, poster session 11, oral session 2

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

We study the additive distortion of social choice functions in the implicit utilitarian model, and argue that it is a more appropriate metric than multiplicative distortion when an alternative that confers significant social welfare may exist (i.e., when the stakes are high). We define a randomized analog of positional scoring rules, and present a rule which is asymptotically optimal within this class as the number of alternatives increases. We then show that the instance-optimal social choice function can be efficiently computed. Next, we take a beyond-worst-case view, bounding the additive distortion of prominent voting rules as a function of the best welfare attainable in an instance. Lastly, we evaluate the additive distortion of a range of rules on real-world election data.

poster session 2 @ blue 6, poster session 11 @ blue 6, poster session 2, poster session 11

Mathematical knots are interesting topological objects. Using simple arcs, lines, and crossings drawn on eleven possible tiles, knot mosaics are a representation of knots on a mosaic board. Our contribution is using SAT solvers as a tool for enumerating nontrivial knot mosaics. By encoding constraints for local knot mosaic properties, we computationally reduce the search space by factors of up to 6600. Our future research directions include encoding constraints for global properties and using parallel SAT techniques to attack larger boards.

poster session 2 @ blue 6, poster session 11 @ blue 6, poster session 2, poster session 11

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

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

Jan-ken, a.k.a. rock-paper-scissors, is a cerebrated example of a non-transitive game with three (pure) strategies, rock, paper and scissors. Interestingly, any Jan-ken generalized to four strategies contains at least one useless strategy unless it allows a tie between distinct pure strategies. Non-transitive dice could be a stochastic analogue of Jan-ken: the stochastic transitivity does not hold on some sets of dice, e.g., Efron's dice. Including the non-transitive dice, this paper is interested in dice sets which do not contain a useless die. In particular, we are concerned with the existence of a strongest (or weakest, symmetrically) die in a dice set under the two conditions that (1) any number appears on at most one die and at most one side, i.e., no tie break between two distinct dice, and (2) the mean pips of dice are the same. We firstly prove that a strongest die never exist if a set of n dice of m-sided is given as a partition of the set of numbers {1,…,mn}. Next, we show some sufficient conditions that a strongest die exists in a dice set which is not a partition of a set of numbers. We also give some algorithms to find a strongest die in a dice set which includes given dice.

poster session 2 @ blue 6, poster session 11 @ blue 6, poster session 2, poster session 11

The classic secretary problem concerns the problem of an employer facing a random sequence of candidates and making online hiring decisions to try to hire the best candidate. In this paper, we study a game-theoretic generalization of the secretary problem where a set of employers compete with each other to hire the best candidate. Different from previous secretary market models, our model assumes that the sequence of candidates arriving at each employer is uniformly random but independent from other sequences. We consider two versions of this secretary game where employers can have adaptive or non-adaptive strategies, and provide characterizations of the best response and Nash equilibrium of each game.

poster session 2 @ blue 6, poster session 11 @ blue 6, oral session 11 @ blue 6, poster session 2, poster session 11, oral session 11

Gerrymandering is the manipulating of redistricting for political gain. While many attempts to formalize and model gerrymandering have been made, the assumption of known voter preference, or perfect information, limits the applicability of these works to model real world scenarios. To more accurately reason about gerrymandering we investigate how to adapt existing models of the problem to work with imperfect information. In our work, we formalize a definition of the gerrymandering problem under probabilistic voter preferences, reason about its complexity compared to the deterministic version, and propose a greedy algorithm to approximate the problem in polynomial time under certain conditions.

poster session 2 @ blue 6, poster session 11 @ blue 6, poster session 2, poster session 11

The classic cake cutting problem concerns the fair allocation of a heterogeneous resource among interested agents. In this paper, we study a public goods variant of the problem, where instead of competing with one another for the cake, the agents all share the same subset of the cake which must be chosen subject to a length constraint. We focus on the design of truthful and fair mechanisms in the presence of strategic agents who have piecewise uniform utilities over the cake. On the one hand, we show that the leximin solution is truthful and moreover maximizes an egalitarian welfare measure among all truthful and position oblivious mechanisms. On the other hand, we demonstrate that the maximum Nash welfare solution is truthful for two agents but not in general. Our results assume that mechanisms can block each agent from accessing parts that the agent does not claim to desire; we provide an impossibility result when blocking is not allowed.

poster session 2 @ blue 6, poster session 11 @ blue 6, oral session 2 @ blue 6, poster session 2, poster session 11, oral 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

We study multi-unit auctions in social networks, where each buyer has a fixed budget and can spread the sale information to the network neighbors. We design a mechanism encouraging buyers to report their valuations truthfully and spread the sale information. Our design uses the idea of the clinching mechanism to decide the transaction price and can be viewed as a network version of the mechanism. Most of the previous clinching mechanisms search for the transaction prices by increasing the current price. Our mechanism directly computes the transaction prices in polynomial time. Furthermore, the mechanism applies a technique to iteratively activate new buyers in the network. This ensures utility preservations of the buyers and benefits the seller. We prove key properties of our mechanism, such as no-positive-transfers, individual rationality, incentive compatibility, non-wastefulness and social welfare preservation.

poster session 2 @ blue 6, poster session 11 @ blue 6, oral session 2 @ blue 6, poster session 2, poster session 11, oral session 2