Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximately Envy-Free Budget-Feasible Allocation
296
0
0.0
(
0
)
Added by
Xiaowei Wu
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In the budget-feasible allocation problem, a set of items with varied sizes and values are to be allocated to a group of agents. Each agent has a budget constraint on the total size of items she can receive. The goal is to compute a feasible allocation that is envy-free (EF), in which the agents do not envy each other for the items they receive, nor do they envy a charity, who is endowed with all the unallocated items. Since EF allocations barely exist even without budget constraints, we are interested in the relaxed notion of envy-freeness up to one item (EF1). The computation of both exact and approximate EF1 allocations remains largely open, despite a recent effort by Wu et al. (IJCAI 2021) in showing that any budget-feasible allocation that maximizes the Nash Social Welfare (NSW) is 1/4-approximate EF1. In this paper, we move one step forward by showing that for agents with identical additive valuations, a 1/2-approximate EF1 allocation can be computed in polynomial time. For the uniform-budget and two-agent cases, we propose efficient algorithms for computing an exact EF1 allocation. We also consider the large budget setting, i.e., when the item sizes are infinitesimal compared with the agents budgets, and show that both the NSW maximizing allocation and the allocation our polynomial-time algorithm computes have an approximation close to 1 regarding EF1.
rate research
Read More
The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. (EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up to one good (EF1). In this paper, we are interested in the fairness of the NSW in a budget-feasible allocation problem, in which each item has a cost that will be incurred to the agent it is allocated to, and each agent has a budget constraint on the total cost of items she receives. We show that a budget-feasible allocation that maximizes the NSW achieves a 1/4-approximation of EF1 and the approximation ratio is tight. The approximation ratio improves gracefully when the items have small costs compared with the agents budgets; it converges to 1/2 when the budget-cost ratio approaches infinity.
We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each sellers true cost for providing their service. These solutions predominantly take the form of randomized sealed-bid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, and thus satisfy a list of properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyers valuation function is submodular over the set of services. In addition, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior work.
Throughout the past decade, there has been an extensive research on scheduling the hospital resources such as the operation theatre(s) (OTs) and the experts (such as nurses, doctors etc.) inside the hospitals. With the technological growth, mainly advancement in communication media (such as smart phones, video conferencing, smart watches etc.) one may think of taking the expertise by the doctors (distributed around the globe) from outside the in-house hospitals. Earlier this interesting situation of hiring doctors from outside the hospitals has been studied from monetary (with patient having infinite budget) and non-monetary perspectives in strategic setting. In this paper, the more realistic situation is studied in terms of hiring the doctors from outside the hospital when a patient is constrained by budget. Our proposed mechanisms follow the two pass mechanism design framework each consisting of allocation rule and payment rule. Through simulations, we evaluate the performance and validate our proposed mechanisms.
We develop and extend a line of recent works on the design of mechanisms for heterogeneous tasks assignment problem in crowdsourcing. The budgeted market we consider consists of multiple task requesters and multiple IoT devices as task executers; where each task requester is endowed with a single distinct task along with the publicly known budget. Also, each IoT device has valuations as the cost for executing the tasks and quality, which are private. Given such scenario, the objective is to select a subset of IoT devices for each task, such that the total payment made is within the allotted quota of the budget while attaining a threshold quality. For the purpose of determining the unknown quality of the IoT devices, we have utilized the concept of peer grading. In this paper, we have carefully crafted a truthful budget feasible mechanism; namely TUBE-TAP for the problem under investigation that also allows us to have the true information about the quality of the IoT devices. The simulations are performed in order to measure the efficacy of our proposed mechanism.
We consider the problem of dividing limited resources to individuals arriving over $T$ rounds. Each round has a random number of individuals arrive, and individuals can be characterized by their type (i.e. preferences over the different resources). A standard notion of `fairness in this setting is that an allocation simultaneously satisfy envy-freeness and efficiency. The former is an individual guarantee, requiring that each agent prefers her own allocation over the allocation of any other; in contrast, efficiency is a global property, requiring that the allocations clear the available resources. For divisible resources, when the number of individuals of each type are known upfront, the above desiderata are simultaneously achievable for a large class of utility functions. However, in an online setting when the number of individuals of each type are only revealed round by round, no policy can guarantee these desiderata simultaneously, and hence the best one can do is to try and allocate so as to approximately satisfy the two properties. We show that in the online setting, the two desired properties (envy-freeness and efficiency) are in direct contention, in that any algorithm achieving additive envy-freeness up to a factor of $L_T$ necessarily suffers an efficiency loss of at least $1 / L_T$. We complement this uncertainty principle with a simple algorithm, HopeGuardrail, which allocates resources based on an adaptive threshold policy. We show that our algorithm is able to achieve any fairness-efficiency point on this frontier, and moreover, in simulation results, provides allocations close to the optimal fair solution in hindsight. This motivates its use in practical applications, as the algorithm is able to adapt to any desired fairness efficiency trade-off.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
