@article{harless_phan_2022, title={Efficient mixtures of priority rules for assigning objects}, volume={132}, ISSN={["1090-2473"]}, DOI={10.1016/j.geb.2021.11.009}, abstractNote={Equity motivates randomization, but often comes at the cost of efficiency. We study the tradeoff within the strategy-proof family of priority rules. Although randomization over all priority orders is incompatible with efficiency, we characterize the maximal subsets of priority for which randomization preserves efficiency: free-agent and adjacent-three families. Introducing equity measures for asymmetric rules, we show that mixtures within these subfamilies admit probabilistic guarantees that priority rules cannot deliver.}, journal={GAMES AND ECONOMIC BEHAVIOR}, author={Harless, Patrick and Phan, William}, year={2022}, month={Mar}, pages={73–89} }
@article{dur_morrill_phan_2022, title={Family ties: School assignment with siblings}, volume={17}, ISSN={["1555-7561"]}, DOI={10.3982/TE4086}, abstractNote={We introduce a generalization of the school choice problem motivated by the following observations: students are assigned to grades within schools, many students have siblings who are applying as well, and school districts commonly guarantee that siblings will attend the same school. This last condition disqualifies the standard approach of considering grades independently as it may separate siblings. We argue that the central criterion in school choice—elimination of justified envy—is now inadequate as it does not consider siblings. We propose a new solution concept, suitability , that addresses this concern, and we introduce a new family of strategy‐proof mechanisms where each satisfies it. Using data from the Wake County magnet school assignment, we demonstrate the impact on families of our proposed mechanism versus the “naive” assignment where sibling constraints are not taken into account.}, number={1}, journal={THEORETICAL ECONOMICS}, author={Dur, Umut and Morrill, Thayer and Phan, William}, year={2022}, month={Jan}, pages={89–120} }
@article{phan_purcell_2022, title={The parameterized complexity of manipulating Top Trading Cycles}, volume={36}, ISSN={["1573-7454"]}, DOI={10.1007/s10458-022-09578-2}, abstractNote={We study the problem of exchange when agents are endowed with heterogeneous indivisible objects, and there is no money. In this setting, no rule satisfies Pareto-efficiency, individual rationality, and strategy-proofness; there is no consensus in the literature on satisfactory second-best mechanisms. A natural generalization of the ubiquitous Top Trading Cycles (TTC) satisfies the first two properties on the lexicographic domain, rendering it manipulable. We characterize the computational complexity of manipulating this mechanism; we show that it is \(\mathbf {W[P]}\)-hard by reduction from MONOTONE WEIGHTED CIRCUIT SATISFIABILITY. We provide a matching upper bound for a wide range of preference domains. We further show that manipulation by groups (when parameterized by group size) is \(\mathbf {W[P]}\)-hard. This provides support for TTC as a second-best mechanism. Lastly, our results are of independent interest to complexity theorists: there are few natural \(\mathbf {W[P]}\)-complete problems and, as far as we are aware, this is the first such problem arising from the social sciences.}, number={2}, journal={AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS}, author={Phan, William and Purcell, Christopher}, year={2022}, month={Oct} }
@article{altuntas_phan_2022, title={Trading probabilities along cycles}, volume={100}, ISSN={["1873-1538"]}, DOI={10.1016/j.jmateco.2021.102631}, abstractNote={Consider the problem of allocating indivisible objects when agents are endowed with fractional amounts and rules can assign lotteries. We study a natural generalization (to the probabilistic domain) of Gale’s Top Trading Cycles. The latter features an algorithm wherein agents trade objects along a cycle—in our new family of rules, agents now trade probabilities of objects along a cycle. We ask if the attractive properties, namely efficiency , individual rationality , and strategy-proofness extended in the stochastic dominance sense, carry over to the Trading-Probabilities-Along-Cycles (TPAC) rules. All of these rules are sd-efficient . We characterize separately the subclass of TPAC rules satisfying the sd-endowment lower bound and sd-strategy-proofness . Regarding fairness, we follow in spirit to the no-envy in net trade condition of Schmeidler and Vind (1972), where the set of allocations satisfying the property essentially coincides with the set of competitive equilibria, and augment the notion appropriately for our environment. We further generalize the TPAC family while extending results on sd-efficiency and the sd-endowment lower bound , and provide sufficient conditions on parameters for the rules to arbitrarily closely satisfy the sd-no-envy in net trade .}, journal={JOURNAL OF MATHEMATICAL ECONOMICS}, author={Altuntas, Acelya and Phan, William}, year={2022}, month={May} }
@article{harless_phan_2020, title={On endowments and indivisibility: partial ownership in the Shapley-Scarf model}, volume={70}, ISSN={["1432-0479"]}, DOI={10.1007/s00199-019-01213-8}, abstractNote={We introduce a parameterized measure of partial ownership, the
$$\alpha $$
-endowment lower bound, appropriate to probabilistic allocation. Strikingly, among all convex combinations of efficient and group strategy-proof rules, only Gale’s Top Trading Cycles is sd efficient and meets a positive
$$\alpha $$
-endowment lower bound (Theorem 2); for efficiency, partial ownership must in fact be complete. We also characterize the rules meeting each
$$\alpha $$
-endowment lower bound (Theorem 1). For each bound, the family is a semilattice ordered by strength of ownership rights. It includes rules where agents’ partial ownership lower bounds are met exactly, rules conferring stronger ownership rights, and the full endowments of TTC. This illustrates the trade-off between sd efficiency and flexible choice of ownership rights.}, number={2}, journal={ECONOMIC THEORY}, author={Harless, Patrick and Phan, William}, year={2020}, month={Sep}, pages={411–435} }
@article{phan_2019, title={Efficient and incentive compatible exchange of real-time information}, volume={48}, ISSN={["1432-1270"]}, DOI={10.1007/s00182-018-0625-y}, abstractNote={We consider the problem of coordinating the exchange of real-time information. For example, a US Department of Transportation pilot program seeks to reduce traffic accidents by allowing each vehicle to transfer crash-relevant information (e.g. position, speed, braking status) to and from neighboring vehicles. Time is of the essence: vehicle information becomes stale quickly. Electronic files are the medium of information and corrupt/useless when partial; hence, we model them as discrete, indivisible objects. Furthermore, each agent may perfectly replicate an object in his possession and transfer it to another agent. However, replication and transfer takes time (e.g. due to bandwidth constraints), and scarcity arises due to fact that information quickly becomes valueless. How should agents transfer such objects? We study efficiency, strategy-proofness, withholding-proofness, and introduce a new axiom based on the concept of reciprocity. Our results are as follows: when each agent owns one object and consumes only one object, we identify a family of rules satisfying all four axioms. If each agent owns a bundle of objects and consumes a bundle, then the four axioms are incompatible. If agents live in a network, then for a large class of incomplete networks, efficiency is only compatible with strategy-proofness.}, number={1}, journal={INTERNATIONAL JOURNAL OF GAME THEORY}, author={Phan, William}, year={2019}, month={Mar}, pages={205–242} }