In this paper, we revisit the problem of fair allocation with subsidy. We first consider the allocation of m indivisible chores to n agents with additive (dis)utility functions. Under the assumption that the maximum (dis)utility of an item can be compensated by one dollar, Wu et al. (WINE 2023) showed that a total of n/4 dollars suffices to guarantee a proportional allocation by rounding fractional allocations. Their subsidy guarantee is optimal when n is even. For odd n, there is still a small gap between the upper and lower bounds for the total subsidy. In this paper, we propose a much simpler algorithm for the problem, which does not require rounding fractional allocations, and achieves an optimal subsidy guarantee for all values of n. Different from existing works, our algorithm does not require the computation and rounding of fractional allocations and admits a much simpler analysis. We further show that our algorithm and analysis framework can be extended to the mixture of (subjective) goods and chores, achieving the optimal subsidy guarantee.
论文检索
输入标题、作者或关键词，从 672 篇学术成果中精准定位
We consider the problem of fair allocation of m indivisible items to a group of n agents with subsidies (money). We address scenarios where agents have general additive cost/utility functions. Our work primarily focuses on the special case of three agents. Assuming that the maximum cost/utility of an item to an agent can be compensated by one dollar, we demonstrate that a total subsidy of 1/6 dollars is sufficient to ensure the existence of Maximin Share (MMS) allocations for both goods and chores. Additionally, we provide examples to establish the lower bounds of the required subsidies.
We study a practical centralized matching problem which assigns children to daycare centers. The collective preferences of siblings from the same family introduce complementarities, which can lead to the absence of stable matchings, as observed in the hospital-doctor matching problems involving couples. Intriguingly, stable matchings are consistently observed in real-world daycare markets, despite the prevalence of sibling applicants. We conduct a probabilistic analysis of large random markets to examine the existence of stable matchings in such markets. Specifically, we focus on scenarios where daycare centers have similar priorities over children, a common characteristic in real-world markets. Our analysis reveals that as the market size approaches infinity, the likelihood of stable matchings existing converges to 1. To facilitate our exploration, we refine an existing heuristic algorithm to address a more rigorous stability concept, as the original one may fail to meet this criterion. Through extensive experiments on both real-world and synthetic datasets, we demonstrate the effectiveness of our revised algorithm in identifying stable matchings, particularly when daycare priorities exhibit high similarity.
We study fair division of indivisible goods under the maximin share (MMS) fairness criterion in settings where agents are grouped into a small number of types, with agents within each type having identical valuations. For the special case of a single type, an exact MMS allocation is always guaranteed to exist. However, for two or more distinct agent types, exact MMS allocations do not always exist, shifting the focus to establishing the existence of approximate-MMS allocations. A series of works over the last decade has resulted in the best-known approximation guarantee of 3/4 + 3/3836. In this paper, we improve the approximation guarantees for settings where agents are grouped into two or three types, a scenario that arises in many practical settings. Specifically, we present novel algorithms that guarantee a 4/5-MMS allocation for two agent types and a 16/21-MMS allocation for three agent types. Our approach leverages the MMS partition of the majority type and adapts it to provide improved fairness guarantees for all types.
We consider a spatial voting model where both candidates and voters are positioned in the d-dimensional Euclidean space, and each voter ranks candidates based on their proximity to the voter's ideal point. We focus on the scenario where the given information about the locations of the voters' ideal points is incomplete; for each dimension, only an interval of possible values is known. In this context, we investigate the computational complexity of determining the possible winners under positional scoring rules. Our results show that the possible winner problem in one dimension is solvable in polynomial time for all k-truncated voting rules with constant k. Moreover, for some scoring rules for which the possible winner problem is NP-complete, such as approval voting for any dimension or k-approval for two or more dimensions, we give an FPT algorithm parameterized by the number of candidates. Finally, we classify tractable and intractable settings of the em weighted possible winner problem in one dimension, and resolve the computational complexity of the weighted case for all two-valued positional scoring rules when d=1.
We study a budget aggregation setting where voters express their preferred allocation of a fixed budget over a set of alternatives, and a mechanism aggregates these preferences into a single output allocation. Motivated by scenarios in which the budget is not perfectly divisible, we depart from the prevailing literature by restricting the mechanism to output allocations that assign integral amounts. This seemingly minor deviation has significant implications for the existence of truthful mechanisms. Specifically, when voters can propose fractional allocations, we demonstrate that the Gibbard-Satterthwaite theorem can be extended to our setting. In contrast, when voters are restricted to integral ballots, we identify a class of truthful mechanisms by adapting moving-phantom mechanisms to our context. Finally, we show that while a weak form of proportionality can be achieved alongside truthfulness, stronger proportionality notions derived from approval-based committee voting are incompatible with truthfulness.
We study the problem of design of strategy-proof in expectation (SP) mechanisms for facility location on a cycle, with the objective of minimizing the sum of costs of n agents. We show that there exists an SP mechanism that attains an approximation ratio of 7/4 with respect to the sum of costs of the agents, thus improving the best known upper bound of 2 - 2/n in the cases of n ≥ 5. The mechanism obtaining the bound randomizes between two mechanisms known in the literature: the Random Dictator (RD) and the Proportional Circle Distance (PCD) mechanism of Meir (2019). To prove the result, we propose a cycle-cutting technique that allows for estimating the problem on a cycle by a problem on a line.
We consider the Hospitals/Residents (HR) problem in the presence of ties in preference lists of hospitals. Among the three notions of stability, viz. weak, strong, and super stability, we focus on strong stability. Strong stability is appealing both theoretically and practically; however, its existence is not guaranteed. In this paper, our objective is to optimally augment the quotas of hospitals to ensure that a strongly stable matching exists in the modified instance. Such an augmentation is guaranteed to exist when resident preference lists are strict. We explore two natural optimization criteria: (i) minimizing the total capacity increase across all hospitals (MINSUM) and (ii) minimizing the maximum capacity increase for any hospital (MINMAX). We show that the MINSUM problem admits a polynomial-time algorithm, whereas the MINMAX problem is NP-hard. We prove an analogue of the Rural Hospitals theorem for the MINSUM problem. When each hospital incurs a cost for a unit increase in its quota, the MINSUM problem becomes NP-hard, even for 0/1 costs. In fact, we show that the problem cannot be approximated to any multiplicative factor. We also present a polynomial-time algorithm for optimal MINSUM augmentation when a specified subset of edges is required to be included in the matching.
In an approval-based committee election, the goal is to select a committee consisting of k out of m candidates, based on n voters who each approve an arbitrary number of the candidates. The core of such an election consists of all committees that satisfy a certain stability property which implies proportional representation. In particular, committees in the core cannot be "objected to" by a coalition of voters who is underrepresented. The notion of the core was proposed in 2016, but it has remained an open problem whether it is always non-empty. We prove that core committees always exist when k ≤ 8, for any number of candidates m and any number of voters n, by showing that the Proportional Approval Voting (PAV) rule, proposed by Thiele in 1895, always satisfies the core when k ≤ 7 and always selects at least one committee in the core when k = 8. We also develop an artificial rule based on recursive application of PAV, and use it to show that the core is non-empty whenever there are m ≤ 15 candidates, for any committee size k ≤ m and any number of voters n. These results are obtained with the help of computer search using linear programs.
We consider a class of jump games in which agents of different types occupy the nodes of a graph aiming to maximize the variety of types in their neighborhood. In particular, each agent derives a utility equal to the number of types different from its own in its neighborhood. We show that the jump game induced by the strategic behavior of the agents (who aim to maximize their utility) may in general have improving response cycles, but is a potential game under any of the following four conditions: there are only two types of agents; or exactly one empty node; or the graph is of degree at most 2; or the graph is 3-regular and there are two empty nodes. Additionally, we show that on trees, cylinder graphs, and tori, there is always an equilibrium. Finally, we show tight bounds on the price of anarchy with respect to two different measures of diversity: the social welfare (the total utility of the agents) and the number of colorful edges (that connect agents of different types).
We study the problem of computing an approximate Nash equilibrium of a game whose strategy space is continuous without access to gradients of the utility function. Lack of access to gradients is common in reinforcement learning settings, where the environment is treated as a black box, as well as equilibrium finding in mechanisms such as auctions, where the mechanism's payoffs are discontinuous in the players' actions. To tackle this problem, we turn to zeroth-order optimization techniques that combine pseudo-gradients with equilibrium-finding dynamics. Specifically, we introduce a new technique that requires a number of utility function evaluations per iteration that is constant rather than linear in the number of players. It achieves this by performing a single joint perturbation on all players' strategies, rather than perturbing each one individually. This is very important for many-player games, especially when the utility function is expensive to compute in terms of wall time, memory, money, or other resources. We evaluate our approach on various games, including auctions, which have important real-world applications. Our approach yields a dramatic improvement in performance in terms of the wall time required to reach an approximate Nash equilibrium.
When dividing items among agents, two of the most widely studied fairness notions are envy-freeness and proportionality. We consider a setting where m chores are allocated to n agents and the disutility of each chore for each agent is drawn from a probability distribution. We show that an envy-free allocation exists with high probability provided that m >= 2n, and moreover, m must be at least n+Theta(n) in order for the existence to hold. On the other hand, we prove that a proportional allocation is likely to exist as long as m = omega(1), and this threshold is asymptotically tight. Our results reveal a clear contrast with the allocation of goods, where a larger number of items is necessary to ensure existence for both notions.
Several resource allocation settings involve agents with unequal entitlements represented by weights. We analyze weighted fair division from an asymptotic perspective: if m items are divided among n agents whose utilities are independently sampled from a probability distribution, when is it likely that a fair allocation exist? We show that if the ratio between the weights is bounded, a weighted envy-free allocation exists with high probability provided that m = Omega(n log n / log log n), generalizing a prior unweighted result. For weighted proportionality, we establish a sharp threshold of m = n / (1 - \mu) for the transition from non-existence to existence, where \mu in (0,1) denotes the mean of the distribution. In addition, we prove that for two agents, a weighted envy-free (and weighted proportional) allocation is likely to exist if m = omega(sqrt{r}), where r denotes the ratio between the two weights.
Consider a social network where each node (user) is blue or red, corresponding to positive or negative opinion on a topic. In the voter model, in discrete time rounds, each node picks a neighbour uniformly at random and adopts its colour. Despite its significant popularity, this model does not capture some fundamental real-world characteristics such as the difference in the strengths of connections, individuals with no initial opinion, and users who are reluctant to update. To address these issues, we introduce a generalisation of the voter model. We study the problem of selecting a set of seed blue nodes to maximise the expected number of blue nodes after some rounds. We prove that the problem is NP-hard and provide a polynomial time approximation algorithm with the best possible approximation guarantee. Our experiments on real-world and synthetic graph data demonstrate that the proposed algorithm outperforms other algorithms. We also prove that the process could take an exponential number of rounds to converge. However, if we limit ourselves to strongly connected graphs, the convergence time is polynomial and the convergence period (size of the stationary configuration) is bounded by the highest common divisor of cycle lengths in the network.
Resource competition problems are often modeled using Colonel Blotto games, where players take simultaneous actions. However, many real-world scenarios involve sequential decision-making rather than simultaneous moves. To model these dynamics, we represent the Lottery Colonel Blotto game as a Stackelberg game, in which one player, the leader, commits to a strategy first, and the other player, the follower, responds. We derive the Stackelberg equilibrium for this game, formulating the leader's strategy as a bi-level optimization problem. To solve this, we develop a constructive method based on iterative game reductions, which allows us to efficiently compute the leader’s optimal commitment strategy in polynomial time. Additionally, we identify the conditions under which the Stackelberg equilibrium coincides with the Nash equilibrium. Specifically, this occurs when the budget ratio between the leader and the follower equals a certain threshold, which we can calculate in closed form. In some instances, we observe that when the leader’s budget exceeds this threshold, both players achieve higher utilities in the Stackelberg equilibrium compared to the Nash equilibrium. Lastly, we show that, in the best case, the leader can achieve an infinite utility improvement by making an optimal first move compared to the Nash equilibrium.
We consider the computation for allocations of indivisible chores that are approximately EFX and fractional Pareto optimal (fPO). It has been shown that 3-EFX and fPO allocations for bi-valued instances always exist, where the cost of an item to an agent is either 1 or k (where k > 1), by rounding the (fractional) earning restricted equilibrium. In this work, we improve the approximation ratio to (2-1/k), while preserving the fractional Pareto optimality. Instead of rounding fractional equilibrium, our algorithm starts with the integral EF1 equilibrium for bi-valued chores and reallocates items until approximate EFX is achieved. We further improve our result for the case when k=2 and devise an algorithm that computes EFX and fPO allocations.
We study the fair k-set selection problem where we aim to select k sets from a given set system such that the (weighted) occurrence times that each element appears in these k selected sets are balanced, i.e., the maximum (weighted) occurrence times are minimized. By observing that a set system can be formulated into a bipartite graph G:=(L cup R, E), our problem is equivalent to selecting k vertices from R such that the maximum (weighted) number selected neighbors of vertices in L is minimized. The problem arises in a wide range of applications in various fields, such as machine learning, artificial intelligence, and operations research. We first prove that the problem is NP-hard even if the maximum degree Delta of the input bipartite graph is 3, and the problem is in P when Delta=2. We then show that the problem is also in P when the input set system forms a laminar family. Based on intuitive linear programming, we show that two rounding algorithms achieve O(log n/(log log n))-approximation on general bipartite graphs, and an independent rounding algorithm achieves O(log(Delta))-approximation on bipartite graphs with a maximum degree Delta. We demonstrate that our analysis is almost tight by providing a hard instance for this linear programming.
We consider fairness in submodular maximization subject to a knapsack constraint, a fundamental problem with various applications in economics, machine learning, and data mining. In the model, we are given a set of ground elements, each associated with a cost and a color, and a monotone submodular function defined over them. The goal is to maximize the submodular function while guaranteeing that the total cost does not exceed a specified budget (the knapsack constraint) and that the number of elements selected for each color falls within a designated range (the fairness constraint). While there exists some recent literature on this topic, the existence of a non-trivial approximation for the problem -- without relaxing either the knapsack or fairness constraints -- remains a challenging open question. This paper makes progress in this direction. We demonstrate that when the number of colors is constant, there exists a polynomial-time algorithm that achieves a constant approximation with high probability. Additionally, we show that if either the knapsack or fairness constraint is relaxed only to require expected satisfaction, a tight approximation ratio of (1-1/e-epsilon) can be obtained in expectation for any epsilon >0.
We study an online variant of the celebrated housing market problem, where each agent owns a single house and seeks to exchange it based on her preferences. In this online setting, agents may arrive and depart at any time, meaning not all agents are present in the housing market simultaneously. We extend the well-known serial dictatorship and top trading cycle mechanisms to the online scenario, aiming to retain their desirable properties, such as Pareto efficiency, individual rationality, and strategy-proofness. These extensions also seek to prevent agents from strategically delaying their arrivals or advancing their departures. We demonstrate that achieving all these properties simultaneously is impossible and present several variants that achieve different subsets of these properties.
In a recently introduced model of successive committee elections, for a given set of ordinal or approval preferences one aims to find a sequence of a given length of “best” same-size committees such that each candidate is a member of a limited number of consecutive committees. However, the practical usability of this model remains limited, as the described task turns out to be NP-hard for most selection criteria already for seeking committees of size three. Non-trivial or somewhat efficient algorithms for these cases are lacking too. Motivated by a desire to unlock the full potential of the described temporal model of committee elections, we devise (parameterized) algorithms that effectively solve the mentioned hard cases in realistic scenarios of a moderate number of candidates or of a limited time horizon.