Private Matchings and Allocations

Download as pptx, pdf

1 like259 views

Steven Wu presented work on designing differentially private algorithms for maximum weight matchings and allocations. The goal is to output high welfare matchings while preserving privacy of individuals' valuations. The algorithms separate outputs so each agent only learns their own matching, and add noise to counters maintained privately to track demand. This allows computing prices that guide matchings without revealing full preferences. Under certain conditions on the number of goods and noise levels, a matching can be found with weight close to the optimal matching.

Science Technology Education

Private Matchings and Allocations
Joint work with
Justin Hsu (Penn)
Zhiyi Huang (HKU)
Aaron Roth (Penn)
Tim Roughgarden (Stanford)
Speaker: Steven Wu
University of Pennsylvania
STOC 2014

The Allocation Problem
n
bidders
m
items

An important special case:
? goods
? ∈ [?]
? agents
i ∈ [?]
1
2
3
A
B
C
? Unit demand valuations
? Equivalent to max-weight matching

Our Goal
High social welfare allocation
Privacy
(without revealing individual private valuations)

D
Differential Privacy
Algorithm
ratio bounded
Alice Bob Chris Donna ErnieXavier

Differential Privacy
? An algorithm A with domain X and range R
satisfies ε-differential privacy if for every outcome r
and every pair of databases D, D’ differing in one
record:
Pr[ A(D) = r ] ≤ (1 + ε)Pr[ A(D’) = r]
? Domain: Reported valuation functions
? Range: Matchings

Problem: Assignment Reveals Preference
? Problem: High welfare matching will give people
what they want.

Joint Differential Privacy (KPRU’14)
(MM09, GLMRT10)

Supply Assumption
? We need multiple copies for each
type of good even under JDP.
? How many?
Impossible Trivial

Main Result
Theorem: There is a JDP algorithm in the that solves the
max-weight matching problem with n people and k
types of goods with supply at least s each, and
outputs a matching of weight
OPT – αn
whenever:

A Framework for JDP
The “Billboard Model”

“Low information” Signal
o From the signal, every bidder can figure out what
item they are matched to in a matching
o Does not reveal each individual’s private data
? Think: Prices

Max Matchings (A Sketch)
A remarkable algorithm for Max-Matchings: [Kelso and Crawford ’82]

0.5 0.1
0 0.2
$0
$0
$0.1
$0.2
Outbid
$0.1
Bid Again

Prices as information
Claim: Bidders just need to see the prices
1. Prices are sufficient to identify the favorite good
2. When price raises again, a bidder is unmatched
3. Bidders are matched to the last thing they bid on
? Just need to count how many bids each good
received!

Privately Maintaining Counts
1 0 0 1 1 1 0 1 032
? Private (noisy) counters under continual observation
[DNPR10, CSS10]
? Given a stream of T bits, maintain an estimate of the
running count with accuracy
o Single Stream of sensitivity 1

Privately Maintaining Counts
1 1 1 1 1 1 0 0 018
1 0 0 1 1 1 0 1 032
0 0 0 1 1 1 1 1 0192
? A straightforward generalization:
K counters on K streams that collectively have
sensitivity Δ gives accuracy

Lower Sensitivity
Stopping the auction early
with a new condition
? Sensitivity

Supply
? Goods might also be under/over-allocated by E.
o Doesn’t reduce the welfare by more than (1-α) factor if

Main Theorem
Theorem: There is a private algorithm in the billboard
model that solves the max-weight matching problem
with n people and k types of goods with supply at
least s each, and outputs a matching of weight
OPT – αn
whenever:

Extensions
? Results extend to the allocation problem
when buyers have gross substitute
preferences.

Conclusions
? Some problems that can’t be solved under DP
can be solved under joint-DP.
o If the output is partitioned among the agents
o The agent’s output is allowed to be sensitive in his input.
? Billboard model: interesting framework to design
a joint-DP algorithm?

This document provides an overview of support vector machines (SVMs), including their basic concepts, formulations, and applications. SVMs are supervised learning models that analyze data, recognize patterns, and are used for classification and regression. The document explains key SVM properties, the concept of finding an optimal hyperplane for classification, soft margin SVMs, dual formulations, kernel methods, and how SVMs can be used for tasks beyond binary classification like regression, anomaly detection, and clustering.

K Nearest NeighborsTilani Gunawardena PhD(UNIBAS), BSc(Pera), FHEA(UK), CEng, MIESL

The document discusses the K-nearest neighbors (KNN) algorithm, a simple machine learning algorithm used for classification problems. KNN works by finding the K training examples that are closest in distance to a new data point, and assigning the most common class among those K examples as the prediction for the new data point. The document covers how KNN calculates distances between data points, how to choose the K value, techniques for handling different data types, and the strengths and weaknesses of the KNN algorithm.

KnnNarkaji Gurung

KNN is a simple machine learning algorithm that classifies new data points based on their similarity to existing stored data points. It works by finding the k nearest neighbors of the new data point based on a distance measure and assigning the most common class (for classification) or average value (for regression) of the k nearest neighbors. Though conceptually simple, KNN can solve complex problems with little information needed and no explicit training. However, it requires storing all training data and is sensitive to representation and feature selection.

Nearest Neighbor Algorithm Zaffar AhmedZaffar Ahmed Shaikh

The document summarizes the K-nearest neighbor (KNN) algorithm. KNN is a memory-based algorithm that finds the K training samples nearest to a query point and predicts the query's classification based on the majority classification of its neighbors. The summary explains: 1) KNN measures the distance between query points and training samples to classify new objects based on the majority category of its K nearest neighbors. 2) To make a prediction, KNN determines K, calculates distances between the query and all training points, identifies the K nearest neighbors, collects their classifications, and predicts the query's classification based on the majority of its neighbors. 3) An example is given where KNN predicts the winner of an

Machine Learning and Data Mining: 13 Nearest Neighbor and Bayesian ClassifiersPier Luca Lanzi

This document provides an overview of nearest neighbor and Bayesian classifiers for machine learning. It discusses how nearest neighbor classifiers work by finding the k closest training examples in attribute space and classifying new examples based on the class of its neighbors. It also explains naive Bayesian classification, which uses Bayes' theorem and assumes attribute independence to calculate class probabilities. Examples are given of how to apply these techniques to classification problems.

[ppt]butest

This document provides an overview of various machine learning classification techniques including decision trees, k-nearest neighbors, decision lists, naive Bayes, artificial neural networks, and support vector machines. For each technique, it discusses the basic approach, how models are trained and tested, and potential issues that may arise such as overfitting, parameter selection, and handling different data types.

sentiment analysis using support vector machineShital Andhale

SVM is a supervised machine learning algorithm that can be used for classification or regression. It works by finding the optimal hyperplane that separates classes by the largest margin. SVM identifies the hyperplane that results in the largest fractional distance between data points of separate classes. It can perform nonlinear classification using kernel tricks to transform data into higher dimensional space. SVM is effective for high dimensional data, uses a subset of training points, and works well when there is a clear margin of separation between classes, though it does not directly provide probability estimates. It has applications in text categorization, image classification, and other domains.

Decision TreesStudent

Decision trees are a type of supervised learning algorithm used for classification and regression. ID3 and C4.5 are algorithms that generate decision trees by choosing the attribute with the highest information gain at each step. Random forest is an ensemble method that creates multiple decision trees and aggregates their results, improving accuracy. It introduces randomness when building trees to decrease variance.

Prezentacja1Asia Gawrońska

PhotoshopSinNombreReader

Prezentacja1Asia Gawrońska

201313044 ??? ???? 20140610blackcat1215

Letter of intenteddygon78

The document provides information about the importance of a letter of intent for university applications and offers professional writing services for various types of letters. It outlines the key components that should be included in a letter of intent and describes the company's process and guarantees to ensure customer satisfaction. Additionally, it emphasizes the benefits of using their service, including tailored writing, proper formatting, and timely delivery.

Open design at large scaleshykes

The document discusses the scalability of Docker in managing contributions from a large community, highlighting the significance of collaboration over technology. It presents metrics from 2014 showing the number of pull requests and their processing times, comparing contributions from Docker, Inc. and the community. The author proposes a new governance model to streamline the management of contributors and sub-projects in open-source development.

Zelfrespect en zelfvertrouwenMarie Helene de Canniere

????????50355

Docker: the road aheadshykes

1. The document discusses Docker's roadmap which includes standardizing interfaces for container sandboxing (libcontainer), communication between containers and components (libchan), and orchestrating distributed services (libswarm). 2. It announces libcontainer becoming a standalone project and new contributors joining its development. Libchan is introduced as a lightweight communication protocol and libswarm is presented as a toolkit for composing network services. 3. Identity and authorization are mentioned as upcoming areas of focus, and the document encourages participation in developing these Docker projects.

Marketing Experiment - Part II: Analysis Minha Hwang

This document outlines an experiment conducted for a marketing research class. It discusses different types of experimental designs, including between-subjects and within-subjects designs. It also covers the trade-offs between field and lab experiments. Finally, it provides an overview of statistical analysis techniques like ANOVA and regression that can be used to analyze experimental data, including an example experiment involving different advertising themes and price levels.

Repeated Measures t-testKaori Kubo Germano, PhD

- The document describes a study that examined whether cursing focuses or distracts from pain using an ice water test. - Participants submerged their hands in ice water under two conditions - when swearing aloud and when not swearing. The length of time each group kept their hands in the water was recorded. - This is an example of a repeated measures or within-subjects design where the same participants undergo both conditions and their results are compared to see if swearing impacted pain tolerance.

Static characteristics of InstrumentsChandan Singh

The document discusses the static characteristics of measuring instruments, focusing on span, range, accuracy, precision, and calibration. It explains concepts such as mean, standard deviation, significant figures, and errors in measurements, alongside practical considerations like resolution and sensitivity. Additionally, it highlights the importance of calibrating instruments and the impact of external factors on measurements, including hysteresis and drift.

[系列活動] 人工智慧與機器學習在推薦系統上的應用台湾资料科学年会

The document provides an overview of recommender systems, including various models and evaluation methods. It covers the benefits of recommendation systems for both service providers and customers, and discusses content-based recommendation, collaborative filtering, and advanced issues. The speaker, Professor Shou-de Lin, outlines key concepts, requirements, and techniques involved in developing effective recommender systems.

Study on Application of Ensemble learning on Credit Scoringharmonylab

This document discusses using ensemble learning techniques for credit scoring applications. It begins by providing background on the growing need for effective credit scoring models due to the expansion of financing opportunities. It then discusses some common problems with credit scoring models, including a lack of understandability, multiple evaluation metrics, and imbalanced data. The purpose is to build a better credit scoring model using machine learning, specifically ensemble learning with XGBoost. Two proposed methods are described: 1) using EasyEnsemble resampling prior to XGBoost to address imbalanced data, and 2) customizing XGBoost by changing the evaluation metric to directly optimize cost or using a focal loss function. Experiments on several credit scoring datasets show these approaches can reduce costs without reducing accuracy

Learning when to give up: theory, practice and perspectivesGiuseppe (Pino) Di Fabbrizio

The document discusses machine learning models learning when to give up or reject classifying examples. It proposes three main approaches: 1) Using calibrated confidence estimates to account for natural confusability in the training data, 2) Handling input noise with a secondary confidence predictor, and 3) Making classifiers aware of what examples are unknown based on the training data. The focus is on classification problems, where rejecting allows transferring to a human for assistance. The goal is to minimize rejections while maintaining a fixed error rate.

W5_CLASSIFICATION.pptxW5_CLASSIFICATION.pptxNandiniKumari54

The k-nearest neighbor (k-NN) algorithm is a simple, non-parametric supervised learning technique used for classification and density estimation based on the similarity between data points. It is a lazy learner that does not learn from the training data until classification begins, and its performance depends significantly on the choice of k, the distance metric, and a balanced training set. The document also discusses applications in image recognition and the importance of distance measurement, highlighting the need for standardization of predictors and cross-validation to determine the most effective parameters.

k-nearest neighbour Machine Learning.pdfSabbirAhmed346057

The document explains the k-nearest neighbor (k-NN) algorithm, a supervised learning method used for classification based on the similarity of neighbors. It covers aspects such as distance metrics, the optimal choice of hyperparameters like the number of neighbors (k), and the impact of noise on decision boundaries. Furthermore, it provides examples and discusses techniques for determining suitable hyperparameters through validation and cross-validation methods.

Lecture 8 about data mining and how to use it.pptxHedraAtif

La minería de datos es el proceso de identificar patrones ocultos en grandes bases de datos para extraer información útil. Se exploran técnicas como clasificaciones de vecinos más cercanos y máquinas de soporte vectorial para resolver problemas de clasificación, optimizando el margen de separación entre clases. También se discute la regresión logística y sus aplicaciones en predicciones de probabilidad de clases, destacando la importancia de encontrar el valor óptimo de los parámetros en modelos predictivos.

Top-N Recommendation for Shared Accountskoeverstrep

The document discusses the challenges faced by recommender systems when multiple users share a single account, identifying three primary issues: the dominance problem, generality problem, and presentation problem. It outlines an algorithm designed to address these issues and improve recommendation relevance for all users sharing an account. The paper highlights the importance of contextual information in item-based recommendation approaches.

Distributed constraint Optimization lec2.pptAhmedAlwakeel9

The document discusses auction-based solutions for distributed constraint optimization in multi-agent systems, particularly focusing on task assignment and scheduling problems. It describes various negotiation methods for agents to obtain optimal task allocations, explores linear and integer programming formulations, and addresses challenges in achieving both individual and global optimizations. The document outlines competitive equilibrium concepts and algorithms to facilitate effective bidding and price adjustments among agents in these systems.

Deep learning from mashine learning AI..premkumarlive

The document introduces machine learning algorithms, emphasizing their ability to improve performance through experience and generalization to unseen inputs. It discusses various types of learning algorithms such as supervised, unsupervised, and semi-supervised learning, as well as different models like classification, regression, and clustering techniques. Key concepts such as decision trees, k-nearest neighbors, and boosting methods, along with challenges like the curse of dimensionality and computational complexity, are also outlined.

Classification Based Machine Learning AlgorithmsMd. Main Uddin Rony

This document provides an overview of classification-based machine learning algorithms, primarily focusing on naive Bayes classifiers and decision trees. It explains the workings of the naive Bayes classifier using Bayes' theorem and class-conditional independence, along with hands-on examples. Furthermore, it outlines the process of building decision trees using the ID3 algorithm, entropy, information gain, and the k-nearest neighbors classification method.

More Related Content

Viewers also liked (9)

Prezentacja1Asia Gawrońska

PhotoshopSinNombreReader

Prezentacja1Asia Gawrońska

201313044 ??? ???? 20140610blackcat1215

Letter of intenteddygon78

Open design at large scaleshykes

Zelfrespect en zelfvertrouwenMarie Helene de Canniere

????????50355

Docker: the road aheadshykes

Prezentacja1Asia Gawrońska

PhotoshopSinNombreReader

Prezentacja1Asia Gawrońska

201313044 ??? ???? 20140610blackcat1215

Letter of intenteddygon78

Open design at large scaleshykes

Zelfrespect en zelfvertrouwenMarie Helene de Canniere

????????50355

Docker: the road aheadshykes

Similar to Private Matchings and Allocations (20)

Marketing Experiment - Part II: Analysis Minha Hwang

Repeated Measures t-testKaori Kubo Germano, PhD

Static characteristics of InstrumentsChandan Singh

[系列活動] 人工智慧與機器學習在推薦系統上的應用台湾资料科学年会

Study on Application of Ensemble learning on Credit Scoringharmonylab

Learning when to give up: theory, practice and perspectivesGiuseppe (Pino) Di Fabbrizio

W5_CLASSIFICATION.pptxW5_CLASSIFICATION.pptxNandiniKumari54

k-nearest neighbour Machine Learning.pdfSabbirAhmed346057

Lecture 8 about data mining and how to use it.pptxHedraAtif

Top-N Recommendation for Shared Accountskoeverstrep

Distributed constraint Optimization lec2.pptAhmedAlwakeel9

Deep learning from mashine learning AI..premkumarlive

Classification Based Machine Learning AlgorithmsMd. Main Uddin Rony

Relational machine-learningBhushan Kotnis

This document provides an overview of relational machine learning models and applications. It discusses how networks and graphs like social networks, biological networks, financial networks, and knowledge graphs can be modeled using relational machine learning. Specific models discussed include recommendation engines that use matrix factorization, the RESCAL model for multi-relational data, bilinear diagonal models for scalability, and TransE which models relationships as translations in the embedding space. The document also covers generating negative samples and different loss functions used for training these models.

Clique and stingSubramanyam Natarajan

CLIQUE is an algorithm for subspace clustering of high-dimensional data. It works in two steps: (1) It partitions each dimension of the data space into intervals of equal length to form a grid, (2) It identifies dense units within this grid and finds clusters as maximal sets of connected dense units. CLIQUE efficiently discovers clusters by identifying dense units in subspaces and intersecting them to obtain candidate dense units in higher dimensions. It automatically determines relevant subspaces for clustering and scales well with large, high-dimensional datasets.

Machine Learning Algorithms Introduction.pdfVinodh58

Rotting Infinitely Many-Armed BanditsJunghunKim27

This document discusses rotting infinitely many-armed bandits, where the mean reward of selected actions decreases over time. It introduces the problem, related work on finite and infinite stationary bandits, and presents the authors' contributions - a regret lower bound and two algorithms that achieve near-optimal regret bounds with and without knowledge of the maximum rotting rate. The algorithms use an upper confidence bound approach and thresholding to explore new arms as current arms become suboptimal due to reward rotting.

k-nearest neighbour Machine Learning.pptxSabbirAhmed346057

The document discusses the k-nearest neighbor (KNN) algorithm, a supervised machine learning method for classification based on the similarity between data points. It explains concepts such as using distance metrics (L1, L2), the importance of choosing the right number of neighbors (k), and techniques for setting hyperparameters, including cross-validation. Additionally, a practical example illustrates how the KNN algorithm classifies data points based on their neighbors.

ilp-nlp-slides.pdfFlorentBersani

This document discusses correlation clustering algorithms that can be used when integer linear programming formulations are not scalable. It presents a greedy voting scheme algorithm and local search as alternatives to ILP. It also introduces a semidefinite programming bound that provides a tighter lower bound than previous methods. The algorithms are evaluated on two clustering tasks: the Twenty Newsgroups dataset and chat disentanglement. The results show local search performs best and is close to optimal, while the objective function does not always predict performance metrics.

A new similarity measurement based on hellinger distance for collaborating fi...Prabhu Kumar

The document presents a new similarity measurement method based on Hellinger distance for collaborative filtering in sparse datasets, fulfilling the requirements for a Master's degree in Technology. It discusses various recommendation systems, their architectures, and measures of similarity, comparing traditional methods with the proposed Hellinger distance approach. The results demonstrate improvements in handling issues such as few co-rated items and simultaneous differences in ratings, validated through evaluations using large datasets.

Marketing Experiment - Part II: Analysis Minha Hwang

Repeated Measures t-testKaori Kubo Germano, PhD

Static characteristics of InstrumentsChandan Singh

[系列活動] 人工智慧與機器學習在推薦系統上的應用台湾资料科学年会

Study on Application of Ensemble learning on Credit Scoringharmonylab

Learning when to give up: theory, practice and perspectivesGiuseppe (Pino) Di Fabbrizio

W5_CLASSIFICATION.pptxW5_CLASSIFICATION.pptxNandiniKumari54

k-nearest neighbour Machine Learning.pdfSabbirAhmed346057

Lecture 8 about data mining and how to use it.pptxHedraAtif

Top-N Recommendation for Shared Accountskoeverstrep

Distributed constraint Optimization lec2.pptAhmedAlwakeel9

Deep learning from mashine learning AI..premkumarlive

Classification Based Machine Learning AlgorithmsMd. Main Uddin Rony

Relational machine-learningBhushan Kotnis

Clique and stingSubramanyam Natarajan

Machine Learning Algorithms Introduction.pdfVinodh58

Rotting Infinitely Many-Armed BanditsJunghunKim27

k-nearest neighbour Machine Learning.pptxSabbirAhmed346057

ilp-nlp-slides.pdfFlorentBersani

A new similarity measurement based on hellinger distance for collaborating fi...Prabhu Kumar

Recently uploaded (20)

Sujay Rao Mandavilli public profile June 2025.pdfSujay Rao Mandavilli

GBSN_ Unit 1 - Introduction to MicrobiologyAreesha Ahmad

Single-Cell Multi-Omics in Neurodegeneration p1.pptxKanakChaudhary10

Properties of Gases siwhdhadpaldndn.pptxCatherineJadeBurce

SULFUR PEARL OF NAMIBIA - Thiomargarita namibiensisaparnamp966

This document explores the fascinating discovery and ecological significance of Thiomargarita namibiensis, known as the "Sulfur Pearl of Namibia"—the largest bacterium ever found. Discovered in 1999 by researchers from the Max Planck Institute, this bacterium thrives in sulfur-rich environments like Walvis Bay, Namibia. Despite sulfur’s toxicity, T. namibiensis plays a crucial role in detoxifying the marine habitat by oxidizing harmful hydrogen sulfide using internally stored nitrate. The bacterium’s ability to store nitrate at concentrations 10,000 times higher than seawater and survive in extreme conditions makes it ecologically vital and a subject of interest for evolutionary research and potential future biotechnological applications. The document emphasizes its environmental role, potential for space-related anaerobic survival, and the challenge of cultivating it in lab settings. Author: Aparna M P

Type of Heat Exchanger operation Socar pptxTuralQuliyev5

Science Holiday Homework (interesting slide )aryanxkohli88

Enzyme Kinetics_Lecture 8.5.2025 Enzymology.pdfayeshaalibukhari125

Operationalising OGC Processes with Application Packages in ILIAD: A Service ...Marco Amaro Oliveira

This contribution presents the integration of the EO Application Package model into the ILIAD Digital Twin of the Ocean architecture, using the OGC API Processes DRU specification. Built on the EOEPCA framework and OGC best practices and specifications, the approach enables standardized, containerized EO applications packaged with CWL to run across a wide range of infrastructures including Kubernetes and HPC. These applications are already in use across several platforms, and in ILIAD they have been applied to models such as oil spill forecasting, aquaculture, wave energy, and ship routing. The EDITO platform supports OGC API Processes but is currently optimized for simpler workflows using environment variables. To enhance compatibility with EO Application Packages, ILIAD introduces a Kubernetes-based ADES implementation, enabling dynamic execution and integration with EDITO's object store and metadata catalog. The experience is also informing the evolution of the OGC Best Practice, and practical solutions for bridging architectural gaps will be discussed.

GBSN__Unit 2 - Control of MicroorganismsAreesha Ahmad

Flexible Denture -Removable partial denture.pptxNekemiya

Relazione di laboratorio Idrolisi dell'amido (in inglese)paolofvesco

An Analysis Of The Pearl Short Story By John SteinbeckBillyDarmawan3

John Steinbeck Popular Short Story The Pearl adalah sebuah novella yang ditulis oleh John Steinbeck yang mengisahkan perjuangan seorang nelayan miskin bernama Kino dan istrinya, Juana, yang hidup sederhana di sebuah desa kecil Meksiko. Suatu hari, Kino menemukan sebuah mutiara raksasa — "the Pearl of the World" — yang diyakini akan mengubah nasib mereka. Namun, alih-alih membawa kebahagiaan, mutiara itu justru menimbulkan keserakahan, kekerasan, dan penderitaan. Masyarakat di sekitarnya mulai menunjukkan niat jahat, dan bahkan keluarga Kino sendiri terjebak dalam konflik batin antara harapan dan kehancuran. Pada akhirnya, The Pearl menjadi simbol ironi: sesuatu yang tampak sebagai berkah berubah menjadi kutukan. Melalui cerita ini, Steinbeck mengeksplorasi tema keserakahan, harapan, kemiskinan, dan ketimpangan sosial. Dengan gaya narasi yang lugas namun penuh makna simbolik, The Pearl menjadi refleksi tajam tentang sifat manusia dan dampak tragis dari keinginan yang tak terkendali.

HERBAL INGREDIENTS USED IN ORAL CARE.pptxVidhi889356

Science grade 7 assesement Quarter I based on matatag curriculumBryanLebasnon1

Lecture 9 Natural selection Evolution.pptxmadi34702

242680824006, 09, 02 suoac guideline nd bacpac091HarshikaModi

What is Skeleton system.pptx by aahil sirbhatbashir421

science, any system of knowledge that is concerned with the physical world and its phenomena and that entails unbiased observations and systematic experimentation. In general, a science involves a pursuit of knowledge covering general truths or the operations of fundamental laws. Science can be divided into different branches based on the subject of study. The physical sciences study the inorganic world and comprise the fields of astronomy, physics, chemistry, and the Earth sciences. The biological sciences such as biology and medicine study the organic world of life and its processes. Social sciences like anthropology and economics study the social and cultural aspects of human behaviour. Science is further treated in a number of articles. For the history of Western and Eastern science, see science, history of. For the conceptualization of science and its interrelationships with culture, see science, philosophy of. For the basic aspects of the scientific approach, see physical science, principles of; and scientific method. Model of a molecule. Atom, Biology, Molecular Structure, Science, Science and Technology. Homepage 2010 arts and entertainment, history and society Britannica Quiz Science Quiz The Editors of Encyclopaedia Britannica This article was most recently revised and updated by Encyclopaedia Britannica. physics Table of Contents Introduction & Top Questions The scope of physics The methodology of physics Relations between physics and other disciplines and society References & Edit History Related Topics Images & Videos Bernoulli model of gas pressureillustration of Robert Hooke's law of elasticity of materialsLaser Interferometer Space Antenna (LISA)curved space-timetemperature scalesBrownian particleElectromagnetic radiationDiffraction gratingMillikan oil-drop experiment Robert Millikan's method for measuring the charge of an electron For Students Diffraction grating physics summary Quizzes Michael Faraday (L) English physicist and chemist (electromagnetism) and John Frederic Daniell (R) British chemist and meteorologist who invented the Daniell cell. Faces of Science Italian-born physicist Dr. Enrico Fermi draws a diagram at a blackboard with mathematical equations. circa 1950. Physics and Natural Law Italian physicist Guglielmo Marconi at work in the wireless room of his yacht Electra, c. 1920. All About Physics Quiz atom. Orange and green illustration of protons and neutrons creating the nucleus of an atom. Another Physics Quiz Encyclopaedia Britannica thistle graphic to be used with a Mendel/Consumer quiz in place of a photograph. How Much Do You Know About Physics? Related Questions Why does physics work in SI units? Read Next Highway Night Traffic Portland, drive, driving, car, automobile. What's the Difference Between Speed and Velocity? Galaxy clusters like Abell 2744 can act as a natural cosmic lens, magnifying light from more distant, background objects through gravity.

The scientific heritage No 162 (162) (2025)The scientific heritage

We are Living in a Dangerous Multilingual World!Editions La Dondaine

They say Artificial Intelligence will solve that problem in a jiffy. They are telling you a tall tale straight from Mark Twain’s trove. It may compare with “The Celebrated Jumping Frog of Calaveras County.” Only a maximum of twelve languages will be able to have an AI, hence translation machines, because only them will have a big enough LLM to be able to produce and train an Artificial Intelligence. That’s the positive element. But on the negative side, several (many) thousand languages will not be able to have an AI, hence a translation machine. The real danger is the homogenization of AI-compatible languages and the statistical customization of all languages on the pattern of these twelve languages. You must be joking! On the model of only ONE AI-compatible language, English, and all other languages will be in contact with this “English-Norm,” and all languages will follow the AI-customized English that all machines, all media, and all people will be repeating after the AI translation machine: “My tailor is rich,” the first sentence of L'Anglais sans peine, the first work in the Assimil method for learning English, written by Alphonse Chérel in 1929. Is that the future of humanity, or the bad nightmare of a cat lost in the jigsaw puzzle of a supernatural spiritual Cat Country? Or maybe the Time Machine that will take us to paradise in a universe at least three million light years away from this dirty earth, in whose mud we are swaddling ourselves piggishly.

Sujay Rao Mandavilli public profile June 2025.pdfSujay Rao Mandavilli

GBSN_ Unit 1 - Introduction to MicrobiologyAreesha Ahmad

Single-Cell Multi-Omics in Neurodegeneration p1.pptxKanakChaudhary10

Properties of Gases siwhdhadpaldndn.pptxCatherineJadeBurce

SULFUR PEARL OF NAMIBIA - Thiomargarita namibiensisaparnamp966

Type of Heat Exchanger operation Socar pptxTuralQuliyev5

Science Holiday Homework (interesting slide )aryanxkohli88

Enzyme Kinetics_Lecture 8.5.2025 Enzymology.pdfayeshaalibukhari125

Operationalising OGC Processes with Application Packages in ILIAD: A Service ...Marco Amaro Oliveira

GBSN__Unit 2 - Control of MicroorganismsAreesha Ahmad

Flexible Denture -Removable partial denture.pptxNekemiya

Relazione di laboratorio Idrolisi dell'amido (in inglese)paolofvesco

An Analysis Of The Pearl Short Story By John SteinbeckBillyDarmawan3

HERBAL INGREDIENTS USED IN ORAL CARE.pptxVidhi889356

Science grade 7 assesement Quarter I based on matatag curriculumBryanLebasnon1

Lecture 9 Natural selection Evolution.pptxmadi34702

242680824006, 09, 02 suoac guideline nd bacpac091HarshikaModi

What is Skeleton system.pptx by aahil sirbhatbashir421

The scientific heritage No 162 (162) (2025)The scientific heritage

We are Living in a Dangerous Multilingual World!Editions La Dondaine

Private Matchings and Allocations

1. Private Matchings and Allocations Joint work with Justin Hsu (Penn) Zhiyi Huang (HKU) Aaron Roth (Penn) Tim Roughgarden (Stanford) Speaker: Steven Wu University of Pennsylvania STOC 2014

2. The Allocation Problem n bidders m items

3. An important special case: ? goods ? ∈ [?] ? agents i ∈ [?] 1 2 3 A B C ? Unit demand valuations ? Equivalent to max-weight matching

4. Our Goal High social welfare allocation Privacy (without revealing individual private valuations)

5. D Differential Privacy Algorithm ratio bounded Alice Bob Chris Donna ErnieXavier

6. Differential Privacy ? An algorithm A with domain X and range R satisfies ε-differential privacy if for every outcome r and every pair of databases D, D’ differing in one record: Pr[ A(D) = r ] ≤ (1 + ε)Pr[ A(D’) = r] ? Domain: Reported valuation functions ? Range: Matchings

7. Problem: Assignment Reveals Preference ? Problem: High welfare matching will give people what they want.

8. Separate Outputs Algorithm

9. Protect from Coalition Algorithm !

10. Joint Differential Privacy (KPRU’14) (MM09, GLMRT10)

11. Supply Assumption ? We need multiple copies for each type of good even under JDP. ? How many? Impossible Trivial

12. Main Result Theorem: There is a JDP algorithm in the that solves the max-weight matching problem with n people and k types of goods with supply at least s each, and outputs a matching of weight OPT – αn whenever:

13. A Framework for JDP The “Billboard Model”

14. “Low information” Signal o From the signal, every bidder can figure out what item they are matched to in a matching o Does not reveal each individual’s private data ? Think: Prices

15. Max Matchings (A Sketch) A remarkable algorithm for Max-Matchings: [Kelso and Crawford ’82]

16. 0.5 0.1 0 0.2 $0 $0 $0.1 $0.2 Outbid $0.1 Bid Again

17. Welfare

18. Prices as information Claim: Bidders just need to see the prices 1. Prices are sufficient to identify the favorite good 2. When price raises again, a bidder is unmatched 3. Bidders are matched to the last thing they bid on ? Just need to count how many bids each good received!

19. Privately Maintaining Counts 1 0 0 1 1 1 0 1 032 ? Private (noisy) counters under continual observation [DNPR10, CSS10] ? Given a stream of T bits, maintain an estimate of the running count with accuracy o Single Stream of sensitivity 1

20. Privately Maintaining Counts 1 1 1 1 1 1 0 0 018 1 0 0 1 1 1 0 1 032 0 0 0 1 1 1 1 1 0192 ? A straightforward generalization: K counters on K streams that collectively have sensitivity Δ gives accuracy

21. Lower Sensitivity Stopping the auction early with a new condition ? Sensitivity

22. Counter Error ? Error per bid counter

23. Supply ? Goods might also be under/over-allocated by E. o Doesn’t reduce the welfare by more than (1-α) factor if

24. Main Theorem Theorem: There is a private algorithm in the billboard model that solves the max-weight matching problem with n people and k types of goods with supply at least s each, and outputs a matching of weight OPT – αn whenever:

25. Extensions ? Results extend to the allocation problem when buyers have gross substitute preferences.

26. Conclusions ? Some problems that can’t be solved under DP can be solved under joint-DP. o If the output is partitioned among the agents o The agent’s output is allowed to be sensitive in his input. ? Billboard model: interesting framework to design a joint-DP algorithm?

27. Private Matchings and Allocations Joint work with Justin Hsu (Penn) Zhiyi Huang (HKU) Aaron Roth (Penn) Tim Roughgarden (Stanford) Speaker: Steven Wu University of Pennsylvania

Editor's Notes

#6: Of course, since our talk is the last talk of this session. The first notion of privacy we would look at is differential privacy. Some of you might have seen this pictures many times. It says that if we change the input database by one record, the output distribution induced by our randomized algorithm is not affected by much.
#8: If there is no contention for goods, a high welfare matching has to give people what they want. A high welfare allocation will give people what they want. Consider a scenario where people either like alcohol or cigarettes. The tension between social welfare and privacy makes it impossible to work with standard differential privacy.
#14: Not the songs you heard on radio. A nice decentralized model
#15: The idea is to have our mechanism broadcast some low information signal to all of the agents. The signal itself should satisfy standard DP. And a natural candidate for such a signal in allocation problem is prices.

狠狠撸

Private Matchings and Allocations

Recommended

More Related Content

Viewers also liked (9)

Similar to Private Matchings and Allocations (20)

Recently uploaded (20)

Private Matchings and Allocations

Editor's Notes