Implementing Fairness Constraints in Markets Using Taxes and Subsidies Alexander Peysakhovich

2025-05-08 0 0 434.67KB 23 页 10玖币

侵权投诉

Implementing Fairness Constraints in Markets Using

Taxes and Subsidies

Alexander Peysakhovich

Meta AI Research

Christian Kroer

Meta Core Data Science

Columbia University

Nicolas Usunier

Meta AI Research

Abstract

Fisher markets are those where buyers with budgets compete for scarce items,

a natural model for many real world markets including online advertising. A

market equilibrium is a set of prices and allocations of items such that supply

meets demand. We show how market designers can use taxes or subsidies in Fisher

markets to ensure that market equilibrium outcomes fall within certain constraints.

We show how these taxes and subsidies can be computed even in an online setting

where the market designer does not have access to private valuations. We adapt

various types of fairness constraints proposed in existing literature to the market

case and show who beneﬁts and who loses from these constraints, as well as the

extent to which properties of markets including Pareto optimality, envy-freeness,

and incentive compatibility are preserved. We ﬁnd that some prior discussed

constraints have few guarantees in terms of who is made better or worse off by

their imposition.

1 Introduction

A market solves the economic problem of “who gets what and why” (Roth, 2015). Unfortunately,

there is no guarantee that market outcomes will always align with other objectives of the market

designer such as business needs, legal constraints, or notions of fairness. Recent work proposes

the addition of ‘fairness constraints’ into various allocation mechanisms (Celis et al

, 2019; Ilvento

et al

, 2020; Chawla and Jagadeesan, 2022; Celli et al

, 2022; Balseiro et al

, 2021b). We study how

market designers can use price interventions to ensure that market outcomes satisfy arbitrary linear

constraints. We consider prior proposed interventions and study them in a market setting, paying

particular attention to both individual and aggregate level consequences. Importantly, we show that

second-order effects in markets can mean that well intended interventions do not achieve their goals.

We focus on Fisher markets where budget constrained buyers compete for items that are in limited

supply (Eisenberg and Gale, 1959). Given prices for items, demand is the result of buyers maximizing

their utilities. An equilibrium in Fisher markets are prices and allocations such that supply equals

demand.

The Fisher model allows us to abstract away from the details of how a market works and study equilib-

ria as properties of demand and supply directly. For example, even though individual impressions in

many real world advertising markets are allocated via paced auctions, the aggregate outcome across

all advertisers and impressions is that prices make supply of ad slots equal to advertiser demand for

ad slots – in other words, a Fisher market equilibrium (Conitzer et al., 2019, 2022).

From the perspectives of buyers and market designers, Fisher equilibria are well understood. The

allocations are Pareto-optimal and envy-free up to budgets (no buyer strictly prefers another buyer’s

bundle to their own bundle when budgets are equal) (Varian, 1974; Budish and Cantillon, 2012).

When markets are ‘large’ buyers have no incentives to lie about their valuations of items (Azevedo

and Budish, 2018; Peysakhovich and Kroer, 2019).

Preprint. Under review.

arXiv:2210.02586v2 [cs.GT] 13 Mar 2023

However, equilibrium-based allocations can have undesirable distributive properties from the point

of view of group-level fairness. For example, recent work argues advertising markets may result in

outcomes which may be ‘unfair’ in various senses (Ali et al

, 2019; Zhang, 2021; Imana et al

, 2021).

We ask how market designers can ‘adjust’ market outcomes to ﬁx these undesirable distributional

properties.

A common tool for market designers is price intervention (Pigou, 1924) – taxing or subsidizing some

market transactions. Our main technical contribution is to give designers a way to target these in

Fisher markets. Given a family of linear constraints, we show to construct a set of price interventions

– taxes and subsidies for some purchases – such that there are allocations which satisfy the constraints

and are also market equilibria. We show how to do this both in a full information one-shot setting, as

well an online, decentralized setting using an algorithm we call online price intervention calculation

(OPIC).

Many constraint families proposed in the literature can be written as linear constraints. For each

of these proposed constraint families we ask: how are market outcome properties affected by the

imposition of these constraints? Does imposition of these constraints always satisfy certain goals?

Who wins and who loses when these interventions are made? The results are not always intuitive

and, because second-order effects abound in markets, do not always achieve the stated goals of the

constraints.

Motivated by work on ad delivery Ali et al

(2019), we consider buyer parity constraints where

items are split into groups

and

and each buyer in a set is required to have parity in allocation

with respect to these groups (Ali et al

, 2019; Celis et al

, 2019; Ilvento et al

, 2020; Chawla and

Jagadeesan, 2022; Celli et al

, 2022). This constraint guarantees parity in exposure between the

and

groups, however it does not guarantee Pareto optimality even when item group welfare is taken

into account. In addition, we show that this intervention can lead to the previously disadvantaged

group receiving less aggregate exposure than before.

Motivated by the work on job search of Geyik et al

(2019) we also consider the ‘transpose’ of the

above constraint - per item parity constraints. Buyers have group labels

and

and some set of

items are each required to have equal exposure in the buyer groups. Here the goal is that items (e.g.

recruiter impressions) have parity in exposure to buyers (e.g. resumes of two groups of individuals).

Here, again, we lack Pareto optimality and the intervention can reduce the utility of a previously

disadvantaged buyer group.

We additionally consider a ‘ﬂoor’ constraint where we require that a subset of buyers have a minimum

exposure to a subset of items. We ﬁnd that this intervention gives outcomes that are Pareto optimal

if item exposure utility is taken into account but not otherwise. Satisfying this constraint in market

outcomes is equivalent to the market designer subsidizing constrained buyers’ purchases of the

protected items, and though this may sound uniformly welfare improving, we show that buyers in the

constrained group can have their welfare reduced by the intervention.

We show that each of the above constraint families maintains the incentive properties of Fisher

markets as long as the group of buyers on whom the constraint applies grows large with the market.

Finally, many of our counter-examples are ‘worst case’ scenarios. We consider random markets with

constraints and ask what an ‘average case’ outcome might look like.

Overall, our contribution can be split into two parts: the ﬁrst is how a market designer

could

implement general linear constraints. The second is a focus whether they

should

implement a

particular sets of constraints. The main takeaway for practitioners is that often there are no guarantees

that second-order effects from constraint imposition may not create more problems than the constraint

solves. We are not arguing for

interventions, but rather that interventions should be made carefully

and thoughtfully.

2 Related Work

There is large interest in centralized market allocation as a solution to the multi-unit assignment

problem (Budish and Cantillon, 2012). Here individuals report their valuations for items, a center

computes an (approximate) equal-budget equilibrium allocation, and returns this allocation to the

agents. This mechanism is known as competitive equilibrium from equal incomes (CEEI, Varian

(1974)) and is used in the allocation of courses to university students though with more complex

utility functions and computations than our Fisher case (Budish et al

, 2013, 2016). Recent work

studies how general constraints can be added to CEEI allocations (Echenique et al

, 2021). Our

work adds to this literature by showing properties of speciﬁc constraints proposed in discussions

of demographic fairness in allocation. We do not seek to prove general results about all possible

constraint families. Instead, we focus on the more restrictive case of linear constraints in Fisher

markets which allows us to derive stronger results–i.e. the convex program to determine optimal

taxes/subsidies–than in general unit demand markets studied by Echenique et al. (2021).

Market equilibria in Fisher markets and their relationship to convex programming are well studied

(Eisenberg and Gale, 1959; Shmyrev, 2009; Cole et al

, 2017; Kroer et al

, 2019; Cole et al

, 2017;

Cole and Gkatzelis, 2018; Caragiannis et al

, 2016; Murray et al

, 2019; Gao and Kroer, 2020). Our

work complements this existing work as we show that the convex program equivalence allows us to

easily construct market interventions in the forms of taxes and subsidies. In addition, we use this

equivalence to construct a provably convergent online algorithm.

A recent literature has begun to study differential outcomes in online systems (Ali et al

, 2019;

Geyik et al

, 2019; Zhang, 2021; Imana et al

, 2021) across categories of users (e.g. job ads across

gender). Though a highly studied cause of these differential outcomes are biases in machine learning

systems, there are also market forces that can cause such issues. For example, Lambrecht and Tucker

(2018) studies STEM job ads competing in a real ad market and shows that “younger women are

a prized demographic and are more expensive to show ads to. An algorithm that simply optimizes

cost-effectiveness in ad delivery will deliver ads that were intended to be gender neutral in an

apparently discriminatory way, because of crowding out.” Our work further highlights the importance

of understanding market dynamics both in terms of how they cause disparate allocations as well as

how various interventions behave.

A recent literature has looked at implementing various notions of fairness in single auctions (Celis

et al

, 2019; Ilvento et al

, 2020; Chawla and Jagadeesan, 2022), paced auctions (Celli et al

, 2022) or

online allocation problems (Balseiro et al

, 2021b). Our work complements this by showing that in

markets similar implementation can be done via the use of the price system. In addition, these papers

study the performance of their algorithms but bypass the questions such as second order market

effects, who wins and who loses, and whether good incentive properties are preserved.

As discussed in Fazelpour et al

(2022), fairness constraints are often designed through desirable

properties of ideal states. However, when the current state is far from ideal, enforcing the constraints

may not bring us closer to the ideal state. Similar points has been made in the context of classiﬁcation

(Corbett-Davies et al

, 2017; Menon and Williamson, 2018; Kasy and Abebe, 2021; Liu et al

, 2018;

Weber et al

, 2022), various ‘statistical discrimination’ scenarios (Fang and Moro, 2011; Mouzannar

et al

, 2019; Emelianov et al

, 2022), and counterfactual or causal deﬁnitions of fairness (Kusner et al

2017; Imai and Jiang, 2020; Nilforoshan et al

, 2022). Our results about parity and ﬂoor constraints

complement this literature showing that interventions in markets can sometimes (note, not always!)

make things worse than before. In the Appendix we provide a longer discussion of the various results

in this literature, which context they apply in, and how they relate to our results.

3 Fisher Markets

We will work with a market where there are

buyers (e.g. advertisers) and

items (e.g. ad

slots). Each item has supply

which for the purposes of this section we take to be

. We assume

that fractional allocations are allowed (these can also be thought of as randomized allocations).

Fractional allocation ensures existence and polynomial time computability of equilibria. In practice

numerically that in many Fisher markets with linear utility, almost all assignments are

(Kroer

and Peysakhovich, 2019).

We let

x∈Rn×m

be an allocation of items to buyers. We let

xi∈Rm

be the bundle of goods

assigned to buyer

with

xij

being the assignment of item

. Each buyer has a utility function

vi(xi)

We assume the utilities are all homogeneous of degree one (i.e. that

αvi(xi) = vi(αxi)

for

α > 0

concave, and continuous. We also assume that there exists an allocation

such that

vi(xi)>0

for

all buyers i.

This class of utilities includes the constant elasticity of substitution (CES) family of utilities, and

linear utilities are special case of CES utilities where each buyer has a value

vij

for each item

and

vi(xi) = Pjvij xij

. Linear utilities are precisely what is assumed in many studies of online

advertising markets (Conitzer et al., 2019; Balseiro et al., 2021a).

Each item will be assigned a price

pj>0

, with

being the full price vector, and each buyer has a

budget

Bi>0

. We study the quasi-linear (QL) case where leftover money is kept by the buyer; this

is most natural for several real world markets such as advertising markets. Most of our results work

the same for the non-QL case.

Let

δi

be the leftover budget under prices

with allocation

(

δi=Bi−pTxi)

. The quasi-linear

utility that a buyer experiences under prices pand allocation xis then

ui(xi, δi) = vi(xi) + δi

Given a price vector p, the demand of a buyer is

Di(p) = argmaxxi:x>

ip≤Biui(xi, δi).

market equilibrium

is an allocation

x∗

and a price vector

p∗

such that 1) allocations are demands:

for each i x∗

i∈Di(p∗), and 2) markets clear: for each j,Pixij ≤1, with equality if pj>0.

In Fisher markets with our family of utilities, market equilibria always exist. The general problem

of market equilibrium is computationally difﬁcult (Chen and Teng, 2009; Vazirani and Yannakakis,

2011; Chen et al

, 2021) but in the family of utilities we are considering the equilibrium allocation

can be found via solving a version of the Eisenberg-Gale convex program (EG) Eisenberg and Gale

(1959):

max

x≥0,δ≥0X

Bilog(vi(xi) + δi)−δi

s.t. X

xij ≤1,∀j= 1, . . . , m

(1)

Note that the market equilibrium deﬁnition says nothing about maximizing the sum of log utilities -

the market ﬁnds equilibrium by ﬁnding prices and allocations to make supply meet demand. Rather,

it is a deep result that the

which solves the EG problem is also an equilibrium of the Fisher market

when we take prices Lagrange multipliers on the supply constraints at the optimum (Eisenberg and

Gale, 1959).

There sometimes may be multiple equilibrium allocations in a Fisher market, however in all equilibria

the prices are the same, and, importantly, the utility realized by each buyer is the same.

This fact that Fisher equilibria are allocations that maximize the budget weighted product of utilities

is an important reason they are studied in the fair division community. In the equal budget case

Nash social welfare has been called an “unreasonably effective fairness criterion” (Caragiannis et al

2016) and is used in practice in allocation mechanisms such as Spliddit.com (Goldman and Procaccia,

2014).

Desirable Properties of Market Equilibria

In addition to making supply meet demand, equilibria have other desirable properties when used as

allocation mechanisms. We discuss them here as later we will want to ask whether our interventions

preserve them or not. We list properties of interest informally before describing them in more detail:

Equilibria are Pareto efﬁcient.

In the QL case this is deﬁned using the leftover budget as well as

the seller who receives the payments. Let

(xi, δi)

be the bundle of goods received by buyer

and

their leftover budget with (x, δ)being all buyers’ allocations/budgets.

An allocation

(x, δ)

Pareto optimal

if for every alternative allocation

(x0, δ0)

such that some buyer

strictly improves their utility, it must be the case that for some other buyer

, we have

vi(x0

i) + δ0

vi(xi) + δi

Piδ0

i>Piδi

, meaning that the seller is worse off. Similarly, if

Piδ0

i<Piδi

meaning the seller strictly improves, then it must be the case that for some buyer

, we have

vi(x0

i) + δ0

i< vi(xi) + δi.

Equilibria are envy-free

when accounting for budgets. Let

(x, δ)

be an equilibrium allocation. For

any two buyers i, i0with budget ratio γ=Bi

Bi0we always have that vi(xi) + δi≥vi(γxi0) + γδi0.

Incentives for strategic behavior are minimized when markets are large.

Consider the Fisher

mechanism: each individual reports their valuation function to a center. The center computes the

market equilibrium, and gives each individual their corresponding allocation. This is strongly related

to CEEI (Varian, 1974; Budish and Cantillon, 2012) though here utilities are quasi-linear.

Auction-based ad markets act somewhat like a centralized Fisher mechanism. Buyers report their

valuations for various events (clicks, conversions, impressions, etc...). Auctions happen for each

impression and the ad system bids for each buyer using logic to adjust bids over time to spend

budgets. For appropriate choices of pacing rules and auctions the resulting outcome is a Fisher market

equilibrium (Conitzer et al

, 2019). In this case, whether the individuals have incentives to lie to the

center is extremely important.

At a high level, a mechanism is said to be

strategy-proof in the large

(SPL (Azevedo and Budish,

2018)) if, when the market is large enough, there is little gain from lying to the center about one’s

valuation.

Formally, a large market is deﬁned as: let there be

buyers, each with budget 1. The size of the

market is determined by this

. Let there be

items with generic item

, and let the supply of

each item be

sjn

where

is some constant. Then SPL is deﬁned as for any

 > 0

for all possible

valuations

, there exists

¯n

such that if

n > ¯n

the gain to any buyer of type

from misreporting any

instead of their true

is less than



. The standard Fisher mechanism is SPL (see the arguments in

(Azevedo and Budish, 2018) and the Appendix for more details).

4 Changing Market Outcomes

We now move to our main problem. We consider a market designer that wants market allocations to

satisfy certain constraints. Though in some cases (e.g. fully centralized) the designer can control

quantities allocated directly. However, in many cases of interest the market designer must work

through the price system or they may wish to do so due to efﬁciency properties.

We consider a market designer that is able to subsidize and tax purchases. Let

¯p

be an

n×m

matrix

of price interventions. We assume that each buyer

faces price

pj+ ¯pij

for item

with

¯pij >0

being

a tax and ¯pij <0being a subsidy. Let ¯pi∈Rmbe the vector of price interventions for buyer i.

The demand of a buyer

with base prices

and interventions

¯p

is given by

Di(p+ ¯pi)

. This lets

us extend the deﬁnition of a market equilibrium. We say that given a

¯p

the triple

(x, p, ¯p)

is a

tax-subsidy equilibrium if

1. Each xi∈Di(p+ ¯pi)

2. For all jPixij ≤1, with equality if pj+ ¯pij >0.

We now show that with appropriate choice of

¯p

the market designer can force the market equilibrium

allocation to satisfy a set of linear constraints. The proof of the result is constructive and gives us the

algorithm for computing such a

¯p

from knowledge of the market structure and the desired constraints.

First, let us formally deﬁne linear constraints. We deﬁne a linear operator

A1:Rn×m→RK1

which inputs the allocation matrix and yields a vector

b∈RK1

. We let

A1x≤b1

be the inequality

constraints we wish to hold (the choice of less than in the inequality is arbitrary as the sign of

can

always be changed). We deﬁne another linear operator

A2:Rn×m→RK2

to represent equality

constraints A2x=b2.

This gives us the constrained EG program:

max

x≥0,δ≥0X

i∈T

Bilog vi(xi) + δi−δi

s.t. X

xij ≤1,∀j,

A1x≤b1,

A2x=b2.

(2)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ImplementingFairnessConstraintsinMarketsUsingTaxesandSubsidiesAlexanderPeysakhovichMetaAIResearchChristianKroerMetaCoreDataScienceColumbiaUniversityNicolasUsunierMetaAIResearchAbstractFishermarketsarethosewherebuyerswithbudgetscompeteforscarceitems,anaturalmodelformanyrealworldmarketsincludingonline...

展开>> 收起<<

Implementing Fairness Constraints in Markets Using Taxes and Subsidies Alexander Peysakhovich.pdf

共23页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Implementing Fairness Constraints in Markets Using Taxes and Subsidies Alexander Peysakhovich

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: