BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Haris Aziz

Haris Aziz contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computer Science and Game TheoryData Structures and AlgorithmsArtificial IntelligenceDiscrete Mathematicsecon.THMultiagent SystemsRobotics

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
14works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

14 published item(s)

preprint2022arXiv

Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions

The theory of algorithmic fair allocation is within the center of multi-agent systems and economics in the last decade due to its industrial and social importance. At a high level, the problem is to assign a set of items that are either goods or chores to a set of agents so that every agent is happy with what she obtains. Particularly, in this survey, we focus on indivisible items, for which absolute fairness such as envy-freeness and proportionality cannot be guaranteed. One main theme in the recent research agenda is about designing algorithms that approximately achieve the fairness criteria. We aim at presenting a comprehensive survey of recent progresses through the prism of algorithms, highlighting the ways to relax fairness notions and common techniques to design algorithms, as well as the most interesting questions for future research.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

How to make the toss fair in cricket?

In the sport of cricket, the side that wins the toss and has the first choice to bat or bowl can have an unfair or a critical advantage. The issue has been discussed by International Cricket Council committees, as well as several cricket experts. In this article, I outline a method to make the toss fair in cricket. The method is based on ideas from the academic fields of game theory and fair division.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Task Allocation using a Team of Robots

Task allocation using a team or coalition of robots is one of the most important problems in robotics, computer science, operational research, and artificial intelligence. In recent work, research has focused on handling complex objectives and feasibility constraints amongst other variations of the multi-robot task allocation problem. There are many examples of important research progress in these directions. We present a general formulation of the task allocation problem that generalizes several versions that are well-studied. Our formulation includes the states of robots, tasks, and the surrounding environment in which they operate. We describe how the problem can vary depending on the feasibility constraints, objective functions, and the level of dynamically changing information. In addition, we discuss existing solution approaches for the problem including optimization-based approaches, and market-based approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Optimal Kidney Exchange with Immunosuppressants

Algorithms for exchange of kidneys is one of the key successful applications in market design, artificial intelligence, and operations research. Potent immunosuppressant drugs suppress the body's ability to reject a transplanted organ up to the point that a transplant across blood- or tissue-type incompatibility becomes possible. In contrast to the standard kidney exchange problem, we consider a setting that also involves the decision about which recipients receive from the limited supply of immunosuppressants that make them compatible with originally incompatible kidneys. We firstly present a general computational framework to model this problem. Our main contribution is a range of efficient algorithms that provide flexibility in terms of meeting meaningful objectives. Motivated by the current reality of kidney exchanges using sophisticated mathematical-programming-based clearing algorithms, we then present a general but scalable approach to optimal clearing with immunosuppression; we validate our approach on realistic data from a large fielded exchange.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Participatory Funding Coordination: Model, Axioms and Rules

We present a new model of collective decision making that captures important crowd-funding and donor coordination scenarios. In the setting, there is a set of projects (each with its own cost) and a set of agents (that have their budgets as well as preferences over the projects). An outcome is a set of projects that are funded along with the specific contributions made by the agents. For the model, we identify meaningful axioms that capture concerns including fairness, efficiency, and participation incentives. We then propose desirable rules for the model and study, which sets of axioms can be satisfied simultaneously. An experimental study indicates the relative performance of different rules as well as the price of enforcing fairness axioms.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Random Assignment Under Bi-Valued Utilities: Analyzing Hylland-Zeckhauser, Nash-Bargaining, and other Rules

The Hylland-Zeckhauser (HZ) rule is a well-known rule for random assignment of items. The complexity of the rule has received renewed interest recently with Vazirani and Yannakakis (2020) proposing a strongly polynomial-time algorithm for the rule under bi-valued utilities, and making several general insights. We study the rule under the case of agents having bi-valued utilities. We point out several characterizations of the HZ rule, drawing clearer relations with several well-known rules in the literature. As a consequence, we point out alternative strongly polynomial-time algorithms for the HZ solution. We also give reductions from computing the HZ solution to computing well-known solutions based on leximin or Nash social welfare. An interesting contrast is that the HZ rule is group-strategyproof whereas the unconstrained competitive equilibrium with equal incomes rule is not even strategyproof. We clarify which results change when moving from 1-0 utilities to the more general bi-valued utilities. Finally, we prove that the closely related Nash bargaining solution violates envy-freeness and strategyproofness even under 1-0 utilities.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation

We consider fair allocation of indivisible items under additive utilities. When the utilities can be negative, the existence and complexity of an allocation that satisfies Pareto optimality and proportionality up to one item (PROP1) is an open problem. We show that there exists a strongly polynomial-time algorithm that always computes an allocation satisfying Pareto optimality and proportionality up to one item even if the utilities are mixed and the agents have asymmetric weights. We point out that the result does not hold if either of Pareto optimality or PROP1 is replaced with slightly stronger concepts.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Probabilistic Approach to Voting, Allocation, Matching, and Coalition Formation

Randomisation and time-sharing are some of the oldest methods to achieve fairness. I make a case that applying these approaches to social choice settings constitutes a powerful paradigm that deserves an extensive and thorough examination. I discuss challenges and opportunities in applying these approaches to settings including voting, allocation, matching, and coalition formation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Achieving Envy-freeness and Equitability with Monetary Transfers

When allocating indivisible resources or tasks, an envy-free allocation or equitable allocation may not exist. We present a sufficient condition and an algorithm to achieve envy-freeness and equitability when monetary transfers are allowed. The approach works for any agent valuation functions (positive or negative) as long as they satisfy superadditivity. For the case of additive utilities, we present a characterization of allocations that can simultaneously be made equitable and envy-free via payments.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

From Matching with Diversity Constraints to Matching with Regional Quotas

In the past few years, several new matching models have been proposed and studied that take into account complex distributional constraints. Relevant lines of work include (1) school choice with diversity constraints where students have (possibly overlapping) types and (2) hospital-doctor matching where various regional quotas are imposed. In this paper, we present a polynomial-time reduction to transform an instance of (1) to an instance of (2) and we show how the feasibility and stability of corresponding matchings are preserved under the reduction. Our reduction provides a formal connection between two important strands of work on matching with distributional constraints. We then apply the reduction in two ways. Firstly, we show that it is NP-complete to check whether a feasible and stable outcome for (1) exists. Due to our reduction, these NP-completeness results carry over to setting (2). In view of this, we help unify some of the results that have been presented in the literature. Secondly, if we have positive results for (2), then we have corresponding results for (1). One key conclusion of our results is that further developments on axiomatic and algorithmic aspects of hospital-doctor matching with regional quotas will result in corresponding results for school choice with diversity constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Participatory Budgeting: Models and Approaches

Participatory budgeting is a democratic approach to deciding the funding of public projects, which has been adopted in many cities across the world. We present a survey of research on participatory budgeting emerging from the computational social choice literature, which draws ideas from computer science and microeconomic theory. We present a mathematical model for participatory budgeting, which charts existing models across different axes including whether the projects are treated as "divisible" or "indivisible" and whether there are funding limits on individual projects. We then survey various approaches and methods from the literature, giving special emphasis on issues of preference elicitation, welfare objectives, fairness axioms, and voter incentives. Finally, we discuss several directions in which research on participatory budgeting can be extended in the future.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Simultaneously Achieving Ex-ante and Ex-post Fairness

We present a polynomial-time algorithm that computes an ex-ante envy-free lottery over envy-free up to one item (EF1) deterministic allocations. It has the following advantages over a recently proposed algorithm: it does not rely on the linear programming machinery including separation oracles; it is SD-efficient (both ex-ante and ex-post); and the ex-ante outcome is equivalent to the outcome returned by the well-known probabilistic serial rule. As a result, we answer a question raised by Freeman, Shah, and Vaish (2020) whether the outcome of the probabilistic serial rule can be implemented by ex-post EF1 allocations. In the light of a couple of impossibility results that we prove, our algorithm can be viewed as satisfying a maximal set of properties. Under binary utilities, our algorithm is also ex-ante group-strategyproof and ex-ante Pareto optimal. Finally, we also show that checking whether a given random allocation can be implemented by a lottery over EF1 and Pareto optimal allocations is NP-hard.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Strategyproof Multi-Item Exchange Under Single-Minded Dichotomous Preferences

We consider multi-item exchange markets in which agents want to receive one of their target bundles of resources. The model encompasses well-studied markets for kidney exchange, lung exchange, and multi-organ exchange. We identify a general and sufficient condition called weak consistency for the exchange mechanisms to be strategyproof even if we impose any kind of distributional, diversity, or exchange cycle constraints. Within the class of weakly consistent and strategyproof mechanisms, we highlight two important ones that satisfy constrained Pareto optimality and strong individual rationality. Several results in the literature follow from our insights. We also derive impossibility results when constrained Pareto optimality is defined with respect to more permissive individual rationality requirements.

0 citations0 reviewsNo code linkedOpen access