Filter by type:

Sort by year:

Class Fairness in Online Matching

Hadi Hosseini, Zhiyi Huang, Ayumi Igarashi, and Nisarg Shah
Working Paper

Abstract

In the classical version of online bipartite matching, there is a given set of offline vertices (aka agents) and another set of vertices (aka items) that arrive online. When each item arrives, its incident edges---the agents who like the item---are revealed and the algorithm must irrevocably match the item to such agents. We initiate the study of class fairness in this setting, where agents are partitioned into a set of classes and the matching is required to be fair with respect to the classes. We adopt popular fairness notions from the fair division literature such as envy-freeness (up to one item), proportionality, and maximin share fairness to our setting. Our class versions of these notions demand that all classes, regardless of their sizes, receive a fair treatment. We study deterministic and randomized algorithms for matching indivisible items (leading to integral matchings) and for matching divisible items (leading to fractional matchings). We design and analyze three novel algorithms. For matching indivisible items, we propose an adaptive-priority-based algorithm, MATCH-AND-SHIFT, prove that it achieves 1/2-approximation of both class envy-freeness up to one item and class maximin share fairness, and show that each guarantee is tight. For matching divisible items, we design a water-filling-based algorithm, EQUAL-FILLING, that achieves (1-1/e)-approximation of class envy-freeness and class proportionality; we prove (1-1/e) to be tight for class proportionality and establish a 3/4 upper bound on class envy-freeness. Finally, we build upon EQUAL-FILLING to design a randomized algorithm for matching indivisible items, EQAUL-FILLING-OCS, which achieves 0.593-approximation of class proportionality. The algorithm and its analysis crucially leverage the recently introduced technique of online correlated selection (OCS) [Fahrbach et al., 2020].

Fairly Dividing Mixtures of Goods and Chores under Lexicographic Preferences

Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia
Working Paper

Abstract

We study fair allocation of indivisible goods and chores among agents with lexicographic preferences -- a subclass of additive valuations. In sharp contrast to the goods-only setting, we show that an allocation satisfying envy-freeness up to any item (EFX) could fail to exist for a mixture of objective goods and chores. To our knowledge, this negative result provides the first counterexample for EFX over (any subdomain of) additive valuations. To complement this non-existence result, we identify a class of instances with (possibly subjective) mixed items where an EFX and Pareto optimal allocation always exists and can be efficiently computed. When the fairness requirement is relaxed to maximin share (MMS), we show positive existence and computation for any mixed instance. More broadly, our work examines the existence and computation of fair and efficient allocations both for mixed items as well as chores-only instances, and highlights the additional difficulty of these problems vis-à-vis their goods-only counterparts.

Two for One & One for All: Two-Sided Manipulation in Matching Markets

Hadi Hosseini, Fatima Umar, and Rohit Vaish
Conference Paper In IJCAI-22: Proc. of the 31st International Joint Conference on Artificial Intelligence, forthcoming.

Abstract

Strategic behavior in two-sided matching markets has been traditionally studied in a "one-sided" manipulation setting where the agent who misreports is also the intended beneficiary. Our work investigates "two-sided" manipulation of the deferred acceptance algorithm where the misreporting agent and the manipulator (or beneficiary) are on different sides. Specifically, we generalize the recently proposed accomplice manipulation model (where a man misreports on behalf of a woman) along two complementary dimensions: (a) the two for one model, with a pair of misreporting agents (man and woman) and a single beneficiary (the misreporting woman), and (b) the one for all model, with one misreporting agent (man) and a coalition of beneficiaries (all women). Our main contribution is to develop polynomial-time algorithms for finding an optimal manipulation in both settings. We obtain these results despite the fact that an optimal one for all strategy fails to be inconspicuous, while it is unclear whether an optimal two for one strategy satisfies the inconspicuousness property. We also study the conditions under which stability of the resulting matching is preserved. Experimentally, we show that two-sided manipulations are more frequently available and offer better quality matches than their one-sided counterparts.

Ordinal Maximin Share Approximation for Goods

Hadi Hosseini, Andrew Searns, and Erel Segal-Halevi
Journal Paper Journal of Artificial Intelligence Research (JAIR), 74 (2022):351-389, 2022.

Abstract

In fair division of indivisible goods, l-out-of-d maximin share (MMS) is the value that an agent can guarantee by partitioning the goods into $d$ bundles and choosing the l least preferred bundles. Most existing works aim to guarantee to all agents a constant fraction of their 1-out-of-n MMS. But this guarantee is sensitive to small perturbation in agents' cardinal valuations. We consider a more robust approximation notion, which depends only on the agents' ordinal rankings of bundles. We prove the existence of l-out-of-(l+1/2)n MMS allocations of goods for any integer l ≥ 1, and present a polynomial-time algorithm that finds a 1-out-of-3n/2 MMS allocation when l = 1. We further develop an algorithm that provides a weaker ordinal approximation to MMS for any l > 1.

The Crawler: Three Equivalence Results for Object (Re)allocation Problems when Preferences Are Single-peaked

Yuki Tamura and Hadi Hosseini
Journal Paper Journal of Economic Theory (JET), 2022.

Abstract

For object reallocation problems, if preferences are strict but otherwise unrestricted, the Top Trading Cycles rule (TTC) is the leading rule: It is the only rule satisfying efficiency, individual rationality, and strategy-proofness. However, on the subdomain of single-peaked preferences, Bade (2019) defines a new rule, the "crawler", which also satisfies these three properties. (i) The crawler selects an allocation by "visiting" agents in a specific order. A natural "dual" rule can be defined by proceeding in the reverse order. Our first theorem states that the crawler and its dual are actually the same. (ii) Single-peakedness of a preference profile may in fact hold for more than one order and its reverse. Our second theorem states that the crawler is invariant to the choice of the order. (iii) For object allocation problems (as opposed to reallocation problems), we define a probabilistic version of the crawler by choosing an endowment profile at random according to a uniform distribution, and applying the original definition. Our third theorem states that this rule is the same as the "random priority rule".

Ordinal Maximin Share Approximation for Chores

Hadi Hosseini, Andrew Searns, and Erel Segal-Halevi
Conference Paper In AAMAS-22: Proc. of 21st International Conference on Autonomous Agents and Multi-Agent Systems, 2022, Forthcoming.

Abstract

We study the problem of fairly allocating a set of m indivisible chores (items with non-positive value) to n agents. We consider the desirable fairness notion of 1-out-of-d maximin share (MMS) -- the minimum value that an agent can guarantee by partitioning items into d bundles and receiving the least valued bundle -- and focus on ordinal approximation of MMS that aims at finding the largest d <= n for which 1-out-of-d MMS allocation exists. Our main contribution is a polynomial-time algorithm for 1-out-of-floor(2n/3) MMS allocation, and a proof of existence of 1-out-of-floor(3n/4) MMS allocation of chores. Furthermore, we show how to use recently-developed algorithms for bin-packing to approximate the latter bound up to a logarithmic factor in polynomial time.

Fair Stable Matching Meets Correlated Preferences

Angelina Brilliantova and Hadi Hosseini
Conference Paper In AAMAS-22: Proc. of 21st International Conference on Autonomous Agents and Multi-Agent Systems, 2022, Forthcoming.

Abstract

The stable matching problem sets the economic foundation of several practical applications ranging from school choice and medical residency to ridesharing and refugee placement. It is concerned with finding a matching between two disjoint sets of agents wherein no pair of agents prefer each other to their matched partners. The Deferred Acceptance (DA) algorithm is an elegant procedure that guarantees a stable matching for any input; however, its outcome may be unfair as it always favors one side by returning a matching that is optimal for one side (say men) and pessimal for the other side (say women). A desirable fairness notion is minimizing the sex-equality cost, i.e. the difference between the total rankings of both sides. Computing such stable matchings is a strongly NP-hard problem, which raises the question of what tractable algorithms to adopt in practice. We conduct a series of empirical evaluations on the properties of sex-equal stable matchings when preferences of agents on both sides are correlated. Our empirical results suggest that under correlated preferences, the DA algorithm returns stable matchings with low sex-equality cost, which further confirms its broad use in many practical applications.

Accomplice Manipulation of the Deferred Acceptance Algorithm

Hadi Hosseini, Fatima Umar, and Rohit Vaish
Conference Paper In IJCAI-21: Proc. of the 30th International Joint Conference on Artificial Intelligence, pp. 231-237, 2021.

Abstract

The deferred acceptance algorithm is an elegant solution to the stable matching problem that guarantees optimality and truthfulness for one side of the market. Despite these desirable guarantees, it is susceptible to strategic misreporting of preferences by the agents on the other side. We study a novel model of strategic behavior under the deferred acceptance algorithm: manipulation through an accomplice. Here, an agent on the proposed-to side (say, a woman) partners with an agent on the proposing side---an accomplice---to manipulate on her behalf (possibly at the expense of worsening his match). We show that the optimal manipulation strategy for an accomplice comprises of promoting exactly one woman in his true list (i.e., an inconspicuous manipulation). This structural result immediately gives a polynomial-time algorithm for computing an optimal accomplice manipulation. We also study the conditions under which the manipulated matching is stable with respect to the true preferences. Our experimental results show that accomplice manipulation outperforms self manipulation both in terms of the frequency of occurrence as well as the quality of matched partners.

Guaranteeing Maximin Shares: Some Agents Left Behind

Hadi Hosseini and Andrew Searns
conference Paper In IJCAI-21: Proc. of the 30th International Joint Conference on Artificial Intelligence, pp. 238-244, 2021.

Abstract

The maximin share (MMS) guarantee is a desirable fairness notion for allocating indivisible goods. While MMS allocations do not always exist, several approximation techniques have been developed to ensure that all agents receive a fraction of their maximin share. We focus on an alternative approximation notion, based on the population of agents, that seeks to guarantee MMS for a fraction of agents. We show that no optimal approximation algorithm can satisfy more than a constant number of agents, and discuss the existence and computation of MMS for all but one agent and its relation to approximate MMS guarantees. We then prove the existence of allocations that guarantee MMS for 2/3 of agents, and devise a polynomial time algorithm that achieves this bound for up to nine agents. A key implication of our result is the existence of allocations that guarantee the value that an agent receives by partitioning the goods into 3n/2 bundles, improving the best known guarantee when goods are partitioned into 2n-2 bundles. Finally, we provide empirical experiments using synthetic data.

Surprisingly Popular Voting Recovers Rankings, Surprisingly!

Hadi Hosseini, Debmalya Mandal, Nisarg Shah, and Kevin Shi
Conference Paper In IJCAI-21: Proc. of the 30th International Joint Conference on Artificial Intelligence, pp. 245-251, 2021.

Abstract

The wisdom of the crowd has long become the de facto approach for eliciting information from individuals or experts in order to predict the ground truth. However, classical democratic approaches for aggregating individual votes only work when the opinion of the majority of the crowd is relatively accurate. A clever recent approach, surprisingly popular voting, elicits additional information from the individuals, namely their prediction of other individuals' votes, and provably recovers the ground truth even when experts are in minority. This approach works well when the goal is to pick the correct option from a small list, but when the goal is to recover a true ranking of the alternatives, a direct application of the approach requires eliciting too much information. We explore practical techniques for extending the surprisingly popular algorithm to ranked voting by partial votes and predictions and designing robust aggregation rules. We experimentally demonstrate that even a little prediction information helps surprisingly popular voting outperform classical approaches.

Fair and Efficient Allocations under Lexicographic Preferences

Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia
Conference Paper In AAAI-21: Proc. of the 35th AAAI Conference on Artificial Intelligence, pp. 5472-5480, 2021.

Abstract

Envy-freeness up to any good (EFX) provides a strong and intuitive guarantee of fairness in the allocation of indivisible goods. But whether such allocations always exist or whether they can be efficiently computed remains an important open question. We study the existence and computation of EFX in conjunction with various other economic properties under lexicographic preferences--a well-studied preference model in artificial intelligence and economics. In sharp contrast to the known results for additive valuations, we not only prove the existence of EFX and Pareto optimal allocations, but in fact provide an algorithmic characterization of these two properties. We also characterize the mechanisms that are, in addition, strategyproof, non-bossy, and neutral. When the efficiency notion is strengthened to rank-maximality, we obtain non-existence and computational hardness results, and show that tractability can be restored when EFX is relaxed to another well-studied fairness notion called maximin share guarantee (MMS).

Necessarily Optimal One-Sided Matchings

Conference Paper In AAAI-21: Proc. of the 35th AAAI Conference on Artificial Intelligence, pp. 5481-5488, 2021.

Abstract

We study the classic problem of matching n agents to n objects, where the agents have ranked preferences over the objects. We focus on two popular desiderata from the matching literature: Pareto optimality and rank-maximality. Instead of asking the agents to report their complete preferences, our goal is to learn a desirable matching from partial preferences, specifically a matching that is necessarily Pareto optimal (NPO) or necessarily rank-maximal (NRM) under any completion of the partial preferences. We focus on the top-k model in which agents reveal a prefix of their preference rankings. We design efficient algorithms to check if a given matching is NPO or NRM, and to check whether such a matching exists given top-k partial preferences. We also study online algorithms to elicit partial preferences adaptively, and prove bounds on their competitive ratio.

Fair Stable Matchings Under Correlated Preferences

Angelina Brilliantova and Hadi Hosseini
Conference Paper In AAAI-21: Proc. of the 35th AAAI Conference on Artificial Intelligence, student abstract, pp. 15763-15764, 2021.

Abstract

Stable matching models are widely used in market design, school admission, and donor organ exchange. The classic Deferred Acceptance (DA) algorithm guarantees a stable matching that is optimal for one side (say men) and pessimal for the other (say women). A sex-equal stable matching aims at providing a fair solution to this problem. We demonstrate that under a class of correlated preferences, the DA algorithm either returns a sex-equal solution or has a very low sex-equality cost.

Customizing Feedback for Introductory Programming Courses using Semantic Clustering

Victor Marin, Hadi Hosseini, and Carlos R. Rivero
Conference Paper In ITS-2021: Proc. of the 17th International Conference on Intelligent Tutoring Systems, 2021.

Abstract

The number of introductory programming learners is increasing worldwide. Delivering feedback to these learners is important to support their progress; however, traditional methods to deliver feedback do not scale to thousands of programs. We identify several opportunities to improve a recent data-driven technique to analyze individual program statements. These statements are grouped based on their semantic intent and usually differ on their actual implementation and syntax. The existing technique groups statements that are semantically close, and considers outliers those statements that reduce the cohesiveness of the clusters. Unfortunately, this approach leads to many statements to be considered outliers. We propose to reduce the number of outliers through a new clustering algorithm that processes vertices based on density. Our experiments over six real-world introductory programming assignments show that we are able to reduce the number of outliers and, therefore, increase the total coverage of the programs that are under evaluation.

Fair Division of Time: Multi-layered Cake Cutting

Hadi Hosseini, Ayumi Igarashi, and Andrew Searns
Conference Paper In IJCAI-20: Proc. of the 29th International Joint Conference on Artificial Intelligence, pp. 182–18, 2020.

Abstract

We initiate the study of multi-layered cake cutting with the goal of fairly allocating multiple divisible resources (layers of a cake) among a set of agents. The key requirement is that each agent can only utilize a single resource at each time interval. Several real-life applications exhibit such restrictions on overlapping pieces; for example, assigning time intervals over multiple facilities and resources or assigning shifts to medical professionals. We investigate the existence and computation of envy-free and proportional allocations. We show that envy-free allocations that are both feasible and contiguous are guaranteed to exist for up to three agents with two types of preferences, when the number of layers is two. We also show that envy-free feasible allocations where each agent receives a polynomially bounded number of intervals exist for any number of agents and layers under mild conditions on agents' preferences. We further devise an algorithm for computing proportional allocations for any number of agents and layers.

Fair Division through Information Withholding

Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, Jun Wang, and Lirong Xia
Conference Paper In AAAI-20: Proc. of the 34th AAAI Conference on Artificial Intelligence, pp. 2014–2021, 2020.

Abstract

Envy-freeness up to one good (EF1) is a well-studied fairness notion for indivisible goods that addresses pairwise envy by the removal of at most one good. In the worst case, each pair of agents might require the (hypothetical) removal of a different good, resulting in a weak aggregate guarantee. We study allocations that are nearly envy-free in aggregate, and define a novel fairness notion based on information withholding. Under this notion, an agent can withhold (or hide) some of the goods in its bundle and reveal the remaining goods to the other agents. We observe that in practice, envy-freeness can be achieved by withholding only a small number of goods overall. We show that finding allocations that withhold an optimal number of goods is computationally hard even for highly restricted classes of valuations. In contrast to the worst-case results, our experiments on synthetic and real-world preference data show that existing algorithms for finding EF1 allocations withhold a close-to-optimal amount of information.

Fairness Does Not Imply Satisfaction

Andrew Searns and Hadi Hosseini
Conference Paper In AAAI-20: Proc. of the 34th AAAI Conference on Artificial Intelligence, pp. 3911–13912, 2020.

Abstract

Fair division is a subfield of multiagent systems related to object distribution. When objects are indivisible, the Maximin Share Guarantee (MMS) is a desirable fairness notion; however, it is not guaranteed to exist. While MMS does not exist, a relaxation of MMS is always guaranteed to exist. We show that there exists a family of instances for which this relaxation fails to guarantee MMS value of all but a small constant number of agents.

MatchU: An Interactive Matching Platform

James Ferris and Hadi Hosseini
Conference Paper In AAAI-20: Proc. of the 34th AAAI Conference on Artificial Intelligence, pp. 3606–13607, 2020. (Demo Paper)

Abstract

MatchU is a web-based platform that offers an interactive framework to find how to form mutually-beneficial relationships, decide how to distribute resources, or resolve conflicts through a suite of matching algorithms rooted in economics and artificial intelligence. In this paper, we discuss MatchU's vision, solutions, and future directions.

Game On: Exploring the Effectiveness of Gamebased Learning

Maxwell Hartt, Hadi Hosseini, and Mehrnaz Mostafapour
Journal Paper Journal of Planning Practice & Research, 35(5):589-604, 2020.

Abstract

Game-based learning has emerged as an innovative learning technique that can increase student motivation, emotional involvement and enjoyment. Our study examines the effectiveness of game-based learning in planning education. Specifically, we explore the impact of gamification on planning students’ perception of learning, engagement and teamwork. Two lectures in an undergraduate planning course were delivered using two different methods of teaching (one traditional lecture-style, one game-based). Feedback was gathered through an online questionnaire and semi-structured interviews. Results show that students favored and were more engaged in the game-based lecture. Finally, we contend that gamification is particularly well suited for planning education.

Multiple Assignment Problems under Lexicographic Preferences

Hadi Hosseini and Kate Larson
Conference Paper In AAMAS-19: Proc. 18th Intl. Conference on Autonomous Agents and Multiagent Systems, pp. 837-845, 2019.

Abstract

We study the problem of allocating multiple objects to agents without transferable utilities, where each agent may receive more than one object according to a quota. Under lexicographic preferences, we characterize the set of strategyproof, non-bossy, and neutral quota mechanisms and show that under a mild Pareto efficiency condition, serial dictatorship quota mechanisms are the only mechanisms satisfying these properties. We then extend quota mechanisms to randomized settings, and show that the random serial dictatorship quota mechanisms (RSDQ) are envyfree, strategyproof, and ex post efficient for any number of agents and objects and any quota system, proving that the well-studied Random Serial Dictatorship (RSD) satisfies envyfreeness when preferences are lexicographic.

The Rise and Fall of Complex Family Structures: Coalition Formation, Stability, and Power Struggle

Angelina Brilliantova, Anton Pletenev, and Hadi Hosseini
Conference Paper In AAMAS-19: Proc. 18th Intl. Conference on Autonomous Agents and Multiagent Systems, pp. 1847-1849, 2019.

Abstract

A complex family is a particular case of family structures in certain animal groups that arises from cooperative breeding. Inspired by this phenomenon, we study the problem of complex family formation from a game-theoretical perspective. While these structures may arise in various domains, such as search and rescue and robotics, the standard types of coalitional games (e.g. simple games) do not capture the observed intricacies of such complex formations. In this paper, we propose a characteristic function game for complex family structures and investigate the stability of coalitions and the existence of the core under various conditions. We provide theoretical bounds on the existence of complex families and the size of coalitions. Furthermore, we empirically examine the proposed framework through an ecological case study and show that our results are consistent with the observed family formations, shedding light on the causes of complex family compositions in the past.

Partners in Crime: Manipulating the Deferred Acceptance Algorithm through an Accomplice

Theodora Bendlin and Hadi Hosseini
Conference Paper In AAAI-19: Proc. of the 33rd AAAI Conference on Artificial Intelligence, pp. 9917-9918, 2019.

Abstract

We introduce a new manipulation strategy available to women in the men-proposing stable matching, called manipulation through an accomplice. In this strategy, a woman can team up with a potential male ``accomplice'' who manipulates on her behalf to obtain a better match for her. We investigate the stability of the matching obtained after this manipulation, provide an algorithm to compute such strategies, and show its benefit compared to single-woman manipulation strategies.

Inferring True Voting Outcomes in Homophilic Social Networks

John A. Doucette, Alan Tsang, Hadi Hosseini, Kate Larson, and Robin Cohen

Abstract

We investigate the problem of opinion aggregation in a social network regarding an objective outcome. Agents receive independent noisy signals relating to the outcome, but may converse with their neighbors in the network before opinions are aggregated, resulting in incorrect opinions gaining prominence in the network. Recent work has shown that, in the general case, there is no procedure for inferring the correct outcome that incorporates information from the connections between agents (i.e. the structure of the social network). We develop a new approach for inferring the true outcome that can benefit from the additional information provided by the social network, under the simple assumption that agents will more readily convert to the true opinion than to a false one. Our proposed approach is computationally efficient, and provides significantly more accurate inference in many domains, which we demonstrate via both simulated and real-world datasets. We also theoretically characterize the properties that are necessary for our approach to perform well. Finally, we extend our approach to directed social networks, and cases with many alternatives, and outline areas for future research.

Learning IS child's play: Game-based Learning in Computer Science Education

Hadi Hosseini, Maxwell Hartt, and Mehrnaz Mostafapour
Journal Paper ACM Transactions on Computing Education (TOCE), Volume 19, Issue 3, pp. 22:1--22:18, 2019.

Abstract

Game-based learning has received significant attention in educational pedagogy as an effective way of increasing student motivation and engagement. The majority of the work in this area has been focused on digital games or games involving technology. We focus on the use of traditional game design in improving student engagement and perception of learning in teaching computer science concepts in higher education. In addition, as part of an interdisciplinary effort, we discuss the interplay between game-based learning in higher education and disciplinary cultures, addressing the lack of empirical evidence on the impact of game design on learning outcomes, engagement, and students' perception of learning.

From the Players Point of View

Maxwell Hartt and Hadi Hosseini
Book Chapter Palgrave Macmillan | 2019 | ISBN-10: 978-3-319-95779-1.
image

The Power of Play in Higher Education: Creativity in Tertiary Learning

This book examines the increasing popularity of creativity and play in tertiary learning, and how it can be harnessed to enhance the student experience at university. While play is often misunderstood as something ‘trivial’ and associated with early years education, the editors and contributors argue that play contributes to social and human development and relations at a fundamental level. This volume invalidates the commonly held assumption that play is only for children, drawing together numerous case studies from higher education that demonstrate how researchers, students and managers can benefit from play as a means of liberating thought, overturning obstacles and discovering fresh approaches to persistent challenges. This diverse and wide-ranging edited collection unites play theory and practice to address the gulf in research on this fascinating topic. It will be of interest and value to educators, students and scholars of play and creativity, as well as practitioners and academic leaders looking to incorporate play into the curriculum.

Are You Game? Assessing Students’ Perception of Learning, Instructors’ Perspective, and Learning Attitude

Hadi Hosseini and Laurel Perweiler
Conference Paper In SIGCSE-19: Proc. 50th ACM Technical Symposium on Computer Science Education, pp. 866-872, 2019.

Abstract

The use of gameful activities in education has been widely celebrated in recent years as an effective pedagogical method in engaging students, exciting cognitive abilities, and promoting mastery. Despite the popularity of game-based learning, to date, little has been done to analyze the impacts of introducing such interventions on students and instructors alike. We focus on hybrid teaching strategies that blend educational games with instructional scaffolding in introductory computer science teaching. We assess the effectiveness of incorporating these teaching strategies by leveraging various empirical evaluation techniques and study their impacts from three different dimensions: students' point of view, instructors' perspective, and students' performance. In addition, we establish correlations between students' approaches to learning and game-based learning, and further discuss how learning concentration and curiosity relate to students' perception of game-based activities.

Investigating the Characteristics of One-Sided Matching Mechanisms Under Various Preferences and Risk Attitudes

Hadi Hosseini, Kate Larson, and Robin Cohen
Journal Paper Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS), Volume 32, Issue 4, pp. 534–567, 2018.

supersedes AAMAS-16 and EXPLORE-16 papers below.

Abstract

One-sided matching mechanisms are fundamental for assigning a set of indivisible objects to a set of self-interested agents when monetary transfers are not allowed. Two widely-studied randomized mechanisms in multiagent settings are the Random Serial Dictatorship (RSD) and the Probabilistic Serial Rule (PS). Both mechanisms require only that agents specify ordinal preferences and have a number of desirable economic and computational properties. However, the induced outcomes of the mechanisms are often incomparable and thus there are challenges when it comes to deciding which mechanism to adopt in practice. In this paper, we first consider the space of general ordinal preferences and provide empirical results on the (in)comparability of RSD and PS. We analyze their respective economic properties under general and lexicographic preferences. We then instantiate utility functions with the goal of gaining insights on the manipulability, efficiency, and envyfreeness of the mechanisms under different risk-attitude models. Our results hold under various preference distribution models, which further confirm the broad use of RSD in most practical applications.

Strategyproof Quota Mechanisms for Multiple Assignment Problems

Hadi Hosseini and Kate Larson
Working Paper In COMSOC-18: Seventh International Workshop on Computational Social Choice, 2018.

Abstract

We study the problem of allocating multiple objects to agents without transferable utilities, where each agent may receive more than one object according to a quota. Under lexicographic preferences, we characterize the set of strategyproof, non-bossy, and neutral quota mechanisms and show that under a mild Pareto efficiency condition, serial dictatorship quota mechanisms are the only mechanisms satisfying these properties. Dropping the neutrality requirement, this class of quota mechanisms further expands to sequential dictatorship quota mechanisms. We then extend quota mechanisms to randomized settings, and show that the random serial dictatorship quota mechanisms (RSDQ) are envyfree, strategyproof, and ex post efficient for any number of agents and objects and any quota system, proving that the well-studied Random Serial Dictatorship (RSD) satisfies envyfreeness when preferences are lexicographic.

An Agent-Based Model of an Endangered Population of the Arctic Fox from Mednyi Island

Angelina Brilliantova, Anton Pletenev, Liliya Doronina, and Hadi Hosseini
Conference Paper In AIWC at IJCAI-18: Workshop on AI for Wildlife Conservation (AIWC), 2018.

Abstract

Artificial Intelligence techniques such as agent-based modeling and probabilistic reasoning have shown promise in modeling complex biological systems and testing ecological hypotheses through simulation. We develop an agent-based model of Arctic foxes from Medniy Island while utilizing Probabilistic Graphical Models to capture the conditional dependencies between the random variables. Such models provide valuable insights in analyzing factors behind catastrophic degradation of this population and in revealing evolutionary mechanisms of its persistence in high-density environment. Using empirical data from studies in Medniy Island, we create a realistic model of Arctic foxes as agents, and study their survival and population dynamics under a variety of conditions.

A Framework for the Game-theoretic Analysis of Censorship Resistance

Tariq Elahi, John Doucette, Hadi Hosseini, Steven Murdoch, and Ian Goldberg
Journal Paper Privacy Enhancing Technologies (PoPET), Volume 2016, Issue 4, pp. 83-101, 2016.

Abstract

We present a game-theoretic analysis of optimal solutions for interactions between censors and censorship resistance systems (CRSs) by focusing on the data channel used by the CRS to smuggle clients’ data past the censors. This analysis leverages the inherent errors (false positives and negatives) made by the censor when trying to classify traffic as either non-circumvention traffic or as CRS traffic, as well as the underlying rate of CRS traffic. We identify Nash equilibrium solutions for several simple censorship scenarios and then extend those findings to more complex scenarios where we find that the deployment of a censorship apparatus does not qualitatively change the equilibrium solutions, but rather only affects the amount of traffic a CRS can support before being blocked. By leveraging these findings, we describe a general framework for exploring and identifying optimal strategies for the censorship circumventor, in order to maximize the amount of CRS traffic not blocked by the censor. We use this framework to analyze several scenarios with multiple data-channel protocols used as cover for the CRS. We show that it is possible to gain insights through this framework even without perfect knowledge of the censor’s (secret) values for the parameters in their utility function.

Game-based Learning in the University Classroom

Hadi Hosseini and Maxwell Hartt
Journal Paper Teaching Innovation Projects, Volume 6, Issue 1 , Article 4, 2016.

Abstract

Gamification focuses on the application of game mechanics and gameful thinking in non-game contexts to engage users in solving problems or carrying out tasks. This interactive workshop will explore the theoretical and psychological relationship between games and learning, with particular focus on Bloom's taxonomy of learning and the relation between its affective domain and gamified learning. The workshop then introduces various elements of gameful design and a variety of gamification methods that can be used in a university classroom. Participants will learn strategies to incorporate gamification into a variety of learning environments and will have the opportunity to design game-based learning events that can be used in undergraduate lectures. Individuals from all disciplines can participate and benefit from techniques to identify and learn from a diverse set of strategies and methods that can be adopted to use in different disciplines and levels of teaching. Finally, the workshop provides an opportunity for participants to dive deeper and discuss strengths, weaknesses, and possible threats in gamified learning.

Investigating the Characteristics of One-Sided Matching Mechanisms

Hadi Hosseini, Kate Larson, and Robin Cohen
Conference Paper In AAMAS-16: Proc. 15th Intl. Joint Conference on Autonomous Agents and Multiagent Systems, pp. 1443-1444, 2016.

Abstract

For one-sided matching problems, two widely studied mechanisms are the Random Serial Dictatorship (RSD) and the Probabilistic Serial Rule (PS). The induced outcomes of these two mechanisms are often incomparable and thus there are challenges when it comes to deciding which mechanism to adopt in practice. Working in the space of general preferences, we provide empirical results on the (in)comparability of RSD and PS and analyze their economic properties.

An Empirical Comparison of One-Sided Matching Mechanisms

Hadi Hosseini, Kate Larson, and Robin Cohen
Conference Paper In EXPLORE at AAMAS-16: Proc. The 3rd Workhop on Exploring Beyond the Worst Case in Computational Social Choice, 2016.

Abstract

For one-sided matching problems, two widely studied mechanisms are the Random Serial Dictatorship (RSD) and the Probabilistic Serial Rule (PS). Both mechanisms require only that agents specify ordinal preferences and have a number of desirable economic and computational properties. However, the induced outcomes of the mechanisms are often incomparable and thus there are challenges when it comes to deciding which mechanism to adopt in practice. In this paper, working in the space of general ordinal preferences, we provide empirical results on the (in)comparability of RSD and PS and analyze their respective economic properties. We then instantiate utility functions for agents, consistent with the ordinal preferences, with the goal of gaining insights on the manipulability, efficiency, and envyfreeness of the mechanisms under different risk attitude models.

Characterization and Computation of Equilibria for Indivisible Goods

Simina Brânzei, Hadi Hosseini, and Peter Bro Miltersen
Conference Paper In SAGT-15: Proc. 8th Intl. Symposium on Algorithmic Game Theory, pp. 244-255, 2015.

Abstract

We consider the problem of allocating indivisible goods using the leading notion of fairness in economics: the competitive equilibrium from equal incomes. Focusing on two major classes of valuations, namely perfect substitutes and perfect complements, we establish the computational properties of algorithms operating in this framework. For the class of valuations with perfect complements, our algorithm yields a surprisingly succinct characterization of instances that admit a competitive equilibrium from equal incomes.

Matching with Dynamic Ordinal Preferences

Hadi Hosseini, Kate Larson, and Robin Cohen
Conference Paper In AAAI-15: Proc. of the 29th AAAI Conference on Artificial Intelligence, pp. 936-943, 2015.

Abstract

We consider the problem of repeatedly matching a set of alternatives to a set of agents with dynamic ordinal preferences. Despite a recent focus on designing one-shot matching mechanisms in the absence of monetary transfers, little study has been done on strategic behavior of agents in sequential assignment problems. We formulate a generic dynamic matching problem via a sequential stochastic matching process. We design a mechanism based on random serial dictatorship (RSD) that, given any history of preferences and matching decisions, guarantees global stochastic strategyproofness while satisfying desirable local properties. We further investigate the notion of envyfreeness in such sequential settings.

On Manipulability of Random Serial Dictatorship in Sequential Matching with Dynamic Preferences

Hadi Hosseini, Kate Larson, and Robin Cohen
Conference Paper In AAAI-15: Proc. of the 29th AAAI Conference on Artificial Intelligence, pp. 4168-4169, 2015.

Abstract

We consider the problem of repeatedly matching a set of alternatives to a set of agents in the absence of monetary transfer. We propose a generic framework for evaluating sequential matching mechanisms with dynamic preferences, and show that unlike single-shot settings, the random serial dictatorship mechanism is manipulable.

Voting with Social Influence: Using Arguments to Uncover Ground Truth

Alan Tsang, John A. Doucette, and Hadi Hosseini
Conference Paper In AAMAS-15: Proc. of the 14th International Conference on Autonomous Agents and Multiagent Systems, pp. 1841-1842, 2015.

Abstract

In certain voting problems, a hidden ground truth is inferred by aggregating the opinions of an electorate. We propose a novel model of these underlying social interactions, and derive maximum likelihood estimators for the ground truth in these models, given the social network and votes. We also evaluate these new estimators, as well as existing ones, on a class of simulated social networks.

Voting with Social Networks: Truth Springs from Argument Amongst Friends

John A. Doucette, Hadi Hosseini, Alan Tsang, Kate Larson, and Robin Cohen
Conference Paper In EXPLORE at AAMAS-15: Proc. The 2nd Workhop on Exploring Beyond the Worst Case in Computational Social Choice, 2015.

Abstract

In certain voting problems, a central authority must infer a hidden ground truth by aggregating the opinions of an electorate. When individual assessments are drawn i.i.d. and are correct with probability p > 0.5, aggregating enough votes will yield the ground truth with high probability. However, in reality voters’ opinions are often influenced by those of their friends. In certain social networks, this interaction may cause the aggregated opinions to be misleading. A center may use the network structure to recover the original distribution of votes from the post-interaction opinions of voters, and so recover the ground truth in spite of confounding discussions. In this paper, we consider a series of novel models of these underlying social interactions, and derive maximum likelihood estimators for the ground truth in these models, given the social network and votes. We also evaluate these new estimators, as well as existing ones, on common classes of social networks, and derive analytical bounds on the estimators’ performance in different environments. In all, we provide important insights into admitting influence from peers during voting.

Modelling Culture with Complex, Multi-dimensional, Multi-agent Systems

Alexis Morris, William Ross, Hadi Hosseini, and Mihaela Ulieru
Book Chapter Springer International Publishing | 2014 | ISBN-10: 978-3-319-01952-9, pp. 13-30, 2014.
image

Perspectives on Culture and Agent-based Simulations

Culture plays a significant role in human civilizations as a key determinant of relationships and organization formation; however, its role, key properties, and mechanisms are not yet fully understood. This work explores culture and cultural modelling from a complex systems, multi-dimensional, and multi-agency standpoint. The need for performing such modelling and simulation is evident since in-vivo organizational experiments are costly, not easily generalizable, and require lengthy analyses that may not be feasible in critical situations. Exploring the role and influence of culture on organizations is the aim of this chapter, whereby definitions, dimensions, and experiments are introduced in order to show the evolution and emergence of culture as a complex, distributed, social system. This work contributes to culture studies by (a) adding to the literature of culture as a complex system, (b) presenting a new seven-dimensional model to describe and encapsulate culture, and (c) simulating cultural interactions using a multi-agent system of high-functioning agents that achieve an equilibrium of beliefs.

A Coordinated MDP Approach to Multi-Agent Planning for Resource Allocation, with Applications to Healthcare

Hadi Hosseini, Jesse Hoey, and Robin Cohen
Conference Paper In MSDM at AAMAS-13: Proc. The 8th Workhop on Multiagent Sequential Decision Making Under Uncertainty, 2013.

Abstract

This paper considers a novel approach to scalable multiagent resource allocation in dynamic settings. We propose an approximate solution in which each resource consumer is represented by an independent MDP-based agent that models expected utility using an average model of its expected access to resources given only limited information about all other agents. A global auction-based mechanism is proposed for allocations based on expected regret. We assume truthful bidding and a cooperative coordination mechanism, as we are considering healthcare scenarios. We illustrate the performance of our coordinated MDP approach against a Monte-Carlo based planning algorithm intended for large-scale applications, as well as other approaches suitable for allocating medical resources. The evaluations show that the global utility value across all consumer agents is closer to optimal when using our algorithms under certain time constraints, with low computational cost. As such, we offer a promising approach for addressing complex resource allocation problems that arise in healthcare settings.

Toffoli Gate Implementation Using The Billiard Ball Model

Hadi Hosseini and Gerhard W. Dueck
Journal Paper Journal of Multiple-Valued Logic and Soft Computing, Volume 19, Number 1-3, pp. 133-147, 2012.

Abstract

The billiard ball model (BBM) is a model demonstrating the ability to build reversible logic circuits with no energy waste. However, there are some physical limitations when dealing with the creation of such models. In this paper, we provide a brief overview on different gates in billiard ball model and then propose an approach to create a universal Toffoli gate in BBM. We discuss the complexities of building larger Toffoli gates and the ways to have multi-level connected Toffoli gates to represent arbitrary logic functions.

Leveraging Domain Knowledge to Learn Normative Behavior: A Bayesian Approach

Hadi Hosseini and Mihaela Ulieru
Conference Paper In ALA-11: Proc. of Adaptive and Learning Agents, pp. 70-84, 2012.

Abstract

This paper addresses the problem of norm adaptation using Bayesian reinforcement learning. We are concerned with the effectiveness of adding prior domain knowledge when facing environments with different settings as well as with the speed of adapting to a new environment. Individuals develop their normative framework via interaction with their surrounding environment (including other individuals). An agent acquires the domain-dependent knowledge in a certain environment and later reuses them in different settings. This work is novel in that it represents normative behaviors as probabilities over belief sets. We propose a two-level learning framework to learn the values of normative actions and set them as prior knowledge, when agents are confident about them, to feed them back to their belief sets. Developing a prior belief set about a certain domain can improve an agent’s learning process to adjust its norms to the new environment’s dynamics. Our evaluation shows that a normative agent, having been trained in an initial environment, is able to adjust its beliefs about the dynamics and behavioral norms in a new environment. Therefore, it converges to the optimal policy more quickly, especially in the early stages of learning.

Dynamic Multiagent Resource Allocation: Integrating Auctions and MDPs for Real-Time Decisions (Doctoral Consortium)

Hadi Hosseini
Conference Paper In AAAI-12: Proc. of the 26th AAAI Conference on Artificial Intelligence, pp. 2394-2395, 2012.

Abstract

Multiagent resource allocation under uncertainty raises various computational challenges in terms of efficiency such as intractability, communication cost, and preference representation. To date most approaches do not provide efficient solutions for dynamic environments where temporal constraints pose particular challenges. We propose two techniques to cope with such settings: auctions to allocate fairly according to preferences, and MDPs to address stochasticity. This research seeks to determine the ideal combination between the two methods to handle wide range of allocation problems with reduced computation and communication cost between agents.

A Market-Based Coordination Mechanism for Resource Planning Under Uncertainty

Hadi Hosseini, Jesse Hoey, and Robin Cohen
Conference Paper In AAAI-12: Proc. of the 26th AAAI Conference on Artificial Intelligence, pp. 2427-2428, 2012.

Abstract

Multiagent resource allocation under uncertainty raises various computational challenges in terms of efficiency such as intractability, communication cost, and preference representation. To date most approaches do not provide efficient solutions for dynamic environments where temporal constraints pose particular challenges. We propose two techniques to cope with such settings: auctions to allocate fairly according to preferences, and MDPs to address stochasticity. This research seeks to determine the ideal combination between the two methods to handle wide range of allocation problems with reduced computation and communication cost between agents.

A Market-Based Bug Allocation Mechanism Using Predictive Bug Lifetimes

Hadi Hosseini, Raymond Nguyen, and Michael W. Godfrey
Conference Paper In CSMR-12: Proc. of the 16th European Conference on Software Maintenance and Re-engineering, pp. 2427-2428, 2012.

Abstract

Bug assignment in large software projects is typically a time-consuming and tedious task, effective assignment requires that bug triagers hold significant contextual information about both the reported bugs and the pool of available developers. In this paper, we propose an auction-based multiagent mechanism for assigning bugs to developers that is intended to minimize backlogs and overall bug lifetime. In this approach, developers and triagers are both modeled as intelligent software agents working on behalf of individuals in a multiagent environment. Upon receiving a bug report, triager agents auction off the bug and collect the requests. Developer agents compute their bids as a function of the developer's profile, preferences, current schedule of assigned bugs, and estimated time-to-fix of the bug. This value is then sent to the triager agent for the final decision. We use the Eclipse and Fire fox bug repositories to validate our approach, our studies suggest that the proposed auction-based multiagent mechanism can improve the bug assignment process compared to currently practiced methods. In particular, we found a 16% improvement in the number of fixed bugs compared to the historic data, based on a sample size of 213,000 bug reports over a period of 6 years.

Toffoli Gate Implementation Using The Billiard Ball Model

Hadi Hosseini and Gerhard W. Dueck
Conference Paper In ISMVL-10: Proc. of 40th IEEE International Symposium on Multiple-Valued Logic, pp. 173-178, 2010.

Abstract

In this paper we review the Billiard Ball Model (BBM) introduced by Toffoli and Fredkin. The analysis of a previous approach to design reversible networks based on BBM it shown to ignored physical realities. We prove that some logic function cannot be realized without additional control balls. For example, to realize the logical OR operation, at least three control balls are needed. We show how reversible Toffoli gates can be constructed with this model. Finally, a Toffoli gate module is proposed that can be used in a cascade of gates and thus implement arbitrary reversible functions.

Building Large Toffoli Gates: A Billiard Ball Model Approach

Hadi Hosseini and Gerhard W. Dueck
Conference Paper In IWBP-10: Proc. of 9th International Workshop on Boolean Problems, 2010.

Abstract

An autonomous agent-based framework for self-healing power grid

Zeinab Noorian, Hadi Hosseini, and Mihaela Ulieru
Conference Paper In SMC-09: Proc. of IEEE International Conference on Systems, Man and Cybernetics, pp. 1983--1988, 2009.