Two birds with one stone


The World Congress on Game Theory which was held in July this year was an opportunity to attend a number of great talks. Three of the talks had an interesting similarity. In each of these talks, the speaker examined a two-sided matching problem and presented a single mechanism which encapsulates two previously introduced well-known mechanisms.

Generalized Matching for School Choice
Atila Abdulkadirogolu

The school choice problem can be formulated as two-sided matching problem with one-sided preferences (if school only have priorities over students but not preferences) or 2-sided matching problem with two-sided preferences (schools are also strategic agents with preferences over students). Abdulkadirogolu introduces a more general hybrid model which covers both the settings. His Stable Transfer Cycles (STC) algorithm for the hybrid model reduces to the Top Trading Cycles (TTC) algorithm in the case of one-sided preferences and Student Optimal Stable Matching (SOSM) algorithm in the case of two sided preferences.

A New Theory on Random Assignments
Mustafa Afacan

Afacan examined a two-sided matching problem with one-sided preferences. The objects have priorities over the agents. If priorities involve indifferences, the common approach is to break ties randomly which leads to random priorities. Since from an ex ante point of view, outcomes are random matchings, Afacan takes a more nuanced view of the setting. He introduces the constrained-probabilistic serial mechanism (CPS) mechanism which is a a generalization of the Deferred Acceptance (DA) algorithm and the Probabilistic Serial (PS) mechanism. It is shown that CPS has same stability properties as the DA algorithm but is more efficient than DA. Moreover under different restrictions on Afacan's model with random priorities, CPS reduced to DA (if there is no indifferences in priorities) and PS (if there are no priorities) respectively.

Matching With Minimal Priority Rights
Szilvia Pápai

Pápai studied a two-sided matching problem with one-sided preferences. Agents have strict priorities over objects. The priorities can be interpreted as either allocation priorities or trade priorities.
Allocation priorities mean that the agents are supposed to be matched in the order of the priorities to the given object. Trade priorities mean that the agents have the right to trade the objects in the order of the priorities. There are two main mechanisms which assign the objects according to these two interpretations, respectively: Gale-Shapley deferred acceptance (DA) procedure, and the TTC procedure enhanced by inheritance. Papai proposes a rule called Acyclic Deferred Trading Cycle Rules which contains the DA rule and the TTC rule.


Comments

Post a Comment

Popular posts from this blog

Smart Lotteries in School Choice Ex-ante Pareto-Improvement with Ex-post Stability

Image
Working Paper: https://cgi.cse.unsw.edu.au/~haziz/PIRMES.pdf  Abstract: In a typical school choice application, the students have strict preferences over the schools while the schools have coarse priorities over the students based on their distance and their enrolled siblings. The outcome of a centralized admission mechanism is then usually obtained by the Deferred Acceptance (DA) algorithm with random tie-breaking. Therefore, every possible outcome of this mechanism is a stable solution for the coarse priorities that will arise with certain probability. This implies a probabilistic assignment, where the admission probability for each student-school pair is specified. In this paper, we propose a new efficiency-improving stable `smart lottery' mechanism. We aim to improve the probabilistic assignment ex-ante in a stochastic dominance sense, while ensuring that the improved random matching is still ex-post stable, meaning that it can be decomposed into stable matchings regarding the ...
Read more

Proportionally Representative Clustering

Image
H. Aziz, B. Lee, S. Morota Chu, and J. Vollen. Proportionally Representative Clustering.  WINE 2024 .  [  Pdf  ]  In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on centroid clustering— one of the fundamental tasks in unsupervised machine learning. We pro- pose a new axiom “proportionally representative fairness” (PRF) that is designed for clustering problems where the selection of centroids re- flects the distribution of data points and how tightly they are clustered together. Our fairness concept is not satisfied by existing fair cluster- ing algorithms. We design efficient algorithms to achieve PRF both for unconstrained and discrete clustering problems. Our algorithm for the unconstrained setting is also the first known polynomial-time approxi- mation algorithm for the well-studied Proportional Fairness (PF) axiom [ 13 ]. Our algorithm for the discrete setting also matches the best kn...
Read more

Fair budgets from ranked ballots: PB-EAR

How do you split a shared budget fairly when people rank projects that cost very different amounts? PB-EAR, from our AAAI 2021 paper  Proportionally Representative Participatory Budgeting with Ordinal Preferences  ( AAAI version ), gives every voter an equal slice of the budget and lets groups pool their slices to fund the projects they rank highest, looking further down the ballots only when nothing is yet affordable. Every cohesive group is guaranteed its proportional share, and the rule extends our  Expanding Approvals Rule  for elections to budgets with project costs, ties and unequal voter weights.  That makes it a natural fit for DAO grant rounds such as   TheDAO Security Fund 's ETHSecurity Initiatives, where badge holders will rank the security initiatives listed on   the app  to allocate the fund's budget. The two-minute video below walks through a worked example. Here's an educational tool someone built to show how PB-EAR works. 
Read more