Algorithmics, Social choice, Market Design, and Other Topics

Our work with Simon Mackenzie is covered in the Science News.   https://www.sciencenews.org/article/cake-cutting-math-problem-fairness-envy  

H. Aziz, A. Ganguly, E. Micha. Best of Both Worlds Fairness under Entitlements. Working Paper. Aug 2022. [ P DF ] We consider probabilistic allocation of indivisible items to agents with additive valuations and weighted entitlements. We explore how far ex-ante and ex-post fairness properties can be achieved simultaneously. Our first result is that in contrast to the case of same entitlements, well-established adaptations of ex-ante envy-freeness and ex-post envy-freeness up to one item (EF1) to the case of entitlements are not compatible. We then present a polynomial-time algorithm that achieves weighted ex-ante envy-freeness and ex-post weighted envy-freeness up to 1 transfer. The outcome is ex-ante weighted envy-free for all utilities consistent with the underlying ordinal preferences but it is not Pareto optimal. We then present an alternative polynomial-time algorithm that satisfies Pareto optimality, ex-ante weighted envy-freeness and ex-post weighted proportionality up to one ...

 https://www.cs.rpi.edu/wine2022/#accepted-papers Accepted Papers Jad Salem, Swati Gupta and Vijay Kamble. Algorithmic Challenges in Ensuring Fairness at the Time of Decision Kamesh Munagala, Yiheng Shen and Kangning Wang. Auditing for Core Stability in Participatory Budgeting Pinyan Lu, Enze Sun and Chenghan Zhou. Better Approximation for Interdependent SOS Valuations Lirong Xia and Weiqiang Zheng. Beyond the Worst Case: Semi-Random Complexity Analysis of Winner Determination Tim Oosterwijk, Daniel Schmand and Marc Schroder. Bicriteria Nash Flows over Time Xiaotie Deng, Ningyuan Li, Weian Li and Qi Qi. Competition Among Parallel Contests Will Ma and David Simchi-Levi. Constructing Demand Curves from a Single Observation of Bundle Sales Grzegorz Pierczyński and Piotr Skowron. Core-Stable Committees under Restricted Domains Peng Shi and Junxiong Yin. Eliminating Waste in Cadaveric Organ Allocation Christine Konicki, Mithun Chakraborty and Michael Wellman. Exploiting Extensive-Form S...

  Accepted Papers/Posters https://www.ac.tuwien.ac.at/matchup2022/accepted/ Accepted papers Lars Ehlers:  Student-Optimal Interdistrict School Choice: District-Based versus School-Based Admissions Josue Ortega and Thilo Klein:  Improving Efficiency and Equality in School Choice Di Feng, Bettina Klaus and Flip Klijn:  A Characterization of the Coordinate-Wise Top-Trading-Cycles Mechanism for Multiple-Type Housing Markets Daniel Kornbluth and Alexey Kushnir:  Undergraduate Course Allocation through Pseudo-Markets Karolina Vocke:  Anonymity and stability in large many-to-many markets Péter Biró and Gergely Csáji:  Strong core and Pareto-optimal solutions for the multiple partners matching problem under lexicographic preferences Haris Aziz and Zhaohong Sun:  Multi-Rank Smart Reserves Ran Shorrer and Sandor Sovago:  Dominated Choices in a Strategically Simple College Admissions Environment: The Effect of Admission Selectivity Xuan Zhang and Yuri F...

Which Voting Rule Will Fix French Politics?  By Haris Aziz The issue The French political system is based on electing a president via the plurality with runoff rule. The rule requires that each voter votes for the most preferred candidate and the two candidates with the highest number of voters are shortlisted for a second round. In the second round, the candidate that is preferred by a majority of voters is selected. Just like the first past the vote, plurality with runoff is a hugely flawed voting rule that is highly susceptible to the spoiler effect. In simple words, the vote bank of a sizeable group of voters can be easily split up among similar candidates.  The following is a simple example that shows how the rule used in France is flawed. The voters express preferences in decreasing order of preference from left to right.  20%: Y>X1>X2>X3>X4>Z 20%  Z>X1>X2>X3>X4>X 15%: X1>X2>X3>X4>Y>Z 15%: X2>X1>X2>X4...

I had the pleasure to chat with Dr. Zartash Uzmi, an academic at LUMS (my undergrad alma mater). Dr Uzmi joined the LUMS faculty when I was doing my undergrad. The chat is part of the LUMS "Alumni Chat" series to hear about the stories of the alumni. It was an opportunity to give some insights into why pursuing research in game theory / AI / math etc. may be interesting and intellectually inspiring for some people. It's amusing that my passion for tennis pops up at random places during the conversation. In the end, I also honoured the memory of Prof. Zaeem Jafri who used to take special interest in student welfare.  https://fb.watch/dKU24T_pz2/ 

 https://www.cs.cityu.edu.hk/~gtsc/ Game theory and social choice are very popular research topics in the study of multi-agent systems. Being rich by themselves, they are also interacting with other research domains, generating many interesting results.  The objective of the summer school is to provide fundamental knowledge in game theory and social choice to researchers or research students who may find the topics useful in their own research or senior undergraduate students who are looking for potential research directions.  At the same time, the students will also have the opportunity to learn about the state of the art in these fields via keynote talks.  The summer school is organized by  Department of Computer Science ,  City University of Hong Kong  via zoom during June 20 - June 24 , 2022. The intended participants of the summer school are students within computer science, or students with mathematics or economics background interested in game t...