Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFurther Results on Stability-Preserving Mechanisms for School Choice
292
0
0.0
(
0
)
Added by
James Liu
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We build on the stability-preserving school choice model introduced and studied recently in [MV18]. We settle several of their open problems and we define and solve a couple of new ones.
rate research
Read More
We address the following dynamic version of the school choice question: a city, named City, admits students in two temporally-separated rounds, denoted $mathcal{R}_1$ and $mathcal{R}_2$. In round $mathcal{R}_1$, the capacity of each school is fixed and mechanism $mathcal{M}_1$ finds a student optimal stable matching. In round $mathcal{R}_2$, certain parameters change, e.g., new students move into the City or the City is happy to allocate extra seats to specific schools. We study a number of Settings of this kind and give polynomial time algorithms for obtaining a stable matching for the new situations. It is well established that switching the school of a student midway, unsynchronized with her classmates, can cause traumatic effects. This fact guides us to two types of results, the first simply disallows any re-allocations in round $mathcal{R}_2$, and the second asks for a stable matching that minimizes the number of re-allocations. For the latter, we prove that the stable matchings which minimize the number of re-allocations form a sublattice of the lattice of stable matchings. Observations about incentive compatibility are woven into these results. We also give a third type of results, namely proofs of NP-hardness for a mechanism for round $mathcal{R}_2$ under certain settings.
We study social choice mechanisms in an implicit utilitarian framework with a metric constraint, where the goal is to minimize textit{Distortion}, the worst case social cost of an ordinal mechanism relative to underlying cardinal utilities. We consider two additional desiderata: Constant sample complexity and Squared Distortion. Constant sample complexity means that the mechanism (potentially randomized) only uses a constant number of ordinal queries regardless of the number of voters and alternatives. Squared Distortion is a measure of variance of the Distortion of a randomized mechanism. Our primary contribution is the first social choice mechanism with constant sample complexity textit{and} constant Squared Distortion (which also implies constant Distortion). We call the mechanism Random Referee, because it uses a random agent to compare two alternatives that are the favorites of two other random agents. We prove that the use of a comparison query is necessary: no mechanism that only elicits the top-k preferred alternatives of voters (for constant k) can have Squared Distortion that is sublinear in the number of alternatives. We also prove that unlike any top-k only mechanism, the Distortion of Random Referee meaningfully improves on benign metric spaces, using the Euclidean plane as a canonical example. Finally, among top-1 only mechanisms, we introduce Random Oligarchy. The mechanism asks just 3 queries and is essentially optimal among the class of such mechanisms with respect to Distortion. In summary, we demonstrate the surprising power of constant sample complexity mechanisms generally, and just three random voters in particular, to provide some of the best known results in the implicit utilitarian framework.
In large scale collective decision making, social choice is a normative study of how one ought to design a protocol for reaching consensus. However, in instances where the underlying decision space is too large or complex for ordinal voting, standard voting methods of social choice may be impractical. How then can we design a mechanism - preferably decentralized, simple, scalable, and not requiring any special knowledge of the decision space - to reach consensus? We propose sequential deliberation as a natural solution to this problem. In this iterative method, successive pairs of agents bargain over the decision space using the previous decision as a disagreement alternative. We describe the general method and analyze the quality of its outcome when the space of preferences define a median graph. We show that sequential deliberation finds a 1.208- approximation to the optimal social cost on such graphs, coming very close to this value with only a small constant number of agents sampled from the population. We also show lower bounds on simpler classes of mechanisms to justify our design choices. We further show that sequential deliberation is ex-post Pareto efficient and has truthful reporting as an equilibrium of the induced extensive form game. We finally show that for general metric spaces, the second moment of of the distribution of social cost of the outcomes produced by sequential deliberation is also bounded.
We present a number of new results about range searching for colored (or categorical) data: 1. For a set of $n$ colored points in three dimensions, we describe randomized data structures with $O(nmathop{rm polylog}n)$ space that can report the distinct colors in any query orthogonal range (axis-aligned box) in $O(kmathop{rm polyloglog} n)$ expected time, where $k$ is the number of distinct colors in the range, assuming that coordinates are in ${1,ldots,n}$. Previous data structures require $O(frac{log n}{loglog n} + k)$ query time. Our result also implies improvements in higher constant dimensions. 2. Our data structures can be adapted to halfspace ranges in three dimensions (or circular ranges in two dimensions), achieving $O(klog n)$ expected query time. Previous data structures require $O(klog^2n)$ query time. 3. For a set of $n$ colored points in two dimensions, we describe a data structure with $O(nmathop{rm polylog}n)$ space that can answer colored type-2 range counting queries: report the number of occurrences of every distinct color in a query orthogonal range. The query time is $O(frac{log n}{loglog n} + kloglog n)$, where $k$ is the number of distinct colors in the range. Naively performing $k$ uncolored range counting queries would require $O(kfrac{log n}{loglog n})$ time. Our data structures are designed using a variety of techniques, including colored variants of randomized incremental construction (which may be of independent interest), colored variants of shallow cuttings, and bit-packing tricks.
This paper gives a theoretical model for design and analysis of mechanisms for online marketplaces where a bidding dashboard enables the bid-optimization of long-lived agents. We assume that a good allocation algorithm exists when given the true values of the agents and we develop online winner-pays-bid and all-pay mechanisms that implement the same outcome of the algorithm with the aid of a bidding dashboard. The bidding dashboards that we develop work in conjunction with the mechanism to guarantee that bidding according to the dashboard is strategically equivalent (with vanishing utility difference) to bidding truthfully in the sequential truthful implementation of the allocation algorithm. Our dashboard mechanism makes only a single call to the allocation algorithm in each stage.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
