Appendix

The appendix is organized as follows: Appendix A: In this section, we prove IS functions are XOS. Appendix B: In this section, we formally prove our main results in Section 3. Appendix C: In this section, we formally prove our main results in Section 4. Appendix D: In this section, we introduce a milder efficiency requirement IO and study its compatibility with EF1. Appendix E: In this section, we discuss our experiments in more details. Regarding agents' utilities, FISP contains three cases, from the most special to the most general: Unweighted: u J, i.e., agents have unary utility for jobs. J, i.e., all jobs have unit processing time.