Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAssignment Mechanisms under Distributional Constraints
88
0
0.0
(
0
)
Added by
Ali Shameli
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the assignment problem of objects to agents with heterogeneous preferences under distributional constraints. Each agent is associated with a publicly known type and has a private ordinal ranking over objects. We are interested in assigning as many agents as possible. Our first contribution is a generalization of the well-known and widely used serial dictatorship. Our mechanism maintains several desirable properties of serial dictatorship, including strategyproofness, Pareto efficiency, and computational tractability while satisfying the distributional constraints with a small error. We also propose a generalization of the probabilistic serial algorithm, which finds an ordinally efficient and envy-free assignment, and also satisfies the distributional constraints with a small error. We show, however, that no ordinally efficient and envy-free mechanism is also weakly strategyproof. Both of our algorithms assign at least the same number of students as the optimum fractional assignment.
rate research
Read More
Consider an online facility assignment problem where a set of facilities $F = { f_1, f_2, f_3, cdots, f_{|F|} }$ of equal capacity $l$ is situated on a metric space and customers arrive one by one in an online manner on that space. We assign a customer $c_i$ to a facility $f_j$ before a new customer $c_{i+1}$ arrives. The cost of this assignment is the distance between $c_i$ and $f_j$. The objective of this problem is to minimize the sum of all assignment costs. Recently Ahmed et al. (TCS, 806, pp. 455-467, 2020) studied the problem where the facilities are situated on a line and computed competitive ratio of Algorithm Greedy which assigns the customer to the nearest available facility. They computed competitive ratio of algorithm named Algorithm Optimal-Fill which assigns the new customer considering optimal assignment of all previous customers. They also studied the problem where the facilities are situated on a connected unweighted graph. In this paper we first consider that $F$ is situated on the vertices of a connected unweighted grid graph $G$ of size $r times c$ and customers arrive one by one having positions on the vertices of $G$. We show that Algorithm Greedy has competitive ratio $r times c + r + c$ and Algorithm Optimal-Fill has competitive ratio $O(r times c)$. We later show that the competitive ratio of Algorithm Optimal-Fill is $2|F|$ for any arbitrary graph. Our bound is tight and better than the previous result. We also consider the facilities are distributed arbitrarily on a plane and provide an algorithm for the scenario. We also provide an algorithm that has competitive ratio $(2n-1)$. Finally, we consider a straight line metric space and show that no algorithm for the online facility assignment problem has competitive ratio less than $9.001$.
We consider a multi-round auction setting motivated by pay-per-click auctions for Internet advertising. In each round the auctioneer selects an advertiser and shows her ad, which is then either clicked or not. An advertiser derives value from clicks; the value of a click is her private information. Initially, neither the auctioneer nor the advertisers have any information about the likelihood of clicks on the advertisements. The auctioneers goal is to design a (dominant strategies) truthful mechanism that (approximately) maximizes the social welfare. If the advertisers bid their true private values, our problem is equivalent to the multi-armed bandit problem, and thus can be viewed as a strategic version of the latter. In particular, for both problems the quality of an algorithm can be characterized by regret, the difference in social welfare between the algorithm and the benchmark which always selects the same best advertisement. We investigate how the design of multi-armed bandit algorithms is affected by the restriction that the resulting mechanism must be truthful. We find that truthful mechanisms have certain strong structural properties -- essentially, they must separate exploration from exploitation -- and they incur much higher regret than the optimal multi-armed bandit algorithms. Moreover, we provide a truthful mechanism which (essentially) matches our lower bound on regret.
We study the role of interactivity in distributed statistical inference under information constraints, e.g., communication constraints and local differential privacy. We focus on the tasks of goodness-of-fit testing and estimation of discrete distributions. From prior work, these tasks are well understood under noninteractive protocols. Extending these approaches directly for interactive protocols is difficult due to correlations that can build due to interactivity; in fact, gaps can be found in prior claims of tight bounds of distribution estimation using interactive protocols. We propose a new approach to handle this correlation and establish a unified method to establish lower bounds for both tasks. As an application, we obtain optimal bounds for both estimation and testing under local differential privacy and communication constraints. We also provide an example of a natural testing problem where interactivity helps.
In this paper, we present approximation algorithms for combinatorial optimization problems under probabilistic constraints. Specifically, we focus on stochastic variants of two important combinatorial optimization problems: the k-center problem and the set cover problem, with uncertainty characterized by a probability distribution over set of points or elements to be covered. We consider these problems under adaptive and non-adaptive settings, and present efficient approximation algorithms for the case when underlying distribution is a product distribution. In contrast to the expected cost model prevalent in stochastic optimization literature, our problem definitions support restrictions on the probability distributions of the total costs, via incorporating constraints that bound the probability with which the incurred costs may exceed a given threshold.
Given a system model where machines have distinct speeds and power ratings but are otherwise compatible, we consider various problems of scheduling under resource constraints on the system which place the restriction that not all machines can be run at once. These can be power, energy, or makespan constraints on the system. Given such constraints, there are problems with divisible as well as non-divisible jobs. In the setting where there is a constraint on power, we show that the problem of minimizing makespan for a set of divisible jobs is NP-hard by reduction to the knapsack problem. We then show that scheduling to minimize energy with power constraints is also NP-hard. We then consider scheduling with energy and makespan constraints with divisible jobs and show that these can be solved in polynomial time, and the problems with non-divisible jobs are NP-hard. We give exact and approximation algorithms for these problems as required.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
