ORCID Profile
0000-0001-9757-4956
Current Organisations
Data61
,
UNSW Sydney
Does something not look right? The information on this page has been harvested from data sources that may not be up to date. We continue to work with information providers to improve coverage and quality. To report an issue, use the Feedback Form.
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 07-2018
Abstract: We introduce and study the class of egalitarian variants of committee scoring rules, where instead of summing up the scores that voters assign to committees---as is done in the utilitarian variants---the score of a committee is taken to be the lowest score assigned to it by any voter. We focus on five rules, which are egalitarian analogues of SNTV, the k-Borda rule, the Chamberlin--Courant rule, the Bloc rule, and the Pessimist rule. We establish their computational complexity, provide their initial axiomatic study, and perform experiments to represent the action of these rules graphically.
Publisher: Springer Science and Business Media LLC
Date: 09-01-2017
Publisher: Springer International Publishing
Date: 2014
Publisher: Cambridge University Press
Date: 25-04-2016
Publisher: Association for Computing Machinery (ACM)
Date: 24-02-2017
Abstract: Although a finite envy-free cake-cutting protocol has been known for more than twenty years, it had been open whether a protocol exists in which the number of steps taken by the protocol is bounded by a function of the number of agents. In this letter, we report on our recent results on discrete, bounded, and envy-free cake-cutting protocols.
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 08-2019
Abstract: We consider mechanisms for the online allocation of perishable resources such as energy or computational power. A main application is electric vehicle charging where agents arrive and leave over time. Unlike previous work, we consider mechanisms without money, and a range of objectives including fairness and efficiency. In doing so, we extend the concept of envy-freeness to online settings. Furthermore, we explore the trade-offs between different objectives and analyse their theoretical properties both in online and offline settings. We then introduce novel online scheduling algorithms and compare them in terms of both their theoretical properties and empirical performance.
Publisher: ACM
Date: 19-06-2016
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 08-2017
Abstract: The assignment problem is one of the most well-studied settings in social choice, matching, and discrete allocation. We consider this problem with the additional feature that agents' preferences involve uncertainty. The setting with uncertainty leads to a number of interesting questions including the following ones. How to compute an assignment with the highest probability of being Pareto optimal? What is the complexity of computing the probability that a given assignment is Pareto optimal? Does there exist an assignment that is Pareto optimal with probability one? We consider these problems under two natural uncertainty models: (1) the lottery model in which each agent has an independent probability distribution over linear orders and (2) the joint probability model that involves a joint probability distribution over preference profiles. For both of these models, we present a number of algorithmic and complexity results highlighting the difference and similarities in the complexity of the two models.
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 08-2017
Abstract: We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein and is majoritarian in spirit. The second one, local stability, is introduced in this paper, and focuses on voter representation. The goal of this paper is to explore these two notions, their implications on restricted domains, and the computational complexity of rules that are consistent with them.
Publisher: Elsevier BV
Date: 09-2018
Publisher: Springer Science and Business Media LLC
Date: 04-12-2020
Publisher: Association for Computing Machinery (ACM)
Date: 28-01-2015
Abstract: Two fundamental problems in economics are voting and assignment. In both settings, random serial dictatorship is a well-established mechanism that satisfies anonymity, ex post efficiency, and strategyproofness. We present an overview of recent results on the computational complexity of problems related to random serial dictatorship.
Publisher: AI Access Foundation
Date: 10-03-2020
DOI: 10.1613/JAIR.1.11994
Abstract: Ranking alternatives is a natural way for humans to explain their preferences. It is used in many settings, such as school choice, course allocations and residency matches. Without having any information on the underlying cardinal utilities, arguing about the fairness of allocations requires extending the ordinal item ranking to ordinal bundle ranking. The most commonly used such extension is stochastic dominance (SD), where a bundle X is preferred over a bundle Y if its score is better according to all additive score functions. SD is a very conservative extension, by which few allocations are necessarily fair while many allocations are possibly fair. We propose to make a natural assumption on the underlying cardinal utilities of the players, namely that the difference between two items at the top is larger than the difference between two items at the bottom. This assumption implies a preference extension which we call diminishing differences (DD), where X is preferred over Y if its score is better according to all additive score functions satisfying the DD assumption. We give a full characterization of allocations that are necessarily-proportional or possibly-proportional according to this assumption. Based on this characterization, we present a polynomial-time algorithm for finding a necessarily-DD-proportional allocation whenever it exists. Using simulations, we compare the various fairness criteria in terms of their probability of existence, and their probability of being fair by the underlying cardinal valuations. We find that necessary-DD-proportionality fares well in both measures. We also consider envy-freeness and Pareto optimality under diminishing-differences, as well as chore allocation under the analogous condition --- increasing-differences.
Publisher: Association for Computing Machinery (ACM)
Date: 31-05-2019
DOI: 10.1145/3327970
Abstract: The work we present in this article initiated the formal study of fractional hedonic games (FHGs), coalition formation games in which the utility of a player is the average value he ascribes to the members of his coalition. Among other settings, this covers situations in which players only distinguish between friends and non-friends and desire to be in a coalition in which the fraction of friends is maximal. FHGs thus not only constitute a natural class of succinctly representable coalition formation games but also provide an interesting framework for network clustering. We propose a number of conditions under which the core of FHGs is non-empty and provide algorithms for computing a core stable outcome. By contrast, we show that the core may be empty in other cases, and that it is computationally hard in general to decide non-emptiness of the core.
Publisher: Springer Science and Business Media LLC
Date: 03-04-2019
Publisher: Elsevier BV
Date: 09-2020
Publisher: No publisher found
Date: 2020
Publisher: Elsevier BV
Date: 11-2015
Publisher: Elsevier BV
Date: 10-2019
Publisher: Association for Computing Machinery (ACM)
Date: 03-2010
Publisher: Association for Computing Machinery (ACM)
Date: 03-2010
Publisher: IEEE
Date: 12-2007
Publisher: Elsevier BV
Date: 05-2022
Publisher: ACM
Date: 27-12-2018
Publisher: Springer Science and Business Media LLC
Date: 14-11-2019
DOI: 10.1007/S00453-019-00650-0
Abstract: We consider the two-sided stable matching setting in which there may be uncertainty about the agents’ preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model—for each agent, there is a probability distribution over linear preferences, (2) compact indifference model—for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability model—there is a lottery over preference profiles. For each of the models, we study the computational complexity of computing the stability probability of a given matching as well as finding a matching with the highest probability of being stable. We also examine more restricted problems such as deciding whether a certainly stable matching exists. We find a rich complexity landscape for these problems, indicating that the form uncertainty takes is significant.
Publisher: No publisher found
Date: 2009
Publisher: Springer Berlin Heidelberg
Date: 2016
Publisher: Association for the Advancement of Artificial Intelligence (AAAI)
Date: 17-07-2019
DOI: 10.1609/AAAI.V33I01.33011740
Abstract: The assignment problem is one of the most well-studied settings in multi-agent resource allocation. Aziz, de Haan, and Rastegari (2017) considered this problem with the additional feature that agents’ preferences involve uncertainty. In particular, they considered two uncertainty models neither of which is necessarily compact. In this paper, we focus on three uncertain preferences models whose size is polynomial in the number of agents and items. We consider several interesting computational questions with regard to Pareto optimal assignments. We also present some general characterization and algorithmic results that apply to large classes of uncertainty models.
Publisher: Springer International Publishing
Date: 2019
Publisher: Springer Berlin Heidelberg
Date: 2009
Publisher: AI Access Foundation
Date: 20-01-2011
DOI: 10.1613/JAIR.3166
Abstract: Weighted voting is a classic model of cooperation among agents in decision-making domains. In such games, each player has a weight, and a coalition of players wins the game if its total weight meets or exceeds a given quota. A player's power in such games is usually not directly proportional to his weight, and is measured by a power index, the most prominent among which are the Shapley-Shubik index and the Banzhaf index.In this paper, we investigate by how much a player can change his power, as measured by the Shapley-Shubik index or the Banzhaf index, by means of a false-name manipulation, i.e., splitting his weight among two or more identities. For both indices, we provide upper and lower bounds on the effect of weight-splitting. We then show that checking whether a beneficial split exists is NP-hard, and discuss efficient algorithms for restricted cases of this problem, as well as randomized algorithms for the general case. We also provide an experimental evaluation of these algorithms. Finally, we examine related forms of manipulative behavior, such as annexation, where a player subsumes other players, or merging, where several players unite into one. We characterize the computational complexity of such manipulations and provide limits on their effects. For the Banzhaf index, we describe a new paradox, which we term the Annexation Non-monotonicity Paradox.
Publisher: Elsevier BV
Date: 07-2013
Publisher: Association for Computing Machinery (ACM)
Date: 13-12-2011
Publisher: Oxford University Press (OUP)
Date: 12-01-2018
DOI: 10.1093/IJE/DYX251
Publisher: No publisher found
Date: 2011
Publisher: Elsevier BV
Date: 07-2018
Publisher: Elsevier BV
Date: 02-2013
Publisher: Oxford University Press (OUP)
Date: 17-06-2021
Abstract: Is cord blood DNA methylation associated with having been conceived by medically assisted reproduction? This study does not provide strong evidence of an association of conception by medically assisted reproduction with variation in infant blood cell DNA methylation. Medically assisted reproduction consists of procedures used to help infertile/subfertile couples conceive, including ART. Due to its importance in gene regulation during early development programming, DNA methylation and its perturbations associated with medically assisted reproduction could reveal new insights into the biological effects of assisted reproductive technologies and potential adverse offspring outcomes. We investigated the association of DNA methylation and medically assisted reproduction using a case–control study design (N = 205 medically assisted reproduction cases and N = 2439 naturally conceived controls in discovery cohorts N = 149 ART cases and N = 58 non-ART controls in replication cohort). We assessed the association between medically assisted reproduction and DNA methylation at birth in cord blood (205 medically assisted conceptions and 2439 naturally conceived controls) at & 000 CpG sites across the genome in two sub-s les of the UK Avon Longitudinal Study of Parents and Children (ALSPAC) and two sub-s les of the Norwegian Mother, Father and Child Cohort Study (MoBa) by meta-analysis. We explored replication of findings in the Australian Clinical review of the Health of adults conceived following Assisted Reproductive Technologies (CHART) study (N = 149 ART conceptions and N = 58 controls). The ALSPAC and MoBa meta-analysis revealed evidence of association between conception by medically assisted reproduction and DNA methylation (false-discovery-rate-corrected P-value & 0.05) at five CpG sites which are annotated to two genes (percentage difference in methylation per CpG, cg24051276: Beta = 0.23 (95% CI 0.15,0.31) cg00012522: Beta = 0.47 (95% CI 0.31, 0.63) cg17855264: Beta = 0.31 (95% CI 0.20, 0.43) cg17132421: Beta = 0.30 (95% CI 0.18, 0.42) cg18529845: Beta = 0.41 (95% CI 0.25, 0.57)). Methylation at three of these sites has been previously linked to cancer, aging, HIV infection and neurological diseases. None of these associations replicated in the CHART cohort. There was evidence of a functional role of medically assisted reproduction-induced hypermethylation at CpG sites located within regulatory regions as shown by putative transcription factor binding and chromatin remodelling. While insufficient power is likely, heterogeneity in types of medically assisted reproduction procedures and between populations may also contribute. Larger studies might identify replicable variation in DNA methylation at birth due to medically assisted reproduction. Newborns conceived with medically assisted procedures present with ergent DNA methylation in cord blood white cells. If these associations are true and causal, they might have long-term consequences for offspring health. This study has been supported by the US National Institute of Health (R01 DK10324), the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ERC Grant agreement no. 669545, European Union’s Horizon 2020 research and innovation programme under Grant agreement no. 733206 (LifeCycle) and the NIHR Biomedical Centre at the University Hospitals Bristol NHS Foundation Trust and the University of Bristol. The UK Medical Research Council and Wellcome (Grant ref: 102215/2/13/2) and the University of Bristol provide core support for ALSPAC. Methylation data in the ALSPAC cohort were generated as part of the UK BBSRC funded (BB/I025751/1 and BB/I025263/1) Accessible Resource for Integrated Epigenomic Studies (ARIES, www.ariesepigenomics.org.uk). D.C., J.J., C.L.R. D.A.L and H.R.E. work in a Unit that is supported by the University of Bristol and the UK Medical Research Council (Grant nos. MC_UU_00011/1, MC_UU_00011/5 and MC_UU_00011/6). B.N. is supported by an NHMRC (Australia) Investigator Grant (1173314). ALSPAC GWAS data were generated by S le Logistics and Genotyping Facilities at Wellcome Sanger Institute and LabCorp (Laboratory Corporation of America) using support from 23andMe. The Norwegian Mother, Father and Child Cohort Study is supported by the Norwegian Ministry of Health and Care Services and the Ministry of Education and Research, NIH/NIEHS (Contract no. N01-ES-75558), NIH/NINDS (Grant nos. (i) UO1 NS 047537-01 and (ii) UO1 NS 047537-06A1). For this work, MoBa 1 and 2 were supported by the Intramural Research Program of the NIH, National Institute of Environmental Health Sciences (Z01-ES-49019) and the Norwegian Research Council/BIOBANK (Grant no. 221097). This work was partly supported by the Research Council of Norway through its Centres of Excellence funding scheme, Project no. 262700. D.A.L. has received support from national and international government and charity funders, as well as from Roche Diagnostics and Medtronic for research unrelated to this study. The other authors declare no conflicts of interest. N/A.
Publisher: Springer International Publishing
Date: 2020
Publisher: Springer Science and Business Media LLC
Date: 05-09-2019
Publisher: Springer Berlin Heidelberg
Date: 2011
Publisher: Association for Computing Machinery (ACM)
Date: 17-03-2014
Publisher: Association for Computing Machinery (ACM)
Date: 27-08-2012
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 07-2020
Abstract: We study the controlled school choice problem where students may belong to overlapping types and schools have soft target quotas for each type. We formalize fairness concepts for the setting that extend fairness concepts considered for restricted settings without overlapping types. Our central contribution is presenting a new class of algorithms that takes into account the representations of combinations of student types. The algorithms return matchings that are non-wasteful and satisfy fairness for same types. We further prove that the algorithms are strategyproof for the students and yield a fair outcome with respect to the induced quotas for type combinations. We experimentally compare our algorithms with two existing approaches in terms of achieving ersity goals and satisfying fairness.
Publisher: Springer Science and Business Media LLC
Date: 20-02-2014
Publisher: Association for Computing Machinery (ACM)
Date: 27-08-2012
Publisher: IEEE
Date: 10-2016
DOI: 10.1109/FOCS.2016.52
Publisher: Elsevier BV
Date: 11-2013
Publisher: Elsevier BV
Date: 10-2015
Publisher: Elsevier BV
Date: 10-2019
Publisher: Association for Computing Machinery (ACM)
Date: 16-10-2020
DOI: 10.1145/3417738
Abstract: We consider a setting in which agents vote to choose a fair mixture of public outcomes. The agents have dichotomous preferences: Each outcome is liked or disliked by an agent. We discuss three outstanding voting rules. The Conditional Utilitarian rule, a variant of the random dictator, is strategyproof and guarantees to any group of like-minded agents an influence proportional to its size. It is easier to compute and more efficient than the familiar Random Priority rule. We show, both formally and by numerical experiments, that its inefficiency is low when the number of agents is low. The efficient Egalitarian rule protects in idual agents but not coalitions. It is excludable strategyproof : An agent does not want to lie if she cannot consume outcomes she claims to dislike. The efficient Max Nash Product rule offers the strongest welfare guarantees to coalitions, which can force any outcome with a probability proportional to their size. But it even fails the excludable form of strategyproofness.
Publisher: Association for Computing Machinery (ACM)
Date: 10-03-2016
Publisher: Elsevier BV
Date: 11-2014
Publisher: Springer Science and Business Media LLC
Date: 07-2014
Publisher: Elsevier BV
Date: 11-2017
Publisher: Springer Science and Business Media LLC
Date: 20-02-2014
Publisher: Elsevier BV
Date: 11-2019
Publisher: Springer Science and Business Media LLC
Date: 23-12-2015
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 07-2020
Abstract: We consider a multi-agent resource allocation setting in which an agent's utility may decrease or increase when an item is allocated. We take the group envy-freeness concept that is well-established in the literature and present stronger and relaxed versions that are especially suitable for the allocation of in isible items. Of particular interest is a concept called group envy-freeness up to one item (GEF1). We then present a clear taxonomy of the fairness concepts. We study which fairness concepts guarantee the existence of a fair allocation under which preference domain. For two natural classes of additive utilities, we design polynomial-time algorithms to compute a GEF1 allocation. We also prove that checking whether a given allocation satisfies GEF1 is coNP-complete when there are either only goods, only chores or both.
Publisher: No publisher found
Date: 2019
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
Date: 2014
Publisher: No publisher found
Date: 2013
Publisher: Springer Science and Business Media LLC
Date: 29-05-2017
Publisher: Springer Berlin Heidelberg
Date: 2013
Publisher: Elsevier BV
Date: 09-2019
Publisher: Springer Science and Business Media LLC
Date: 05-2019
Publisher: Elsevier BV
Date: 09-2013
Publisher: Springer Science and Business Media LLC
Date: 09-08-2020
Publisher: Association for Computing Machinery (ACM)
Date: 28-01-2020
Abstract: It is standard in computational social choice to analyse welfare considerations under the assumptions of normalized utilities. In this note, we summarize some common reasons for this approach. We then mention another justification which is ignored but has solid normative appeal. The central concept used in the `new' justification can also be used more widely as a social objective.
Publisher: No publisher found
Date: 2014
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 08-2017
Abstract: We consider the problem of deleting nodes in a covert network to minimize its performance. The inverse geodesic length (IGL) is a well-known and widely used measure of network performance. It equals the sum of the inverse distances of all pairs of vertices. In the MinIGL problem the input is a graph $G$, a budget $k$, and a target IGL $T$, and the question is whether there exists a subset of vertices $X$ with $|X|=k$, such that the IGL of $G-X$ is at most $T$. In network analysis, the IGL is often used to evaluate how well heuristics perform in strengthening or weakening a network. In this paper, we undertake a study of the classical and parameterized complexity of the MinIGL problem. The problem is NP-complete even if $T=0$ and remains both NP-complete and $W[1]$-hard for parameter $k$ on bipartite and on split graphs. On the positive side, we design several multivariate algorithms for the problem. Our main result is an algorithm for MinIGL parameterized by the twin cover number.
Publisher: Springer Berlin Heidelberg
Date: 2013
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 08-2019
Abstract: We initiate the work on fair and strategyproof allocation of in isible chores. The fairness concept we consider in this paper is maxmin share (MMS) fairness. We consider three previously studied models of information elicited from the agents: the ordinal model, the cardinal model, and the public ranking model in which the ordinal preferences are publicly known. We present both positive and negative results on the level of MMS approximation that can be guaranteed if we require the algorithm to be strategyproof. Our results uncover some interesting contrasts between the approximation ratios achieved for chores versus goods.
Publisher: ACM
Date: 06-2014
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 08-2019
Abstract: We consider the problem of fairly iding a set of items. Much of the fair ision literature assumes that the items are ``goods'' i.e., they yield positive utility for the agents. There is also some work where the items are ``chores'' that yield negative utility for the agents. In this paper, we consider a more general scenario where an agent may have negative or positive utility for each item. This framework captures, e.g., fair task assignment, where agents can have both positive and negative utilities for each task. We show that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We present several new and efficient algorithms for finding fair allocations in this general setting. We also point out several gaps in the literature regarding the existence of allocations satisfying certain fairness and efficiency properties and further study the complexity of computing such allocations.
Publisher: Association for Computing Machinery (ACM)
Date: 07-2009
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 08-2019
Abstract: We initiate the study of in isible chore allocation for agents with asymmetric shares. The fairness concept we focus on is the weighted natural generalization of maxmin share: WMMS fairness and OWMMS fairness. We first highlight the fact that commonly-used algorithms that work well for allocation of goods to asymmetric agents, and even for chores to symmetric agents do not provide good approximations for allocation of chores to asymmetric agents under WMMS. As a consequence, we present a novel polynomial-time constant-approximation algorithm, via linear program, for OWMMS. For two special cases: the binary valuation case and the 2-agent case, we provide exact or better constant-approximation algorithms.
Publisher: Springer Science and Business Media LLC
Date: 17-02-2020
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 2016
DOI: 10.1109/MIS.2016.7
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 08-2019
Abstract: A public isible resource is to be ided among projects. We study rules that decide on a distribution of the budget when voters have ordinal preference rankings over projects. Ex les of such portioning problems are participatory budgeting, time shares, and parliament elections. We introduce a family of rules for portioning, inspired by positional scoring rules. Rules in this family are given by a scoring vector (such as plurality or Borda) associating a positive value with each rank in a vote, and an aggregation function such as leximin or the Nash product. Our family contains well-studied rules, but most are new. We discuss computational and normative properties of our rules. We focus on fairness, and introduce the SD-core, a group fairness notion. Our Nash rules are in the SD-core, and the leximin rules satisfy in idual fairness properties. Both are Pareto-efficient.
Publisher: AI Access Foundation
Date: 16-12-2015
DOI: 10.1613/JAIR.4856
Abstract: We study the problem of computing possible and necessary winners for partially specified weighted and unweighted tournaments. This problem arises naturally in elections with incompletely specified votes, partially completed sports competitions, and more generally in any scenario where the outcome of some pairwise comparisons is not yet fully known. We specifically consider a number of well-known solution concepts---including the uncovered set, Borda, ranked pairs, and maximin---and show that for most of them, possible and necessary winners can be identified in polynomial time. These positive algorithmic results stand in sharp contrast to earlier results concerning possible and necessary winners given partially specified preference profiles.
Publisher: Elsevier BV
Date: 12-2013
Publisher: Association for Computing Machinery (ACM)
Date: 16-03-2016
Abstract: Fair allocation of in isible objects under ordinal preferences is an important problem. Unfortunately, a fairness notion like envy- freeness is both incompatible with Pareto optimality and is also NP-complete to achieve. To tackle this predicament, we consider a different notion of fairness, namely proportionality. We frame allocation of in isible objects as randomized assignment but with integrality requirements. We then use the stochastic dominance relation to define two natural notions of proportionality. Since an assignment may not exist even for the weaker notion of proportionality, we propose relaxations of the concepts --- optimal weak proportionality and optimal proportionality. For both concepts, we propose algorithms to compute fair assignments under ordinal preferences. Both new fairness concepts appear to be desirable in view of the following: they are compatible with Pareto optimality, admit efficient algorithms to compute them, are based on proportionality, and are guaranteed to exist.
Publisher: Springer Berlin Heidelberg
Date: 2009
Publisher: AI Access Foundation
Date: 06-08-2016
DOI: 10.1613/JAIR.5021
Abstract: We survey existing rules of thumb, propose novel methods, and comprehensively evaluate a number of solutions to the problem of calculating the cost to serve each location in a single-vehicle transport setting. Cost to serve analysis has applications both strategically and operationally in transportation settings. The problem is formally modeled as the traveling salesperson game (TSG), a cooperative transferable utility game in which agents correspond to locations in a traveling salesperson problem (TSP). The total cost to serve all locations in the TSP is the length of an optimal tour. An allocation ides the total cost among in idual locations, thus providing the cost to serve each of them. As one of the most important normative ision schemes in cooperative games, the Shapley value gives a principled and fair allocation for a broad variety of games including the TSG. We consider a number of direct and s ling-based procedures for calculating the Shapley value, and prove that approximating the Shapley value of the TSG within a constant factor is NP-hard. Treating the Shapley value as an ideal baseline allocation, we survey six proxies for it that are each relatively easy to compute. Some of these proxies are rules of thumb and some are procedures international delivery companies use(d) as cost allocation methods. We perform an experimental evaluation using synthetic Euclidean games as well as games derived from real-world tours calculated for scenarios involving fast-moving goods where deliveries are made on a road network every day. We explore several computationally tractable allocation techniques that are good proxies for the Shapley value in problem instances of a size and complexity that is commercially relevant.
Publisher: No publisher found
Date: 2013
Publisher: Springer Science and Business Media LLC
Date: 10-02-2015
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 08-2017
Abstract: Ranking alternatives is a natural way for humans to explain their preferences. It is being used in many settings, such as school choice (NY, Boston), Course allocations, and the Israeli medical lottery. In some cases (such as the latter two), several ``items'' are given to each participant. Without having any information on the underlying cardinal utilities, arguing about fairness of allocation requires extending the ordinal item ranking to ordinal bundle ranking. The most commonly used such extension is stochastic dominance (SD), where a bundle X is preferred over a bundle Y if its score is better according to all additive score functions. SD is a very conservative extension, by which few allocations are necessarily fair while many allocations are possibly fair. We propose to make a natural assumption on the underlying cardinal utilities of the players, namely that the difference between two items at the top is larger than the difference between two items at the bottom. This assumption implies a preference extension which we call diminishing differences (DD), where a X is preferred over Y if its score is better according to all additive score functions satisfying the DD assumption. We give a full characterization of allocations that are necessarily-proportional or possibly-proportional according to this assumption. Based on this characterization, we present a polynomial-time algorithm for finding a necessarily-DD-proportional allocation if it exists. Using simulations, we show that with high probability, a necessarily-proportional allocation does not exist but a necessarily-DD-proportional allocation exists, and moreover, that allocation is proportional according to the underlying cardinal utilities.
Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
Date: 30-01-2023
Abstract: Consider the problem of allocating in isible goods among agents with additive valuations, where monetary payments are not allowed. When randomization is allowed, it is possible to achieve compelling notions of fairness such as EV, which states that no agent should prefer any other agent's allocation to their own. When allocations must be deterministic, achieving exact fairness is impossible but approximate notions such as EV up to one good can be guaranteed. In “Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation,” H. Aziz, R. Freeman, N. Shah, and R. Vaish ask whether it is possible to achieve both types of guarantees simultaneously. More specifically, they ask whether there exists a probability distribution over deterministic allocations such that every deterministic allocation is envy-free up to one good and the distribution is exactly envy-free in expectation. The main result of the paper answers this question in the affirmative, showing that ex ante and ex post fairness need not be in conflict.
Publisher: Elsevier BV
Date: 11-2017
Publisher: No publisher found
Date: 2017
Publisher: Elsevier BV
Date: 11-2020
Publisher: Elsevier BV
Date: 09-2018
Publisher: No publisher found
Date: 2016
Publisher: Association for Computing Machinery (ACM)
Date: 20-03-2020
DOI: 10.1145/3382129
Abstract: We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation of a isible resource based on queries from agents. The problem has received attention in mathematics, economics, and computer science. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. We report on our algorithm that resolved the open problem.
Publisher: Springer International Publishing
Date: 2017
Publisher: No publisher found
Date: 2009
Location: United Kingdom of Great Britain and Northern Ireland
No related grants have been discovered for Haris Aziz.