We generalize the classic problem of fairly allocating indivisible goods to fair public decision making, in which a must be made on several social issues simultaneously, and, unlike setting, can provide positive utility multiple players. extend popular fairness notion proportionality (which is not guaranteeable) our more general and introduce three novel relaxations --- up one issue, round robin share, pessimistic proportional share that are also interesting allocation setting. show Maximum...

Consider the problem of allocating indivisible goods among agents with additive valuations, where monetary payments are not allowed. When randomization is allowed, it possible to achieve compelling notions fairness such as EV, which states that no agent should prefer any other agent's allocation their own. allocations must be deterministic, achieving exact impossible but approximate EV up one good can guaranteed. In “Best Both Worlds: Ex Ante and Post Fairness in Resource Allocation,” H....

We consider the problem of fairly dividing a collection indivisible goods among set players. Much existing literature on fair division focuses notions individual fairness. For instance, envy-freeness requires that no player prefer allocated to another her own allocation. observe an algorithm satisfying such fairness can still treat groups players unfairly, with one group desiring another. Our main contribution is notion fairness, which implies most Group (like fairness) cannot be satisfied...

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

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

We initiate the study of incentive-compatible forecasting competitions in which multiple forecasters make predictions about one or more events and compete for a single prize. have two objectives: (1) to incentivize report truthfully (2) award prize most accurate forecaster. Proper scoring rules truthful reporting if all are paid according their scores. However, incentives become distorted only best-scoring forecaster wins prize, since can often increase probability having highest score by...

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 commit not only a distribution over actions, but also scheme stochastically signaling information about these actions follower. This can result higher utility leader. In paper, we extend methodology Bayesian games, which either or follower payoff-relevant private both. leads novel variants model, example by imposing incentive...

In the late 19th century, Lars Edvard Phragmé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 maximal load and variance of loads —and sequential variant. study Phragmén's methods an axiomatic point view, focussing justified representation related properties that have recently been introduced by Aziz et al. (2015a) Sánchez-Fernández (2017)....

We study the problem of allocating indivisible goods among agents. When randomization is allowed, it possible to achieve compelling fairness guarantees such as envy-freeness (Foley, 1967), which states that no agent should (in expectation) prefer any other agent's allocation her own. For instance, we can simply allocate each good, independently goods, an chosen uniformly at random. However, while this scheme fair ex-ante, may produce outcomes are very unfair ex-post, by chance assigning all...

We study a participatory budgeting setting in which single divisible resource (such as money or time) must be divided among set of projects. For example, could used to decide how divide city's tax surplus between its departments health, education, infrastructure, and parks. A voter might propose division the four into fractions (30%, 40%, 20%, 10%). The city invite each citizen submit such budget proposal, they then aggregated by suitable mechanism. In this paper, we seek mechanisms form...

It would be desirable if, as a society, we could reduce the amount of landfill trash create, carbon dioxide emit, forest clear, etc. Since cannot (or are in any case not willing to) simultaneously pursue all these objectives to their maximum extent, must prioritize among them. Currently, this is done mostly an ad-hoc manner, with people, companies, local governments, and other entities deciding on individual basis which pursue, what extent.A more systematic approach set, at global level,...

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 fixed-size set winners (committee). propose natural axiom for this setting, which we call justified representation (JR). This requires that if large enough group voters exhibits agree- ment by supporting same candidate, at least one in has an approved candidate winning committee. show every list ballots it is possible provides JR. check...

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 hardness manipulation, well (human) practice because they relatively easy understand. However, not known for compliance with desirable axiomatic properties, which we attempt rectify here. We characterize runoff that based on scoring using two axioms: a weakening local independence irrelevant alternatives variant...

In (computational) social choice, how ties are broken can affect the axiomatic and computational properties of a voting rule. this paper, we first consider settings where may have multiple winners. We formalize notion parallel universes tiebreaking with respect to particular tree that represents computation winners, show specific used does not matter if certain conditions hold. then move on single winner must be returned, generally by randomized tiebreaking, examine some drawbacks existing...

Abstract In the late 19th century, Swedish mathematician Edvard Phragmé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 maximum load and one variance of loads—and sequential variant. study ’s methods an axiomatic point view, focusing properties capturing proportional representation. show that variant satisfies justified representation , which...

We study the budget aggregation problem in which a set of strategic voters must split finite divisible resource (such as money or time) among competing projects. Our goal is twofold: seek truthful mechanisms that provide fairness guarantees to For first objective, we focus on class moving phantom mechanisms, are -- this day essentially only known setting. project fairness, consider mean division fair baseline, and bound maximum difference between funding received by any baseline. propose...

Sharing computational resources amortizes cost and improves utilization efficiency. When agents pool their resources, each becomes entitled to a portion of the shared pool. Static allocations in round can guarantee entitlements are strategy-proof, but efficiency suffers because do not reflect variations agents' demands for across rounds. Dynamic allocation mechanisms assign multiple rounds while guaranteeing entitlements. Designing dynamic is challenging, however, when strategic benefit by...

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 one good and maximin share guarantee. In our model, each agent is matched multiple agents on other side over whom she has additive preferences. demand separately, giving rise double match (DEF1) guarantee (DMMS). show that (a slight strengthening of) DEF1 cannot always be achieved, but in special case where both sides have identical...

We study fair allocation of indivisible chores (i.e., items with non-positive value) among agents additive valuations. An is deemed if it (approximately) equitable, which means that the disutilities are equal. Our main theoretical contribution to show there always exists an simultaneously equitable up one chore (EQ1) and Pareto optimal (PO), provide a pseudopolynomial-time algorithm for computing such allocation. In addition, we observe Leximin solution---which known satisfy strong form...

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. have two objectives: (1) to award prize most accurate forecaster, (2) incentivize report truthfully, so that forecasts are informative need not spend any cognitive effort strategizing reports. Proper scoring rules truthful reporting if all paid according their scores. However, incentives become distorted only best-scoring...

We develop the first incentive compatible and near-Pareto-optimal wagering mechanism. Wagering mechanisms can be used to elicit predictions from agents who reveal their beliefs by placing bets. Lambert et al. [20, 21] introduced weighted score mechanisms, a class of budget-balanced under which with immutable truthfully report predictions. However, we demonstrate that these other existing are not Pareto optimal: have significant budget left over even when additional trade would mutually...

We study proportionality in approval-based multiwinner elections with a variable number of winners, where both the size and identity winning committee are informed by voters' opinions. While has been studied fixed it not considered winners setting. The measure we consider is average satisfaction (AS), which intuitively measures agreements on between sufficiently large cohesive groups voters output voting rule. First, show an upper bound AS that any deterministic rule can provide,...