We study online fair division when there are a finite number of item types and the player values for the items are drawn randomly from distributions with unknown means. In this setting, a sequence of indivisible items arrives according to a random online process, and each item must be allocated to a single player. The goal is to maximize expected social welfare while maintaining that the allocation satisfies proportionality in expectation. When player values are normalized, we show that it is possible to with high probability guarantee proportionality constraint satisfaction and achieve $\tilde{O}(\sqrt{T})$ regret. To achieve this result, we present an upper confidence bound (UCB) algorithm that uses two rounds of linear optimization. This algorithm highlights fundamental aspects of proportionality constraints that allow for a UCB algorithm despite the presence of many (potentially tight) constraints. This result improves upon the previous best regret rate of $\tilde{O}(T^{2/3})$.

Improved Regret Bounds for Online Fair Division with Bandit Learning

Currently, e-commerce platforms integrate ads and organic content into a mixed list for users. While platforms seek to maximize profit from advertisers, organic items enhance user experience. To ensure long-term development, platforms aim to design mechanisms that optimize both revenue and user satisfaction. Traditional methods rank ads and organic items separately before integrating them. Even if each part is locally optimal, the combined result may not be globally optimal. Recent research has proposed inserting candidate ads into the organic list one by one. However, this approach, which constructs the final mixed result based on a sequential list, remains suboptimal. In this paper, we come up with the $\textbf{J}$oint $\textbf{INTE}$grated $\textbf{R}$egret $\textbf{Net}$work (JINTER Net). Unlike traditional methods, which pre-order ads and organic items separately, JINTER Net directly selects from the combined set of candidate ads and organic items to generate an optimal list. This approach aims to maximize both platform revenue and user experience while satisfying approximate dominant strategy incentive compatibility and individual rationality constraints. We validate the effectiveness of JINTER Net using both synthetic data and real dataset, and our experimental results show that it significantly outperforms baseline models across multiple metrics.

On Designing the Optimal Integrated Ad Auction in E-commerce Platforms

Mean field games (MFGs) tractably model behavior in large agent populations. The literature on learning MFG equilibria typically focuses on finding Nash equilibria (NE), which assume perfectly rational agents and are hence implausible in many realistic situations.
To overcome these limitations, we incorporate bounded rationality into MFGs by leveraging the well-known concept of quantal response equilibria (QRE). Two novel types of MFG QRE enable the modeling of large agent populations where individuals only noisily estimate the true objective. We also introduce a second source of bounded rationality to MFGs by restricting agents' planning horizon. The resulting novel receding horizon (RH) MFGs are combined with QRE and existing approaches to model different aspects of bounded rationality in MFGs.
We formally define MFG QRE and RH MFGs and compare them to existing equilibrium concepts such as entropy-regularized NE. Subsequently, we design generalized fixed point iteration and fictitious play algorithms to learn QRE and RH equilibria. After a theoretical analysis, we give different examples to evaluate the capabilities of our learning algorithms and outline practical differences between the equilibrium concepts.

Bounded Rationality Equilibrium Learning in Mean Field Games

This paper introduces state abstraction for two-player zero-sum Markov games (TZMGs) where the payoffs for the two players are determined by the state representing the environment and their respective actions, with state transitions following a Markov decision processes (MDPs). For example, in games like soccer, the value of actions changes according to the state of play, we should describe them as Markov games. In TZMGs, the more the number of states becomes, the more difficult computing the equilibrium becomes. Therefore, we abstract the states of TZMGs and examine the performance. State abstraction reduces the number of states by treating multiple different states as a single state, and there is a substantial body of research on finding optimal policies for Markov decision processes using state abstraction. This study extends the state abstraction for MDPs to Markov games. In this case, the game with state abstraction may yield different equilibrium solutions from those of the ground game. To evaluate the equilibrium solutions of the game with state abstraction, we derived bounds on duality gap, which represents the distance from the equilibrium solutions of the ground game. Finally, we demonstrate our state abstraction with Markov Soccer, compute equilibrium policies, and examine the results.

Approximate State Abstraction for Markov Games

Previous ad auctions predominantly relied on rule-based mechanisms, which selected winning advertisements (ads) at the ad-level and subsequently combined them into page views (PVs), leading to suboptimal allocations in multi-round auctions. This limitation stems from the significant computational burden required to design ranking score rules and select winning ad sets, as well as the inability to fully capture contextual information within PVs during ad-level selection. In this paper, we propose a key-performance-indicator (KPI) based auction mechanism that selects winning PVs at the PV-level, modeling the ad allocation as a constrained optimization problem. This approach enables us to address both short-term and long-term KPIs while leveraging the comprehensive contextual information available within PVs. Based on this framework, we design GenAuction, a generative auction mechanism utilizing a Generator-Evaluator architecture powered by Transformer algorithms. The Generator swiftly generates multiple candidate PVs, while the Evaluator selects the optimal PVs based on contextual information, adhering to the objectives and KPIs of multi-round auctions. We conduct extensive experiments using real-world data and online A/B tests to validate that GenAuction efficiently handles multi-objective allocation tasks, demonstrating its efficacy and potential for real-world application.

GenAuction: A Generative Auction for Online Advertising

Federated Learning (FL) mitigates privacy leakage in decentralized machine learning by allowing multiple clients to train collaboratively locally.  However, dynamic mobile networks with high mobility, intermittent connectivity, and bandwidth limitation severely hinder model updates to the cloud server. Although previous studies have typically addressed user mobility issue through task reassignment or predictive modeling, frequent migrations may result in high communication overhead. Addressing this challenge involves not only dealing with resource constraints, but also finding ways to mitigate the challenges posed by user migrations. We therefore propose a intertemporal incentive framework, FedCross, which ensures the continuity of FL tasks by migrating interrupted training tasks to feasible mobile devices. FedCross comprises two distinct stages: Specifically, in Stage 1, we address the task allocation problem across regions under resource constraints by employing a multi-objective migration algorithm to quantify the optimal task receivers. Moreover, we adopt evolutionary game theory to capture the dynamic decision-making of users, forecasting the evolution of user proportions across different regions to mitigate frequent migrations. In Stage 2, we utilize a procurement auction mechanism to allocate rewards among base stations, ensuring that those providing high-quality models receive optimal compensation. This approach incentivizes sustained user participation, thereby ensuring the overall feasibility of FedCross. Finally, experimental results validate the theoretical soundness of FedCross and demonstrate its significant reduction in communication overhead.

FedCross: Intertemporal Federated Learning Under Evolutionary Games

Man-made and natural disruptions such as planned constructions on roads, suspensions of bridges, and blocked roads by
trees/mudslides/floods can often create obstacles that separate two connected regions. As a result, the traveling and reachability of agents from their respective regions to other regions can be affected. To minimize the impact of the obstacles and maintain agent accessibility, we initiate the problem of constructing a new pathway (e.g., a detour or new bridge) connecting the regions disconnected by obstacles from the mechanism design perspective. In the problem, each agent in their region has a private location and is required to access the other region. The cost of an agent is the distance from their location to the other region via the pathway. Our goal is to design strategyproof mechanisms that elicit truthful locations from the agents and approximately optimize the social or maximum cost of agents by determining locations in the regions for building a pathway. We provide a characterization of all strategyproof and anonymous mechanisms. For the social and maximum costs, we provide upper and lower bounds on the approximation ratios of strategyproof mechanisms.

Mechanism Design for Connecting Regions Under Disruptions

SHAP scores represent the proposed use of the well-known Shapley values in eXplainable Artificial Intelligence (XAI). Recent work has shown that the exact computation of SHAP scores can produce unsatisfactory results. Concretely, for some ML models, SHAP scores will mislead with respect to relative feature influence. To address these limitations, recently proposed alternatives exploit different axiomatic aggregations, all of which are defined in terms of abductive explanations. However, the proposed axiomatic aggregations are not Shapley values. This paper investigates how SHAP scores can be modified so as to extend axiomatic aggregations to the case of Shapley values in XAI. More importantly, the proposed new definition of SHAP scores avoids all the known cases where unsatisfactory results have been identified. The paper also characterizes the complexity of computing the novel definition of SHAP scores, highlighting families of classifiers for which computing these scores is tractable. Furthermore, the paper proposes modifications to the existing implementations of SHAP scores. These modifications eliminate some of the known limitations of SHAP scores, and have negligible impact in terms of performance.

Towards Trustable SHAP Scores

Student placements under diversity constraints are a common practice globally. This paper addresses the selection of students by a single school under a \emph{one-to-one convention}, where students can belong to multiple types but are counted only once based on one type. While existing algorithms in both economics and computer science have been designed to help schools meet diversity goals and priorities, we show that these methods can lead to significant imbalances among students with different type combinations.

To resolve this issue, we introduce a new property called \emph{balanced representation}, which aims to ensure fair representation across all types and type combinations. We propose a novel choice function that uniquely satisfies four critical properties: maximal diversity, non-wastefulness, balanced representation, and justified envy-freeness. 
While previous work has focused on developing efficient algorithms based on ranked reservation graphs, we propose an alternative approach using flow networks. This approach allows us to formalize the problem more compactly and achieve significant improvements in computational efficiency. We then propose efficient algorithms for implementing the choice function within both the ranked reservation graph framework and the flow network framework.

Achieving Balanced Representation in School Choice with Diversity Goals

We consider a general non-stochastic online pricing bandit setting in a procurement scenario where a buyer with a budget wants to procure items from a fixed set of sellers to maximize the buyer's reward by dynamically offering purchasing prices to the sellers, where the sellers' costs and values at each time period can change arbitrarily and the sellers determine whether to accept the offered prices to sell the items. This setting models online pricing scenarios of procuring resources or services in multi-agent systems. We first consider the offline setting when sellers' costs and values are known in advance and investigate the best fixed-price policy in hindsight. We show that it has a tight approximation guarantee with respect to the offline optimal solutions. In the general online setting, we propose an online pricing policy,  Granularity-based Pricing (GAP),  which exploits underlying side-information from the feedback graph when the budget is given as the input. We show that GAP achieves an upper bound of $O(n\frac{v_{max}}{c_{min}}\sqrt{B/c_{min}}\ln B)$ on the $\alpha$-regret where $n, v_{max}, c_{min}$, and $B$ are the number, the maximum value, the minimum cost of sellers, and the budget, respectively. We then extend it to the unknown budget case by developing a variant of GAP, namely Doubling-GAP, and show its $\alpha$-regret is at most $O(n\frac{v_{max}}{c_{min}}\sqrt{B/c_{min}}\ln^2 B)$. We also provide an  $\alpha$-regret lower bound $\Omega(v_{max}\sqrt{Bn/c_{min}})$  of any online policy that is tight up to sub-linear terms. We conduct simulation experiments to show that the proposed policy outperforms the baseline algorithms.

Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback

Machine learning has grown in popularity to help assign resources and make decisions about users, which can result in discrimination. This includes hiring markets, where employers have increasingly been interested in using automated tools to help hire candidates. In response, there has been significant effort to understand and mitigate the sources of discrimination in these tools.  However, previous work has largely assumed that discrimination, in any area of ML, is the result of some initial \textit{unequal distribution of resources} across groups: One group is on average less qualified, there is less training data for one group, or the classifier is less accurate on one group, etc. However, in this work, we find that resource-symmetric agents with equal merit still experience discrimination at equilibrium. Recent work on relational equality have suggested that there are other sources of discrimination, such as inequality in social relationships, that are notably non-distributional. So, first, we show equal-merit discrimination can arise from a non-distributional source: We provide subgame perfect equilibria in a simple sequential model of a hiring market with Rubinstein-style bargaining between firms and candidates that exhibits asymmetric outcomes resulting from agents' ability to make threats during bargaining. 
Second, we show how equal-merit discrimination can arise endogenously to the learning process via convergence of a learning algorithm to asymmetric equilibria. Ultimately, this work motivates the further study of endogenous, possibly non-distributional, mechanisms of inequality in ML.

Equal Merit Does Not Imply Equality: Discrimination at Equilibrium in a Hiring Market with Symmetric Agents

Today we rely on networks that are created and maintained by smart devices. For such networks, there is no governing central authority but instead  the network structure is shaped by the decisions of selfish intelligent agents. A key property of such communication networks is that they should be easy to navigate for routing data. For this, a common approach is greedy routing, where every device simply routes data to a neighbor that is closer to the respective destination.    

Networks of intelligent agents can be analyzed via a game-theoretic approach and in the last decades many variants of network creation games have been proposed and analyzed. In this paper we present the first game-theoretic network creation model that incorporates greedy routing, i.e., the strategic agents in our model are embedded in some metric space and strive for creating a network among themselves where all-pairs greedy routing is enabled. Besides this, the agents optimize their connection quality within the created network by aiming for greedy routing paths with low stretch.

For our model, we analyze the existence of (approximate)-equilibria and the computational hardness in different underlying metric spaces. E.g., we characterize the set of equilibria in 1-2-metrics and tree metrics and show that Nash equilibria always exist. For Euclidean space, the setting which is most relevant in practice, we prove that equilibria are not guaranteed to exist but that the well-known $\Theta$-graph construction yields networks having a low stretch that are game-theoretically almost stable. For general metric spaces, we show that approximate equilibria exist where the approximation factor depends on the cost of maintaining any link.

Underline digital video library

Improved Regret Bounds for Online Fair Division with Bandit Learning

On Designing the Optimal Integrated Ad Auction in E-commerce Platforms

Bounded Rationality Equilibrium Learning in Mean Field Games

Approximate State Abstraction for Markov Games

GenAuction: A Generative Auction for Online Advertising

FedCross: Intertemporal Federated Learning Under Evolutionary Games

Mechanism Design for Connecting Regions Under Disruptions

Towards Trustable SHAP Scores

Achieving Balanced Representation in School Choice with Diversity Goals

Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback

Equal Merit Does Not Imply Equality: Discrimination at Equilibrium in a Hiring Market with Symmetric Agents

Strategic Network Creation for Enabling Greedy Routing

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES