AI Representation and Problem Solving: Social Choice Theory and Voting Models
Explore the world of artificial intelligence with a focus on social choice theory, mechanism design, and voting models. Dive into the ethics of AI, social choice theory, and voting rules with key insights and practical applications in economics and public policy.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Artificial Intelligence: Representation and Problem Solving Multi-agent Systems (4): Social Choice and Mechanism Design 15-381 / 681 Instructors: Fei Fang (This Lecture) and Dave Touretzky feifang@cmu.edu Wean Hall 4126 1 3/21/2025
Required Reading for Next Lecture THE ETHICS OF ARTIFICIAL INTELLIGENCE (2011) by Nick Bostrom and Eliezer Yudkowsky https://nickbostrom.com/ethics/artificial- intelligence.pdf 2 Fei Fang 3/21/2025
Faculty Course Evaluation Ends Dec 16 3 Fei Fang 3/21/2025
Recap Given a game, find solution / equilibrium Solution Concepts Dominant Strategy Equilibrium Pure Strategy Nash Equilibrium Mixed Strategy Nash Equilibrium How to Find/Compute Brute Force Enumeration Iterative Elimination, Brute Force Enumeration Same as Minimax/Maximin for two-player zero-sum games Support Enumeration Method for two-player general-sum games Linear Programming Multiple LPs Minimax/Maximin Strong Stackelberg Equilibrium 4 Fei Fang 3/21/2025
Outline Social Choice Voting Model Voting Rules Properties of Voting Rules Key Results Mechanism Design with Money Second-Price Auction 5 Fei Fang 3/21/2025
Social Choice Theory A mathematical theory that deal with aggregation of individual preferences Wide applications in economics, public policy, etc. Kenneth Arrow Amartya Kumar Sen Winners of Nobel Memorial Prize in Economic Sciences 6 Fei Fang 3/21/2025
Voting Model Model Set of voters ? = 1..? Set of alternatives ? ( ? = ?) Each voter has a ranking over the alternatives Preference profile: collection of all voters rankings Basic voting model: No explicit utility associated with the alternatives Voter ID Ranking over alternatives (first row is the most preferred) 1 a b c 2 c a b 3 b c a 7 Fei Fang 3/21/2025
Voting Rules Voting rule: function that maps preference profiles to alternatives that specifies the winner of the election Commonly used voting rules Plurality (used in almost all political elections) Each voter give one point to top alternative Alternative with most points win Borda count (used for national election in Slovenia) Each voter awards ? ? points to alternative ranked ?? Alternative with most points win Plurality with runoff First round: two alternatives with highest plurality scores survive Second round: pairwise election between the two ? beats ? if majority of voters prefer ? to ? 8 Fei Fang 3/21/2025
Voting Rules Commonly used voting rules (continued) Single Transferable Vote (STV) (used in Ireland, Australia, New Zealand, Maine, San Francisco, Cambridge) ? 1 rounds In each round, alternative with least plurality votes is eliminated Alternative left is the winner 2 voters a b c d 2 voters b a d c 1 voter c d b a 9 Fei Fang 3/21/2025
Social Choice Axioms How do we choose among different voting rules? What are the desirable properties? Majority consistency: If a majority of voters (more than half) rank alternative ? first, then ? should be the winner 11 Fei Fang 3/21/2025
Quiz 1 Which rules are not majority consistent? A: Plurality B: Plurality with runoff C: Borda count D: STV E: None Plurality: Each voter give one point to top alternative Borda count: Each voter awards ? ? points to alternative ranked ?? Plurality with runoff: Pairwise election between two alternatives with highest plurality scores STV: In each round, alternative with least plurality votes is eliminated 12 Fei Fang 3/21/2025
Condorcet Winner Recall: ? beats ? in a pairwise election if majority of voters prefer ? to ? Condorcet winner beats every other alternative in pairwise election Condorcet paradox = cycle in majority preferences Condorcet consistency: select a Condorcet winner if one exists Are the introduced voting rules Condorcet consistent? Voter ID Ranking over alternatives (first row is the most preferred) 1 a b c 2 c a b 3 b c a 14 Fei Fang 3/21/2025
Example Plurality: a; Borda: b; STV: d; Plurality with runoff: e Condorcet winner: c 33 voters 16 voters 3 voter 8 voters 18 voters 22 voters a b c d e b d c e a c d b a e c e b d a d e c b a e c b d a 15 Fei Fang 3/21/2025
Voter Manipulation Using Borda Count If voter 3 change his vote, he get a better outcome Voter ID Ranking over alternatives (first row is the most preferred) 1 b a c d 2 b a c d 3 a b c d ? ? 3 2 1 0 b: 2*3+1*2=8 a: 2*2+1*3=7 b is the winner Voter ID Ranking over alternatives (first row is the most preferred) 1 b a c d 2 b a c d 3 a c d b ? ? 3 2 1 0 b: 2*3+1*0=6 a: 2*2+1*3=7 a is the winner 16 Fei Fang 3/21/2025
Strategy-Proofness A voting rule is strategyproof (SP) if a voter can never benefit from lying about his preferences 17 Fei Fang 3/21/2025
Other Properties A voting rule is dictatorial if there is a voter who always gets his most preferred alternative A voting rule is constant if the same alternative is always chosen (regardless of the stated preferences) A voting rule is onto if any alternative can win, for some set of stated preferences 18 Fei Fang 3/21/2025
Results in Social Choice Theory Constant functions and dictatorships are SP Theorem (Gibbard-Satterthwaite): If ? 3, then any voting rule that is SP and onto is dictatorial Therefore, any voting rule that is onto and nondictatorial is manipulable 19 Fei Fang 3/21/2025
Greedy Algorithm for ? Manipulation Given voting rule ? and preference profile of ? 1 voters, how can the last voter report preference to let a specific alternative ?uniquely win (no tie breaking)? Greedy algorithm Rank ? in the first place While there are unranked alternatives If there is an alternative that can be placed in the next spot without preventing ? from winning, place this alternative Otherwise return false Correctness proved (Bartholdi et al., 1989) 20 Fei Fang 3/21/2025
Example Borda Voter ID Ranking over alternatives (first row is the most preferred) 1 b a c d 2 b a c d 3 a 21 Fei Fang 3/21/2025
Quiz 2: Second-Price Auction 1 box of milk chocolate to be purchased Each participant submit a bid (a number 0) I will give the chocolate to the one with the highest bid The person who get the chocolate needs to pay a price that equals the second highest bid provided by any participant (in dollars) How much will you bid? 23 Fei Fang 3/21/2025
Mechanism Design with Money Overview Mechanism specifies what actions the agent can take (possibly over time), and what is the outcome after the agents take actions Given a mechanism, the interaction among agents can be seen as a ?-player game Induced game Recall: Payoffs / Utility functions ??(?1, ,??) Special type of utility model An outcome consists of nonmonetary part (who gets the chocolate) and a monetary part (how much each agent pays) Transferable Utility Numeraire currency Utility = utility of nonmonetary part monetary part 24 Fei Fang 3/21/2025
Bayesian Game A player s utility function depends on his type In chocolate auction, a person on diet may have different valuation of the chocolate from a person who loves chocolate and is not on diet, leading to different utility functions Each participant knows his own type but only knows a prior distribution of other players type Keep in mind that once the auction mechanism is specified, it is a game among participating agents 25 Fei Fang 3/21/2025
Bayesian Game A Bayesian Game is a tuple ?,?, ,?,? where ? = {1 ?} (also written as [?]) is the set of players, ? = ?1 ?? and ?? is the set of actions available to agent ?, = 1 ? and ? is the type space of player ?, ?: [0,1] is the common prior over types, ? = (?1, ,??) and ??:? is the utility function for player ? A player knows his own type and the prior distribution ? over the set of type profiles Given a common prior ? of player type , a Bayesian Nash equilibrium is defined as a strategy profile ? where ? ?, player ? s strategy maximizes the expected payoff given ? ? (derived from and ??) and ? ? 26 Fei Fang 3/21/2025
Bayesian Game Setting A Bayesian game setting: (?,?, ,?,?) where ??:? Bayesian Game Bayesian Game Setting ?,?, ,?,? (?,?, ,?,?) Action set ? is not specified How an action profile is mapped to an outcome is not specified ??:? ??:? 27 Fei Fang 3/21/2025
Mechanism A mechanism for a Bayesian game setting ?,?, ,?,? is a pair (?,?) where ? = ?1 ??, ?? is the action set for player ? ? and ?:? (?) maps each action profile ? ? to a distribution over outcomes in ? In this lecture, we will mostly focus on deterministic mechanisms, i.e., each action profile leads to a deterministic outcome 28 Fei Fang 3/21/2025
Induced Game Given a game setting (?,?, ,?,?) and a mechanism (?,?), the induced game is ?,?, ,?,? We often assume independent private type: Agent s utility only depends on his own type and the joint action of all agents, does not depend on other agents types, i.e., ??? = ??? ? ,? = ??? ? ,??, ? ? Commonly used solution concepts: dominant strategy solution, Bayesian Nash Equilibrium 29 Fei Fang 3/21/2025
Mechanism Design Choose a mechanism that can will cause rational agents to behave in a desired way, i.e., the solution or equilibrium of the induced game satisfy properties or optimize certain goals Mechanism Designer Participant / Player ? What do they know? ?,?,?, ,?,?, ?? Knows what the designer knows and specifies ?,?, ,?,? Who are the agents Possible outcomes Agents type space and distribution Agents preferences for each type Specify ? and ? Knows his own type (private information) What can they do? Choose an action from ?? 30 Fei Fang 3/21/2025
Transferable Utility Quasilinear utility function: linear in one argument (virtual currency) Agents have quasilinear preferences with transferable utility in a ?-player game when the set of outcomes is ? = ? ? for a set ? if the utility of an agent ? can be written as ???,? = ???,?? ?? where ? = ?,? ?, ? ?, ? ? and ??:? ? Note: we abuse the use ? since all these functions are all representing utility and the concrete meaning of ? can be determined by the context 31 Fei Fang 3/21/2025
Choice Rule and Payment Rule With transferable utility, a deterministic mapping ?:? ? can be split into Choice rule ?:? ? Payment rule ?:? ? And agent ? s utility in the induced game is ??? = ??? ? ,?? ??(?) 32 Fei Fang 3/21/2025
Quiz 3 What do you think are the desired properties and reasonable goals in the chocolate auction? A: The participant who wants the chocolate the most gets it B: Every participant can afford the required payment C: If a participant does not get the chocolate, he does not pay D: Every participant is willing to bid a price that equals his true valuation of the chocolate E: Designer maximize total payment collected from the participants F: Designer minimize the maximum difference among the participants payments G: Designer maximize the winner s valuation of the chocolate H: Designer make everyone likes him 33 Fei Fang 3/21/2025
Mechanism Design Desirable Properties Truthfulness Efficiency Budget balance Individual rationality In this lecture, we will focus on transferable utility and explain in the context of auction We will only introduce the high level idea instead of the rigorous definition 34 Fei Fang 3/21/2025
Truthfulness A mechanism is truthful if each agent ? s equilibrium strategy is to report his true valuation 35 Fei Fang 3/21/2025
Second Price Auction Every participant submitting a bid that equals their true valuation is a (Weakly) Dominant Strategy Equilibrium v or b 8 If ??< ?? If ?? ?? ?2 6 If ?1< ?2 If ?1> ?2 If ?1= ?1 (< ?2) If ?1< ?2 If ?1 ?2 If ?1= ?1 ( ?2) ?3 4 ?1 2 0 Player 1 Player 2 Player 3 36 Fei Fang 3/21/2025
Efficiency A mechanism for transferable utility function is efficient if total valuation of the non-monetary part of the outcome, i.e., ?=1 ??(?,??), is maximized in equilibrium Let agent 0 be the agent who collects payment (usually also the mechanism designer), and define his utility as the total payments he collects Then definition of efficiency is equivalent to: the total utility of all players (including the agent who collects payment from participants), i.e., ?=0 ??(?) is maximized In the chocolate auction, the mechanism is efficient if the chocolate go to the agent who values them most ? ? 38 Fei Fang 3/21/2025
Budget Balance A mechanism for transferable utility function is budget balanced when ?=1 equilibrium strategy profile and ??(?) is the payment of player ? The mechanism disburses and collects same amount of money to and from the participants ? ??? = 0 where ? is the How to make the chocolate auction budget balanced? Note: When ? is mixed strategy, it matters whether you consider ex ante or ex post A transferable utility mechanism is weakly budget balanced when ?=1 ??? 0 The mechanism may make a profit ? 39 Fei Fang 3/21/2025
Individual rationality A mechanism for transferable utility function is individual rational when ? [?],??(?) 0 where ? in the equilibrium strategy profile and ??(?) is the utility of player ? No agent lose by participating in the mechanism 40 Fei Fang 3/21/2025
Mechanism Design Commonly studied goals Revenue maximization Revenue minimization Maximin fairness Price of anarchy minimization 41 Fei Fang 3/21/2025
Revenue Maximization A mechanism for transferable utility function is revenue maximizing when, among the set of function ? and ? that satisfy the other constraints, the mechanism selects the ? and ? that maximize ?=1 ??(?) where ? is the equilibrium strategy profile Maximize the total payment the mechanism collects ? 42 Fei Fang 3/21/2025
Revenue Minimization A mechanism for transferable utility function is revenue maximizing when, among the set of function ? and ? that satisfy the other constraints, the mechanism selects the ? and ? that minimize ?=1 ??(?) where ? is the equilibrium strategy profile Minimize the total payment the mechanism collects ? 43 Fei Fang 3/21/2025
Survey In chocolate auction, which of the following do you think is fairest? A: Everyone pays 0, give the chocolate to the one who value the chocolate the highest B: Everyone pays 1/N of the actual cost of buying the chocolate, give the chocolate randomly C: The one submit the highest bid gets the chocolate, and pays the amount he submit. Everyone else pays 0 D: Each agent gets the chocolate with probability proportional to his true valuation, and the winner pays the actual cost of buying the chocolate 44 Fei Fang 3/21/2025
Maximin Fairness A mechanism for transferable utility function is maximin fair when, among the set of function ? and ? that satisfy the other constraints, the mechanism selects the ? and ? that maximize min ? [?]??? ? strategy profile Make the least-happy agent the happiest ??(?) where ? is the equilibrium 45 Fei Fang 3/21/2025
Price of Anarchy Minimization Recall: Once the mechanism is specified, it is a game among participating agents Price of Anarchy Minimization Minimize the ratio between optimal social welfare and the social welfare achieved in equilibrium given the mechanism A mechanism for transferable utility function minimizes the price of anarchy when, among the set of function ? and ? that satisfy the other constraints, the mechanism selects the ? and ? that minimize ?=1 strategy profile with the lowest ?=1 ma? ? ???? ? ??(?(?)) where ? is the equilibrium ? ??(?(?)) 46 Fei Fang 3/21/2025
Online Ads Bidding Commonly used: Generalized second-price auction or more complex variations 47 Fei Fang 3/21/2025
Summary Social Choice Voting model Voting rule: Majority consistency, Condorcet consistency, strategyproof, dictatorial, constant, onto Mechanism Design with Money Second-Price Auction 48 Fei Fang 3/21/2025
Advertisement 17-737/17-537 Artificial Intelligence Methods for Social Good: https://feifang.info/artificial-intelligence- methods-for-social-good-spring-2019/ Research opportunities: https://docs.google.com/forms/u/1/d/e/1FAIpQLSeB8F 0KgKRpYqd3Ctd8MWq5xThOKTMPJt6ZkywfF- ZqbTzVdw/viewform?usp=sf_link 49 Fei Fang 3/21/2025
Acknowledgment Some slides are borrowed from previous slides made by Ariel Procaccia Some slides are prepared based on course slides of Game Theory Online II (Matt Jackson, Kevin Leyton-Brown, Yoav Shoham) 50 Fei Fang 3/21/2025
