2024-12-03 | | Total: 16
We study relationships between different relaxed notions of core stability in hedonic games, which are a class of coalition formation games. Our unified approach applies to a newly introduced family of hedonic games, called $\alpha$-hedonic games, which contains previously studied variants such as fractional and additively separable hedonic games. In particular, we derive an upper bound on the maximum factor with which a blocking coalition of a certain size can improve upon an outcome in which no deviating coalition of size at most $q$ exists. Counterintuitively, we show that larger blocking coalitions might sometimes have lower improvement factors. We discuss the tightness conditions of our bound, as well as its implications on the price of anarchy of core relaxations. Our general result has direct implications for several well-studied classes of hedonic games, allowing us to prove two open conjectures by Fanelli et al. (2021) for fractional hedonic games.
In this paper, we study the Facility Location Problem with Scarce Resources (FLPSR) under the assumption that agents' type follow a probability distribution. In the FLPSR, the objective is to identify the optimal locations for one or more capacitated facilities to maximize Social Welfare (SW), defined as the sum of the utilities of all agents. The total capacity of the facilities, however, is not enough to accommodate all the agents, who thus compete in a First-Come-First-Served game to determine whether they get accommodated and what their utility is. The main contribution of this paper ties Optimal Transport theory to the problem of determining the best truthful mechanism for the FLPSR tailored to the agents' type distributions. Owing to this connection, we identify the mechanism that maximizes the expected SW as the number of agents goes to infinity. For the case of a single facility, we show that an optimal mechanism always exists. We examine three classes of probability distributions and characterize the optimal mechanism either analytically represent the optimal mechanism or provide a routine to numerically compute it. We then extend our results to the case in which we have two capacitated facilities to place. While we initially assume that agents are independent and identically distributed, we show that our techniques are applicable to scenarios where agents are not identically distributed. Finally, we validate our findings through several numerical experiments, including: (i) deriving optimal mechanisms for the class of beta distributions, (ii) assessing the Bayesian approximation ratio of these mechanisms for small numbers of agents, and (iii) assessing how quickly the expected SW attained by the mechanism converges to its limit.
This paper explores the application of large language models (LLMs) in designing strategic mechanisms -- including auctions, contracts, and games -- for specific purposes in communication networks. Traditionally, strategic mechanism design in telecommunications has relied on human expertise to craft solutions based on game theory, auction theory, and contract theory. However, the evolving landscape of telecom networks, characterized by increasing abstraction, emerging use cases, and novel value creation opportunities, calls for more adaptive and efficient approaches. We propose leveraging LLMs to automate or semi-automate the process of strategic mechanism design, from intent specification to final formulation. This paradigm shift introduces both semi-automated and fully-automated design pipelines, raising crucial questions about faithfulness to intents, incentive compatibility, algorithmic stability, and the balance between human oversight and artificial intelligence (AI) autonomy. The paper discusses potential frameworks, such as retrieval-augmented generation (RAG)-based systems, to implement LLM-driven mechanism design in communication networks contexts. We examine key challenges, including LLM limitations in capturing domain-specific constraints, ensuring strategy proofness, and integrating with evolving telecom standards. By providing an in-depth analysis of the synergies and tensions between LLMs and strategic mechanism design within the IoT ecosystem, this work aims to stimulate discussion on the future of AI-driven information economic mechanisms in telecommunications and their potential to address complex, dynamic network management scenarios.
Traditional recommendation systems focus on maximizing user satisfaction by suggesting their favorite items. This user-centric approach may lead to unfair exposure distribution among the providers. On the contrary, a provider-centric design might become unfair to the users. Therefore, this paper proposes a re-ranking model FairSort\footnote{\textbf{Reproducibility:}The code and datasets are available at \url{https://github.com/13543024276/FairSort}} to find a trade-off solution among user-side fairness, provider-side fairness, and personalized recommendations utility. Previous works habitually treat this issue as a knapsack problem, incorporating both-side fairness as constraints. In this paper, we adopt a novel perspective, treating each recommendation list as a runway rather than a knapsack. In this perspective, each item on the runway gains a velocity and runs within a specific time, achieving re-ranking for both-side fairness. Meanwhile, we ensure the Minimum Utility Guarantee for personalized recommendations by designing a Binary Search approach. This can provide more reliable recommendations compared to the conventional greedy strategy based on the knapsack problem. We further broaden the applicability of FairSort, designing two versions for online and offline recommendation scenarios. Theoretical analysis and extensive experiments on real-world datasets indicate that FairSort can ensure more reliable personalized recommendations while considering fairness for both the provider and user.
Edge computing (EC), positioned near end devices, holds significant potential for delivering low-latency, energy-efficient, and secure services. This makes it a crucial component of the Internet of Things (IoT). However, the increasing number of IoT devices and emerging services place tremendous pressure on edge servers (ESs). To better handle dynamically arriving heterogeneous tasks, ESs and IoT devices with idle resources can collaborate in processing tasks. Considering the selfishness and heterogeneity of IoT devices and ESs, we propose an incentive-driven multi-level task allocation framework. Specifically, we categorize IoT devices into task IoT devices (TDs), which generate tasks, and auxiliary IoT devices (ADs), which have idle resources. We use a bargaining game to determine the initial offloading decision and the payment fee for each TD, as well as a double auction to incentivize ADs to participate in task processing. Additionally, we develop a priority-based inter-cell task scheduling algorithm to address the uneven distribution of user tasks across different cells. Finally, we theoretically analyze the performance of the proposed framework. Simulation results demonstrate that our proposed framework outperforms benchmark methods.
The two standard fairness notions in the resource allocation literature are proportionality and envy-freeness. If there are n agents competing for the available resources, then proportionality requires that each agent receives at least a 1/n fraction of their total value for the set of resources. On the other hand, envy-freeness requires that each agent weakly prefers the resources allocated to them over those allocated to any other agent. Each of these notions has its own benefits, but it is well known that neither one of the two is always achievable when the resources being allocated are indivisible. As a result, a lot of work has focused on satisfying fairness notions that relax either proportionality or envy-freeness. In this paper, we focus on MXS (a relaxation of proportionality) and EFL (a relaxation of envy-freeness). Each of these notions was previously shown to be achievable on its own [Barman et al.,2018, Caragiannis et al., 2023], and our main result is an algorithm that computes allocations that simultaneously satisfy both, combining the benefits of approximate proportionality and approximate envy-freeness. In fact, we prove this for any instance involving agents with valuation functions that are restricted MMS-feasible, which are more general than additive valuations. Also, since every EFL allocation directly satisfies other well-studied fairness notions like EF1, 1/2-EFX, 1/2-GMMS, and 2/3-PMMS, and every MXS allocation satisfies 4/7-MMS, the allocations returned by our algorithm simultaneously satisfy a wide variety of fairness notions and are, therefore, universally fair [Amanatidis et al., 2020].
A popular approach of automated mechanism design is to formulate a linear program (LP) whose solution gives a mechanism with desired properties. We analytically derive a class of optimal solutions for such an LP that gives mechanisms achieving standard properties of efficiency, incentive compatibility, strong budget balance (SBB), and individual rationality (IR), where SBB and IR are satisfied in expectation. Notably, our solutions are represented by an exponentially smaller number of essential variables than the original variables of LP. Our solutions, however, involve a term whose exact evaluation requires solving a certain optimization problem exponentially many times as the number of players, $N$, grows. We thus evaluate this term by modeling it as the problem of estimating the mean reward of the best arm in multi-armed bandit (MAB), propose a Probably and Approximately Correct estimator, and prove its asymptotic optimality by establishing a lower bound on its sample complexity. This MAB approach reduces the number of times the optimization problem is solved from exponential to $O(N\,\log N)$. Numerical experiments show that the proposed approach finds mechanisms that are guaranteed to achieve desired properties with high probability for environments with up to 128 players, which substantially improves upon the prior work.
We study the fair allocation of indivisible goods among a group of agents, aiming to limit the envy between any two agents. The central open problem in this literature, which has proven to be extremely challenging, is regarding the existence of an EFX allocation, i.e., an allocation such that any envy from some agent i toward another agent j would vanish if we were to remove any single good from the bundle allocated to j. When the agents' valuations are additive, which has been the main focus of prior works, Chaudhury et al. [2024] showed that an EFX allocation is guaranteed to exist for all instances involving up to three agents. Subsequently, Berger et al. [2022] extended this guarantee to nice-cancelable valuations and Akrami et al. [2023] to MMS-feasible valuations. However, the existence of EFX allocations for instances involving four agents remains open, even for additive valuations. We contribute to this literature by focusing on EF2X, a relaxation of EFX which requires that any envy toward some agent vanishes if any two of the goods allocated to that agent were to be removed. Our main result shows that EF2X allocations are guaranteed to exist for any instance with four agents, even for the class of cancelable valuations, which is more general than additive. Our proof is constructive, proposing an algorithm that computes such an allocation in pseudopolynomial time. Furthermore, for instances involving three agents we provide an algorithm that computes an EF2X allocation in polynomial time, in contrast to EFX, for which the fastest known algorithm for three agents is only pseudopolynomial.
With computing now ubiquitous across government, industry, and education, cybersecurity has become a critical component for every organization on the planet. Due to this ubiquity of computing, cyber threats have continued to grow year over year, leading to labor shortages and a skills gap in cybersecurity. As a result, many cybersecurity product vendors and security organizations have looked to artificial intelligence to shore up their defenses. This work considers how to characterize attackers and defenders in one approach to the automation of cyber defense -- the application of reinforcement learning. Specifically, we characterize the types of attackers and defenders in the sense of Bayesian games and, using reinforcement learning, derive empirical findings about how to best train agents that defend against multiple types of attackers.
This paper studies the performative policy learning problem, where agents adjust their features in response to a released policy to improve their potential outcomes, inducing an endogenous distribution shift. There has been growing interest in training machine learning models in strategic environments, including strategic classification and performative prediction. However, existing approaches often rely on restrictive parametric assumptions: micro-level utility models in strategic classification and macro-level data distribution maps in performative prediction, severely limiting scalability and generalizability. We approach this problem as a complex causal inference task, relaxing parametric assumptions on both micro-level agent behavior and macro-level data distribution. Leveraging bounded rationality, we uncover a practical low-dimensional structure in distribution shifts and construct an effective mediator in the causal path from the deployed model to the shifted data. We then propose a gradient-based policy optimization algorithm with a differentiable classifier as a substitute for the high-dimensional distribution map. Our algorithm efficiently utilizes batch feedback and limited manipulation patterns. Our approach achieves high sample efficiency compared to methods reliant on bandit feedback or zero-order optimization. We also provide theoretical guarantees for algorithmic convergence. Extensive and challenging experiments on high-dimensional settings demonstrate our method's practical efficacy.
Dynamic game theory is an increasingly popular tool for modeling multi-agent, e.g. human-robot, interactions. Game-theoretic models presume that each agent wishes to minimize a private cost function that depends on others' actions. These games typically evolve over a fixed time horizon, which specifies the degree to which all agents care about the distant future. In practical settings, however, decision-makers may vary in their degree of short-sightedness. We conjecture that quantifying and estimating each agent's short-sightedness from online data will enable safer and more efficient interactions with other agents. To this end, we frame this inference problem as an inverse dynamic game. We consider a specific parametrization of each agent's objective function that smoothly interpolates myopic and farsighted planning. Games of this form are readily transformed into parametric mixed complementarity problems; we exploit the directional differentiability of solutions to these problems with respect to their hidden parameters in order to solve for agents' short-sightedness. We conduct several experiments simulating human behavior at a real-world crosswalk. The results of these experiments clearly demonstrate that by explicitly inferring agents' short-sightedness, we can recover more accurate game-theoretic models, which ultimately allow us to make better predictions of agents' behavior. Specifically, our results show up to a 30% more accurate prediction of myopic behavior compared to the baseline.
It is well-known that Federated Learning (FL) is vulnerable to manipulated updates from clients. In this work we study the impact of data heterogeneity on clients' incentives to manipulate their updates. We formulate a game in which clients may upscale their gradient updates in order to ``steer'' the server model to their advantage. We develop a payment rule that disincentivizes sending large gradient updates, and steers the clients towards truthfully reporting their gradients. We also derive explicit bounds on the clients' payments and the convergence rate of the global model, which allows us to study the trade-off between heterogeneity, payments and convergence.
Remote estimation is a crucial element of real time monitoring of a stochastic process. While most of the existing works have concentrated on obtaining optimal sampling strategies, motivated by malicious attacks on cyber-physical systems, we model sensing under surveillance as a game between an attacker and a defender. This introduces strategic elements to conventional remote estimation problems. Additionally, inspired by increasing detection capabilities, we model an element of information leakage for each player. Parameterizing the game in terms of uncertainty on each side, information leakage, and cost of sampling, we consider the Stackelberg Equilibrium (SE) concept where one of the players acts as the leader and the other one as the follower. By focusing our attention on stationary probabilistic sampling policies, we characterize the SE of this game and provide simulations to show the efficacy of our results.
This paper characterizes extreme points of the set of incentive-compatible mechanisms for screening problems with linear utility. Extreme points are exhaustive mechanisms, meaning their menus cannot be scaled and translated to make additional feasibility constraints binding. In problems with one-dimensional types, extreme points admit a tractable description with a tight upper bound on their menu size. In problems with multi-dimensional types, every exhaustive mechanism can be transformed into an extreme point by applying an arbitrarily small perturbation. For mechanisms with a finite menu, this perturbation displaces the menu items into general position. Generic exhaustive mechanisms are extreme points with an uncountable menu. Similar results hold in applications to delegation, veto bargaining, and monopoly problems, where we consider mechanisms that are unique maximizers for specific classes of objective functionals. The proofs involve a novel connection between menus of extreme points and indecomposable convex bodies, first studied by Gale (1954).
Two-sided matching markets have demonstrated significant impact in many real-world applications, including school choice, medical residency placement, electric vehicle charging, ride sharing, and recommender systems. However, traditional models often assume that preferences are known, which is not always the case in modern markets, where preferences are unknown and must be learned. For example, a company may not know its preference over all job applicants a priori in online markets. Recent research has modeled matching markets as multi-armed bandit (MAB) problem and primarily focused on optimizing matching for one side of the market, while often resulting in a pessimal solution for the other side. In this paper, we adopt a welfarist approach for both sides of the market, focusing on two metrics: (1) Utilitarian welfare and (2) Rawlsian welfare, while maintaining market stability. For these metrics, we propose algorithms based on epoch Explore-Then-Commit (ETC) and analyze their regret bounds. Finally, we conduct simulated experiments to evaluate both welfare and market stability.
A voting rule is a Condorcet extension if it returns a candidate that beats every other candidate in pairwise majority comparisons whenever one exists. Condorcet extensions have faced criticism due to their susceptibility to variable-electorate paradoxes, especially the reinforcement paradox (Young and Levenglick, 1978) and the no-show paradox (Moulin, 1988). In this paper, we investigate the susceptibility of Condorcet extensions to these paradoxes for the case of exactly three candidates. For the reinforcement paradox, we establish that it must occur for every Condorcet extension when there are at least eight voters and demonstrate that certain refinements of maximin, a voting rule originally proposed by Condorcet (1785), are immune to this paradox when there are at most seven voters. For the no-show paradox, we prove that the only homogeneous Condorcet extensions immune to it are refinements of maximin. We also provide axiomatic characterizations of maximin and two of its refinements, Nanson's rule and leximin, highlighting their suitability for three-candidate elections.