People care about others’ welfare to varying degrees, captured by the welfare tradeoff ratio (WTR), or the weight placed on another person’s welfare compared to one’s own. People can infer another person’s WTR toward themselves and reciprocate by adjusting their own WTR toward that person. However, the evolutionary origin of such a capacity is unclear. In games with perfect information, a heuristic strategy with tit-for-tat-like reciprocity is unbeatable, and the additional computation of inferring the opponent’s WTR confers no benefit. Here we show that in games with asymmetric information, where the actor has more accurate information about the payoff structure than the observer, the heuristic strategy is prone to errors from misperception, while reciprocity based on the inference of WTRs is robust. These findings suggest that asymmetric information about social decisions, a realistic modification to the game environment, may have contributed to the evolution of people’s understanding of others’ WTRs.


The evolution of reciprocity based on welfare tradeoff ratios in games with asymmetric information

AI systems can interact in unexpected ways, sometimes with disastrous consequences. As AI gets to control more of our world, these interactions will become more common and have higher stakes. As AI becomes more advanced, these interactions will become more sophisticated, and game theory will provide the tools for analyzing these interactions. However, AI agents are in some ways unlike the agents traditionally studied in game theory, introducing new challenges as well as opportunities. We propose a research agenda to develop the game theory of highly advanced AI agents, with a focus on achieving cooperation.

Foundations of Cooperative AI

In many applications we want to influence the decisions of independent agents by designing incentives for their actions. We revisit a fundamental problem in this area, called Game Implementation: Given a game in standard form and a set of desired strategies, can we design a set of payment promises such that, if the players take the payment promises into account, then all undominated strategies are desired? Furthermore, we aim to minimize the cost, that is, the worst-case amount of payments.

We study the tractability of computing such payment promises and determine more closely what obstructions we may have to overcome in doing so. We show that Game Implementation is NP-hard even for two players, solving in particular a long open question (Eidenbenz et al. 2011). This suggests more restrictions are necessary to obtain tractability. We thus study the regime in which players have only a small constant number of strategies and obtain the following. First, this case remains NP-hard even if each player's utility depends only on three others. Second, we repair a flawed efficient algorithm for the case of both small number of strategies and small number of players. Among further results, we characterize sets of desired strategies that can be implemented at zero cost as a kind of stable core of the game.

Game Implementation: What are the Obstructions?

Time or money? That is a question! In this paper, we consider this dilemma in the pricing regime, in which we try to find the optimal pricing scheme for identical items with heterogenous time-sensitive buyers. We characterize the revenue-optimal solution and propose an efficient algorithm to find it in a Bayesian setting. Our results also demonstrate the tight ratio between the value of wasted time and the seller's revenue, as well as that of two common-used pricing schemes, the $k$-step function and the fixed pricing. To explore the nature of the optimal scheme in the general setting, we present the closed forms over the product distribution and show by examples that positive correlation between the valuation of the item and the cost per unit time could help increase revenue. To the best of our knowledge, it is the first step towards understanding the impact of the time factor as a part of the buyer cost in pricing problems, in the computational view.

Optimal Pricing Schemes for Identical Items with Time-Sensitive Buyers

Digital advertising constitutes one of the main revenue sources for online platforms. In recent years, some advertisers tend to adopt auto-bidding tools to facilitate advertising performance optimization, making the classical \emph{utility maximizer} model in auction theory not fit well. Some recent studies proposed a new model, called \emph{value maximizer}, for auto-bidding advertisers with return-on-investment (ROI) constraints. However, the model of either utility maximizer or value maximizer could only characterize partial advertisers in real-world advertising platforms. In a mixed environment where utility maximizers and value maximizers coexist, the truthful ad auction design would be challenging since bidders could manipulate both their values and affiliated classes, leading to a multi-parameter mechanism design problem. In this work, we address this issue by proposing a payment rule which combines the corresponding ones in classical VCG and GSP mechanisms in a novel way. Based on this payment rule, we propose a truthful auction mechanism with an approximation ratio of $2$ on social welfare, which is close to the lower bound of at least $\frac{5}{4}$ that we also prove. The designed auction mechanism is a generalization of VCG for utility maximizers and GSP for value maximizers.

Utility Maximizer or Value Maximizer: Mechanism Design for Mixed Bidders in Online Advertising

Multivariate time series classiﬁcation (MTSC), one of the most fundamental time series applications, has not only gained substantial research attentions but has also emerged in many real-life applications. Recently, using transformers to solve MTSC has been reported. However, current transformer-based methods take data points of individual timestamps as inputs (timestamp-level), which only capture the temporal dependencies, not the dependencies among variables. In this
paper, we propose a novel method, called SVP-T. Specifically, we ﬁrst propose to take time series subsequences, which can be from different variables and positions (time interval), as the inputs (shape-level). The temporal and variable dependencies are both handled by capturing the long- and short-term dependencies among shapes. Second, we propose a variable-position encoding layer (VP-layer) to utilize both the variable and position information of each shape. Third, we introduce a novel VP-based (Variable-Position) self-attention mechanism to allow the enhancing the attention weights of overlapping shapes. We evaluate our method on all UEA MTS datasets. SVP-T achieves the best accuracy rank when compared with several competitive state-of-the-art methods. Furthermore, we demonstrate the effectiveness of the VP-layer and the VP-based self-attention mechanism. Finally, we present one case study to interpret the result of SVP-T. 

SVP-T: A Shape-Level Variable-Position Transformer for Multivariate Time Series Classification

Electroencephalogram (EEG) signals are effective tools towards seizure analysis where one of the most important challenges is accurate detection of seizure events and brain regions in which seizure happens or initiates. However, all existing machine learning-based algorithms for seizure analysis require access to the labeled seizure data while acquiring labeled data is very labor intensive, expensive, as well as clinicians dependent given the subjective nature of the visual qualitative interpretation of EEG signals. In this paper, we propose to detect seizure channels and clips in a self-supervised manner where no access to the seizure data is needed. The proposed method considers local structural and contextual information embedded in EEG graphs by employing positive and negative sub-graphs. We train our method through minimizing contrastive and generative losses. The employ of local EEG sub-graphs makes the algorithm an appropriate choice when accessing to the all EEG channels is impossible due to complications such as skull fractures. We conduct an extensive set of experiments on the largest seizure dataset and demonstrate that our proposed framework outperforms the state-of-the-art methods in the EEG-based seizure study. The proposed method is the only study that requires no access to the seizure data in its training phase, yet establishes a new state-of-the-art to the field, and outperforms all related supervised methods.

Self-Supervised Learning for Anomalous Channel Detection in EEG Graphs: Application to Seizure Analysis

Cake-cutting is a fundamental model of dividing a heterogeneous resource, such as land, broadcast time, and advertisement space. In this study, we consider the problem of dividing indivisible goods fairly under the connectivity constraints of a path. We prove that a connected division of indivisible items satisfying a discrete counterpart of envy-freeness, called {\em envy-freeness up to one good} (EF1), always exists for any number of agents $n$ with monotone valuations. Our result settles an open question raised by Bil\`o et al. (2019), who proved that an EF1 connected division always exists for the number of agents $n \le 4$. Moreover, the proof can be extended to show the following (1) ``secretive" and (2) ``extra" versions: (1) for $n$ agents with monotone valuations, the path can be divided into $n$ connected bundles such that an EF1 assignment of the remaining bundles can be made to the other agents for any selection made by the “secretive agent”; (2) for $n+1$ agents with monotone valuations, the path can be divided into $n$ connected bundles such that when any ``extra agent” leaves, an EF1 assignment of the bundles can be made to the remaining agents.  

How to cut a discrete cake fairly

We consider the fair division problem of indivisible items. It is well-known that an envy-free allocation may not exist, and a relaxed version of envy-freeness, envy-freeness up to one item (EF1), has been widely considered. In an EF1 allocation, an agent may envy others' allocated shares, but only up to one item. In many applications, we may wish to specify a subset of prioritized agents where strict envy-freeness needs to be guaranteed from these agents to the remaining agents, while ensuring the whole allocation is still EF1. Prioritized agents may be those agents who are envious in a previous EF1 allocation, those agents who belong to underrepresented groups, etc. Motivated by this, we propose a new fairness notion named envy-freeness with prioritized agents EFprior, and study the existence and the algorithmic aspects for the problem of computing an EFprior allocation. With additive valuations, the simple round-robin algorithm is able to compute an EFprior allocation. In this paper, we mainly focus on general valuations. In particular, we present a polynomial-time algorithm that outputs an EFprior allocation with most of the items allocated. When all the items need to be allocated, we also present polynomial-time algorithms for some well-motivated special cases.

Fair Division with Prioritized Agents

Multi-agent path planning (MAPP) is the problem of planning collision-free trajectories from start to goal locations for a team of agents. This work explores a relatively unexplored setting of MAPP where streams of agents have to go through the starts and goals with high throughput. We tackle this problem by formulating a new variant of MAPP called periodic MAPP in which the timing of agent appearances is periodic. The objective with periodic MAPP is to find a periodic plan, a set of collision-free trajectories that the agent streams can use repeatedly over periods, with periods that are as small as possible. To meet this objective, we propose a solution method that is based on constraint relaxation and optimization. We show that the periodic plans once found can be used for a more practical case in which agents in a stream can appear at random times. We confirm the effectiveness of our method compared with baseline methods in terms of throughput in several scenarios that abstract autonomous intersection management tasks.

Periodic Multi-Agent Path Planning

Predicting the trajectories of pedestrians in crowded conditions is an important task for applications like autonomous navigation systems. Previous studies have tackled this problem using two strategies. They (1) infer all future steps recursively, or (2) predict the potential destinations of pedestrians at once and interpolate the intermediate steps to arrive there. However, these strategies often suffer from the accumulated errors of the recursive inference, or restrictive assumptions about social relations in the intermediate path. In this paper, we present a graph convolutional network-based trajectory prediction. Firstly, we propose a control point prediction that divides the future path into three sections and infers the intermediate destinations of pedestrians to reduce the accumulated error. To do this, we construct multi-relational weighted graphs to account for their physical and complex social relations. We then introduce a trajectory refinement step based on a spatio-temporal and multi-relational graph. By considering the social interactions between neighbors, better prediction results are achievable. In experiments, the proposed network achieves state-of-the-art performance on various real-world trajectory prediction benchmarks.

Underline digital video library

The evolution of reciprocity based on welfare tradeoff ratios in games with asymmetric information

Foundations of Cooperative AI

Game Implementation: What are the Obstructions?

Optimal Pricing Schemes for Identical Items with Time-Sensitive Buyers

Utility Maximizer or Value Maximizer: Mechanism Design for Mixed Bidders in Online Advertising

SVP-T: A Shape-Level Variable-Position Transformer for Multivariate Time Series Classification

Self-Supervised Learning for Anomalous Channel Detection in EEG Graphs: Application to Seizure Analysis

How to cut a discrete cake fairly

Fair Division with Prioritized Agents

Periodic Multi-Agent Path Planning

A Set of Control Points Conditioned Pedestrian Trajectory Prediction

Game Implementation: What are the Obstructions?

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES