Here are some new developments in the course allocation mechanism used initially in Wharton and now elsewhere. It turns out that strategy-proofness in the (very) large doesn't imply strategyproofness in samples of realistic size, but this seems to be fixable (and profitable manipulations were not easy to find). The paper concludes with some far ranging thoughts on the econ-cs interface.
Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI) by ERIC BUDISH, RUIQUAN GAO, ABRAHAM OTHMAN AVIAD RUBINSTEIN, and QIANFAN ZHANG
Abstract: "Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is an equilibrium-based solution concept for fair division of discrete items to agents with combinatorial demands. In theory, it is known that in asymptotically large markets:
•For incentives, the A-CEEI mechanism is Envy-Free-but-for-Tie-Breaking (EF-TB), which implies that it is Strategyproof-in-the-Large (SP-L).
•From a computational perspective, computing the equilibrium solution is unfortunately a computationally intractable problem (in the worst-case, assuming PPAD≠FP).
We develop a new heuristic algorithm that outperforms the previous state-of-the-art by multiple orders of magnitude. This new, faster algorithm lets us perform experiments on real-world inputs for the first time. We discover that with real-world preferences, even in a realistic implementation that satisfies the EF-TB and SP-L properties, agents may have surprisingly simple and plausible deviations from truthful reporting of preferences. To this end, we propose a novel strengthening of EF-TB, which dramatically reduces the potential for strategic deviations from truthful reporting in our experiments. A (variant of ) our algorithm is now in production: on real course allocation problems it is much faster, has zero clearing error, and has stronger incentive properties than the prior state-of-the-art implementation"
Here's an intriguing passage:
"In Section 6 we use our manipulation-finding algorithm in combination with our fast A-CEEI
finding algorithm to explore the plausibility of effective manipulations for students bidding in ACEEI. Originally, we had expected that since our mechanism satisfies the EF-TB and SP-L properties,
it would at least be practically strategyproof — if even we don’t really understand the way our
algorithm chooses among the many possible equilibria, how can a student with limited information
learn to strategically bid in such a complex environment?
"Indeed, in 2 out of 3 schools that we tested, our manipulation-finding algorithms finds very few
or no statistically significant manipulations at all. However, when analyzing the 3rd school, we
stumbled upon a simple and effective manipulation for (the first iteration of) our mechanism. We
emphasize that although the manipulation is simple in hindsight, in over a year of working on this
project we failed to predict it by analyzing the algorithm — the manipulation was discovered by the
algorithm.
"Inspired by this manipulation, we propose a natural strengthening of envy-free (discussed below),
which we call contested-envy free. We encode the analogous contested EF-TB as a new constraint
in our algorithm (specifically, the integer program for finding optimal budget perturbations).
Fortunately, our algorithm is still very fast even with this more elaborate constraint. And, when
we re-run our manipulation-finding experiments, we observe that contested EF-TB significantly
reduces the potential for manipulations in practice."
...
"Conclusion: In this work, we give a significantly faster algorithm for computing A-CEEI. Kamal Jain’s famous
formulation “if your laptop cannot find it then neither can the market” [Papadimitriou 2007] was
originally intended as a negative result, casting doubt on the practical implications of many famous
economic concepts because of their worst-case computational complexity results. Even for course
allocation, where a heuristic algorithm existed and worked in practice, Jain’s formulation seemed
to still bind, as solving A-CEEI involved an intense day-long process with a fleet of high-powered
cloud servers operating in parallel. The work detailed in this paper has significantly progressed
what laptops can find: even the largest and most challenging real course allocation problems we
have access to can now be solved in under an hour on a commodity laptop.
"This significant practical improvement suggests that the relationship between prices and demand
for the course allocation problem—and potentially other problems of economic interest with complex
agent preferences and heterogeneous goods—may be much simpler than has been previously
believed and may be far more tractable in practice than the worst-case theoretical bounds. Recalling
Jain’s dictum, perhaps many more market equilibria can be found by laptops—or, perhaps, Walras’s
original and seemingly naive description of how prices iterate in the real world may in fact typically
produce approximate equilibria.
"Our fast algorithm also opens the door for empirical research on A-CEEI, because we can now
solve many instances and see how the solution changes for different inputs. We took it in one
direction: empirically investigating the incentives properties of A-CEEI for the first time. For course
allocation specifically, this faster algorithm opens up new avenues for improving student outcomes
through experimentation. For instance, university administrators often want to subsidize some
6
group of students (e.g., second-year MBA students over first-year MBA students), but are unsure
how large of a budget subsidy to grant those students to balance equity against their expectations.
Being able to run more assignments with different subsidies can help to resolve this issue."
*************
Earlier related posts:
Posts
