GenAI4ELab/papercli-papers huggingface dataset:
Representation with Incomplete Votes
Authors: Daniel Halpern; Gregory Kehne; Ariel D. Procaccia; Jamie Tucker-Foltz; Manuel Wüthrich
Venue: AAAI 2023 (main)

Abstract: Platforms for online civic participation rely heavily on methods for condensing thousands of comments into a relevant handful, based on whether participants agree or disagree with them. These methods should guarantee fair representation of the participants, as their outcomes may affect the health of the conversation and inform impactful downstream decisions. To that end, we draw on the literature on approval-based committee elections. Our setting is novel in that the approval votes are incomplete since participants will typically not vote on all comments. We prove that this complication renders non-adaptive algorithms impractical in terms of the amount of information they must gather. Therefore, we develop an adaptive algorithm that uses information more efficiently by presenting incoming participants with statements that appear promising based on votes by previous participants. We prove that this method satisfies commonly used notions of fair representation, even when participants only vote on a small fraction of comments. Finally, an empirical evaluation using real data shows that the proposed algorithm provides representative outcomes in practice.
Optimizing Multiple Simultaneous Objectives for Voting and Facility Location
Authors: Yue Han; Christopher Jerrett; Elliot Anshelevich
Venue: AAAI 2023 (main)

Abstract: We study the classic facility location setting, where we are given n clients and m possible facility locations in some arbitrary metric space, and want to choose a location to build a facility. The exact same setting also arises in spatial social choice, where voters are the clients and the goal is to choose a candidate or outcome, with the distance from a voter to an outcome representing the cost of this outcome for the voter (e.g., based on their ideological differences). Unlike most previous work, we do not focus on a single objective to optimize (e.g., the total distance from clients to the facility, or the maximum distance, etc.), but instead attempt to optimize several different objectives simultaneously. More specifically, we consider the l-centrum family of objectives, which includes the total distance, max distance, and many others. We present tight bounds on how well any pair of such objectives (e.g., max and sum) can be simultaneously approximated compared to their optimum outcomes. In particular, we show that for any such pair of objectives, it is always possible to choose an outcome which simultaneously approximates both objectives within a factor of 1 plus square root of 2, and give a precise characterization of how this factor improves as the two objectives being optimized become more similar. For q>2 different centrum objectives, we show that it is always possible to approximate all q of these objectives within a small constant, and that this constant approaches 3 as q increases. Our results show that when optimizing only a few simultaneous objectives, it is always possible to form an outcome which is a significantly better than 3 approximation for all of these objectives.
Class Fairness in Online Matching
Authors: Hadi Hosseini; Zhiyi Huang; Ayumi Igarashi; Nisarg Shah
Venue: AAAI 2023 (main)

Abstract: We initiate the study of fairness among classes of agents in online bipartite matching where there is a given set of offline vertices (aka agents) and another set of vertices (aka items) that arrive online and must be matched irrevocably upon arrival. In this setting, 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 (e.g. envy-freeness, proportionality, and maximin share) and their relaxations to this setting and study deterministic and randomized algorithms for matching indivisible items (leading to integral matchings) and for matching divisible items (leading to fractional matchings).
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.
How to Cut a Discrete Cake Fairly
Authors: Ayumi Igarashi
Venue: AAAI 2023 (main)

Abstract: Cake-cutting is a fundamental model of dividing a heterogeneous resource, such as land, broadcast time, and advertisement space. In this study, we consider the problem of dividing indivisible goods fairly under the connectivity constraints of a path. We prove that a connected division of indivisible items satisfying a discrete counterpart of envy-freeness, called envy-freeness up to one good (EF1), always exists for any number of agents n with monotone valuations. Our result settles an open question raised by Bilò et al. (2019), who proved that an EF1 connected division always exists for four agents with monotone valuations. Moreover, the proof can be extended to show the following (1) ``secretive" and (2) ``extra" versions: (1) for n agents with monotone valuations, the path can be divided into n connected bundles such that an EF1 assignment of the remaining bundles can be made to the other agents for any selection made by the “secretive agent”; (2) for n+1 agents with monotone valuations, the path can be divided into n connected bundles such that when any ``extra agent” leaves, an EF1 assignment of the bundles can be made to the remaining agents.
Competition, Alignment, and Equilibria in Digital Marketplaces
Authors: Meena Jagadeesan; Michael I. Jordan; Nika Haghtalab
Venue: AAAI 2023 (main)

Abstract: Competition between traditional platforms is known to improve user utility by aligning the platform's actions with user preferences. But to what extent is alignment exhibited in data-driven marketplaces? To study this question from a theoretical perspective, we introduce a duopoly market where platform actions are bandit algorithms and the two platforms compete for user participation. A salient feature of this market is that the quality of recommendations depends on both the bandit algorithm and the amount of data provided by interactions from users. This interdependency between the algorithm performance and the actions of users complicates the structure of market equilibria and their quality in terms of user utility. Our main finding is that competition in this market does not perfectly align market outcomes with user utility. Interestingly, market outcomes exhibit misalignment not only when the platforms have separate data repositories, but also when the platforms have a shared data repository. Nonetheless, the data sharing assumptions impact what mechanism drives misalignment and also affect the specific form of misalignment (e.g. the quality of the best-case and worst-case market outcomes). More broadly, our work illustrates that competition in digital marketplaces has subtle consequences for user utility that merit further investigation.
Voting with Preference Intensities
Authors: Anson Kahng; Mohamad Latifian; Nisarg Shah
Venue: AAAI 2023 (main)

Abstract: When an agent votes, she typically ranks the set of available alternatives. Occasionally, she may also wish to report the intensity of her preferences by indicating adjacent pairs of alternatives in her ranking between which her preference is acutely decisive; for instance, she may suggest that she likes alternative a more than b, but b much more than c. We design near-optimal voting rules which aggregate such preference rankings with intensities using the recently-popular distortion framework. We also show that traditional voting rules, which aggregate preference rankings while ignoring (or not eliciting) intensities, can incur significant welfare loss.
Approximations for Indivisible Concave Allocations with Applications to Nash Welfare Maximization
Authors: Nathaniel Kell; Kevin Sun
Venue: AAAI 2023 (main)

Abstract: We study a general allocation setting where agent valuations are concave additive. In this model, a collection of items must be uniquely distributed among a set of agents, where each agent-item pair has a specified utility. The objective is to maximize the sum of agent valuations, each of which is an arbitrary non-decreasing concave function of the agent's total additive utility. This setting was studied by Devanur and Jain (STOC 2012) in the online setting for divisible items. In this paper, we obtain both multiplicative and additive approximations in the offline setting for indivisible items. Our approximations depend on novel parameters that measure the local multiplicative/additive curvatures of each agent valuation, which we show correspond directly to the integrality gap of the natural assignment convex program of the problem. Furthermore, we extend our additive guarantees to obtain constant multiplicative approximations for Asymmetric Nash Welfare Maximization when agents have smooth valuations. This algorithm also yields an interesting tatonnement-style interpretation, where agents adjust uniform prices and items are assigned according to maximum weighted bang-per-buck ratios.
Strategic Facility Location with Clients That Minimize Total Waiting Time
Authors: Simon Krogmann; Pascal Lenzner; Alexander Skopalik
Venue: AAAI 2023 (main)

Abstract: We study a non-cooperative two-sided facility location game in which facilities and clients behave strategically.
This is in contrast to many other facility location games in which clients simply visit their closest facility.
Facility agents select a location on a graph to open a facility to attract as much purchasing power as possible, while client agents choose which facilities to patronize by strategically distributing their purchasing power in order to minimize their total waiting time. Here, the waiting time of a facility depends on its received total purchasing power.    
We show that our client stage is an atomic splittable congestion game, which implies existence, uniqueness and efficient computation of a client equilibrium.
Therefore, facility agents can efficiently predict client behavior and make strategic decisions accordingly.
Despite that, we prove that subgame perfect equilibria do not exist in all instances of this game and that their existence is NP-hard to decide.
On the positive side, we provide a simple and efficient algorithm to compute 3-approximate subgame perfect equilibria.
Proportional Decisions in Perpetual Voting
Authors: Martin Lackner; Jan Maly
Venue: AAAI 2023 (main)

Abstract: Perpetual voting is a framework for long-term collective decision making. In this framework, we consider a sequence of subsequent approval-based elections and try to achieve a fair overall outcome. To achieve fairness over time, perpetual voting rules take the history of previous decisions into account and identify voters that were dissatisfied with previous decisions. In this paper, we look at perpetual voting rules from an axiomatic perspective. First, we define two classes of perpetual voting rules that are particularly easy to explain to voters and explore the bounds imposed by this simplicity. Second, we study proportionality in the perpetual setting and identify two rules with strong proportionality guarantees. However, both rules yield different guarantees and we prove them to be incompatible with each other.
Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule
Authors: Bo Li; Xiaowei Wu; Chenyang Xu; Ruilong Zhang
Venue: AAAI 2023 (main)

Abstract: Given a connected graph on whose edges we can build roads to connect the nodes, a number of agents hold possibly different perspectives on which edges should be selected by assigning different edge weights. Our task is to build a minimum number of roads so that every agent has a spanning tree in the built subgraph whose weight is the same as a minimum spanning tree in the original graph. We first show that this problem is NP-hard and does not admit better than ((1-o(1)) ln k)-approximation polynomial-time algorithms unless P = NP, where k is the number of agents. We then give a simple voting algorithm with an optimal approximation ratio. Moreover, our algorithm only needs to access the agents' rankings on the edges. Finally, we extend our problem to submodular objective functions and Matroid rank constraints.
When Congestion Games Meet Mobile Crowdsourcing: Selective Information Disclosure
Authors: Hongbo Li; Lingjie Duan
Venue: AAAI 2023 (main)

Abstract: In congestion games, users make myopic routing decisions to jam each other, and the social planner with the full information designs mechanisms on information or payment side to regulate. However, it is difficult to obtain time-varying traffic conditions, and emerging crowdsourcing platforms (e.g., Waze and Google Maps) provide a convenient way for mobile users travelling on the paths to learn and share the traffic conditions over time. When congestion games meet mobile crowdsourcing, it is critical to incentive selfish users to change their myopic routing policy and reach the best exploitation-exploration trade-off. By considering a simple but fundamental parallel routing network with one deterministic path and multiple stochastic paths for atomic users, we prove that the myopic routing policy's price of anarchy (PoA) can be arbitrarily large as the discount factor approaches 1. To remedy such huge efficiency loss, we propose a selective information disclosure (SID) mechanism: we only reveal the latest traffic information to users when they intend to over-explore the stochastic paths, while hiding such information when they want to under-explore. We prove that our mechanism reduces PoA to less than 2. Besides the worst-case performance, we further examine our mechanism's average-case performance by using extensive simulations.
Partitioning Friends Fairly
Authors: Lily Li; Evi Micha; Aleksandar Nikolov; Nisarg Shah
Venue: AAAI 2023 (main)

Abstract: We consider the problem of partitioning n agents in an undirected social network into k almost equal in size (differing by at most one) groups, where the utility of an agent for a group is the number of her neighbors in the group. The core and envy-freeness are two compelling axiomatic fairness guarantees in such settings. The former demands that there be no coalition of agents such that each agent in the coalition has more utility for that coalition than for her own group, while the latter demands that no agent envy another agent for the group they are in. We provide (often tight) approximations to both fairness guarantees, and many of our positive results are obtained via efficient algorithms.
Differentially Private Condorcet Voting
Authors: Zhechen Li; Ao Liu; Lirong Xia; Yongzhi Cao; Hanpin Wang
Venue: AAAI 2023 (main)

Abstract: Designing private voting rules is an important and pressing problem for trustworthy democracy. In this paper, under the framework of differential privacy, we propose a novel famliy of randomized voting rules based on the well-known Condorcet method, and focus on three classes of voting rules in this family: Laplacian Condorcet method (CMLAP), exponential Condorcet method (CMEXP), and randomized response Condorcet method (CMRR), where λ represents the level of noise. We prove that all of our rules satisfy absolute monotonicity, lexi-participation, probabilistic Pareto efficiency, approximate probabilistic Condorcet criterion, and approximate SD-strategyproofness. In addition, CMRR satisfies (non-approximate) probabilistic Condorcet criterion, while CMLAP and CMEXP satisfy strong lexi-participation. Finally, we regard differential privacy as a voting axiom, and discuss its relations to other axioms.
Function Approximation for Solving Stackelberg Equilibrium in Large Perfect Information Games
Authors: Chun Kai Ling; J. Zico Kolter; Fei Fang
Venue: AAAI 2023 (main)

Abstract: Function approximation (FA) has been a critical component in solving large zero-sum games. Yet, little attention has been given towards FA in solving general-sum extensive-form games, despite them being widely regarded as being computationally more challenging than their fully competitive  or cooperative counterparts. A key challenge is that for many equilibria in general-sum games, no simple analogue to the state value function used in Markov Decision Processes and zero-sum games exists. In this paper, we propose learning the Enforceable Payoff Frontier (EPF)---a generalization of the state value function for general-sum games. We approximate the optimal Stackelberg extensive-form correlated equilibrium by representing EPFs with neural networks and training them by using appropriate backup operations and loss functions. This is the first method that applies FA to the Stackelberg setting, allowing us to scale to much larger games while still enjoying performance guarantees based on FA error. Additionally, our proposed method guarantees incentive compatibility and is easy to evaluate without having to depend on self-play or approximate best-response oracles.
Optimal Pricing Schemes for Identical Items with Time-Sensitive Buyers
Authors: Zhengyang Liu; Liang Shan; Zihe Wang
Venue: AAAI 2023 (main)

Abstract: Time or money? That is a question! In this paper, we consider this dilemma in the pricing regime, in which we try to find the optimal pricing scheme for identical items with heterogenous time-sensitive buyers. We characterize the revenue-optimal solution and propose an efficient algorithm to find it in a Bayesian setting. Our results also demonstrate the tight ratio between the value of wasted time and the seller's revenue, as well as that of two common-used pricing schemes, the k-step function and the fixed pricing. To explore the nature of the optimal scheme in the general setting, we present the closed forms over the product distribution and show by examples that positive correlation between the valuation of the item and the cost per unit time could help increase revenue. To the best of our knowledge, it is the first step towards understanding the impact of the time factor as a part of the buyer cost in pricing problems, in the computational view.
Approval-Based Voting with Mixed Goods
Authors: Xinhang Lu; Jannik Peters; Haris Aziz; Xiaohui Bei; Warut Suksompong
Venue: AAAI 2023 (main)

Abstract: We consider a voting scenario in which the resource to be voted upon may consist of both indivisible and divisible goods. This generalizes both the well-studied model of multiwinner voting and the recently introduced model of cake sharing. Under approval votes, we propose two variants of the extended justified representation (EJR) notion from multiwinner voting, a stronger one called EJR for mixed goods (EJR-M) and a weaker one called EJR up to 1 (EJR-1). We extend three multiwinner voting rules to our setting—GreedyEJR, the method of equal shares (MES), and proportional approval voting (PAV)—and show that while all three generalizations satisfy EJR-1, only the first one provides EJR-M. In addition, we derive tight bounds on the proportionality degree implied by EJR-M and EJR-1, and investigate the proportionality degree of our proposed rules.
Utility Maximizer or Value Maximizer: Mechanism Design for Mixed Bidders in Online Advertising
Authors: Hongtao Lv; Zhilin Zhang; Zhenzhe Zheng; Jinghan Liu; Chuan Yu; Lei Liu; Lizhen Cui; Fan Wu
Venue: AAAI 2023 (main)

Abstract: Digital advertising constitutes one of the main revenue sources for online platforms. In recent years, some advertisers tend to adopt auto-bidding tools to facilitate advertising performance optimization, making the classical utility maximizer model in auction theory not fit well. Some recent studies proposed a new model, called value maximizer, for auto-bidding advertisers with return-on-investment (ROI) constraints. However, the model of either utility maximizer or value maximizer could only characterize partial advertisers in real-world advertising platforms. In a mixed environment where utility maximizers and value maximizers coexist, the truthful ad auction design would be challenging since bidders could manipulate both their values and affiliated classes, leading to a multi-parameter mechanism design problem. In this work, we address this issue by proposing a payment rule which combines the corresponding ones in classical VCG and GSP mechanisms in a novel way. Based on this payment rule, we propose a truthful auction mechanism with an approximation ratio of 2 on social welfare, which is close to the lower bound of at least 5/4 that we also prove. The designed auction mechanism is a generalization of VCG for utility maximizers and GSP for value maximizers.
Facility Location Games with Entrance Fees
Authors: Mengfan Ma; Mingyu Xiao; Tian Bai; Bakh Khoussainov
Venue: AAAI 2023 (main)

Abstract: The facility location game is an extensively studied problem in mechanism design. In the classical model, the cost of each agent is her distance to the nearest facility. In this paper, we consider a novel model where each facility charges an entrance fee, which is a function of the facility's location. Thus, in our model, the cost of each agent is the sum of the distance to the facility and the entrance fee of the facility. The generalized model captures more real-life scenarios. In our model, the entrance fee function can be an arbitrary function, and the corresponding preferences of agents may not be single-peaked anymore: this makes the problem complex and requires new techniques in the analysis. We systematically study the model and design strategyproof mechanisms with nice approximation ratios and also complement these with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms, with respect to the utilitarian and egalitarian objectives. Most of our bounds are tight, and these bounds are independent of the entrance fee functions. Our results also match the results of the classical model.
Securing Lifelines: Safe Delivery of Critical Services in Areas with Volatile Security Situation via a Stackelberg Game Approach
Authors: Tien Mai; Arunesh Sinha
Venue: AAAI 2023 (main)

Abstract: Vaccine delivery in under-resourced locations with security risks is not just challenging but also life threatening. The COVID pandemic and the need to vaccinate added even more urgency to this issue. Motivated by this problem, we propose a general framework to set-up limited temporary (vaccination) centers that balance physical security and desired (vaccine) service coverage with limited resources. We set-up the problem as a Stackelberg game between the centers operator (defender) and an adversary, where the set of centers is not fixed a priori but is part of the decision output. This results in a mixed combinatorial and continuous optimization problem. As part of our scalable approximation solution, we provide a fundamental contribution by identifying general duality conditions of switching max and min when both discrete and continuous variables are involved. Via detailed experiments, we show that the solution proposed is scalable in practice.
Differentially Private Fair Division
Authors: Pasin Manurangsi; Warut Suksompong
Venue: AAAI 2023 (main)

Abstract: Fairness and privacy are two important concerns in social decision-making processes such as resource allocation. We study privacy in the fair allocation of indivisible resources using the well-established framework of differential privacy. We present algorithms for approximate envy-freeness and proportionality when two instances are considered to be adjacent if they differ only on the utility of a single agent for a single item. On the other hand, we provide strong negative results for both fairness criteria when the adjacency notion allows the entire utility function of a single agent to change.