Author name cluster

Rupert Freeman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

22 papers

2 author rows

AAMAS Conference 2025 Conference Paper

Order Symmetry: A New Fairness Criterion for Assignment Mechanisms

Rupert Freeman
Geoffrey Pritchard
Mark C. Wilson

We introduce a new criterion, order symmetry, for assignment mechanisms that match 𝑛 objects to 𝑛 agents having ordinal preferences over the objects. An assignment mechanism is order-symmetric with respect to a given probability measure over preference profiles if every agent has equal probability of receiving their favorite object, equal probability of receiving their second favorite, and so on. Crucially, and unlike other fairness notions such as anonymity or envy-freeness, order symmetry can be satisfied by discrete assignment mechanisms when associated with a sufficiently symmetric probability measure. It can also be interpreted as a criterion of procedural fairness or fairness under uncertainty. Furthermore, it can be achieved without sacrificing other desirable axiomatic properties satisfied by existing mechanisms. In particular, we show that it can be achieved in conjunction with strategyproofness and efficiency by the Top Trading Cycles mechanism, but not by Serial Dictatorship. We also use the lens of order symmetry to improve the fairness of existing mechanisms with no loss in social welfare, focusing on the widely used family of Boston mechanisms. In addition to theoretical results, we present simulations using data from the Mallows distribution over its full range of parameters, which show an improvement in fairness even on probability measures for which full order symmetry is impossible.

PDF

AAAI Conference 2024 Conference Paper

Project-Fair and Truthful Mechanisms for Budget Aggregation

Rupert Freeman
Ulrike Schmidt-Kraepelin

We study the budget aggregation problem in which a set of strategic voters must split a finite divisible resource (such as money or time) among a set of competing projects. Our goal is twofold: We seek truthful mechanisms that provide fairness guarantees to the projects. For the first objective, we focus on the class of moving phantom mechanisms, which are -- to this day -- essentially the only known truthful mechanisms in this setting. For project fairness, we consider the mean division as a fair baseline, and bound the maximum difference between the funding received by any project and this baseline. We propose a novel and simple moving phantom mechanism that provides optimal project fairness guarantees. As a corollary of our results, we show that our new mechanism minimizes the L1 distance to the mean for three projects and gives the first non-trivial bounds on this quantity for more than three projects.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Efficient Resource Allocation with Secretive Agents

Soroush Ebadian
Rupert Freeman
Nisarg Shah

We consider the allocation of homogeneous divisible goods to agents with linear additive valuations. Our focus is on the case where some agents are secretive and reveal no preference information, while the remaining agents reveal full preference information. We study distortion, which is the worst-case approximation ratio when maximizing social welfare given such partial information about agent preferences. As a function of the number of secretive agents k relative to the overall number of agents n, we identify the exact distortion for every p-mean welfare function, which includes the utilitarian welfare (p=1), the Nash welfare (p -> 0), and the egalitarian welfare (p -> -Inf).

PDF Details DOI

IJCAI Conference 2021 Conference Paper

Two-Sided Matching Meets Fair Division

Rupert Freeman
Evi Micha
Nisarg Shah

We introduce a new model for two-sided matching which allows us to borrow popular fairness notions from the fair division literature such as envy-freeness up to one good and maximin share guarantee. In our model, each agent is matched to multiple agents on the other side over whom she has additive preferences. We demand fairness for each side separately, giving rise to notions such as double envy-freeness up to one match (DEF1) and double maximin share guarantee (DMMS). We show that (a slight strengthening of) DEF1 cannot always be achieved, but in the special case where both sides have identical preferences, the round-robin algorithm with a carefully designed agent ordering achieves it. In contrast, DMMS cannot be achieved even when both sides have identical preferences.

PDF Details DOI

ICML Conference 2020 Conference Paper

No-Regret and Incentive-Compatible Online Learning

Rupert Freeman
David M. Pennock
Chara Podimata
Jennifer Wortman Vaughan

We study online learning settings in which experts act strategically to maximize their influence on the learning algorithm’s predictions by potentially misreporting their beliefs about a sequence of binary events. Our goal is twofold. First, we want the learning algorithm to be no-regret with respect to the best-fixed expert in hindsight. Second, we want incentive compatibility, a guarantee that each expert’s best strategy is to report his true beliefs about the realization of each event. To achieve this goal, we build on the literature on wagering mechanisms, a type of multi-agent scoring rule. We provide algorithms that achieve no regret and incentive compatibility for myopic experts for both the full and partial information settings. In experiments on datasets from FiveThirtyEight, our algorithms have regret comparable to classic no-regret algorithms, which are not incentive-compatible. Finally, we identify an incentive-compatible algorithm for forward-looking strategic agents that exhibits diminishing regret in practice.

Details

AAAI Conference 2020 Conference Paper

Preventing Arbitrage from Collusion When Eliciting Probabilities

Rupert Freeman
David M. Pennock
Dominik Peters
Bo Waggoner

We consider the design of mechanisms to elicit probabilistic forecasts when agents are strategic and may collude with one another. Chun and Shachter (2011) have shown that when agents may form coalitions, many known mechanisms for elicitation permit arbitrage, allowing the coalition members to guarantee themselves higher payments by misreporting their beliefs. We consider two approaches to protect against colluding agents. First, we present a novel strictly proper mechanism that does not admit arbitrage provided that the reports of the agents are bounded away from 0 and 1, a common assumption in many settings. Second, we discover strictly arbitrage-free mechanisms that satisfy an intermediate guarantee between weak and strict properness.

PDF Details

IJCAI Conference 2020 Conference Paper

Proportionality in Approval-Based Elections With a Variable Number of Winners

Rupert Freeman
Anson Kahng
David M. Pennock

We study proportionality in approval-based multiwinner elections with a variable number of winners, where both the size and identity of the winning committee are informed by voters' opinions. While proportionality has been studied in multiwinner elections with a fixed number of winners, it has not been considered in the variable number of winners setting. The measure of proportionality we consider is average satisfaction (AS), which intuitively measures the number of agreements on average between sufficiently large and cohesive groups of voters and the output of the voting rule. First, we show an upper bound on AS that any deterministic rule can provide, and that straightforward adaptations of deterministic rules from the fixed number of winners setting do not achieve better than a 1/2 approximation to AS even for large numbers of candidates. We then prove that a natural randomized rule achieves a 29/32 approximation to AS.

PDF Details DOI

AAAI Conference 2019 Conference Paper

An Equivalence between Wagering and Fair-Division Mechanisms

Rupert Freeman
David M. Pennock
Jennifer Wortman Vaughan

We draw a surprising and direct mathematical equivalence between the class of allocation mechanisms for divisible goods studied in the context of fair division and the class of weakly budget-balanced wagering mechanisms designed for eliciting probabilities. The equivalence rests on the intuition that wagering is an allocation of financial securities among bettors, with a bettor’s value for each security proportional to her belief about the likelihood of a future event. The equivalence leads to theoretical advances and new practical approaches for both fair division and wagering. Known wagering mechanisms based on proper scoring rules yield fair allocation mechanisms with desirable properties, including the first strictly incentive compatible fair-division mechanism. At the same time, allocation mechanisms make for novel wagering rules, including one that requires only ordinal uncertainty judgments and one that outperforms existing rules in a range of simulations.

PDF Details

IJCAI Conference 2019 Conference Paper

Equitable Allocations of Indivisible Goods

Rupert Freeman
Sujoy Sikdar
Rohit Vaish
Lirong Xia

In fair division, equitability dictates that each participant receives the same level of utility. In this work, we study equitable allocations of indivisible goods among agents with additive valuations. While prior work has studied (approximate) equitability in isolation, we consider equitability in conjunction with other well-studied notions of fairness and economic efficiency. We show that the Leximin algorithm produces an allocation that satisfies equitability up to any good and Pareto optimality. We also give a novel algorithm that guarantees Pareto optimality and equitability up to one good in pseudopolynomial time. Our experiments on real-world preference data reveal that approximate envy-freeness, approximate equitability, and Pareto optimality can often be achieved simultaneously.

PDF Details

AAAI Conference 2019 Conference Paper

Group Fairness for the Allocation of Indivisible Goods

Vincent Conitzer
Rupert Freeman
Nisarg Shah
Jennifer Wortman Vaughan

We consider the problem of fairly dividing a collection of indivisible goods among a set of players. Much of the existing literature on fair division focuses on notions of individual fairness. For instance, envy-freeness requires that no player prefer the set of goods allocated to another player to her own allocation. We observe that an algorithm satisfying such individual fairness notions can still treat groups of players unfairly, with one group desiring the goods allocated to another. Our main contribution is a notion of group fairness, which implies most existing notions of individual fairness. Group fairness (like individual fairness) cannot be satisfied exactly with indivisible goods. Thus, we introduce two “up to one good” style relaxations. We show that, somewhat surprisingly, certain local optima of the Nash welfare function satisfy both relaxations and can be computed in pseudo-polynomial time by local search. Our experiments reveal faster computation and stronger fairness guarantees in practice.

PDF Details

IJCAI Conference 2018 Conference Paper

An Axiomatic View of the Parimutuel Consensus Mechanism

Rupert Freeman
David M. Pennock

We consider an axiomatic view of the Parimutuel Consensus Mechanism defined by Eisenberg and Gale (1959). The parimutuel consensus mechanism can be interpreted as a parimutuel market for wagering with a proxy that bets optimally on behalf of the agents, depending on the bets of the other agents. We show that the parimutuel consensus mechanism uniquely satisfies the desirable properties of Pareto optimality, individual rationality, budget balance, anonymity, sybilproofness and envy-freeness. While the parimutuel consensus mechanism does violate the key property of incentive compatibility, it is incentive compatible in the limit as the number of agents becomes large. Via simulations on real contest data, we show that violations of incentive compatibility are both rare and only minimally beneficial for the participants. This suggests that the parimutuel consensus mechanism is a reasonable mechanism for eliciting information in practice.

PDF Details

AAMAS Conference 2018 Conference Paper

An Axiomatic View of the Parimutuel Consensus Wagering Mechanism

Rupert Freeman
David M. Pennock

We consider an axiomatic view of the Parimutuel Consensus Mechanism defined by Eisenberg and Gale [6]. The parimutuel consensus mechanism can be interpreted as a parimutuel market for wagering with a proxy that bets optimally on behalf of the agents, depending on the bets of the other agents. We show that, while the parimutuel consensus mechanism does violate the key property of incentive compatibility, it is incentive compatible in the limit as the number of agents becomes large. Via simulations on real contest data, we show that violations of incentive compatibility are both rare and only minimally beneficial for the participants. This suggests that the parimutuel consensus mechanism is a reasonable mechanism for eliciting information in practice.

PDF

AAAI Conference 2018 Conference Paper

Incentive-Compatible Forecasting Competitions

Jens Witkowski
Rupert Freeman
Jennifer Vaughan
David Pennock
Andreas Krause

We consider the design of forecasting competitions in which multiple forecasters make predictions about one or more independent events and compete for a single prize. We have two objectives: (1) to award the prize to the most accurate forecaster, and (2) to incentivize forecasters to report truthfully, so that forecasts are informative and forecasters need not spend any cognitive effort strategizing about reports. Proper scoring rules incentivize truthful reporting if all forecasters are paid according to their scores. However, incentives become distorted if only the best-scoring forecaster wins a prize, since forecasters can often increase their probability of having the highest score by reporting extreme beliefs. Even if forecasters do report truthfully, awarding the prize to the forecaster with highest score does not guarantee that high-accuracy forecasters are likely to win; in extreme cases, it can result in a perfect forecaster having zero probability of winning. In this paper, we introduce a truthful forecaster selection mechanism. We lower-bound the probability that our mechanism selects the most accurate forecaster, and give rates for how quickly this bound approaches 1 as the number of events grows. Our techniques can be generalized to the related problems of outputting a ranking over forecasters and hiring a forecaster with high accuracy on future events.

PDF Details

AAAI Conference 2017 Conference Paper

Crowdsourced Outcome Determination in Prediction Markets

Rupert Freeman
Sebastien Lahaie
David Pennock

A prediction market is a useful means of aggregating information about a future event. To function, the market needs a trusted entity who will verify the true outcome in the end. Motivated by the recent introduction of decentralized prediction markets, we introduce a mechanism that allows for the outcome to be determined by the votes of a group of arbiters who may themselves hold stakes in the market. Despite the potential conﬂict of interest, we derive conditions under which we can incentivize arbiters to vote truthfully by using funds raised from market fees to implement a peer prediction mechanism. Finally, we investigate what parameter values could be used in a real-world implementation of our mechanism.

PDF Details

IJCAI Conference 2017 Conference Paper

Fair and Efficient Social Choice in Dynamic Settings

Rupert Freeman
Seyed Majid Zahedi
Vincent Conitzer

We study a dynamic social choice problem in which an alternative is chosen at each round according to the reported valuations of a set of agents. In the interests of obtaining a solution that is both efficient and fair, we aim to maximize the long-term Nash social welfare, which is the product of all agents' utilities. We present and analyze two greedy algorithms for this problem, including the classic Proportional Fair (PF) algorithm. We analyze several versions of the algorithms and how they relate, and provide an axiomatization of PF. Finally, we evaluate the algorithms on data gathered from a computer systems application.

PDF Details

AAAI Conference 2017 Conference Paper

PhragmnÕs Voting Methods and Justified Representation

Markus Brill
Rupert Freeman
Svante Janson
Martin Lackner

In the late 19th century, Lars Edvard Phragmén proposed a load-balancing approach for selecting committees based on approval ballots. We consider three committee voting rules resulting from this approach: two optimization variants—one minimizing the maximal load and one minimizing the variance of loads—and a sequential variant. We study Phragmén’s methods from an axiomatic point of view, focussing on justiﬁed representation and related properties that have recently been introduced by Aziz et al. (2015a) and Sánchez-Fernández et al. (2017). We show that the sequential variant satisﬁes proportional justiﬁed representation, making it the ﬁrst known polynomial-time computable method with this property. Moreover, we show that the optimization variants satisfy perfect representation. We also analyze the computational complexity of Phragmén’s methods and provide mixed-integer programming based algorithms for computing them.

PDF Details

AAAI Conference 2016 Conference Paper

Computing Possible and Necessary Equilibrium Actions (and Bipartisan Set Winners)

Markus Brill
Rupert Freeman
Vincent Conitzer

In many multiagent environments, a designer has some, but limited control over the game being played. In this paper, we formalize this by considering incompletely speciﬁed games, in which some entries of the payoff matrices can be chosen from a speciﬁed set. We show that it is NP-hard for the designer to make this choices optimally, even in zero-sum games. In fact, it is already intractable to decide whether a given action is (potentially or necessarily) played in equilibrium. We also consider incompletely speciﬁed symmetric games in which all completions are required to be symmetric. Here, hardness holds even in weak tournament games (symmetric zero-sum games whose entries are all −1, 0, or 1) and in tournament games (symmetric zero-sum games whose non-diagonal entries are all −1 or 1). The latter result settles the complexity of the possible and necessary winner problems for a social-choice-theoretic solution concept known as the bipartisan set. We ﬁnally give a mixed-integer linear programming formulation for weak tournament games and evaluate it experimentally.

PDF Details

AAMAS Conference 2016 Conference Paper

False-Name-Proof Recommendations in Social Networks

Markus Brill
Vincent Conitzer
Rupert Freeman
Nisarg Shah

We study the problem of finding a recommendation for an uninformed user in a social network by weighting and aggregating the opinions offered by the informed users in the network. In social networks, an informed user may try to manipulate the recommendation by performing a false-name manipulation, wherein the user submits multiple opinions through fake accounts. To that end, we impose a no harm axiom: false-name manipulations by a user should not reduce the weight of other users in the network. We show that this axiom has deep connections to false-nameproofness. While it is impossible to design a mechanism that is best for every network subject to this axiom, we propose an intuitive mechanism LEGIT +, and show that it is uniquely optimized for small networks. Using real-world datasets, we show that our mechanism performs very well compared to two baseline mechanisms in a number of metrics, even on large networks.

PDF

AAAI Conference 2016 Conference Paper

Rules for Choosing Societal Tradeoffs

Vincent Conitzer
Rupert Freeman
Markus Brill
Yuqian Li

We study the societal tradeoffs problem, where a set of voters each submit their ideal tradeoff value between each pair of activities (e. g. , “using a gallon of gasoline is as bad as creating 2 bags of landﬁll trash”), and these are then aggregated into the societal tradeoff vector using a rule. We introduce the family of distance-based rules and show that these can be justiﬁed as maximum likelihood estimators of the truth. Within this family, we single out the logarithmic distance-based rule as especially appealing based on a social-choice-theoretic axiomatization. We give an efﬁcient algorithm for executing this rule as well as an approximate hill climbing algorithm, and evaluate these experimentally.

PDF Details

AAMAS Conference 2016 Conference Paper

Signaling in Bayesian Stackelberg Games

Haifeng Xu
Rupert Freeman
Vincent Conitzer
Shaddin Dughmi
Milind Tambe

Algorithms for solving Stackelberg games are used in an ever-growing variety of real-world domains. Previous work has extended this framework to allow the leader to commit not only to a distribution over actions, but also to a scheme for stochastically signaling information about these actions to the follower. This can result in higher utility for the leader. In this paper, we extend this methodology to Bayesian games, in which either the leader or the follower has payoff-relevant private information or both. This leads to novel variants of the model, for example by imposing an incentive compatibility constraint for each type to listen to the signal intended for it. We show that, in contrast to previous hardness results for the case without signaling [5, 16], we can solve unrestricted games in time polynomial in their natural representation. For security games, we obtain hardness results as well as efficient algorithms, depending on the settings. We show the benefits of our approach in experimental evaluations of our algorithms.

PDF

AAAI Conference 2015 Conference Paper

Justified Representation in Approval-Based Committee Voting

Haris Aziz
Markus Brill
Vincent Conitzer
Edith Elkind
Rupert Freeman
Toby Walsh

We consider approval-based committee voting, i. e. , the setting where each voter approves a subset of candidates, and these votes are then used to select a fixed-size set of winners (committee). We propose a natural axiom for this setting, which we call justified representation (JR). This axiom requires that if a large enough group of voters exhibits agreement by supporting the same candidate, then at least one voter in this group has an approved candidate in the winning committee. We show that for every list of ballots it is possible to select a committee that provides JR. We then check if this axiom is fulfilled by well-known approval-based voting rules. We show that the answer is negative for most of the rules we consider, with notable exceptions of PAV (Proportional Approval Voting), an extreme version of RAV (Reweighted Approval Voting), and, for a restricted preference domain, MAV (Minimax Approval Voting). We then introduce a stronger version of the JR axiom, which we call extended justified representation (EJR), and show that PAV satisfies EJR, while other rules do not. We also consider several other questions related to JR and EJR, including the relationship between JR/EJR and unanimity, and the complexity of the associated algorithmic problems.

PDF Details

AAAI Conference 2014 Conference Paper

On the Axiomatic Characterization of Runoff Voting Rules

Rupert Freeman
Markus Brill
Vincent Conitzer

Runoff voting rules such as single transferable vote (STV) and Baldwin’s rule are of particular interest in computational social choice due to their recursive nature and hardness of manipulation, as well as in (human) practice because they are relatively easy to understand. However, they are not known for their compliance with desirable axiomatic properties, which we attempt to rectify here. We characterize runoff rules that are based on scoring rules using two axioms: a weakening of local independence of irrelevant alternatives and a variant of population-consistency. We then show, as our main technical result, that STV is the only runoff scoring rule satisfying an independence-of-clones property. Furthermore, we provide axiomatizations of Baldwin’s rule and Coombs’ rule.

PDF Details