0.9 0.999695549213939
0.95 1
1 1
$R = 5$
[line width = 1pt, darkorange25512714]
0 0.0839588985100597
0.05 0.0839588985100597
0.1 0.083964859560875
0.15 0.084333672518481
0.2 0.084333672518481
0.25 0.0843898391610377
0.3 0.123164930449549
0.35 0.298068764040212
0.4 0.604362835347428
0.45 0.768933462750956
0.5 0.858432131042332
0.55 0.943673926539339
0.6 0.972596750588812
0.65 0.990833787337509
0.7 0.995751886389841
0.75 0.997512424184067
0.8 0.998367364281925
0.85 0.999049512857504
0.9 0.999434358554778
0.95 0.999922000019503
1 0.999923761411651
$R = 10$
[line width = 1pt, forestgreen4416044]
0 0.0839454021349645
0.05 0.0839454021349645
0.1 0.0839571460221351
0.15 0.083957146022135
0.2 0.083957146022135
0.25 0.083957146022135
0.3 0.119292800026624
0.35 0.294846977063576
0.4 0.59826954137749
0.45 0.759821518917097
0.5 0.854543030986416
0.55 0.937245961151214
0.6 0.972244164456357
0.65 0.988414105397947
0.7 0.993584616623345
0.75 0.996214030209123
0.8 0.997434099303078
0.85 0.998559869475965
0.9 0.999116903865483
0.95 0.999722632846589
1 0.999802589206477
$R = 15$
[line width = 1pt, crimson2143940]
0 0.0840089081278611
0.05 0.0840089081278611
0.1 0.0840089081278611
0.15 0.0840089081278611
0.2 0.0840089081278611
0.25 0.0840089081278611
0.3 0.120018258984578
0.35 0.294475193551885
0.4 0.597609071170664
0.45 0.759192984114778
0.5 0.854308600614215
0.55 0.936807037711187
0.6 0.972060343163231
0.65 0.988092600689493
0.7 0.993311014668923
0.75 0.996109103132544
0.8 0.997359390883083
0.85 0.998522705211775
0.9 0.999083779337896
0.95 0.999695912397683
1 0.999775166140761
$R = 20$
[line width = 1pt, mediumpurple148103189]
0 0.0840089081278611
0.05 0.0840089081278611
0.1 0.0840089081278611
0.15 0.0840089081278611
0.2 0.0840089081278611
0.25 0.0840089081278611
0.3 0.120018258984578
0.35 0.294475193551885
0.4 0.597609071170664
0.45 0.759192984114778
0.5 0.854308600614215
0.55 0.936807037711187
0.6 0.972060343163231
0.65 0.988092600689493
0.7 0.993311014668923
0.75 0.996109103132544
0.8 0.997359390883083
0.85 0.998522705211775
0.9 0.999083779337896
0.95 0.999695912397683
1 0.999775166140761
$R = 30$

tick align=outside,
tick pos=left,
x grid style=darkgray176,
xlabel=Contract ($\alpha$),
xlabel style= font = ,
xmin=-0.05, xmax=1.05,
xtick style=color=black, font = ,
x tick label style= font = ,
y grid style=darkgray176,
title = Variation in Fine Levels,
title style = font = ,

ymin=0.0391237050485077, ymax=1.04575601404531,
ytick style=color=black, font = ,
y tick label style=
/pgf/number format/.cd,
fixed zerofill,
font = ,
legend style=
fill opacity=0.8,
draw opacity=1,
text opacity=1,
anchor=north west,
font = =2pt

[line width = 1pt, steelblue31119180]
0 0.383981875028984
0.05 0.434835076985053
0.1 0.456733004881273
0.15 0.47566595214692
0.2 0.48841374860277
0.25 0.494250182433593
0.3 0.521926182668142
0.35 0.640940264280219
0.4 0.825858001887382
0.45 0.911909193211684
0.5 0.936079225650587
0.55 0.98647230469254
0.6 1
0.65 1
0.7 1
0.75 1
0.8 1
0.85 1
0.9 1
0.95 1
1 1
$k = 50$
[line width = 1pt, darkorange25512714]
0 0.228126012028327
0.05 0.228126012028327
0.1 0.229567456992579
0.15 0.230019950404685
0.2 0.233595336188618
0.25 0.233744096052169
0.3 0.269505116011905
0.35 0.410345737179787
0.4 0.663368733358696
0.45 0.827238816531979
0.5 0.902151525814269
0.55 0.961056447144435
0.6 0.987624598210578
0.65 0.99764040742609
0.7 0.999459676959618
0.75 0.999459676959618
0.8 0.999459676959618
0.85 0.999937970539026
0.9 1
0.95 1
1 1
$k = 150$
[line width = 1pt, forestgreen4416044]
0 0.149606211639067
0.05 0.151290463043025
0.1 0.153136570823481
0.15 0.153179621379093
0.2 0.153203521258589
0.25 0.15473944302698
0.3 0.189640471066976
0.35 0.345957666368713
0.4 0.626398283430321
0.45 0.787191776213746
0.5 0.871478053999744
0.55 0.952614548051142
0.6 0.979257705228733
0.65 0.991777881041976
0.7 0.996327880394975
0.75 0.997948288804707
0.8 0.998652870729374
0.85 0.999051019340505
0.9 0.999474475910003
0.95 0.999998903664458
1 0.999998903664458
$k = 250$
[line width = 1pt, crimson2143940]
0 0.114763212707139
0.05 0.114768814876231
0.1 0.114768814876231
0.15 0.114768814876232
0.2 0.114769459858759
0.25 0.114769459858759
0.3 0.149867115599807
0.35 0.311212863068258
0.4 0.610553136946898
0.45 0.771011118528984
0.5 0.86474036942945
0.55 0.945244349763855
0.6 0.975459590805187
0.65 0.990655281928307
0.7 0.995121394507654
0.75 0.997265512120745
0.8 0.99812511346114
0.85 0.999066823808743
0.9 0.999441609576393
0.95 0.999916636212638
1 0.999916636212638
$k = 350$
[line width = 1pt, mediumpurple148103189]
0 0.0839454021349645
0.05 0.0839454021349645
0.1 0.0839571460221351
0.15 0.083957146022135
0.2 0.083957146022135
0.25 0.083957146022135
0.3 0.119292800026624
0.35 0.294846977063576
0.4 0.59826954137749
0.45 0.759821518917097
0.5 0.854543030986416
0.55 0.937245961151214
0.6 0.972244164456357
0.65 0.988414105397947
0.7 0.993584616623345
0.75 0.996214030209123
0.8 0.997434099303078
0.85 0.998559869475965
0.9 0.999116903865483
0.95 0.999722632846589
1 0.999802589206477
$k = 500$

Variation in the proportion of the optimal social welfare corresponding to different contract levels $\alpha$ for different values of the number of resources ($R$) and the fine ($k$). The plot on the left considers the setting when the fine level is set to $k = 500$ while that on the right considers the setting with $R = 15$.

§ CONCLUSION AND FUTURE WORK

In this work, we studied the problem of policing and monitoring fraudulent activities at potentially susceptible nodes or locations in a system as a security game between an administrator and fraudulent users. Motivated by several real-world settings where fraudulent and illegal activities by certain groups of users are prevalent (see Section <ref>), we introduced a model of a security game wherein the administrator can deploy a budget of security resources across locations and levy fines against users found engaging in illegal activities. We studied our security game under both welfare and revenue maximization administrator objectives. In both settings, we showed that, in general, the problem of computing the optimal resource allocation strategy of the administrator is NP-hard, and we developed greedy-like algorithms for both administrator objectives with associated approximation ratio and resource augmentation guarantees. Finally, given that the revenue and welfare-maximizing outcomes of the administrator can differ significantly from each other, we presented a framework inspired by contract theory that helps ensure that a revenue-maximizing administrator incorporates welfare maximization as part of its objective when allocating security resources. Beyond extending our theoretical results in the welfare and revenue maximization settings to the contract framework, we also presented numerical experiments based on a real-world application case of intermediate public transport services in Mumbai, India. Our numerical results validated our theoretical insights and highlighted the effectiveness of using contracts in bridging the gap between the revenue and welfare-maximizing outcomes of the administrator.

There are several future research directions. First, it would be interesting to investigate whether our greedy algorithms achieve the best approximation ratios for the studied problem setting or if algorithms with improved approximation guarantees can be derived, e.g., a PTAS.
Next, while we studied the probabilistic setting, where the administrator knows the distribution of each location's type, it would be interesting to study a repeated game setting where the administrator learns these distributions. Finally, it would be worthwhile to explore more properties of our contract framework and develop (and compare) other alternative formulations to incentivize a revenue-maximizing administrator to incorporate welfare in its objective. For further directions of future research, we refer to Appendix <ref>, where we present several extensions of the model studied in this work.

§ ACKNOWLEDGEMENTS

This work was supported by the Stanford Interdisciplinary Graduate Fellowship (SIGF).

[1]
Andreas Bjerre-Nielsen, Lykke Sterll Christensen, Mikkel Host Gandil, and
Hans Henrik Sievertsen.
Playing the system: address manipulation and access to schools.
Papers 2305.18949, arXiv.org, May 2023.

[2]
Philippe Askenazy, Thomas Breda, Flavien Moreau, and Vladimir Pecheu.
Do French companies under-report their workforce at 49 employees to
get around the law?
PSE Working Papers halshs-03828729, HAL, March 2022.

[3]
Andrew Estornell, Sanmay Das, and Yevgeniy Vorobeychik.
Incentivizing truthfulness through audits in strategic
Proceedings of the AAAI Conference on Artificial Intelligence,
35(6):5347–5354, May 2021.

[4]
Andrew Estornell, Yatong Chen, Sanmay Das, Yang Liu, and Yevgeniy Vorobeychik.
Incentivizing recourse through auditing in strategic classification.
In Edith Elkind, editor, Proceedings of the Thirty-Second
International Joint Conference on Artificial Intelligence, IJCAI-23, pages
400–408. International Joint Conferences on Artificial Intelligence
Organization, 8 2023.
Main Track.

[5]
Eduardo Perez-Richet and Vasiliki Skreta.
Fraud-proof non-market allocation mechanisms.
Technical report, Working paper, 2023.

[6]
Taylor Lundy, Alexander Wei, Hu Fu, Scott Duke Kominers, and Kevin
Allocation for social good: Auditing mechanisms for utility
In Proceedings of the 2019 ACM Conference on Economics and
Computation, EC '19, page 785–803, New York, NY, USA, 2019. Association
for Computing Machinery.

[7]
Lee Bolton.
Manipulation of the waitlist priority of the organ allocation system
through the escalation of medical therapies.
OPTN/UNOS EthicsCommittee, 2018.

[8]
Benjamin J McMichael.
Stealing organs?
Ind. LJ, 97:135, 2022.

[9]
Milind Tambe.
Security and game theory: algorithms, deployed systems, lessons
Cambridge university press, 2011.

[10]
Robert Cervero.
Informal transport in the developing world.
UN-HABITAT, 2000.

[11]
Robert Cervero and Aaron Golub.
Informal transport: A global perspective.
Transport Policy, 14(6):445–457, 2007.

[12]
Andreas Neumann, Daniel Röder, and Johan W. Joubert.
Toward a simulation of minibuses in south africa.
Journal of Transport and Land Use, 8(1):137–154, 2015.

[13]
Ilan Salomon and Lionel Silman.
Scheduled bus and sherut taxi operation in israel.
Transportation Research Part B: Methodological, 19(3):259–264,

[14]
F Zwick.
Analysis and simulation of Santiago de Chile’s colectivo
PhD thesis, Bachelor’s thesis. TU Berlin, 2017.

[15]
Ravi Gadapalli.
Role of intermediate public transport in indian cities.
Economic and Political Weekly, 51(9):46–49, 2016.

[16]
Rupa Subramanya.
Economics journal: Stupid taxi rules in mumbai.
<https://www.wsj.com/articles/BL-IRTB-16187>, Jul 2012.
[Accessed: 2024-01-14].

[17]
Chris Wood.
The art of queue-jumping on hong kong trams.
[Accessed: 2024-02-09].

[18]
Yongbin Li, Jing Xu, Fang Wang, Bin Wang, Liqun Liu, Wanli Hou, Hong Fan,
Yeqing Tong, Juan Zhang, and Zuxun Lu.
Overprescribing in china, driven by financial incentives, results in
very high use of antibiotics, injections, and corticosteroids.
Health affairs, 31(5):1075–1082, 2012.

[19]
Yan S Kim, Eric C Kleerup, Patricia A Ganz, Ninez A Ponce, Karl A Lorenz, and
Jack Needleman.
Medicare payment policy creates incentives for long-term care
hospitals to time discharges for maximum reimbursement.
Health Affairs, 34(6):907–915, 2015.

[20]
Drew Fudenberg and Jean Tirole.
Game theory.
MIT press, 1991.

[21]
James Pita, Manish Jain, Janusz Marecki, Fernando Ordóñez, Christopher
Portway, Milind Tambe, Craig Western, Praveen Paruchuri, and Sarit Kraus.
Deployed armor protection: the application of a game theoretic model
for security at the los angeles international airport.
In Proceedings of the 7th International Joint Conference on
Autonomous Agents and Multiagent Systems: Industrial Track, AAMAS '08, page
125–132, Richland, SC, 2008. International Foundation for Autonomous Agents
and Multiagent Systems.

[22]
Eric Shieh, Bo An, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben
Maule, and Garrett Meyer.
Protect: an application of computational game theory for the security
of the ports of the united states.
In Proceedings of the Twenty-Sixth AAAI Conference on Artificial
Intelligence, AAAI'12, page 2173–2179. AAAI Press, 2012.

[23]
Zhengyu Yin, Albert Xin Jiang, Milind Tambe, Christopher Kiekintveld, Kevin
Leyton-Brown, Tuomas Sandholm, and John P Sullivan.
Trusts: Scheduling randomized patrols for fare inspection in transit
systems using game theory.
AI magazine, 33(4):59–59, 2012.

[24]
Lily Xu, Elizabeth Bondi, Fei Fang, Andrew Perrault, Kai Wang, and Milind
Dual-mandate patrols: Multi-armed bandits for green security.
Proceedings of the AAAI Conference on Artificial Intelligence,
35(17):14974–14982, May 2021.

[25]
Rong Yang, Benjamin Ford, Milind Tambe, and Andrew Lemieux.
Adaptive resource allocation for wildlife protection against illegal
In Proceedings of the 2014 International Conference on
Autonomous Agents and Multi-Agent Systems, AAMAS '14, page 453–460,
Richland, SC, 2014. International Foundation for Autonomous Agents and
Multiagent Systems.

[26]
Fei Fang, Peter Stone, and Milind Tambe.
When security games go green: designing defender strategies to
prevent poaching and illegal fishing.
In Proceedings of the 24th International Conference on
Artificial Intelligence, IJCAI'15, page 2589–2595. AAAI Press, 2015.

[27]
Fei Fang, Thanh H. Nguyen, Rob Pickles, Wai Y. Lam, Gopalasamy R. Clements,
Bo An, Amandeep Singh, Milind Tambe, and Andrew Lemieux.
Deploying paws: field optimization of the protection assistant for
wildlife security.
In Proceedings of the Thirtieth AAAI Conference on Artificial
Intelligence, AAAI'16, page 3966–3973. AAAI Press, 2016.

[28]
Arunesh Sinha, Fei Fang, Bo An, Christopher Kiekintveld, and Milind Tambe.
Stackelberg security games: Looking beyond a decade of success.
In Proceedings of the Twenty-Seventh International Joint
Conference on Artificial Intelligence, IJCAI-18, pages 5494–5501.
International Joint Conferences on Artificial Intelligence Organization, 7

[29]
Dorit S Hochba.
Approximation algorithms for np-hard problems.
ACM Sigact News, 28(2):40–52, 1997.

[30]
David P Williamson and David B Shmoys.
The design of approximation algorithms.
Cambridge university press, 2011.

[31]
David Kempe, Jon Kleinberg, and Éva Tardos.
Maximizing the spread of influence through a social network.
In Proceedings of the Ninth ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining, KDD '03, page 137–146, New York,
NY, USA, 2003. Association for Computing Machinery.

[32]
Tim Roughgarden.
Resource Augmentation, page 72–92.
Cambridge University Press, 2021.

[33]
Mohammad Akbarpour, Suraj Malladi, and Amin Saberi.
Just a Few Seeds More: Value of Network Information for Diffusion.
Research Papers 3678, Stanford University, Graduate School of
Business, April 2018.

[34]
Mohammad Akbarpour, Yeganeh Alimohammadi, Shengwu Li, and Amin Saberi.
The value of excess supply in spatial matching markets.
In Proceedings of the 23rd ACM Conference on Economics and
Computation, EC '22, page 62, New York, NY, USA, 2022. Association for
Computing Machinery.

[35]
Moshe Babaioff, Kira Goldner, and Yannai A. Gonczarowski.
Bulow-Klemperer-Style Results for Welfare Maximization in
Two-Sided Markets, pages 2452–2471.

[36]
Jeremy Bulow and Paul Klemperer.
Auctions versus negotiations.
The American Economic Review, 86(1):180–194, 1996.

[37]
Jason D. Hartline and Tim Roughgarden.
Simple versus optimal mechanisms.
In Proceedings of the 10th ACM Conference on Electronic
Commerce, EC '09, page 225–234, New York, NY, USA, 2009. Association for
Computing Machinery.

[38]
Sergiu Hart and Noam Nisan.
Approximate revenue maximization with multiple items.
Journal of Economic Theory, 172:313–347, 2017.

[39]
Oliver Hart and Bengt Holmström.
The theory of contracts, page 71–156.
Econometric Society Monographs. Cambridge University Press, 1987.

[40]
Patrick Bolton and Mathias Dewatripont.
Contract theory.
MIT press, 2004.

[41]
Bengt Holmström.
Moral hazard and observability.
The Bell journal of economics, pages 74–91, 1979.

[42]
Sanford J Grossman and Oliver D Hart.
An analysis of the principal-agent problem.
In Foundations of Insurance Economics: Readings in Economics and
Finance, pages 302–340. Springer, 1992.

[43]
Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim.
Combinatorial contracts.
In 2021 IEEE 62nd Annual Symposium on Foundations of Computer
Science (FOCS), pages 815–826, 2022.

[44]
Paul Dutting, Michal Feldman, and Yoav Gal Tzur.
Combinatorial contracts beyond gross substitutes.
In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 92–108. SIAM, 2024.

[45]
Moshe Babaioff, Michal Feldman, and Noam Nisan.
Combinatorial agency.
In Proceedings of the 7th ACM Conference on Electronic
Commerce, EC '06, page 18–28, New York, NY, USA, 2006. Association for
Computing Machinery.

[46]
Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim.
Multi-agent contracts.
In Proceedings of the 55th Annual ACM Symposium on Theory of
Computing, STOC 2023, page 1311–1324, New York, NY, USA, 2023. Association
for Computing Machinery.

[47]
Matthew Prensky and Rob Johnson.
It's a trap! small towns across us use traffic tickets to collect big
money from drivers.
Dec 2023.
[Accessed: 2023-12-31].

[48]
Christopher Kiekintveld, Manish Jain, Jason Tsai, James Pita, Fernando
Ordóñez, and Milind Tambe.
Computing optimal randomized resource allocations for massive
security games.
In Proceedings of The 8th International Conference on Autonomous
Agents and Multiagent Systems - Volume 1, AAMAS '09, page 689–696,
Richland, SC, 2009. International Foundation for Autonomous Agents and
Multiagent Systems.

[49]
Mikhail Solodov.
An explicit descent method for bilevel convex optimization.
Journal of Convex Analysis, 14(2):227, 2007.

[50]
Mumbai metropolitan region development authority.
<https://mmrda.maharashtra.gov.in>, 2024.
[Accessed: 2024-01-30].

[51]
Vincent Conitzer and Tuomas Sandholm.
Computing the optimal strategy to commit to.
In Proceedings of the 7th ACM Conference on Electronic
Commerce, EC '06, page 82–90, New York, NY, USA, 2006. Association for
Computing Machinery.

[52]
Gary S Becker.
Crime and punishment: An economic approach.
Journal of political economy, 76(2):169–217, 1968.

[53]
The Economist.
Looking for the african middle class? head to the bus park.
[Accessed: 2023-05-21].

[54]
Team Acko.
New traffic rules in mumbai: List of rules and fines for violations.
[Accessed: 2024-02-03].

§ ADDITIONAL DISCUSSION ON MODELING ASSUMPTIONS

In this section, we present some additional discussions on our modeling assumptions for the security game that we study.

First, as in prior literature on security games [9], we model our problem as a Stackelberg game, wherein users at each location observe and best respond to the administrator's mixed strategy [51]. Such an assumption on the game structure is reasonable for several applications of interest to this paper. For instance, in the case of queue jumping in intermediate public transport services, users typically use the IPT service at the same location every day; thus, users can estimate the likelihood of being caught by a security resource (e.g., a police officer) on a given day. We note that similar assumptions on the game structure have been considered even in related examples in the literature, e.g., the scheduling of randomized patrols for inspecting whether users have paid their fares in transit systems [23]. While we assume that users observe the probability of a security resource being allocated to their respective locations precisely, exploring alternative models of equilibrium formation when such perfect observability is not possible is an exciting direction for future research.

Next, in this work, we assume that if the administrator allocates a security resource to a given location, then the security resource will collect fines from any defaulting users and prevent any fraudulent or illegal activities from occurring at that location. Such an assumption on the efficacy of a security resource in preventing a security breach at the location to which it is allocated is ubiquitous in the literature on security games [9] and also natural, as, for instance, the presence of a police officer is likely to deter users from engaging in queue jumping in IPT services.

Moreover, we assume that the fine levied on defaulting users is a fixed (potentially small) constant. While setting high fines is likely to deter fraud, in most practical applications, fines for engaging in fraudulent or illegal activities are not arbitrarily high, e.g., traffic light or speeding violations cost about $100 in California. Furthermore, we note that our numerical experiments in Section <ref> and Appendix <ref> highlight the benefits of setting low to moderate fines in practice as it deters an administrator from solely maximizing revenues through the collected fines.

In addition, in this work, we assume that fines are the only penalty for users engaging in fraudulent or illegal activities. Such an assumption is particularly applicable for the setting with queue jumping in IPT services, as the penalty imposed on defaulting users is likely to only come in the form of a fine. However, for other application settings, different forms of punishment may be pertinent depending on the magnitude of the fraud [52], e.g., users may be sent to prison for certain crimes they commit. While we do not account for other forms of punishment beyond levying fines on defaulting users, there is scope to generalize the model presented in this work to account for different forms of punishment, which we defer to future research.

Finally, while we consider allocating security resources, e.g., police officers, to monitor and police susceptible nodes or locations in the system, which is typical in the literature on security games [9], policing can be performed through many other security mechanisms. Most notably, modern security technology, such as security cameras, is frequently used to monitor certain fraudulent or illegal activities, e.g., store theft. Yet we note that while such technology has proven effective in some applications, e.g., in detecting theft at grocery stores, such technology is unlikely to be as effective for many examples of interest in this paper, e.g., the transportation and healthcare examples presented in Section <ref>. For instance, in the case of healthcare, human intervention is often necessary to conduct thorough audits to ensure that medications have not been over-prescribed or that patients do not have to stay longer than necessary at a hospital.

Furthermore, while security cameras are often effective in detecting and fining users for road speeding violations, as user records can be determined using license plate information, such technology is likely far more ineffective in monitoring queue jumping in IPT services. In particular, using cameras to identify and fine users that skip queues is difficult, particularly in developing nation cities where IPT services are prevalent, as this would require advanced facial recognition software and a database of records of the entire population in the city. Moreover, given the commotion during the hailing of IPT services and that users often steal public property such as security cameras, a frequent occurrence in developing nation contexts, camera technology on its own may not be the most effective in policing queue jumping in IPT services. Consequently, the traditional mechanism of deploying security resources, such as police officers, as is typically the case for monitoring many traffic violations, such as speeding, despite the prevalence of camera technology, is likely the most effective mechanism in policing queue jumping in IPT services. Yet, we note that modern security technology, such as security cameras, has a role in augmenting traditional enforcement mechanisms, e.g., deploying police officers, in policing and monitoring fraudulent or illegal activities in the applications we consider. To that end, incorporating features of modern-day technology, such as security cameras, and how they can augment policing through traditional mechanisms into our studied framework is a worthwhile direction for future research.

§ PROOFS

§.§ Proof of Theorem <ref>

We prove Theorem <ref> using two intermediate lemmas. Our first intermediate lemma shows that the optimal solution of the revenue maximization bi-level Program (<ref>)-(<ref>) can be computed using a linear program, as is elucidated by the following lemma.

The optimal solution of the revenue maximization bi-level Program (<ref>)-(<ref>) can be computed through the solution of the following linear program:
\beginmaxi!|s|[2]
∑_l ∈L σ_l k Λ_l,

σ_l∈[0, d_l/d_l+k],   for all  l ∈L,
∑_l ∈L σ_l≤R.
\endmaxi!

For a proof of Lemma <ref>, see Appendix <ref>. Lemma <ref> establishes that computing an optimal revenue maximizing strategy of the administrator can be done efficiently in polynomial time. Our next intermediate lemma states that Algorithm <ref> achieves the optimal solution of the linear Program (<ref>)-(<ref>).

The allocation strategy corresponding to Algorithm <ref> achieves an optimal solution to the linear Program (<ref>)-(<ref>).

For a proof of Lemma <ref>, see Appendix <ref>. Lemma <ref> implies that the linear Program (<ref>)-(<ref>) can be solved in $O(|L| \log(|L|))$ time as the time taken to sort the locations is $O(|L| \log(|L|))$ and that taken to iterate through the locations in linear in $|L|$.

Notice that jointly Lemmas <ref> and <ref> imply Theorem <ref>.

§.§.§ Proof of Lemma <ref>

To prove this claim, we first present the linear program that can be used to compute the solution of the bi-level Program (<ref>)-(<ref>). To construct this linear program, we note that any optimal solution to the bi-level Program (<ref>)-(<ref>) must satisfy $\sigma_l \in [0, \frac{d_l}{d_l+k}]$ for all locations $l \in L$. Note that if this relation is not satisfied and $\sigma_l > \frac{d_l}{d_l+k}$ for some location $l$, then we can consider an alternative allocation strategy $\Tilde{\sigmaa}$ where $\Tilde{\sigma}_l = \min \{ \sigma_l, \frac{d_l}{d_l+k} \}$ for all locations $l$. We note that $\Tilde{\sigmaa}$ is clearly feasible, i.e., $\Tilde{\sigmaa} \in \Omega_R$, as the strategy $\sigmaa$ is feasible. Next, by the best-response function of users in the revenue maximization setting given by Equation (<ref>), we note that $y_l(\Tilde{\sigmaa}) = 1$ for all locations $l$, while $y_l(\sigmaa) = 0$ if $\sigma_l > \frac{d_l}{d_l+k}$ and $y_l(\sigmaa) = 1$ otherwise. As a consequence, we obtain for any strategy $\sigmaa$ that:

\begin{align*}
Q_R(\sigmaa) &= \sum_{l \in L} \sigma_l y_l(\sigmaa) k \Lambda_l = \sum_{l: \sigma_l > \frac{d_l}{d_l+k}} \sigma_l y_l(\sigmaa) k \Lambda_l +  \sum_{l: \sigma_l \leq \frac{d_l}{d_l+k}} \sigma_l y_l(\sigmaa) k \Lambda_l, \\
&\stackrel{(a)}{=} \sum_{l: \sigma_l \leq \frac{d_l}{d_l+k}} \sigma_l k \Lambda_l \stackrel{(b)}{=}  \sum_{l : \sigma_l \leq \frac{d_l}{d_l+k}} \Tilde{\sigma}_l k \Lambda_l, \\
&\leq \sum_{l \in L} \Tilde{\sigma}_l k \Lambda_l, \\
&\stackrel{(c)}{=} Q_R(\Tilde{\sigmaa})
\end{align*}

where (a) follows as $y_l(\sigmaa) = 0$ if $\sigma_l > \frac{d_l}{d_l+k}$ and $y_l(\sigmaa) = 1$ otherwise, (b) follows as $\Tilde{\sigma}_l = \sigma_l$ when $\sigma_l \leq \frac{d_l}{d_l+k}$, and (c) follows as $y_l(\Tilde{\sigmaa}) = 1$ for all locations $l$.

The above analysis implies that there exists an revenue-maximizing allocation such that $\Tilde{\sigma}_l \in [0, \frac{d_l}{d_l+k}]$ for all locations $l$, where it holds by Equation (<ref>) that $y_l(\Tilde{\sigmaa}) = 1$ for all locations $l$. Thus, imposing the restriction that $\sigma_l \in [0, \frac{d_l}{d_l+k}]$ and that $y_l(\Tilde{\sigmaa}) = 1$ for all locations $l$, we have that the bi-level Program (<ref>)-(<ref>) can be reformulated as the following linear program:
\beginmaxi!|s|[2]
Q_R() = ∑_l ∈L σ_l k Λ_l,

σ_l∈[0, d_l/d_l+k],   for all  l ∈L,
∑_l ∈L σ_l≤R,
\endmaxi!
where Constraints (<ref>) captures the upper bound on the administrator strategy required for optimality, Constraint (<ref>) represents the resource constraint of the administrator, and Objective (<ref>) represents the revenue maximization objective of the administrator when $y_l(\Tilde{\sigmaa}) = 1$, which follows from Equation (<ref>) under Constraint (<ref>). This establishes our claim.

§.§.§ Proof of Lemma <ref>

For simplicity of exposition, we prove this result in the setting when the values of $\Lambda_l$ are all distinct, i.e., for any two locations $l, l' \in L$, it holds that $\Lambda_l \neq \Lambda_{l'}$. We note that our analysis can be extended naturally to the setting when there are ties.

To prove this claim, let $\sigmaa^G = (\sigma_l^G)_{l \in L}$ denote the allocations of the greedy algorithm and $\sigmaa^* = (\sigma_l^*)_{l \in L}$ denote the revenue-maximizing allocation. Further, suppose for contradiction that the greedy algorithm is not optimal, i.e., $\sum_{l \in L} \sigma_l^G \Lambda_l < \sum_{l \in L} \sigma_l^* \Lambda_l$, where we have dropped the fine $k$ from the objective of the linear Program (<ref>)-(<ref>). Note that this implies that there is some location $l$ such that $\sigma_l^G \neq \sigma_l^*$, which consequently implies by the nature of the greedy algorithm that there is a location $\Tilde{l}$ such that $\sigma_{\Tilde{l}}^G > \sigma_{\Tilde{l}}^{*}$. However, by the feasibility constraint that $\sum_{l \in L} \sigma_l \leq R$ and the optimality of the revenue-maximizing solution it must hold that there is some location $l'$ such that $\sigma_{l'}^G < \sigma_{l'}^{*}$.

To derive our desired contradiction, we now construct another feasible strategy with a strictly higher objective than the strategy $\sigmaa^*$. In particular, consider $\epsilon>0$ as some small positive constant such that $\sigma_{\Tilde{l}}^{*} + \epsilon \leq \sigma_{\Tilde{l}}^{G}$ and $\sigma_{l'}^{*} \geq \sigma_{l'}^{G} + \epsilon$. Then, define the strategy $\sigmaa' = (\sigma_l')_{l \in L}$, where $\sigma_l' = \sigma_l^*$ for all $l \neq l', \Tilde{l}$, $\sigma_{l'} = \sigma_{l'}^* - \epsilon$ and $\sigma_{\Tilde{l}}' = \sigma_{\Tilde{l}}^{*} + \epsilon$. Note that this new strategy is feasible. In particular, it is straightforward to check that $\sigma_l' \in [0, \frac{d_l}{d_l+k}]$ for all locations $l$ and that the resource constraint is satisfied as:

\begin{align*}
\sum_{l} \sigma_l' = \sum_{l \neq \{ l', \Tilde{l}\} } \sigma_l' + \sigma_{l'}' + \sigma_{\Tilde{l}}' = \sum_{l \neq \{ l', \Tilde{l}\} } \sigma_l^* + \sigma_{l'}^*-\epsilon + \sigma_{\Tilde{l}}^*+\epsilon = \sum_{l} \sigma_l^* \leq R,
\end{align*}

where the final inequality follows by the feasibility of $\sigmaa^*$.

Next, we show that the revenue of the new strategy $\sigmaa'$ is greater than that of $\sigmaa^*$. To see this note that:

\begin{align*}
Q_R(\sigmaa') &= \sum_{l \in L} \sigma_l' \Lambda_l, \\
&= \sum_{l \neq \{ l', \Tilde{l}\} } \sigma_l^* \Lambda_l + (\sigma_{l'}^*-\epsilon) \Lambda_{l'} + (\sigma_{\Tilde{l}}^* + \epsilon) \Lambda_{\Tilde{l}}, \\
&= \sum_{l \in L} \sigma_l^* \Lambda_l + \epsilon (\Lambda_{\Tilde{l}} - \Lambda_{l'}), \\
&> \sum_{l \in L} \sigma_l^* \Lambda_l = Q_R(\sigmaa^*),
\end{align*}

where the inequality follows as $\Lambda_{l'} < \Lambda_{\Tilde{l}}$ due to the nature of the greedy algorithm which allocates resources to locations in the descending order of the values of $\Lambda_l$. The above relationship implies that the strategy $\sigmaa'$ achieves a greater revenue compared to $\sigmaa^*$, a contradiction. Thus, it follows that Algorithm <ref> cannot have a strictly lower objective than the optimal algorithm, implying its optimality, which established our claim.

§.§ Proof of Proposition <ref>

Given the best-response function of the users at a given location $l$ in Equation (<ref>), we prove Proposition <ref> using two intermediate lemmas. Our first lemma establishes that, without loss of generality, it suffices to restrict our attention to administrator strategies where the total allocation of security personnel $\sigma_l$ at any location $l$ does not exceed $\frac{d_l}{d_l+k}$, i.e., establishing the first point in the statement of Proposition <ref>.

Suppose that users at each location best-respond by solving Problem (<ref>). Then, there exists an administrator strategy $\Tilde{\sigmaa}^*$ that satisfies $\Tilde{\sigma}_l^* \leq \frac{d_l}{d_l+k}$ for all locations $l$ and is a solution to the Problem (<ref>)-(<ref>).

For a proof of Lemma <ref>, see Appendix <ref>. Lemma <ref> establishes that allocating more than a certain threshold of resources, as specified by the fraction $\frac{d_l}{d_l+k}$, at any location $l$ will not improve the administrator's objective. Such a result holds as, by Equation (<ref>), allocating $\sigma_l = \frac{d_l}{d_l+k}$ is enough to deter users from engaging in fraudulent behavior at a given location $l$; hence, allocating any more resources than this threshold at a given location will not result in a further improvement in the administrator's objective (see right of Figure <ref>).

Our second intermediate lemma establishes the existence of an optimal administrator strategy $\Tilde{\sigmaa}^*$ such that for at most one location $l'$ $\Tilde{\sigma}_{l'}^* \in \left( 0, \frac{d_{l'}}{d_{l'}+k} \right)$, thereby establishing the second condition in Proposition <ref>.

Suppose that users at each location best-respond by solving Problem (<ref>). Then, there exists an administrator strategy $\Tilde{\sigmaa}^*$ that is a solution to Problem (<ref>)-(<ref>) such that for at most one location $l'$ $\Tilde{\sigma}_{l'}^* \in \left( 0, \frac{d_{l'}}{d_{l'}+k} \right)$. For all other locations $l$, it holds that either $\Tilde{\sigma}_l^* = 0$ or $\Tilde{\sigma}_l^* = \frac{d_l}{d_l+k}$.

For a proof of Lemma <ref>, see Appendix <ref>. Using the structure of the optimal administrator strategy established in Lemmas <ref> and <ref>, it is straightforward to see that the optimal administrator objective satisfies the relation in the statement of Proposition <ref>. To see this, let $L_1$, $L_2$, and $l'$ be as defined in the statement of Proposition <ref>. Then, we have that:

\begin{align*}
W_R^-(\Tilde{\sigmaa}^*) &= \sum_{l \in L} (1 - \Tilde{\sigma}_l^*) y_l(\Tilde{\sigmaa}^*) v_l, \\
&= \sum_{l \in L_1} (1 - \Tilde{\sigmaa}^*) y_l(\Tilde{\sigmaa}^*) v_l + \sum_{l \in L_2} (1 - \Tilde{\sigma}_l^*) y_l(\Tilde{\sigmaa}^*) v_l + (1 - \Tilde{\sigma}_{l'}^*) y_{l'}(\Tilde{\sigmaa}^*) v_{l'}, \\
&\stackrel{(a)}{=} \sum_{l \in L_2} (1 - \Tilde{\sigma}_l^*) y_l(\Tilde{\sigmaa}^*) v_l + (1 - \Tilde{\sigma}_{l'}^*) y_{l'}(\Tilde{\sigmaa}^*) v_{l'}, \\
&\stackrel{(b)}{=} \sum_{l \in L_2} v_l + (1 - \Tilde{\sigma}_{l'}^*) v_{l'},
\end{align*}

where (a) follows from the fact that $y_l(\Tilde{\sigmaa}^*) = 0$ for $l \in L_1$ by Equation (<ref>) as $\Tilde{\sigma}_l^* = \frac{d_l}{d_l+k}$ for all $l \in L_1$ and (b) follows as $y_l(\Tilde{\sigmaa}^*) = 1$ for $l \in L \backslash L_1$ and the fact that $\Tilde{\sigma}_l^* = 0$ for all $l \in L_2$ and that $\Tilde{\sigma}_{l'}^* \in \left(0, \frac{d_{l'}}{d_{l'}+k} \right)$.

Using the above inequality, we have the following relation for the welfare under the strategy $\Tilde{\sigmaa}^*$:

\begin{align}
W_R(\Tilde{\sigmaa}^*) &= \sum_{l \in L} v_l - W_R^-(\Tilde{\sigmaa}^*), \\
&= \sum_{l \in L} v_l - \left( \sum_{l \in L_2} v_l + (1 - \Tilde{\sigma}_{l'}^*) v_{l'} \right), \\
&= \sum_{l \in L_1} v_l + \Tilde{\sigma}_{l'}^* v_{l'},
\end{align}

which establishes the desired relation for the administrator's objective under the optimal strategy $\Tilde{\sigmaa}^*$, thereby proving our claim.

§.§.§ Proof of Lemma <ref>

Suppose that $\sigmaa^*$ is a welfare maximizing strategy of the administrator and $\y(\sigmaa^*)$ is the corresponding best-response of users given by Equation (<ref>), i.e., $(\sigmaa^*, \y(\sigmaa^*))$ is an optimal solution to Problem (<ref>)-(<ref>). Then, we define a new feasible strategy $\Tilde{\sigmaa}^*$ that satisfies $\Tilde{\sigma}_l^* \leq \frac{d_l}{d_l+k}$ for all locations $l$ and show that it achieves the same welfare as the strategy $\sigmaa^*$ using users' best response function given by Equation (<ref>). In particular, define $\Tilde{\sigmaa}^*$ such that $\Tilde{\sigma}_l^* = \min \{ \sigma_l^*, \frac{d_l}{d_l+k} \}$ for all locations $l$.

It is straightforward to check that $\Tilde{\sigmaa}^*$ is a feasible strategy, i.e., $\Tilde{\sigmaa}^* \in \Omega_R$. To see this, note that $\Tilde{\sigma}_l^* = \min \{ \sigma_l^*, \frac{d_l}{d_l+k} \} \geq 0$ for all locations $l$ as $\sigma_l^* \geq 0$ by its feasibility to Problem (<ref>)-(<ref>). Furthermore, we have that $\Tilde{\sigma}_l^* = \min \{ \sigma_l^*, \frac{d_l}{d_l+k} \} \leq 1$ as $\frac{d_l}{d_l+k} \leq 1$ for all locations $l$. Finally, since it holds that $\sum_{l \in L} \sigma_l^* \leq R$ by the feasibility of $\sigmaa^*$ to Problem (<ref>)-(<ref>), it follows that

\begin{align*}
\sum_{l \in L} \Tilde{\sigma}_l^* = \sum_{l \in L} \min \{ \sigma_l^*, \frac{d_l}{d_l+k} \} \leq \sum_{l \in L} \sigma_l^* \leq R,
\end{align*}

which establishes the feasibility of strategy $\Tilde{\sigmaa}^*$ for Problem (<ref>)-(<ref>).

Next, to see that $\Tilde{\sigmaa}^*$ achieves the same welfare for the administrator as $\sigmaa^*$, we first note that the best-response strategy of users at each location is unchanged under $\sigmaa^*$ and $\Tilde{\sigmaa}^*$, i.e., $\y(\sigmaa^*) = \y(\Tilde{\sigmaa}^*)$. To see this, we show that $y_l(\sigmaa^*) = y_l(\Tilde{\sigmaa}^*)$ for all locations $l$ by considering two cases: (i) $\sigma_l^* < \frac{d_l}{d_l+k}$ and (ii) $\sigma_l^* \geq \frac{d_l}{d_l+k}$. Note that in the first case, $\Tilde{\sigma}_l^* = \sigma_l^*$ and thus it must be that $y_l(\sigmaa^*) = y_l(\Tilde{\sigmaa}^*) = 1$. On the other hand, in the second case, note that $y_l(\sigmaa^*) = 0$ and that $\Tilde{\sigma}_l^* = \frac{d_l}{d_l+k}$, from which it follows by Equation (<ref>) that $y_l(\Tilde{\sigmaa}^*) = 0$ as well. Having shown that $\y(\sigmaa^*) = \y(\Tilde{\sigmaa}^*)$, we now obtain that:

\begin{align*}
W_R^-(\sigmaa^*) &= \sum_{l \in L} (1-\sigma_l^*) y_l^*(\sigmaa^*) v_l, \\
&\stackrel{(a)}{=} \sum_{l \in L: y_l(\sigmaa^*) = 0} (1-\sigma_l^*) y_l^*(\sigmaa^*) v_l + \sum_{l \in L: y_l(\sigmaa^*) = 1} (1-\sigma_l^*) y_l^*(\sigmaa^*) v_l, \\
&\stackrel{(b)}{=} \sum_{l \in L: y_l(\Tilde{\sigmaa}^*) = 1} (1-\Tilde{\sigma_l}^*) y_l^*(\Tilde{\sigmaa}^*)v_l, \\
&\stackrel{(c)}{=} W_R^-(\Tilde{\sigmaa}^*)
\end{align*}

where (a) follows by splitting the sum, (b) follows from the fact that $\Tilde{\sigma}_l^* = \sigma_l^*$ for all $l$ where $y_l(\sigmaa^*) = 1$, as in this regime $\sigma_l^* < \frac{d_l}{d_l+k}$ by Equation (<ref>), and (c) follows from the fact that $\y(\sigmaa^*) = \y(\Tilde{\sigmaa}^*)$.

Finally, by the optimality of $\sigmaa^*$ and from the above obtained relations for the new administrator strategy $\Tilde{\sigmaa}^*$, it holds $W_R^-(\Tilde{\sigmaa}^*) = W_R^-(\sigmaa^*) \leq W_R^-(\sigmaa)$, for all feasible $\sigmaa \in \Omega_R$. Thus, we have established our claim that there exists an administrator strategy $\Tilde{\sigmaa}^*$ that satisfies $\Tilde{\sigma}_l^* \leq \frac{d_l}{d_l+k}$ for all locations $l$ and is a solution to Problem (<ref>)-(<ref>).

§.§.§ Proof of Lemma <ref>

To prove this claim, we show that any administrator strategy $\sigmaa^*$ can be transformed into another strategy $\Tilde{\sigmaa}^*$ satisfying the condition in the statement of the lemma with at most the same objective as that corresponding to $\sigmaa^*$.

To see this, consider an optimal administrator strategy $\sigmaa^*$ such that the strategies $(\sigmaa^*, \y(\sigmaa^*))$ are an optimal solution to Problem (<ref>)-(<ref>). Further, suppose that there are at least two locations $l_1$ and $l_2$ such that $\sigma_{l_1}^* \in \left( 0, \frac{d_{l_1}}{d_{l_1}+k} \right)$ and $\sigma_{l_2}^* \in \left( 0, \frac{d_{l_2}}{d_{l_2}+k} \right)$. In particular, let $L' \subseteq L$ be the set of locations such that for any $l' \in L'$ it holds that $\sigma_{l'}^* \in \left( 0, \frac{d_{l'}}{d_{l'}+k} \right)$. Then, we order the locations in the set $L'$ in descending order of the values $v_l$ and without loss of generality number these locations $1, \ldots, |L'|$. Then, we construct $\Tilde{\sigmaa}^*$ through a water-filling approach. To elucidate this approach, we begin by transferring the mass $\sigma_{|L'|}^*$ corresponding the location with the smallest value of $v_l$ in the set $L'$ to the location with the highest value of $v_l$ in the set $L'$. In particular, we transfer $\min \{ \sigma_{|L'|}^*, \frac{d_1}{d_1+k} - \sigma_{1}^* \}$ from location $|L'|$ to location $1$. If location $|L'|$'s mass is exhausted before filling up location one to $\frac{d_1}{d_1+k}$, then we transfer further mass of location $|L'-1|$ to location one. On the other hand, if location $1$ is filled up to $\frac{d_1}{d_1+k}$ with location $|L'|$, then the remaining mass from location $|L'|$ is transferred to location two in an analogous way. We then repeat this process of transferring mass from locations with lower values of $v_l$ to those with higher values of $v_l$ in the set $L'$ until there is at most one location remaining such that $\Tilde{\sigma}_{l'}^* \in \left( 0, \frac{d_{l'}}{d_{l'}+k} \right)$, where $\Tilde{\sigmaa}^*$ is the administrator strategy constructed by the above procedure.

Having constructed the strategy $\Tilde{\sigmaa}^*$ in the above manner, it is then straightforward to see that $W_R^-(\Tilde{\sigmaa}^*) \leq W_R^-(\sigmaa^*)$ as:

\begin{align*}
W_R^-(\sigmaa^*) &= \sum_{l \in L} (1-\sigma_l^*) y_l(\sigmaa^*) v_l, \\
&= \sum_{l \in L'} (1-\sigma_l^*) y_l(\sigmaa^*) v_l + \sum_{l \in L \backslash L'} (1-\sigma_l^*) y_l(\sigmaa^*) v_l , \\
&\stackrel{(a)}{=} \sum_{l \in L'} (1-\sigma_l^*) y_l(\sigmaa^*) v_l + \sum_{l \in L \backslash L'} (1-\Tilde{\sigma}_l^*) y_l(\Tilde{\sigmaa}^*) v_l , \\
&\stackrel{(b)}{\geq} \sum_{l \in L'} (1-\Tilde{\sigma}_l^*) y_l(\sigmaa^*) v_l + \sum_{l \in L \backslash L'} (1-\Tilde{\sigma}_l^*) y_l(\Tilde{\sigmaa}^*) v_l , \\
&\stackrel{(c)}{\geq} \sum_{l \in L'} (1-\Tilde{\sigma}_l^*) y_l(\Tilde{\sigmaa}^*) v_l + \sum_{l \in L \backslash L'} (1-\Tilde{\sigma}_l^*) y_l(\Tilde{\sigmaa}^*) v_l , \\
&= W_R^-(\Tilde{\sigmaa}^*),
\end{align*}

where (a) follows as $\sigma_l^* = \Tilde{\sigma}_l^*$ for all $l \in L \backslash L'$, (b) follows by our algorithmic procedure of constructing $\Tilde{\sigmaa}^*$ as we transfer mass from lower values of $v_l$ to higher values of $v_l$ in the set $L'$, and (c) follows as $y_l(\Tilde{\sigmaa}^*) \leq 1 = y_l(\sigmaa^*)$ for all $l \in L'$.

The above analysis establishes our claim that there exists an administrator strategy $\Tilde{\sigmaa}^*$ that is a solution to Problem (<ref>)-(<ref>) such that for at most one location $l'$, it holds that $\Tilde{\sigma}_{l'}^* \in \left( 0, \frac{d_{l'}}{d_{l'}+k} \right)$, which establishes our claim.

§.§ Proof of Theorem <ref>

We prove this result through a reduction from an instance of the partition problem. A partition instance consists of a sequence of numbers $a_1, \ldots, a_n$ with $\sum_{l \in [n]} a_l = A$ and involves the task of deciding whether there is some subset $S_1$ of numbers such that $\sum_{l \in S_1} a_l = \frac{A}{2}$. Without loss of generality, we consider a partition instance where $\max_{l \in [n]} a_l \leq \frac{A}{2}$. Note that if $\max_{l \in [n]} a_l > \frac{A}{2}$, then clearly, there is no subset $S_1$ of numbers such that $\sum_{l \in S_1} a_l = \frac{A}{2}$, i.e., such an instance of partition can be solved in polynomial time.

We now construct an instance of the welfare maximization problem. In particular, we consider an instance with $n+1$ locations, where the first $n$ locations correspond to each number of the partition instance, where we define $v_l = a_l$ and let $\frac{d_l}{d_l+k} = \frac{a_l}{A}$ for all locations $l \in [n]$. Furthermore, we consider a location $n+1$ such that $v_{n+1} = \max_{l \in [n]} v_l + \epsilon$ and $\frac{d_{n+1}}{d_{n+1}+k} = \frac{1}{2} + \delta$, where $\epsilon>0$ and $\delta>0$ can be interpreted as small constants. We choose $\epsilon$ such that $\max_{l \in [n]} a_l + \epsilon < A$, which is well defined as we consider partition instances where $\max_{l \in [n]} a_l \leq \frac{A}{2}$. Finally, we let the total resource budget $R = \frac{1}{2}$. Given this instance of the welfare maximization problem, we now show that a sequence of numbers correspond to a “Yes” instance of the partition problem if and only if the objective of Problem (<ref>)-(<ref>) for above defined instance is at most $\frac{A}{2} + v_{n+1}$, i.e., the total welfare is at least $\frac{A}{2}$.

($\implies$:) We first suppose that we have a “Yes” instance of the partition problem, i.e., there exists a set $S$ of numbers such that $\sum_{l \in S} a_l = \frac{A}{2}$. In this case, we present a method to construct a feasible resource allocation strategy $\sigmaa$ of the administrator that achieves $W_R(\sigmaa) \geq \frac{A}{2}$. In particular, we consider an allocation $\sigmaa$ for the above defined instance of the welfare maximization problem, where $\sigma_l = \frac{d_l}{d_l+k}$ units of resources are invested in for all locations $l \in S$ and $\sigma_l = 0$ for all $l \in [n+1] \backslash S$. Such an allocation is feasible for this instance of the welfare maximization problem as:

\begin{align*}
\sum_{l \in [n+1]} \sigma_l = \sum_{l \in S} \frac{d_l}{d_l+k} = \sum_{l \in S} \frac{a_l}{A} = \frac{1}{A} \sum_{l \in S} a_l = \frac{1}{A} \times \frac{A}{2} = \frac{1}{2} = R,
\end{align*}

i.e., the resource constraint is satisfied.

Furthermore, the objective of Problem (<ref>)-(<ref>) under the strategy $\sigmaa$ is given by

\begin{align*}
W_R^-(\sigmaa) &= \sum_{l \in [n+1]} (1 - \sigma_l) y_l(\sigmaa) v_l, \\
&\stackrel{(a)}{=} \sum_{l \in S} (1 - \frac{d_l}{d_l+k}) y_l(\sigmaa) v_l + \sum_{l \in [n+1] \backslash S} (1 - 0) y_l(\sigmaa) v_l, \\
&\stackrel{(b)}{=} \sum_{l \in [n] \backslash S} v_l + v_{n+1}, \\
&\stackrel{(c)}{=} \frac{A}{2} + v_{n+1},
\end{align*}

where (a) follows as $\sigma_l = \frac{d_l}{d_l+k}$ for all $l \in S$ and $\sigma_l = 0$ for all $l \in [n+1] \backslash S$, (b) follows as $y_l(\sigmaa) = 0$ when $\sigma_l = \frac{d_l}{d_l+k}$ and $y_l(\sigmaa) = 1$ when $\sigma_l = 0$ by the best-response of users in Equation (<ref>), and (c) follows as $\sum_{l \in [n] \backslash S} v_l = \frac{A}{2}$. The above relation implies that the welfare of the allocation $\sigmaa$ is given by

\begin{align*}
W_R(\sigmaa) = \sum_{l \in [n+1]} v_l -  W_R^-(\sigmaa) = A + v_{n+1} - \left( \frac{A}{2} + v_{n+1} \right) = \frac{A}{2}.
\end{align*}

The above relation implies that $W_R(\sigmaa) \geq \frac{A}{2}$, and thus we have shown that a “Yes” instance of the partition problem implies that the administrator's optimal welfare for the above defined instance is at least $\frac{A}{2}$, which establishes the forward direction of our claim.

($\impliedby$:) Next, suppose that the optimal resource allocation strategy $\sigmaa$ of the administrator is such that $W_R(\sigmaa) \geq \frac{A}{2}$, i.e., $W_R^-(\sigmaa) \leq \frac{A}{2} + v_{n+1}$ where $\sigmaa \in \Omega_R$ satisfies $\sum_{l \in [n+1]} \sigma_l \leq R = \frac{1}{2}$. From the structure of the optimal administrator strategy established in Proposition <ref>, we note that the objective of Problem (<ref>)-(<ref>) is given by:

\begin{align} \label{eq:helper-wr-minus-relation}
W_R^-(\sigmaa) = \sum_{l \in L_2} v_l + (1-\sigma_{l'} ) v_{l'},
\end{align}

for some location $l'$ and a set of locations $L_2$, where it holds that $\sum_{l \in [n+1] \backslash L_2} \sigma_l \leq \frac{1}{2}$. Then, we show that we have a “Yes” instance of the partition problem by considering two cases: (i) $l' = \emptyset$ and (ii) $l' \neq \emptyset$.

Case (i): In the setting when $l' = \emptyset$, without loss of generality, for ease of notation, we define $L_2 \cup \{ n+1\}$ as the set of locations for which $\sigma_l = 0$ and $L_1$ as the set of locations for which $\sigma_l = \frac{d_l}{d_l+k}$. Note here that as $R = \frac{1}{2} < \frac{1}{2}+\delta = \frac{d_{n+1}}{d_{n+1}+k}$ it follows for location $n+1$ that $\sigma_{n+1} = 0$ as $l' = \emptyset$. Next, for our welfare maximization instance, we note by assumption that the following two inequalities are satisfied: (i) $\sum_{l \in L_2 \cup \{ n+1\}} v_l \leq \frac{A}{2} + v_{n+1}$ and (ii) $\sum_{l \in L_1} \frac{a_l}{A} = \sum_{l \in L_1} \frac{d_l}{d_l+k} \leq \frac{1}{2}$. From the first inequality, we have that

\begin{align*}
\sum_{l \in L_1} a_l = \sum_{l \in L_1} v_l = \sum_{l \in L} v_l - \sum_{l \in L_2 \cup \{ n+1\}} v_l \geq \frac{A}{2},
\end{align*}

where the inequality follows as $\sum_{l \in [n+1]} a_l = A + v_{n+1}$ and the fact that $\sum_{l \in L_2 \cup \{ n+1\}} v_l \leq \frac{A}{2} + v_{n+1}$. Combining this derived inequality with the resource constraint that $\sum_{l \in L_1} \frac{a_l}{A} \leq \frac{1}{2}$, it follows that $\sum_{l \in L_1} a_l = \frac{A}{2}$, i.e., we have a “Yes” instance of the partition problem.

Case (ii): In the setting when $l' \neq \emptyset$, we first show that it must follow that $l' = \{ n+1\}$. At a high-level, this result follows as location $n+1$ has the highest value of $v_l$ among all the locations. We now proceed by contradiction to establish this claim by supposing that $l' \neq \{ n+1\}$. Next, note that by our constructed instance that $\frac{d_{n+1}}{d_{n+1}+k} = \frac{1}{2} + \delta > R$ and thus the location $n+1 \in L_2$.

To derive our contradiction, we consider an allocation $\Tilde{\sigmaa}$ where $\Tilde{\sigma}_{l'} = 0$ and $\Tilde{\sigma}_{n+1} = \sigma_{l'}$. Note that $\sigma_{l'} \in \left( 0, \frac{d_{l^{'}}}{d_{l^{'}}+k}\right)$ and thus it also holds that $\sigma_{l'} \in \left( 0, \frac{d_{n+1}}{d_{n+1}+k}\right)$, as $\frac{d_{n+1}}{d_{n+1}+k} > \frac{1}{2} \geq \frac{\max_{l \in [n]} a_l}{A} = \frac{d_{l^{'}}}{d_{l^{'}}+k}$. Clearly the new allocation $\Tilde{\sigmaa}$ is feasible as $\sigmaa$ is feasible. Next, we observe that

\begin{align*}
W_R^-(\sigmaa) &\stackrel{(a)}{=} \sum_{l \in L_2} v_l + (1-\sigma_{l'} ) v_{l'} = \sum_{l \in L_2 \backslash \{ n+1\}} v_l + v_{n+1} + (1-\sigma_{l'} ) v_{l'}, \\
&\stackrel{(b)}{>} \sum_{l \in L_2 \cup \{ l'\}} v_l + (1-\sigma_{l'} ) v_{n+1}, \\
&\stackrel{(c)}{=} \sum_{l \in L_2 \cup \{ l'\}} v_l + (1-\Tilde{\sigma}_{n+1} ) v_{n+1}, \\
&\stackrel{(d)}{=} W_R^-(\Tilde{\sigmaa}),
\end{align*}

where (a) follows from Equation (<ref>), (b) follows as $v_{n+1} = \max_{l \in [n]} v_l + \epsilon > v_{l'}$, (c) follows as $\Tilde{\sigma}_{n+1} = \sigma_{l'}$, and (d) follows by the definition of $W_R^-(\Tilde{\sigmaa})$ and the fact that the only change in the allocation between $\sigmaa$ and $\Tilde{\sigmaa}$ is for locations $l'$ and $n+1$. The above relations imply that the allocation strategy $\Tilde{\sigmaa}$ achieves a lower objective for Problem (<ref>)-(<ref>) than the strategy $\sigmaa$, a contradiction. Thus, it follows that if $l' \neq \emptyset$, then it must be that $l' = \{ n+1\}$ for our above defined instance of the welfare maximization problem.

Next, recall that $L_2$ are the set of locations for which $\sigma_l = 0$ and $L_1$ are the set of locations for which $\sigma_l = \frac{d_l}{d_l+k}$. Then, for our welfare maximization instance, we have that the following two inequalities hold:

\begin{align}
&\sum_{l \in L_2} v_l + (1-\sigma_{n+1}) v_{n+1} \leq \frac{A}{2} + v_{n+1}, \label{eq:helper-1-} \\
&\sum_{l \in L_2} \frac{d_l}{d_l+k} + \sigma_{n+1} \leq \frac{1}{2}. \label{eq:helper-2-}
\end{align}

The first inequality represents the fact that the optimal objective of the Problem (<ref>)-(<ref>) is at most $\frac{A}{2} + v_{n+1}$ and the second inequality implies that the total resource spending does not exceed the available resources.

Then, noting that $\sum_{l \in [n+1]} v_l = A + v_{n+1}$, we have from the Equation (<ref>) that:

\begin{align*}
\sum_{l \in L_1} v_l + \sigma_{n+1} v_{n+1} = \sum_{l \in [n+1]} v_l - \left( \sum_{l \in L_2} v_l + (1-\sigma_{n+1}) v_{n+1} \right) \geq A + v_{n+1} - \left( \frac{A}{2} + v_{n+1} \right) = \frac{A}{2}.
\end{align*}

Substituting $v_l = a_l$ and $v_{n+1} = \max_{l \in [n]} a_l + \epsilon$ in the above inequality, we obtain that:

\begin{align} \label{eq:modified-objective-helper-}
\sum_{l \in L_1} a_l + \sigma_{n+1} (\max_{l \in [n]} a_l + \epsilon) \geq \frac{A}{2}.
\end{align}

Moreover, substituting $\frac{d_l}{d_l+k} = \frac{a_l}{A}$ in Equation (<ref>), we obtain that:

\begin{align} \label{eq:mnodified-resource-helper-}
\sum_{l \in L_1} a_l + \sigma_{n+1} A \leq \frac{A}{2}.
\end{align}

Combining Equations (<ref>) and (<ref>), we obtain that:

\begin{align*}
\sigma_{n+1} (\max_{l \in [n]} a_l + \epsilon) \geq \sigma_{n+1} A.
\end{align*}

Note that this inequality can only be satisfied if either $\sigma_{n+1} = 0$ or $\max_{l \in [n]} a_l + \epsilon \geq A = \sum_{l \in [n]} a_l$. Note that the latter inequality cannot be satisfied as $\epsilon$ has been chosen to be a small constant such that $\max_{l \in [n]} a_l + \epsilon < A$, where, recall that $\max_{l \in [n]} a_l \leq \frac{A}{2}$. As a result, the above relation implies $\sigma_{n+1} = 0$, which, from Equations (<ref>) and (<ref>), implies the following two relations:

\begin{align*}
\sum_{l \in L_1} a_l \geq \frac{A}{2} \text{ and } \sum_{l \in L_1} a_l \leq \frac{A}{2},
\end{align*}

which together imply that $\sum_{l \in L_1} a_l = \frac{A}{2}$. Thus, again, we have a “Yes” instance of partition, which establishes our claim.

§.§ Proof of Theorem <ref>

§.§.§ Proof Overview

We first define a linear program resembling a fractional knapsack like optimization and leverage Proposition <ref> to show that the optimal administrator welfare is upper bounded by the optimal objective of this linear program. Next, since the optimal objective of the fractional knapsack problem satisfies $\sum_{l \in S} v_l + x_{\Tilde{l}} v_{\Tilde{l}}$ for some subset of locations $S$ and a location $\Tilde{l}$ with $x_{\Tilde{l}} \leq \frac{d_{\Tilde{l}}}{d_{\Tilde{l}}+k}$, to establish the desired half approximation, we show that (i) $W_R(\sigmaa') \geq x_{\Tilde{l}} v_{\Tilde{l}}$ and (ii) $W_R(\Tilde{\sigmaa}) \geq \sum_{l \in S} v_l$, where the allocations $\sigmaa'$ and $\Tilde{\sigmaa}$ are as defined in Algorithm <ref>. Notice that the proof of claim (i) is by construction as $\sigmaa'$ by definition is chosen to maximize the welfare from spending on a single location. The proof of claim (ii) relies on the fact that the greedy algorithm in Step 1 on Algorithm <ref> precisely corresponds to the greedy algorithm to optimize the knapsack linear program. Finally, combining the results of claims (i) and (ii), the desired result follows.

§.§.§ Complete Proof of Theorem <ref>

To prove this claim, we first recall from Proposition <ref> that the welfare maximizing objective of the administrator at the solution $\sigmaa^*$ is given by $W_R(\sigmaa^*) = \sum_{l \in L_1} v_l + \sigma_{\Tilde{l}}^* v_{\Tilde{l}}$ for some subset of locations $L_1$ where $\sigma_l^* = \frac{d_l}{d_l+k}$ for all $l \in L_1$ and a location $\Tilde{l}$ such that $\sum_{l \in L_1} \frac{d_l}{d_l+k} + \sigma_{\Tilde{l}}^* \leq R$. Furthermore, we consider the following knapsack optimization problem:

\begin{align} \label{eq:fractional-knapsack-ub}
G_R' = \max_{0 \leq x_l \leq 1} \sum_{l \in L} x_l v_l \text{ s.t. } \sum_{l \in L} \frac{d_l}{d_l+k} x_l \leq R.
\end{align}

Then, to prove this claim, we proceed in two steps. First, we show that the optimal welfare-maximizing objective of the administrator is no more than $G_R'$, the optimal objective corresponding to Problem (<ref>). Then, we use this result and the property of the optimal welfare-maximizing objective of the administrator from Proposition<ref> to establish the half approximation guarantee of Algorithm <ref>.

Proof of $W_R(\sigmaa^*) \leq G_R'$: To prove this claim, first note by the structure of the optimal solution established in Proposition <ref> that $\sigma^*_l \geq 0$ and $\sigma^*_l \leq \frac{d_l}{d_l+k}$ for all locations $l$, and by the feasibility of $\sigmaa^*$ that $\sum_{l \in L} \sigma^*_l \leq R$. Then, we transform $\sigmaa^*$ to a feasible solution of Problem (<ref>) by defining $x_l = \frac{d_l+k}{d_l} \sigma_l^*$ for all $l$. Note that $\x = (x_l)_{l \in L}$ is a feasible solution to Problem (<ref>) as, by definition of $\x$ it holds that $0 \leq x_l \leq 1$, and the resource constraint is satisfied:

\begin{align*}
\sum_{l \in L} \frac{d_l}{d_l+k} x_l = \sum_{l \in L} \frac{d_l}{d_l+k} \frac{d_l+k}{d_l} \sigma_l^* = \sum_{l \in L} \sigma_l^* \leq R.
\end{align*}

Next, to show that $G_R' \geq W_R(\sigmaa^*)$, we have:

\begin{align*}
G_R' &\stackrel{(a)}{\geq} \sum_{l \in L} x_l v_l, \\
&\stackrel{(b)}{=} \sum_{l \in L_1} \frac{d_l+k}{d_l} \sigma_l^* v_l + \frac{d_{\Tilde{l}}+k}{d_{\Tilde{l}}} \sigma_{\Tilde{l}}^* v_{\Tilde{l}}, \\
&\stackrel{(c)}{\geq} \sum_{l \in L_1} v_l + \sigma_{\Tilde{l}}^* v_{\Tilde{l}}, \\
&\stackrel{(d)}{=} W_R(\sigmaa^*),
\end{align*}

where (a) follows from the fact that $\x = (x_l)_{l \in L}$ is one of the feasible solutions to Problem (<ref>), (b) follows from the fact that $x_l = \frac{d_l+k}{d_l} \sigma^*_l$ and that $\sigma^*_l = 0$ for $l \notin L_1 \cup \{ \Tilde{l} \}$, (c) follows from the fact that $\sigma_{l}^* = \frac{d_l}{d_l+k}$ for all $l \in L_1$ and that $\frac{d_{\Tilde{l}}+k}{d_{\Tilde{l}}} \geq 1$, and (d) follows by the definition of $W_R(\sigmaa^*)$. Thus, we have shown that $G_R' \geq W_R(\sigmaa^*)$.

Proving the Approximation Ratio: Finally, to complete the proof of our claim, notice that as Problem (<ref>) is a fractional knapsack problem that $G_R' = \sum_{l \in S} v_l + x_{l'}^* v_{l'}$ for some subset $S$ and allocation $\x^*$, where resources are allocated to locations in the descending orders of the bang-per-buck. Next, note that by Algorithm <ref> that

\begin{align} \label{eq:helper-greedy-lb}
W_R(\sigmaa^*_A) \geq W_R(\Tilde{\sigmaa}) \geq \sum_{l \in S} v_l,
\end{align}

where recall that $\Tilde{\sigmaa}$ is the allocation corresponding to the greedy algorithm in Step 1 of Algorithm <ref> and the second inequality follows as the greedy algorithm selects at least the first $S$ locations in the descending order of their bang-per-buck values. Furthermore, by Step 2 of Algorithm <ref> and the construction of the allocation $\sigmaa'$, it follows that

\begin{align} \label{eq:helper-single-location-lb}
W_R(\sigmaa^*_A) \geq W_R(\sigmaa') \geq x_{'}^* v_{l'}.
\end{align}

Then, summing Equations (<ref>) and (<ref>), we obtain that:

\begin{align*}
2 W_R(\sigmaa^*_A) \geq \sum_{l \in S} v_l + x_{l'}^* v_{l'} = G_R' \geq W_R(\sigmaa^*),
\end{align*}

which establishes our claim that $W_R(\sigmaa^*_A) \geq \frac{1}{2} W_R(\sigmaa^*)$, i.e., Algorithm <ref> is a half approximation to the optimal solution to the bi-level Program (<ref>)-(<ref>).

§.§ Proof of Theorem <ref>

To prove this result, we again consider the fractional knapsack Problem (<ref>) defined in the proof of Theorem <ref> and use the fact that the objective of the fractional knapsack Problem (<ref>) upper bounds the optimal administrator welfare, given by $W_R(\sigmaa^*)$. In particular, to establish the desired resource augmentation guarantee, we first recall from the optimal solution of the fractional knapsack problem that $G_R' = \sum_{l \in S} v_l + x_{l'}^* v_{l'}$ for some subset $S$ and allocation $\x^*$, where resources are allocated to locations in the descending orders of the bang-per-buck. Next, given $R+1$ resources, we define $\Tilde{\sigmaa}^{R+1}$ as the allocation corresponding to Step 1 of Algorithm <ref> and let $\sigmaa_A^{R+1}$ be the allocation corresponding to Algorithm <ref> with $R+1$ resources. We now show that $W_{R+1}(\sigmaa_A^{R+1}) \geq W_R(\sigmaa^*)$ to prove our claim.

To show this, we note by our greedy procedure in Step 1 of Algorithm <ref> that $\Tilde{\sigmaa}^{R+1} \geq \Tilde{\sigmaa}$ and that $\Tilde{\sigma}_{l'}^{R+1} = \frac{d_{l'}}{d_{l'}+k}$. Such a result holds as the additional resource ensures that the administrator will allocate $ \frac{d_{l'}}{d_{l'}+k} \leq 1$ units of resources to location $l'$, as location $l'$ has the highest bang-per-buck ratio among the remaining locations by definition (as $G_R' = \sum_{l \in S} v_l + x_{l'}^* v_{l'}$ for some subset $S$ and allocation $\x^*$, where resources are allocated to locations in the descending orders of the bang-per-buck). Since $\Tilde{\sigma}^{R+1}_{l'} = \frac{d_{l'}}{d_{l'}+k}$, note by the best-response Problem (<ref>) of users that $y_{l'}(\Tilde{\sigmaa}^{R+1}) = 0$. Consequently, as the allocation $\Tilde{\sigmaa}^{R+1}$ allocates resources to locations in the descending order of the bang-per-buck ratios and, in particular, allocates $\frac{d_{l'}}{d_{l'}+k} \leq 1$ fraction of resources to location $l'$, it follows that

\begin{align*}
W_{R+1}(\sigmaa_A^{R+1}) \stackrel{(a)}{\geq} W_R(\Tilde{\sigmaa}^{R+1}) \stackrel{(b)}{\geq} \sum_{l \in S} v_l + v_{l'} \stackrel{(c)}{\geq} \sum_{l \in S} v_l + x_{l'}^* v_{l'} = G_R' \stackrel{(d)}{\geq} W_R^*(\sigmaa^*)
\end{align*}

where (a) follows from the fact that $\sigmaa_A^{R+1}$ corresponds to the outcome with a greater welfare from steps 1 and 2 of Algorithm <ref>, (b) follows as $\Tilde{\sigmaa}^{R+1}$ corresponds to an allocation of resources in the descending orders of the bang-per-buck when an administrator has an additional resource that it can spend on location $l'$ and that $y_{l'}(\Tilde{\sigmaa}^{R+1}) = 0$. Furthermore, (c) follows from the fact that $x_{l'}^* \in (0, \frac{d_{l'}}{d_{l'}+k})$ and (d) follows from our relation derived in proof of Theorem <ref> that the optimal objective of the fractional knapsack Problem (<ref>) is at least the welfare-maximizing objective. Thus, we have shown that $W_{R+1}(\sigmaa_A^{R+1}) \geq W_R(\sigmaa^*)$, which establishes our claim.

§.§ Proof of Theorem <ref>

We prove Theorem <ref> through a reduction from an instance of the partition problem. Recall that a partition instance consists of a sequence of numbers $a_1, \ldots, a_n$ with $\sum_{l \in [n]} a_l = A$ and involves the task of deciding whether there is some subset $S_1$ of numbers such that $\sum_{l \in S_1} a_l = \frac{A}{2}$.

In the following, we construct an instance of the expected revenue maximization problem, henceforth referred to as ERMP for brevity, based on a partition instance and present four intermediate lemmas to complete the proof of Theorem <ref>. We then present the detailed proofs of these lemmas in later subsections.

To this end, we begin by constructing an instance of the ERMP problem with with two types, i.e., where $|\I| = 2$, and $n$ locations, where each number $a_l$ corresponds to a given location. In this setting, for ease of exposition, we drop the fine $k$ from the expected revenue maximization Objective (<ref>) of the administrator as this is a uniform constant that applies to all locations $l$ and types $i$. Then, we define the following four quantities: (i) $\frac{d_l^1}{d_l^1+k} = \frac{1}{2} \frac{a_l}{A}$, (ii) $\frac{d_l^2}{d_l^2+k} = \frac{a_l}{A}$, (iii) $q_l^1 \Lambda_l^1 = A \left( 2 \frac{\max_{l' \in [n]} a_{l'}}{a_l} - 1 \right)$, and (iv) $q_l^2 \Lambda_l^2 = A \left(1+ \frac{2 \max_{l' \in [n]} a_{l'}}{a_l} \right)$ for all $l \in [n]$. Moreover, we define the resource budget as $R = \frac{3}{4}$.

Given this instance of ERMP, we claim that we have a “Yes” instance of partition if and only if there is a feasible allocation of resources to locations with total expected revenue that is at least $\frac{A}{2} + 2 n \times \max_{l \in [n]} a_l$ for the above defined ERMP instance.

To establish this claim, we first prove its forward direction that if we have a “Yes” instance of partition, then there exists a feasible allocation of resources to locations with total expected revenue that is at least $\frac{A}{2} + 2 n \times \max_{l \in [n]} a_l$ for the above defined ERMP instance.

Consider a partition instance with a sequence of numbers $a_1, \ldots, a_n$ with $\sum_{l \in [n]} a_l = A$, such that there exists a subset $S_1$ of numbers such that $\sum_{l \in S_1} a_l = \frac{A}{2}$. Then, there exists a feasible allocation of resources to locations with total expected revenue that is at least $\frac{A}{2} + 2 n \times \max_{l \in [n]} a_l$ for the above defined ERMP instance.

To prove this claim, we present a method to construct a feasible administrator strategy $\sigmaa$ for the above defined ERMP instance and show that the expected revenue of this administrator strategy satisfies $Q_R(\sigmaa) \geq \frac{A}{2} + 2 n \times \max_{l \in [n]} a_l$. For a proof of Lemma <ref>, see Appendix <ref>.

Next, to prove the reverse direction of this claim, we suppose that the optimal resource allocation strategy corresponding to the above defined ERMP instance is such that the expected revenue $Q_R(\sigmaa) \geq \frac{A}{2} + 2 n \times \max_{l \in [n]} a_l$ and the total resources $\sum_{l \in [n]} \sigma_l \leq \frac{3}{4} = R$. To prove that such a setting corresponds to a “Yes” instance of partition, we use three intermediate lemmas. Our first two lemmas establish certain structural properties of the administrator's expected revenue maximizing solution. In particular, we first establish a lower bound on the resources allocated to each location under the expected revenue maximizing strategy of the administrator, as is elucidated through the following lemma.

Suppose that there is some feasible administrator strategy $\sigmaa$ that satisfies $Q_R(\sigmaa) \geq \frac{A}{2} + 2 n \times \max_{l \in [n]} a_l$ for $R = \frac{3}{4}$. Then, there exists an expected revenue maximizing administrator strategy $\Tilde{\sigmaa}^*$ for the above defined ERMP instance such that $\Tilde{\sigma}_l^* \geq \frac{d_l^1}{d_l^1+k}$ for all locations $l$.

For a proof of Lemma <ref>, see Appendix <ref>. Given the result obtained in Lemma <ref>, for the remainder of this proof, we focus on expected-revenue maximizing administrator strategies $\sigmaa$ that satisfy $\sigma_l \geq \frac{d_l^1}{d_l^1+k}$ for all locations $l$ for our above defined ERMP instance.

Next, following a similar analysis in the proof of Proposition <ref>, we can establish the following property on the optimal solution of Problem (<ref>)-(<ref>).

Suppose that users at each location best-respond based on Equation (<ref>). Then, there exists an expected revenue maximizing strategy $\Tilde{\sigmaa}^*$ of the administrator corresponding to the solution of Problem (<ref>)-(<ref>) such that:

* There exists a set of locations $L_1$ such that $\Tilde{\sigma}_l^* = \frac{d_l^{i_l}}{d_l^{i_l}+k}$ for all $l \in L_1$ for some type $i_l \in \I$ that can be location specific, a set of locations $L_2$ such that $\Tilde{\sigma}_l^* = 0$ for all $l \in L_2$, and at most one location $l'$ such that either $\Tilde{\sigma}_{l'}^* \in (0, \frac{d_{l'}^{1}}{d_{l'}^{1}+k})$ or $\Tilde{\sigma}_{l'}^* \in (\frac{d_{l'}^{i-1}}{d_{l'}^{i-1}+k}, \frac{d_{l'}^{i}}{d_{l'}^{i}+k})$ for some $i>1$. Here, $L_1$, $L_2$, and $l'$ are all disjoint and $L_1 \cup L_2 \cup \{ l'\} = L$.

Since the analysis of the above result follows similar arguments to that in the proof of Proposition<ref>, we omit it for brevity.

Finally, we use the structure of the optimal (expected revenue maximizing) solution of the above defined ERMP instance established in Lemmas <ref> and <ref> to show that our ERMP instance with $Q_R(\sigmaa) \geq \frac{A}{2} + 2 n \times \max_{l \in [n]} a_l$ corresponds to a “Yes” instance of partition.

Suppose that there is some feasible administrator strategy $\sigmaa$ that satisfies $Q_R(\sigmaa) \geq \frac{A}{2} + 2 n \times \max_{l \in [n]} a_l$ for $R = \frac{3}{4}$. Then, for the above defined ERMP instance, there exists a subset $S_1$ of numbers such that $\sum_{l \in S_1} a_l = \frac{A}{2}$, i.e., we have a “Yes” instance of partition.

For a proof of Lemma <ref>, see Appendix <ref>. Note that Lemmas <ref>-<ref> prove Theorem <ref>.

§.§.§ Proof of Lemma <ref>

We first suppose that we have a “Yes” instance of partition, i.e., there exists a set of $S$ numbers such that $\sum_{l \in S} a_l = \frac{A}{2}$. Then, consider an administrator strategy $\sigmaa$ such that $\sigma_l = \frac{a_l}{A}$ for all $l \in S$ and $\sigma_l = \frac{1}{2} \frac{a_l}{A}$ for all $l \in [n] \backslash S$. We first note that $\sigmaa$ is feasible, i.e., $\sigmaa \in \Omega_R$, as $\sigma_l \in [0, 1]$ by construction and the resource constraint is satisfied as:

\begin{align*}
\sum_{l \in [n]} \sigma_l &= \sum_{l \in S} \sigma_l + \sum_{l \in S \backslash [n]} \sigma_l = \sum_{l \in S} \frac{a_l}{A} + \sum_{l \in [n] \backslash S} \frac{1}{2} \frac{a_l}{A}, \\
&\stackrel{(a)}{=} \frac{1}{A} \frac{A}{2} + \frac{1}{2A} \frac{A}{2} = \frac{3}{4} = R,
\end{align*}

where (a) follows as $\sum_{l \in S} a_l = \frac{A}{2}$ and $\sum_{l \in [n] \backslash S} a_l = \frac{A}{2}$ as we have a “Yes” instance of partition.

Next, we obtain the following expected revenue objective for the administrator when it plays the above defined strategy $\sigmaa$:

\begin{align*}
Q_R(\sigmaa) &= \sum_{i \in \I} \sum_{l \in L} \sigma_l y_l^i(\sigmaa) q_{l}^i \Lambda_l^i \stackrel{(a)}{=} \sum_{l \in S} q_l^2 \Lambda_l^2 \frac{d_l^2}{d_l^2+k} + \sum_{l \in [n] \backslash S} (q_l^1 \Lambda_l^1 + q_l^2 \Lambda_l^2) \frac{d_l^1}{d_l^1+k}, \\
&\stackrel{(b)}{=}  \sum_{l \in S} A \left(1 \! + \! \frac{2 \max_{l' \in [n]} a_{l'}}{a_l} \right)  \! \! \frac{a_l}{A} + \! \! \sum_{l \in S \backslash [n]} \! \! \! \left( A \left( 2 \frac{\max_{l' \in [n]} a_{l'}}{a_l} \! - \! 1 \right) \! + \! A \left(1 \! + \! \frac{2 \max_{l' \in [n]} a_{l'}}{a_l} \right) \right) \frac{1}{2} \frac{a_l}{A} , \\
&= \sum_{l \in S} \left( a_l + 2 \max_{l' \in [n]} a_{l'} \right) + \sum_{l \in S \backslash [n]} 2 \max_{l' \in [n]} a_{l'}, \\
&= \frac{A}{2} + 2 \sum_{l \in [n]} \max_{l' \in [n]} a_{l'}, \\
&= \frac{A}{2} + 2n \max_{l' \in [n]} a_{l'},
\end{align*}

where we have dropped the fine $k$ from the objective for ease of exposition, (a) follows by the definition of $y_l^i(\sigmaa)$ as given in Equation (<ref>), and (b) follows by plugging in the values of the respective quantities in the above defined instance. The above analysis implies that $\sigmaa$ is both feasible and achieves a total expected revenue of $\frac{A}{2} + 2 n \times \max_{l \in [n]} a_l$, which establishes the forward direction of our claim.

§.§.§ Proof of Lemma <ref>

To prove this claim, we first show that in the setting when $R = \frac{3}{4}$ any optimal administrator strategy $\Tilde{\sigmaa}^*$ satisfies $\Tilde{\sigma}_l^* \geq \frac{d_l^1}{d_l^1+k}$ for all locations $l$.
To this end, suppose for contradiction that there is an optimal solution $\sigmaa^*$ to the ERMP instance such that there is some set of locations $S'$ for which $\sigma_{l'}^* < \frac{d_{l'}^1}{d_{l'}^1+k}$ for all $l' \in S'$. Furthermore, define $\gamma = \sum_{l \in L} \min \{ \sigma_l^*, \frac{d_l^1}{d_l^1+k} \}$ to represent the total spending across locations to cover the first type $i = 1$. In this case we note that $\gamma < \frac{1}{2}$, as

\begin{align*}
\gamma &= \sum_{l \in L} \min \{ \sigma_l^*, \frac{d_l^1}{d_l^1+k} \} \stackrel{(a)}{<} \sum_{l \in L} \frac{d_l^1}{d_l^1+k} \stackrel{(b)}{=} \sum_{l \in L} \frac{1}{2} \frac{a_l}{A} \stackrel{(c)}{=} \frac{1}{2},
\end{align*}

where (a) follows as there is some set of location $S'$ for which $\sigma_{l'}^* < \frac{d_{l'}^1}{d_{l'}^1+k}$ for all $l' \in S'$ by our contradiction assumption, (b) follows by substituting $\frac{d_l^1}{d_l^1+k} = \frac{1}{2} \frac{a_l}{A}$ for our defined ERMP instance, and (c) follows as $\sum_{l \in [n]} a_l = A$.

We now define an allocation strategy $\Tilde{\sigmaa}$ with a strictly higher expected revenue than $\sigmaa^*$ to derive our desired contradiction. To do so, we first define $\delta = \sum_{l \in L} \max \{ 0, \sigma_l^* - \frac{d_l^1}{d_l^1+k} \}$ as the cumulative resources allocated to locations beyond $\frac{d_l^1}{d_l^1+k}$. In this case, we note that $\delta \geq \frac{1}{2} - \gamma$, as if this were not the case then $\Tilde{\sigmaa}^*$ would not be optimal (as the amount of resources $\frac{1}{2} - \gamma$ could be spent on locations in the set $S'$ for which $\sigma_{l'}^* < \frac{d_{l'}^1}{d_{l'}^1+k}$ for all $l' \in S'$ to obtain a higher expected revenue for the administrator). Then, we construct $\Tilde{\sigmaa}$ by transferring $\frac{1}{2} - \gamma$ of mass from locations $l \in [n] \backslash S'$ with $\sigma_l^* > \frac{d_l^1}{d_l^1+k}$ to locations in the set $S'$ with $\sigma_l^* < \frac{d_l^1}{d_l^1+k}$, such that $\Tilde{\sigma}_l \geq \frac{d_l^1}{d_l^1+k}$ for all locations $l$ and the total resource spending $\sum_{l \in L} \Tilde{\sigma}_l = \sum_{l \in L} \sigma_l^*$.

We now show that such a defined strategy $\Tilde{\sigmaa}$ achieves a strictly higher expected revenue than $\sigmaa^*$. To see this, first note that the maximum additional gain in the expected revenue from spending $\sigma_l' = \frac{d_l^2}{d_l^2+k}$ as compared to $\sigma_l' = \frac{d_l^1}{d_l^1+k}$ is given by $q_l^2 \Lambda_l^2 \frac{d_l^2}{d_l^2+k} - (q_l^1 \Lambda_l^1 + q_l^2 \Lambda_l^2) \frac{d_l^1}{d_l^1+k} = a_l$ for all locations $l$ (see left of Figure <ref>). Furthermore, the spending required to gain this amount $a_l$ is given by $\frac{d_l^2}{d_l^2+k} - \frac{d_l^1}{d_l^1+k} = \frac{1}{2}\frac{a_l}{A}$. In other words, for the additional spending of $\frac{1}{2} - \gamma$ on locations in the set $[n] \backslash S'$, the maximum gain in the administrator's expected revenue is given by $(\frac{1}{2} - \gamma) \max_{l \in [n]} a_l$, regardless of which location(s) this additional amount $\frac{1}{2} - \gamma$ is spent on. However, spending the same amount on locations in the set $S'$ with $\sigma_{l'}^* < \frac{d_{l'}^1}{d_{l'}^1+k}$ for all $l' \in S'$, will result in an increase in the administrator revenue by

\begin{align*}
\sum_{l \in S'} (q_l^1 \Lambda_l^1 + q_l^2 \Lambda_l^2) (\frac{d_l^1}{d_l^1+k} - \sigma_l^*) &\stackrel{(a)}{=}  \sum_{l \in S'} 4 \frac{A}{a_l} \max_{l \in [n]} a_l (\frac{d_l^1}{d_l^1+k} - \sigma_l^*) \stackrel{(b)}{\geq}  4 \max_{l \in [n]} a_l \sum_{l \in S'} (\frac{d_l^1}{d_l^1+k} - \sigma_l^*), \\
&\stackrel{(c)}{=} 4 \max_{l \in [n]} a_l (\frac{1}{2} - \gamma) > (\frac{1}{2} - \gamma) \max_{l \in [n]} a_l,
\end{align*}

where (a) follows by substituting the relations for $q_l^1 \Lambda_l^1$ and $q_l^2 \Lambda_l^2$ for our above defined ERMP instance, (b) follows $A \geq a_l$ for all locations $l$ as $\sum_l a_l = A$, and (c) follows as $\sum_{l \in S'} (\frac{d_l^1}{d_l^1+k} - \sigma_l^*) = \frac{1}{2} - \gamma$ by our definition of $\gamma$. Thus, we have obtained that the increase in the administrator's expected revenue corresponding to shifting $\frac{1}{2} - \gamma$ of resources from locations $l \in [n] \backslash S'$ to locations $l \in S'$ (as in our allocation $\Tilde{\sigmaa}$) outweighs the maximum loss in the administrator objective from shifting these resources from $\sigmaa^*$ to $\Tilde{\sigmaa}$, given by $(\frac{1}{2} - \gamma) \max_{l \in [n]} a_l$. As a result, this relation implies that $\sigmaa^*$ is not optimal, a contradiction. Consequently, any optimal solution to the above defined ERMP instance must be such that $\Tilde{\sigma}_l^* \geq \frac{d_l^1}{d_l^1+k}$ for all locations $l$, which establishes our claim.

from a given location for spending i

First, we show that there is always an optimal solution that allocates to the first types of all locations. To see this, consider a solution $(\sigma_l^*)_{l \in [L]}$ such that there are some locations $l$ such that $\sigma_l^* < \frac{d_l^1}{d_l^1+k}$. Then, it must hold that there are some locations with $\sigma_l^* > \frac{d_l^1}{d_l^1+k}$. Then, we show that shifting the $\sigma^*$ mass to the locations with  $\sigma_l^* < \frac{d_l^1}{d_l^1+k}$ will only result in at least a higher objective. In particular, consider shifting a mass of $y = \frac{L}{2} \frac{a_l}{A} - \sum_{\text{spending on type 1}} \sigma_l^*$ from type to locations to the remaining type one locations. Then, we get the following change in objective:

\begin{align*}
y \times 2 \times \max_{l} a_l \geq y \times \max_{l} a_l,
\end{align*}

which is clearly greater than the corresponding spending of $y$ on type two. Thus, it is clear that spending on type 1 will at least result in as high an objective as that for type 2.

§.§.§ Proof of Lemma <ref>

We now use the structure of the optimal solution established in Lemmas <ref> and <ref> to show that our ERMP instance with $Q_R(\sigmaa) \geq \frac{A}{2} + 2 n \times \max_{l \in [n]} a_l$ corresponds to a “Yes” instance of partition. To do so, we first note that the total expected revenue when spending exactly $\frac{d_l^1}{d_l^1+k}$ at each location $l$ is given by: $\sum_{l \in [n]} (q_l^1 \Lambda_l^1 + q_l^2 \Lambda_l^2) \frac{d_l^1}{d_l^1+k} = 2n \max_{l' \in [n]} a_{l'}$. Note that the total such spending on locations is $\sum_{l \in [n]}\frac{d_l^1}{d_l^1+k} = \frac{1}{2}$; hence, the total additional spending beyond $\frac{d_l^1}{d_l^1+k}$ across all locations $l$ must not be more than $\frac{1}{4}$ as the total available resources $R = \frac{3}{4}$. In particular, we have that $\sum_{l \in [n]} x_l \leq \frac{1}{4}$, where $\sigma_l = \frac{d_l}{d_l+k} + x_l$ for all locations $l$.

Next, from Lemma <ref>, we have that there exists a solution to the ERMP problem such that there is at most one location $\Tilde{l}$ for which $x_{\Tilde{l}} \in (0, \frac{d_{\Tilde{l}}^2}{d_{\Tilde{l}}^2 + k} - \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1 + k}) = (0, \frac{1}{2} \frac{a_{\Tilde{l}}}{A})$. Such a result holds as from Lemma <ref> we have that $\sigma_l \geq \frac{d_l^1}{d_l^1+k}$ for all locations $l$ and that from Lemma <ref>, there exists at most one location $\Tilde{l}$ for which $\sigma_l \in (\frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1 + k}, \frac{d_{\Tilde{l}}^2}{d_{\Tilde{l}}^2 + k})$. As a consequence, the spending of the administrator beyond $\frac{d_l^1}{d_l^1+k}$ must satisfy $\sum_{l \in S''} \frac{1}{2} \frac{a_l}{A} + x_{\Tilde{l}} \leq \frac{1}{4}$ for some location set $S''$ and some location $\Tilde{l}$, and the expected revenue of the administrator must satisfy:

\begin{align*}
Q_R(\sigmaa) &= \sum_{l \in S''} q_l^2 \Lambda_l^2 \frac{d_l^2}{d_l^2+k} + q_{\Tilde{l}}^2 \Lambda_{\Tilde{l}}^2 \left( x_{\Tilde{l}} + \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k} \right) + \sum_{l \in [n] \backslash (S'' \cup \{ \Tilde{l}\})} (q_l^1 \Lambda_l^1 + q_l^2 \Lambda_l^2) \frac{d_l^1}{d_l^1+k}, \\
&\stackrel{(a)}{=} \sum_{l \in S''} q_l^2 \Lambda_l^2 \frac{d_l^2}{d_l^2+k} - \sum_{l \in S''} (q_l^1 \Lambda_l^1 + q_l^2 \Lambda_l^2) \frac{d_l^1}{d_l^1+k} + q_{\Tilde{l}}^2 \Lambda_{\Tilde{l}}^2 \left( x_{\Tilde{l}} + \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k} \right) \\
&- \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k} (q_{\Tilde{l}}^1 \Lambda_{\Tilde{l}}^1 + q_{\Tilde{l}}^2 \Lambda_{\Tilde{l}}^2) + \sum_{l \in [n]} (q_l^1 \Lambda_l^1 + q_l^2 \Lambda_l^2) \frac{d_l^1}{d_l^1+k}, \\
&\stackrel{(b)}{=}\sum_{l \in S''} a_l + \left( x_{\Tilde{l}} + \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k} \right) q_{\Tilde{l}}^2 \Lambda_{\Tilde{l}}^2 - \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k} (q_{\Tilde{l}}^1 \Lambda_{\Tilde{l}}^1 + q_{\Tilde{l}}^2 \Lambda_{\Tilde{l}}^2) + 2n \max_{l' \in [n]} a_{l'},
\end{align*}

where (a) follows from adding and subtracting $\sum_{l \in S'' \cup \Tilde{l}} (q_l^1 \Lambda_l^1 + q_l^2 \Lambda_l^2) \frac{d_l^1}{d_l^1+k}$, and (b) follows by substituting the relations for $q_l^1 \Lambda_l^1$, $q_l^2 \Lambda_l^2$, and $\frac{d_l^i}{d_l^i+k}$ for our above defined ERMP instance.

Then, since $Q_R(\sigmaa) \geq \frac{A}{2} + 2n \max_{l' \in [n]} a_{l'}$, the above equalities implies that, we have the following relation is satisfied:

\begin{align} \label{eq:helper-ermp-obj}
\sum_{l \in S''} a_l + \left( x_{\Tilde{l}} + \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k} \right) q_{\Tilde{l}}^2 \Lambda_{\Tilde{l}}^2 - \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k} (q_{\Tilde{l}}^1 \Lambda_{\Tilde{l}}^1 + q_{\Tilde{l}}^2 \Lambda_{\Tilde{l}}^2) \geq \frac{A}{2}.
\end{align}

We now show that we have a “Yes” instance of the partition problem by showing that $\Tilde{l} = \emptyset$.

To show this, we proceed by contradiction and suppose that there is some location $\Tilde{l}$ such that $x_{\Tilde{l}} \in (0, \frac{1}{2} \frac{a_l}{A})$. In this setting, we first note that the resource constraint $\frac{1}{4} \geq \sum_{l \in S'' \cup \{ \Tilde{l} \}} x_l = \sum_{l \in S''} \frac{1}{2} \frac{a_l}{A} + x_{\Tilde{l}}$ can be rewritten as:

\begin{align}
&\sum_{l \in S''} \frac{1}{2} \frac{a_l}{A} + x_{\Tilde{l}} \leq \frac{1}{4}, \nonumber \\
\implies &\sum_{l \in S''} a_l + 2A x_{\Tilde{l}} \leq \frac{A}{2} \label{eq:helper-23-resource-con}
\end{align}

Furthermore, from Equation (<ref>), we have that:

\begin{align}
\frac{A}{2} &\leq \sum_{l \in S''} a_l + \left( x_{\Tilde{l}} + \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k} \right) q_{\Tilde{l}}^2 \Lambda_{\Tilde{l}}^2 -  \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k} (q_{\Tilde{l}}^1 \Lambda_{\Tilde{l}}^1 + q_{\Tilde{l}}^2 \Lambda_{\Tilde{l}}^2), \nonumber \\
&< \sum_{l \in S''} a_l + \frac{x_{\Tilde{l}}}{\frac{d_{\Tilde{l}}^2}{d_{\Tilde{l}}^2+k} - \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k}} a_{\Tilde{l}}, \label{eq:helper-ermp-obj-22}
%\frac{d_{\Tilde{l}}^2}{d_{\Tilde{l}}^2+k} q_{\Tilde{l}}^2 \Lambda_{\Tilde{l}}^2 -  \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k} (q_{\Tilde{l}}^1 \Lambda_{\Tilde{l}}^1 + q_{\Tilde{l}}^2 \Lambda_{\Tilde{l}}^2), \\
%&= \sum_{l \in S' \cup \{ \Tilde{l} \}} a_l
\end{align}

where the second inequality follows as the total gain from spending $\frac{d_{\Tilde{l}}^2}{d_{\Tilde{l}}^2+k}$ compared to $\frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k}$ is given by $\frac{d_{\Tilde{l}}^2}{d_{\Tilde{l}}^2+k} q_{\Tilde{l}}^2 \Lambda_{\Tilde{l}}^2 -  \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k} (q_{\Tilde{l}}^1 \Lambda_{\Tilde{l}}^1 + q_{\Tilde{l}}^2 \Lambda_{\Tilde{l}}^2) = a_{\Tilde{l}}$ and the fact that $\frac{x_{\Tilde{l}}}{\frac{d_{\Tilde{l}}^2}{d_{\Tilde{l}}^2+k} - \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k}} a_{\Tilde{l}}$ represents a strict upper bound on the expected revenue that the administrator can gain for any $x_{\Tilde{l}} \in (0, \frac{d_{\Tilde{l}}^2}{d_{\Tilde{l}}^2+k} - \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k})$. For more intuition on the derivation of the second inequality, we refer to Figure <ref>, which provides a geometric intuition for this claim through a depiction of the social revenue function (in blue) and its corresponding upper bound (in orange).

Depiction of the expected revenue of the above defined ERMP instance with the amount of resources spent at location $\Tilde{l}$ in the range $\left[0, \frac{d_{\Tilde{l}}^2}{d_{\Tilde{l}}^2+k} \right]$. The curve in blue represents the expected revenue as a function of the number of resources allocated to location $\Tilde{l}$, while the dashed line in orange represents the upper bound on the expected revenue function. Moreover, the two points marked in yellow represent the expected revenue (bottom yellow point) and its corresponding upper bound (top yellow point) corresponding to a resource allocation of $\frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k} + x_{\Tilde{l}}$ at location $\Tilde{l}$.

From Equations (<ref>) and (<ref>), we obtain that:

\begin{align*}
\sum_{l \in S''} a_l + \frac{x_{\Tilde{l}}}{\frac{d_l^2}{d_l^2+k} - \frac{d_l^1}{d_l^1+k}} a_{\Tilde{l}} \stackrel{(a)}{=} \sum_{l \in S''} a_l + \frac{x_{\Tilde{l}}}{\frac{1}{2} \frac{a_{\Tilde{l}}}{A}} a_{\Tilde{l}} = \sum_{l \in S''} a_l + 2A x_{\Tilde{l}} \stackrel{(b)}{\leq} \frac{A}{2} \stackrel{(c)}{<} \sum_{l \in S''} a_l + \frac{x_{\Tilde{l}}}{\frac{d_{\Tilde{l}}^2}{d_{\Tilde{l}}^2+k} - \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1+k}} a_{\Tilde{l}},
\end{align*}

for any $x_{\Tilde{l}} \in (0, \frac{1}{2} \frac{a_l}{A})$, a contradiction. Here, (a) follows by substituting for the values of $\frac{d_l^2}{d_l^2+k}$ and $\frac{d_l^1}{d_l^1+k}$ for our above defined ERMP instance, (b) follows by Equation (<ref>), and (c) follows by Equation (<ref>). Thus, we have that $\Tilde{l} \neq \emptyset$ is not possible.

Finally, since $\Tilde{l} = \emptyset$, we have that Equation (<ref>) reduces to:

\begin{align} \label{eq:helper-1-revenue-obj}
\sum_{l \in S''} a_l \geq \frac{A}{2}.
\end{align}

Moreover, we have by the resource constraint that for these locations $S''$ that $\frac{1}{4} \geq \sum_{l \in S''} x_l =  \frac{d_{\Tilde{l}}^2}{d_{\Tilde{l}}^2 + k} - \frac{d_{\Tilde{l}}^1}{d_{\Tilde{l}}^1 + k} = \sum_{l \in S''} \frac{1}{2} \frac{a_l}{A}$. This inequality for the resource constraint implies the following relation:

\begin{align} \label{eq:helper-2-allocation}
\sum_{l \in S''} a_l \leq \frac{A}{2}.
\end{align}

Together, Equations (<ref>) and (<ref>) imply that there exists a set $S''$ such that $ \sum_{l \in S''} a_l = \frac{A}{2}$, i.e., we have a “Yes” instance of partition. This establishes our claim.

§.§ Proof of Theorem <ref>

For ease of exposition, we suppose that the MCUA of expected revenue function is identical to the upper bound of the expected revenue function, as depicted in Figure <ref>, i.e., the MCUA corresponding to each location $l$ has as many segments as the number of types $|\I|$. We note here that our proof readily generalizes to the setting when the MCUA and the upper bound of the expected revenue function are not identical with a more cumbersome linear program to optimize the MCUA of the expected revenue function. Moreover, for this proof, for ease of notation, we drop the fine $k$ from the objective of the expected revenue function of the administrator, which is equivalent to normalizing the fine $k$ to one. We now prove our claim in three steps. First, we show that optimizing the MCUA of the expected revenue function is equivalent to solving a linear program. Then, we show that the optimal solution of this linear program corresponds to an analogous version of the greedy algorithm in step one of Algorithm <ref>. Finally, we use these results to establish our desired approximation ratio.

Linear Program to Optimize MCUA of Expected Revenue Function:

We begin the proof of our claim, by presenting a linear program, which we claim optimizes the MCUA of the expected revenue function and whose optimal solution corresponds to the greedy-like solution akin to that in Step 1 of Algorithm <ref>. To present this linear program, we first define a variable $c_l^i$ for each location $l$ and type $i$ as follows:

* $c_l^1 = \sum_i q_l^i \Lambda_l^i$

* $c_l^{i} = \sum_{j \geq i} q_l^j \Lambda_l^j - \frac{\frac{d_l^{i-1}}{d_l^{i-1}+k}}{\frac{d_l^{i}}{d_l^{i}+k} - \frac{d_l^{i-1}}{d_l^{i-1}+k}} ( q_l^{i-1} \Lambda_l^{i-1} )$ for all $i \geq 2$.

Then, we consider the following linear program:
\beginmaxi!|s|[2]
x_l^i    ∀l ∈L, i ∈
V(Z) = ∑_l ∈L ∑_i ∈ℐ  z_l^i c_l^i,

z_l^1∈[0, d_l^1/d_l^1+k], ∀l ∈[L],   for all  l ∈L,
z_l^i∈[0, d_l^i/d_l^i+k - d_l^i-1/d_l^i-1+k],   for all  l ∈L, i > 1,
∑_l ∈L ∑_i ∈ℐ z_l^i≤R,   for all  l ∈L,
\endmaxi!
where $\textbf{Z} = (z_l^i)_{l \in L, i \in \I}$.

We now show that the objective of the MCUA of the expected revenue function for any allocation strategy $\sigmaa$, given by $M(\sigmaa)$, corresponds to the objective of the linear Program (<ref>)-(<ref>) for an appropriately chosen transformation of $\sigmaa$ to the matrix $\textbf{Z} = (z_l^i)_{l \in L, i \in \I}$. In particular, for each location $l$, define $\sum_{i \in \I} z_l^i = \sigma_l$, where $\sigma_l$ at each location is allocated in order of increasing types at each location $l$, i.e., type one is allocated until $z_l^1 = \min \{ \sigma_l, \frac{d_l^1}{d_l^1+k} \}$, following which type two is allocated until $z_l^2 = \min\{ \sigma_l - \frac{d_l^1}{d_l^1+k}, \frac{d_l^2}{d_l^2+k} - \frac{d_l^1}{d_l^1+k} \}$ and so on until the amount $\sigma_l$ is exhausted.

To achieve the goal mentioned in the previous paragraph and correspondingly show that the linear Program (<ref>)-(<ref>) indeed solves for the optimal resource allocation strategy of the MCUA of the expected revenue function, we show that the objective value of the above linear program interpolates the point $(0, 0)$ and the points of discontinuity $\frac{d_l^i}{d_l^i+k}$ for all $i \in \I$ of the expected revenue function for all locations $l$, e.g., the optimal objective of the linear program exactly corresponds to the orange curve corresponding to the MCUA for the three type instance in Figure <ref>.

To show this claim, fix a location $l$ and define $M_l(\sigmaa)$ as the MCUA objective corresponding to location $l$ and let $V_l(\textbf{Z}) = \sum_{i \in \I} c_l^i z_l^i$ be the objective of the linear Program (<ref>)-(<ref>) corresponding to location $l$. Then, we show that $M_l(\sigmaa) = V_l(\textbf{Z})$ for the above defined construction of $\textbf{Z}$ for any allocation $\sigma_l$ where $\sigma_l = 0$ or $\sigma_l = \frac{d_l^i}{d_l^i+k}$. Note that showing that the MCUA of the expected revenue function and the objective of the linear Program (<ref>)-(<ref>) coincides at $(0, 0)$ and the points of discontinuity $\frac{d_l^i}{d_l^i+k}$ for all $i \in \I$ implies, by the linearity of the objective of Problem (<ref>)-(<ref>), that the objective of the linear Program (<ref>)-(<ref>) also interpolates between these points.

Thus, we now show that $M_l(\sigmaa) = V_l(\textbf{Z})$ for the above defined construction of $\textbf{Z}$ for any allocation $\sigma_l$ that satisfies either $\sigma_l = 0$ or $\sigma_l = \frac{d_l^i}{d_l^i+k}$. To do so, we begin by recalling that the MCUA of the expected revenue function coincides with the expected revenue function for any $\sigma_l = 0$ or $\sigma_l = \frac{d_l^i}{d_l^i+k}$ for any $i \geq 1$.

We first consider the case when $\sigma_l = 0$. In this case, by our construction of $\textbf{Z}$, we have that $z_l^i = 0$ for all locations $l$ and types $i$. Hence, it holds that $\sum_i c_l^i z_l^i = 0 = \sigma_l \sum_i \sigma_l q_l^i y_l^i(\sigmaa)$

Next, we consider the case when $\sigma_l = \frac{d_l^i}{d_l^i+k}$ for some type $i \geq 1$. In this setting, we first note that when $\sigma_l = \frac{d_l^{s_l}}{d_l^{s_l}+k}$ for some $s_l$, the expected revenue function takes on the value $\sigma_l \sum_{i \geq s_l} q_l^i \Lambda_l^i$ by the best-response function $y_l^i(\sigmaa)$ in Equation (<ref>). We now prove by induction on the value $s_l$ that $\sum_i x_l^i c_l^i = \sigma_l \sum_{i \geq s_l} q_l^i \Lambda_l^i$ for any location $l$.

To see this, first consider the base case when $s_l = 1$. In this case, it holds that:

\begin{align*}
\sum_{i} z_l^i c_l^i &\stackrel{(a)}{=} z_l^1 c_l^1 = \frac{d_l^1}{d_l^1+k} \left(\sum_i q_l^i \Lambda_l^i \right) \stackrel{(b)}{=} \frac{d_l^1}{d_l^1+k} \left(\sum_{i \geq s_l} q_l^i \Lambda_l^i \right) \stackrel{(c)}{=} \sigma_l^* \sum_{i \geq s_l} q_l^i \Lambda_l^i,
\end{align*}

where (a) follows as $s_l = 1$ and thus $z_l^i = 0$ for all $i \geq 2$, (b) follows as $s_l = 1$ and thus $\sum_i q_l^i \Lambda_l^i = \sum_{i \geq s_l} q_l^i \Lambda_l^i$, and (c) follows as $\sigma_l^* = \frac{d_l^1}{d_l^1+k}$ for location $l$ as $s_l = 1$.

Next, by induction, suppose that the above relation holds for $s_l = j$. We now show that it also holds for $s_l = j+1$. In particular, we have for the setting when $s_l = j+1$ that:

\begin{align}
\sum_{i} z_l^i c_l^i &\stackrel{(a)}{=} \sum_{i = 1}^{j+1} z_l^i c_l^i = z_l^{j+1} c_l^{j+1} + \sum_{i = 1}^{j} z_l^i c_l^i, \nonumber \\
&\stackrel{(b)}{=} \left( \frac{d_l^{j+1}}{d_l^{j+1}+k} - \frac{d_l^{j}}{d_l^{j}+k} \right) \left( \sum_{i \geq j+1} q_l^i \Lambda_l^i - \frac{\frac{d_l^j}{d_l^j+k}}{\frac{d_l^{j+1}}{d_l^{j+1}+k} - \frac{d_l^{j}}{d_l^{j}+k}} ( q_l^j \Lambda_l^j ) \right) + \frac{d_l^j}{d_l^j+k} \left( \sum_{i \geq j} q_l^i \Lambda_l^i \right), \nonumber \\
&= \frac{d_l^{j+1}}{d_l^{j+1}+k} \sum_{i \geq j+1} q_l^i \Lambda_l^i - \frac{d_l^{j}}{d_l^{j}+k} \sum_{i \geq j+1} q_l^i \Lambda_l^i - \frac{d_l^j}{d_l^j+k} q_l^j \Lambda_l^j + \frac{d_l^j}{d_l^j+k} \sum_{i \geq j} q_l^i \Lambda_l^i, \nonumber \\
&= \frac{d_l^{j+1}}{d_l^{j+1}+k} \sum_{i \geq j+1} q_l^i \Lambda_l^i - \frac{d_l^j}{d_l^j+k} \sum_{i \geq j} q_l^i \Lambda_l^i + \frac{d_l^j}{d_l^j+k} \sum_{i \geq j} q_l^i \Lambda_l^i, \nonumber \\
&= \frac{d_l^{j+1}}{d_l^{j+1}+k} \sum_{i \geq j+1} q_l^i \Lambda_l^i \stackrel{(c)}{=} \sigma_l^* \sum_{i \geq j+1} q_l^i \Lambda_l^i, \label{eq:helper-equality-x_l-to_sigma_l}
\end{align}

where (a) follows as $s_l = j+1$ and thus $z_l^i = 0$ for all $i \geq j+2$, (b) follows by our inductive assumption and substituting for the respective values of $z_{l}^{j+1}$ and $c_l^{j+1}$, and (c) follows as $\sigma_l^* = \frac{d_l^{j+1}}{d_l^{j+1}+k}$ as $s_l = j+1$.

Thus, we have shown for all locations $i \geq 1$ that $\sum_{i} z_l^i c_l^i = \sigma_l \sum_{i \geq j+1} q_l^i \Lambda_l^i$. This establishes that $M_l(\sigmaa) = V_l(\textbf{Z})$ when $\sigma_l$ satisfies either $\sigma_l = 0$ or $\sigma_l = \frac{d_l^i}{d_l^i+k}$ for some $i \geq 1$. Consequently, by the linearity of the objective of the linear Program (<ref>)-(<ref>), we have that its objective interpolates between the point $(0, 0)$ and the points of discontinuity at $\sigma_l = \frac{d_l^i}{d_l^i+k}$.

Furthermore, we note that the above defined $c_l^i$ values correspond to the slopes of the segments of the piece-wise linear MCUA of the expected revenue function that connects the point $(0, 0)$ with the points of discontinuity of the expected revenue function, as depicted in Figure <ref>. Also, since the MCUA of the expected revenue function for each location $l$ is a concave function, it holds that the slopes, i.e., $c_l^i$ values, form a decreasing sequence for each location $l$, i.e., $c_l^1 \geq c_l^2 \geq \ldots \geq c_l^{|\I|}$. Consequently, given our above analysis, we have that solving the linear Program (<ref>)-(<ref>) coupled with our earlier defined method to transform an solution $\mathbf{Z}^*$ to an allocation $\sigmaa^*$ is equivalent to optimizing the MCUA of the expected revenue function, where we have already established earlier that the objective of the linear Program (<ref>)-(<ref>) interpolates between the point $(0, 0)$ and the points of discontinuity at $\sigma_l = \frac{d_l^i}{d_l^i+k}$.

Depiction of the expected revenue as a function of the amount of resources spent at location $l$ for an instance with 3 types, i.e., $|\I| = 3$. The curve in blue represents the expected revenue as a function of the number of resources allocated to location $l$, while the dashed line in orange represents the upper bound on the expected revenue function, which by assumption in the proof also corresponds to the MCUA of the expected revenue function. Moreover, the values of the slopes of the MCUA curve are depicted in the plot and correspond to the $c_l^i$ values for all types $i$.

Greedy Algorithm to Optimize Linear Program:

Next, to show that a greedy procedure optimizes the linear program that maximizes the MCUA of the expected revenue function, we recall that the above defined $c_l^i$ values correspond to the slopes of the segments of the piece-wise linear MCUA of the expected revenue function that connects the point $(0, 0)$ with the points of discontinuity of the expected revenue function, as depicted in Figure <ref>. Then, as the $c_l^i$ values form a decreasing sequence for each location $l$ (by the concavity of the expected revenue function), we can use the greedy procedure presented in Algorithm <ref>, where the segments of the MCUA of the expected revenue function are ordered in descending order of their $c_l^i$ values, to find an optimal solution to the linear Program (<ref>)-(<ref>). Notice that Algorithm <ref> is analogous to the greedy allocation rule in step one of Algorithm <ref> other than that the resources are allocated until either all the resources are exhausted or there are no further segments remaining to iterate over. We also note that following a similar line of reasoning to that in the proof of Theorem <ref>, the solution computed using Algorithm <ref> can be shown to correspond to a solution of the linear Program (<ref>)-(<ref>). Thus, since optimizing the MCUA of the expected revenue function can be done by solving the linear Program (<ref>)-(<ref>) and setting $\sigma_l = \sum_{i} z_l^i$, where $(z_{l}^i)_{l \in L, i \in \I}$ is a solution to the linear program, we have that greedy procedure in Algorithm <ref> also solves for the optimal solution that maximizes the MCUA of the expected revenue function.

Total Resource capacity $R$, Segment set $\S = \{(l_s, c_s, x_s)\}_{s \in \S}$ of MCUA of expected revenue function
Resource Allocation Strategy $\Tilde{\sigmaa}^*$
$\Tilde{\S} \leftarrow $ Ordered list of segments $s$ across all locations of this MCUA in descending order of slopes $c_s$
Initialize available resources $\Tilde{R} \leftarrow R$
Initialize allocation strategy $\Tilde{\sigmaa} \leftarrow \mathbf{0}$
segment $s \in \Tilde{\S}$
$\Tilde{\sigma}_{l_s} \leftarrow \Tilde{\sigma}_{l_s} + \min\{\Tilde{R}, x_s\}$ ;
$\Tilde{R} \leftarrow \Tilde{R} -  \min\{\Tilde{R}, x_s\}$;

Greedy Algorithm for MCUA of Expected Revenue Function

Next, consider the setting when $l = l'$. In this case, we show that $\sum_i x_{l'}^i c_{l'}^i \geq \sigma_{l'}^* \sum_{i>s_{l'}} q_{l'}^i \Lambda_{l'}^i$. To see this, we consider two cases: (i) $s_{l'} = 0$ and (ii) $s_{l'} \geq 1$.

Case (i): In the case when $s_{l'} = 0$ it holds that $\sigma_l^* = \delta < \frac{d_{l'}^1}{d_{l'}^1 + k}$, which implies that $x_{l'}^1 = \sigma_l^* = \delta$. Thus, it follows that $\sigma_{l'}^* \sum_{i>s_{l'}} q_{l'}^i \Lambda_{l'}^i = \sigma_{l'}^* \sum_{i} q_{l'}^i \Lambda_{l'}^i = x_{l'}^1 c_{l'}^1 = \sum_i x_{l'}^i c_{l'}^i$, which establishes our claim for the case when $s_{l'} = 0$.

Case (ii): We now consider the case when $s_{l'}>0$, i.e., it holds that $\sigma_{l'}^* = \frac{d_{l'}^{s_{l'}}}{d_{l'}^{s_{l'}} + k} + \delta$.

Thus, we obtain that:

\begin{align*}
\sum_i x_{l'}^i c_{l'}^i &\stackrel{(a)}{=} \sum_{i = 1}^{s_{l'}} x_{l'}^i c_{l'}^i + \delta c_{l'}^{s_{l'}+1}, \\
&\stackrel{(b)}{=} \frac{d_{l'}^{s_{l'}}}{d_{l'}^{s_{l'}} + k} \sum_{i \geq s_{l'}} q_{l'}^i \Lambda_{l'}^i + \delta \left( \sum_{i > s_{l'}} q_{l'}^i \Lambda_{l'}^i - \frac{\frac{d_l^{s_{l'}}}{d_l^{s_{l'}}+k}}{\frac{d_l^{s_{l'} + 1}}{d_l^{s_{l'}+1}+k} - \frac{d_l^{s_{l'}}}{d_l^{s_{l'}}+k}} ( q_l^{s_{l'}} \Lambda_l^{s_{l'}} ) \right), \\
&\stackrel{(c)}{\geq} \frac{d_{l'}^{s_{l'}}}{d_{l'}^{s_{l'}} + k} \sum_{i \geq s_{l'}} q_{l'}^i \Lambda_{l'}^i + \delta \sum_{i > s_{l'}} q_{l'}^i \Lambda_{l'}^i  - \frac{d_{l'}^{s_{l'}}}{d_{l'}^{s_{l'}} + k} q_l^{s_{l'}} \Lambda_l^{s_{l'}}, \\
&= \left( \frac{d_{l'}^{s_{l'}}}{d_{l'}^{s_{l'}} + k} + \delta \right) \sum_{i > s_{l'}} q_{l'}^i \Lambda_{l'}^i, \\
&\stackrel{(d)}{=} \sigma_{l'}^* \sum_{i > s_{l'}} q_{l'}^i \Lambda_{l'}^i,
\end{align*}

where (a) follows from the fact that $x_{l'}^i = 0$ for all $i > s_{l'}+1$, and (b) follows by the definition of $c_{l'}^{s_{l'}+1}$ and the fact that $\sum_{i = 1}^{s_{l'}} x_{l'}^i c_{l'}^i = \frac{d_{l'}^{s_{l'}}}{d_{l'}^{s_{l'}} + k} \sum_{i \geq s_{l'}} q_{l'}^i \Lambda_{l'}^i$ as $x_{l'}^i = \frac{d_{l'}^{i}}{d_{l'}^{i} + k} - \frac{d_{l'}^{i-1}}{d_{l'}^{i-1} + k}$ for all $i \leq s_{l'}$. Furthermore, (c) follows as $\delta < \frac{d_l^{s_{l'} + 1}}{d_l^{s_{l'}+1}+k} - \frac{d_l^{s_{l'}}}{d_l^{s_{l'}}+k}$, and (d) follows as $\sigma_l^* = \frac{d_{l'}^{s_{l'}}}{d_{l'}^{s_{l'}} + k} + \delta$.

Proving the Approximation Ratio:

Finally, we use our above developed results to complete the proof of our claim that $Q_R(\sigmaa_A^*) \geq \frac{1}{2} Q_R(\sigmaa^*)$. To this end, we first introduce some notation. In particular, we define $\Tilde{\sigmaa^*}$ as the optimal solution corresponding to directly optimizing the MCUA of the expected revenue function.

Then, to establish our approximation guarantee, we first recall from our earlier obtained results that maximizing the MCUA of the expected revenue function corresponds to the solution of Algorithm <ref>. As a result, we have that the solution maximizing the MCUA of the expected revenue function exactly corresponds to the solution in step one of Algorithm <ref> other than that resources are allocated until either all the resources are exhausted or there are no further segments remaining to iterate over. Consequently, by the termination condition of step one of Algorithm <ref>, there is at most one segment $s'$ and associated location $l_{s'} = l'$ such that the solutions of step one of Algorithm <ref> and that of Algorithm <ref> differ. In particular, it holds that $\Tilde{\sigma}^*_l = \Tilde{\sigma}_l$ for all $l \neq l'$ and for $l = l'$ it holds that $\Tilde{\sigma}^*_{l'} \geq \Tilde{\sigma}_{l'}$, where $\Tilde{\sigma}^*_{l'} = \Tilde{\sigma}_{l'} + x_{s'}$. For the remainder of this proof, we assume without loss of generality that $l' \neq \emptyset$. Then, we can write the optimal objective of the MCUA of the expected revenue function as:

\begin{align} \label{eq:helper-ub-ermp-helper}
M(\Tilde{\sigmaa}^*) = \sum_{l \in L \backslash \{ l' \}} \Tilde{\sigma}_l^* \sum_{i \geq s_l}  q_l^i \Lambda_l^i + \Tilde{\sigma}_{l'}^* \sum_{i>s_{l'}} q_{l'}^i \Lambda_{l'}^i.
\end{align}

From the above form of the optimal objective of the MCUA of the expected revenue function, we now establish three inequalities: (i) $Q_R(\sigmaa^*) \leq M(\Tilde{\sigmaa}^*)$, (ii) $Q_R(\sigmaa') \geq \sigma_{l'}^* \sum_{i>s_{l'}} q_{l'}^i \Lambda_{l'}^i$, and (iii) $Q_R(\Tilde{\sigmaa}) \geq \sum_{l \in L \backslash \{ l' \}} \sigma_l^* \sum_{i \geq s_l}  q_l^i \Lambda_l^i$.

Consequently, the optimal objective of the MCUA of the expected revenue function,

In particular, recall that the allocation maximizing the MCUA of the expected revenue function corresponds to the solution in step one of Algorithm <ref>, where resources are allocated until either all the resources are exhausted or there are no further segments remaining to iterate over.

To see this, we first recall from Lemma <ref> that the optimal objective of the bi-level Program (<ref>)-(<ref>) can be written as

\begin{align} \label{eq:helper-ub-ermp-helper}
Q_R(\sigmaa^*) = \sum_{l} \sum_i \sigma_l^* q_l^i y_l^i(\sigmaa^*) \Lambda_l^i = \sum_{l \in L \backslash \{ l' \}} \sigma_l^* \sum_{i \geq s_l}  q_l^i \Lambda_l^i + \sigma_{l'}^* \sum_{i>s_{l'}} q_{l'}^i \Lambda_{l'}^i
\end{align}

for some location $l'$ and corresponding type indices $s_l$ for all locations $l$. Here, the second equality follows from the best-response Problem (<ref>) of users and the fact that for at most one location $l'$ it holds that either $\sigma_{l'}^* \in (0, \frac{d_{l'}^1}{d_{l'}^1+k})$ or $\sigma_{l'}^* \in (\frac{d_{l'}^{i-1}}{d_{l'}^{i-1}+k}, \frac{d_{l'}^{i}}{d_{l'}^{i}+k})$ for $i\geq 2$. In the remainder of this proof, we suppose, without loss of generality, that $l' \neq \emptyset$.

Given the above notation, we, in particular, consider the following feasible solution to the linear Program (<ref>)-(<ref>): for $l \neq l'$, we let $x_{l}^1 = \frac{d_l^1}{d_l^1+k}$ if $s_l \geq 1$, otherwise, $x_l^1 = 0$, and we have that $x_l^i = \frac{d_l^i}{d_l^i+k} - \frac{d_l^{i-1}}{d_l^{i-1}+k}$ for $1 < i \leq s_l$ for all $l \neq l'$.

Then, combining
the above obtained inequality for the location $l'$ and equalities for the locations $l \neq l'$, it follows that:

\begin{align} \label{eq:helper-ub-ermp-helper}
Q_R(\sigmaa^*) &= \sum_{l \in L \backslash \{ l' \}} \sigma_l^* \sum_{i \geq s_l}  q_l^i \Lambda_l^i + \sigma_{l'}^* \sum_{i>s_{l'}} q_{l'}^i \Lambda_{l'}^i, \\
&\leq \sum_{l \in L \backslash \{ l' \}} \sum_{i} x_l^i c_l^i + \sum_i x_{l'}^i c_{l'}^i.
\end{align}

Inequality (i): $Q_R(\sigmaa^*) \leq M(\Tilde{\sigmaa}^*)$: By construction, the MCUA of the expected revenue function upper bounds the expected revenue for all allocation strategies $\sigmaa$. Hence, it follows that:

\begin{align*}
Q_R(\sigmaa^*) \leq M(\sigmaa^*) \leq M(\Tilde{\sigmaa}^*),
\end{align*}

where the first inequality follows as the MCUA of the expected revenue function upper bounds the expected revenue at $\sigmaa^*$ and the latter inequality follows by the optimality of $\Tilde{\sigmaa}^*$ for the MCUA of the expected revenue function.

Inequality (ii): $Q_R(\sigmaa') \geq \sigma_{l'}^* \sum_{i>s_{l'}} q_{l'}^i \Lambda_{l'}^i$: To establish this inequality, we first note by construction of $\sigmaa'$ for $R \geq 1$ resources that it corresponds to an allocation that maximizes the expected revenue from spending on a single location. In particular, we have that:

\begin{align*}
Q_R(\sigmaa') \geq \frac{d_{l'}^{s_{l'+1}}}{d_{l'}^{s_{l'+1}}+k} \sum_{i > s_{l'}} q_{l'}^i \Lambda_{l'}^i \geq \sigma_{l'}^* \sum_{i>s_{l'}} q_{l'}^i \Lambda_{l'}^i,
\end{align*}

where recall that $\sigma_{l'}^* \in (\frac{d_{l'}^{s_{l'} -1}}{d_{l'}^{s_{l'} -1} + k}, \frac{d_{l'}^{s_{l'}}}{d_{l'}^{s_{l'}} + k})$ by the definition of $s_{l'}$. Here, the first inequality follows as $\sigmaa'$ by definition is the solution with the highest expected revenue among all allocation corresponding to a single location and the second inequality follows as $\frac{d_{l'}^{s_{l'+1}}}{d_{l'}^{s_{l'+1}}+k} > \sigma_{l'}^*$. Thus, we have established our desired inequality that $Q_R(\sigmaa') \geq \sigma_{l'}^* \sum_{i>s_{l'}} q_{l'}^i \Lambda_{l'}^i$.

Next, by construction of the MCUA of the expected revenue function, we note that it is monotonically increasing in the resource spending at each location $l$ and the maximum of the MCUA at each location coincides with the expected revenue function itself by construction of the MCUA. Thus, since $\sigma_{l'}^* \sum_{i>s_{l'}} q_{l'}^i \Lambda_{l'}^i$ corresponds to the objective of the MCUA at location $l'$, we can consider an allocation $\sigmaa^{l'} = \argmax_{\sigmaa \in \Omega_R: \sigma_l = 0, \forall l \neq l'} Q_R(\sigmaa)$. Then, it follows that:

\begin{align*}
Q_R(\sigmaa') \stackrel{(a)}{\geq} Q_R(\sigmaa^l) \stackrel{(b)}{\geq} \sum_i x_{l'}^i c_{l'}^i,
\end{align*}

where (a) follows as $\sigmaa' = \argmax_l \sigmaa^l$, as defined in step two of Algorithm <ref> and (b) follows as the maximum of the MCUA at each location coincides with the expected revenue function itself by construction of the MCUA. Thus, we have established our desired inequality that $Q_R(\sigmaa') \geq \sigma_{l'}^* \sum_{i>s_{l'}} q_{l'}^i \Lambda_{l'}^i$.

Next, to establish our approximation ratio, we note that the allocation $\sigmaa'$ in Step 2 of Algorithm <ref> satisfies $Q_R(\sigmaa') \geq \sum_i x_{l'}^i c_{l'}^i$, which holds by the construction of $\sigmaa'$ for $R \geq 1$ and the fact that the MCUA of the expected revenue function is monotone for each location $l$. As a result, we have that:

\begin{align} \label{eq:helper-qr-single-loc}
Q_R(\sigmaa') \geq \sum_i x_{l'}^i c_{l'}^i.
\end{align}

Inequality (iii): $Q_R(\Tilde{\sigmaa}) \geq \sum_{l \in L \backslash \{ l' \}} \sigma_l^* \sum_{i \geq s_l}  q_l^i \Lambda_l^i$:

We recall from earlier that the solution maximizing the MCUA of the expected revenue function exactly corresponds to the solution in step one of Algorithm <ref> other than that resources are allocated until either all the resources are exhausted or there are no further segments remaining to iterate over. Consequently, it holds that $\Tilde{\sigma}^*_l = \Tilde{\sigma}_l$ for all $l \neq l'$ and for $l = l'$ it holds that $\Tilde{\sigma}^*_{l'} \geq \Tilde{\sigma}_{l'}$, where $\Tilde{\sigma}^*_{l'} = \Tilde{\sigma}_{l'} + x_{s'}$. Thus, it follows that $Q_R(\Tilde{\sigmaa}) = \sum_{l \in L \backslash \{ l' \}} \sigma_l^* \sum_{i \geq s_l}  q_l^i \Lambda_l^i$, which implies our desired inequality.

Together, the inequalities (i), (ii), and (iii) imply that

\begin{align} \label{eq:helper-ub-opt-sum-1}
Q_R(\Tilde{\sigmaa}) + Q_R(\sigmaa') &\geq \sum_{l \in L \backslash \{ l' \}} \Tilde{\sigma}_l^* \sum_{i \geq s_l}  q_l^i \Lambda_l^i + \Tilde{\sigma}_{l'}^* \sum_{i>s_{l'}} q_{l'}^i \Lambda_{l'}^i = M(\Tilde{\sigmaa}^*) \geq Q_R(\sigmaa^*),
\end{align}

where the equality follows from Equation (<ref>).

Finally, since $\sigmaa^*_A = \argmax \{ Q_R(\Tilde{\sigmaa}), Q_R(\sigmaa') \}$ from step 3 of Algorithm <ref>, it follows from the above inequality that

\begin{align*}
2 Q_R(\sigmaa^*_A) \geq Q_R(\Tilde{\sigmaa}) + Q_R(\sigmaa') \stackrel{(a)}{\geq}  Q_R(\sigmaa^*),
\end{align*}

where inequality (a) follows from Equation (<ref>). Thus, we have proved the desired half-approximation that $Q_R(\sigmaa^*_A) \geq \frac{1}{2} Q_R(\sigmaa^*)$, which establishes our result.

§.§ Proof of Theorem <ref>

To prove this claim, we first denote the objective of the MCUA of the expected revenue function summed across all locations given by $M(\sigmaa)$ for an administrator's resource allocation strategy $\sigmaa$. Then, we recall that, by construction, the developed MCUA is an upper bound on the expected revenue function for all feasible administrator strategies, i.e., $M(\sigmaa) \geq Q_R(\sigmaa)$ for all $\sigmaa \in \Omega_R$ (also see proof of Theorem <ref>). Next, to establish our resource augmentation guarantee with $R+1$ resources, we define $\Tilde{\sigmaa}^{R+1}$ as the allocation corresponding to Step 1 of Algorithm <ref> with $R+1$ resources and $\Tilde{\sigmaa}_A^{R+1}$ as the allocation corresponding to Algorithm <ref> with $R+1$ resources. Moreover, we let $\Tilde{\sigmaa}^*$ be the optimal solution corresponding to directly optimizing the MCUA of the expected revenue function. We now show that $Q_R(\sigmaa^*) \leq Q_{R+1}(\Tilde{\sigmaa}_A^{R+1})$ to establish our claim.

To show that $Q_R(\sigmaa^*) \leq Q_{R+1}(\Tilde{\sigmaa}_A^{R+1})$, we establish four key relations: (i) $Q_R(\sigmaa^*) \leq M(\Tilde{\sigmaa}^*)$, (ii) $M(\Tilde{\sigmaa}^*) \leq M(\Tilde{\sigmaa}^{R+1})$, (iii) $M(\Tilde{\sigmaa}^{R+1}) = Q_{R+1}(\Tilde{\sigmaa}^{R+1})$, and (iv) $Q_{R+1}(\Tilde{\sigmaa}^{R+1}) \leq Q_{R+1}(\Tilde{\sigmaa}_A^{R+1})$.

Relation (i): $Q_R(\sigmaa^*) \leq M(\Tilde{\sigmaa}^*)$: By construction, the MCUA of the expected revenue function upper bounds the expected revenue for all allocation strategies $\sigmaa$. Hence, it follows that:

\begin{align*}
Q_R(\sigmaa^*) \leq M(\sigmaa^*) \leq M(\Tilde{\sigmaa}^*),
\end{align*}

where the first inequality follows as the MCUA of the expected revenue function upper bounds the expected revenue at $\sigmaa^*$ and the latter inequality follows by the optimality of $\Tilde{\sigmaa}^*$ for the MCUA of the expected revenue function.

Relation (ii): $M(\Tilde{\sigmaa}^*) \leq M(\Tilde{\sigmaa}^{R+1})$:

We recall from the proof of Theorem <ref> that the allocation maximizing the MCUA of the expected revenue function corresponds to the solution of Algorithm <ref>. In other words, the allocation maximizing the MCUA of the expected revenue function corresponds to the solution in the step 1 of Algorithm <ref>, where resources are allocated until either all the resources are exhausted or there are no further segments are remaining to iterate over. Consequently, by the termination condition of step one of Algorithm <ref>, there is at most one segment $s'$ and associated location $l_{s'}$ such that the solutions of step one of Algorithm <ref> and that of Algorithm <ref> differ. In particular, it holds that $\Tilde{\sigma}^*_l = \Tilde{\sigma}_l$ for all $l \neq l_{s'}$ and for $l = l_{s'}$ it holds that $\Tilde{\sigma}^*_{l_{s'}} \geq \Tilde{\sigma}_{l_{s'}}$, where $\Tilde{\sigma}^*_{l_{s'}} \leq \Tilde{\sigma}_{l_{s'}} + x_{s'}$. Without loss of generality, we assume that $\Tilde{\sigma}^*_{l_{s'}} > \Tilde{\sigma}_{l_{s'}}$, as if this were not the case, then our desired inequality trivially holds.

Next, with $R+1$ resources, it must hold that the allocation $\Tilde{\sigmaa}^{R+1}$ corresponding to the solution of Algorithm <ref> satisfies $\Tilde{\sigma}_l^{R+1} \geq \Tilde{\sigma}_l = \Tilde{\sigma}^*_l$ for all $l \neq l_{s'}$, as the greedy allocation with $R+1$ resources will at least allocate the same amount of resources to all locations as that with $R$ resources. Furthermore, since $x_{s'} \leq 1$ for all segments $s$, it also holds for $l = l_{s'}$ that the greedy allocation will completely allocate $x_{s'}$ to location $l_{s'}$; hence, it holds that $\Tilde{\sigma}_{l_{s'}}^{R+1} \geq \Tilde{\sigma}_{l_{s'}} + x_{s'} \geq \Tilde{\sigma}^*_{l_{s'}}$.

Thus, we have established for all locations $l$ that $\Tilde{\sigma}^{R+1}_l \geq \Tilde{\sigma}^*_l$. Finally, our desired inequality that $M(\Tilde{\sigmaa}^*) \leq M(\Tilde{\sigmaa}^{R+1})$ follows by the monotonicity of the MCUA of the expected revenue function in the resource spending at each location.

Relation (iii): $M(\Tilde{\sigmaa}^{R+1}) = Q_{R+1}(\Tilde{\sigmaa}^{R+1})$: We note that the allocation corresponding to the greedy procedure in Step 1 of Algorithm <ref> corresponds to a point where both the expected revenue function and its corresponding MCUA coincide. Consequently, it follows that $M(\Tilde{\sigmaa}^{R+1}) = Q_{R+1}(\Tilde{\sigmaa}^{R+1})$.

Relation (iv): $Q_{R+1}(\Tilde{\sigmaa}^{R+1}) \leq Q_{R+1}(\Tilde{\sigmaa}_A^{R+1})$: This result directly follows, by definition, from the fact that $\Tilde{\sigmaa}_A^{R+1} = \argmax \{ Q_{R+1}(\Tilde{\sigmaa}), Q_{R+1}(\sigmaa') \}$.

Finally, combining the above four relations that we have shown, we obtain that:

\begin{align*}
Q_R(\sigmaa^*) \leq M(\Tilde{\sigmaa}^*) \leq M(\Tilde{\sigmaa}^{R+1}) = Q_{R+1}(\Tilde{\sigmaa}^{R+1}) \leq Q_{R+1}(\Tilde{\sigmaa}_A^{R+1}),
\end{align*}

which proves our claim that $Q_R(\sigmaa^*) \leq Q_{R+1}(\Tilde{\sigmaa}_A^{R+1})$, i.e., Algorithm <ref> with $R+1$ resources achieves a total expected revenue that is at least that corresponding to the optimal solution of Problem (<ref>)-(<ref>). This establishes our claim.

To show this, we note by the greedy procedure in Step 1 of Algorithm <ref> that $\Tilde{\sigmaa}^{R+1} \geq \Tilde{\sigmaa}$, where $\Tilde{\sigmaa}$ corresponds to the un-truncated allocation of the greedy procedure in Step 1 of Algorithm <ref> with $R$ resources. Furthermore, the greedy solution as computed in Step 1 of Algorithm <ref> is such that there is at most one location $l'$ for which $\Tilde{\sigma}_{l'} \in (0, \frac{d_{l'}^1}{d_{l'}^1+k})$ or $\Tilde{\sigma}_{l'} \in (\frac{d_{l'}^{i-1}}{d_{l'}^{i-1}+k}, \frac{d_{l'}^{i}}{d_{l'}^{i}+k})$ for some type $i>1$. Further, for notational simplicity, define $i'$ as the type such that either $\Tilde{\sigma}_{l'} \in (0, \frac{d_{l'}^{i'}}{d_{l'}^{i'}+k})$, where $i' = 1$, or $\Tilde{\sigma}_{l'} \in (\frac{d_{l'}^{i'-1}}{d_{l'}^{i'-1}+k}, \frac{d_{l'}^{i'}}{d_{l'}^{i'}+k})$, where $i'>1$.

Next, by the nature of our greedy algorithm with $R+1$ resources, $\Tilde{\sigma}_{l'}^{R+1} \geq \frac{d_{l'}^{i_{l'}}}{d_{l'}^{i_{l'}}+k}$. Thus, it follows from the nature of our greedy algorithm that $\Tilde{\sigmaa}^{R+1} \geq \Tilde{\sigmaa}$. Such a result holds as for all locations $l \neq l'$, it holds that $\Tilde{\sigma}_l = \leq \Tilde{\sigma}^{R+1}_l $ and for $l=l'$ it holds that $\Tilde{\sigma}_{l'}^{R+1} \geq \frac{d_{l'}^{i_{l'}}}{d_{l'}^{i_{l'}}+k} > \Tilde{\sigma}_{l'}$. Consequently, we have:

\begin{align*}
Q_{R+1}(\Tilde{\sigmaa}^{R+1}) \stackrel{(a)}{=} M(\Tilde{\sigmaa}^{R+1}) \stackrel{(b)}{\geq} M(\Tilde{\sigmaa}^*),
\end{align*}

where (a) follows as the expected revenue function and its MCUA coincide due to the nature of the truncated allocation strategies and (b) follows due to the monotonicity of the MCUA function.

Finally, combining the above relations, it follows that:

\begin{align}
Q_R(\sigmaa^*) \stackrel{(a)}{\leq} M(\Tilde{\sigmaa}^*) \stackrel{(b)}{\leq} M(\Tilde{\sigmaa}^{R+1}) \stackrel{(c)}{=} Q_{R+1}(\Tilde{\sigmaa}^{R+1}) \stackrel{(d)}{\leq} Q_{R+1}(\Tilde{\sigmaa}_A^{R+1}),
\end{align}

where (a) follows from the fact that the MCUA upper bounds the expected revenue function and correspondingly the optimal solution of the MCUA has a greater objective than the optimal solution for the expected revenue function and (b) follows by the monotonicity of the MCUA of the expected revenue function and the fact that $\lfloor \Tilde{\sigmaa}^{R+1} \rfloor \geq \Tilde{\sigmaa}$. Moreover, (c) follows as the as the expected revenue function and its MCUA coincide due to the nature of the truncated allocation strategies, and (d) follows from the fact that $\Tilde{\sigmaa}_A^{R+1}$ is an allocation with a greater expected revenue than the allocations computed steps 1 and 2 of Algorithm <ref>. Thus, since we have shown that $Q_R(\sigmaa^*) \leq Q_{R+1}(\Tilde{\sigmaa}_A^{R+1})$, we have proved our claim that Algorithm <ref> with $R+1$ resources achieves a total expected revenue that is at least that corresponding to the optimal solution of Problem (<ref>)-(<ref>), which establishes our claim.

§ WELFARE MAXIMIZATION IN PROBABILISTIC SETTING

In this section, we extend our results obtained in the probabilistic setting for the revenue maximization objective of the administrator to the welfare maximization objective. To this end, we first introduce the problem of maximizing the expected total welfare in the system (Section <ref>), following which we present the associated greedy algorithm for the administrator's welfare maximization objective and its corresponding approximation ratio and resource augmentation guarantees (Section <ref>).

§.§ Administrator's Expected Welfare Maximization Problem

We recall that, in the probabilistic setting, we assume that while users know the realization of the type $i \in \I$ at each location, the administrator only knows the distribution of each location's type. Consequently, to elucidate the expected welfare maximization problem of the administrator, as with the welfare maximization problem of the administrator in the deterministic setting (see Section <ref>), we first notice that the expected total social welfare in the system is given by $\sum_{l \in L} \sum_{i \in \I} q_l^i v_l^i$ and the level of welfare not accrued by the administrator under a strategy $\sigmaa$ with $R$ resources is given by $W_R^-(\sigmaa) = \sum_{l \in L} (1-\sigma_l) \sum_{i \in \I} q_l^i v_l^i y_l^i(\sigmaa)$. Then, the total accrued welfare under a strategy $\sigmaa$ with $R$ resources is given by $W_R(\sigmaa) = \sum_{l \in L} \sum_{i \in \I} q_l^i v_l^i - W_R^-(\sigmaa)$; hence, the expected welfare maximizing strategy of the administrator is equivalent to the strategy that minimizes $W_R^-(\sigmaa)$. Consequently, the expected welfare maximizing strategy of the administrator can be computed through the solution of the following bi-level program:
\beginmaxi!|s|[2]
y_l^i() ∈[0, 1], ∀l ∈L, i ∈
W_R^-() = ∑_l ∈L (1-σ_l) ∑_i ∈ q_l^i v_l^i y_l^i(),

y_l^i()∈_y ∈[0, 1] U_l^i(, y) = y[ (1-σ_l) d_l^i - σ_l k],   for all  l ∈L, i ∈,
\endmaxi!
where in upper-level problem, the administrator employs a strategy $\sigmaa$ that maximizes its expected welfare to which the users at each location of each type best respond by maximizing their utilities in the lower-level problem based on the realized type at that location. As in the deterministic setting, we note that the best response of users is given by the threshold function

\begin{align} \label{eq:best-response-users-wel-max-prob}
y_l^i(\sigmaa) =
\begin{cases}
0, &\text{if } \sigma_l \geq \frac{d_l^i}{d_l^i+k}, \\
1, &\text{otherwise}.
\end{cases}
\end{align}

We reiterate, as with the best response of users in the deterministic setting in Equation (<ref>), that when $\sigma_l = \frac{d_l^i}{d_l^i+k}$, any $y_l^i(\sigmaa) \in [0, 1]$ is a best-response for users at a location $l$ with type $i$. Yet, we let $y_l^i(\sigmaa) = 0$ when $\sigma_l = \frac{d_l^i}{d_l^i+k}$ as it corresponds to the highest expected welfare outcome for the administrator (see Section <ref> for a further discussion). We note that unlike the best-response function in the expected revenue maximization setting, where $y_l^i(\sigmaa) = 1$ when $\sigma_l = \frac{d_l^i}{d_l^i+k}$, in the expected welfare maximization setting, $y_l^i(\sigmaa) = 0$ when $\sigma_l = \frac{d_l^i}{d_l^i+k}$. For a further discussion on this difference between the best-response function of users under the welfare and revenue maximization administrator objectives, see Section <ref>.

§.§ Greedy Algorithm for Expected Welfare Maximization

In studying the expected welfare maximization problem of the administrator, we first note that the problem of computing the administrator's welfare-maximizing strategy in the probabilistic setting is NP-hard, which follows by our hardness result on solving for the administrator's welfare-maximizing strategy in the deterministic setting (Theorem <ref>). Thus, in this section, we introduce a greedy algorithm, described in Algorithm <ref>, to approximately solve for the administrator's expected welfare maximizing resource allocation strategy and highlight its corresponding approximation ratio and resource augmentation guarantees.

We begin by first describing our algorithmic approach to achieve an approximate solution to the administrator's expected welfare maximization problem, which proceeds as follows. First, rather than directly optimizing the expected welfare of the administrator, which as noted earlier is NP-hard to optimize, we maximize its corresponding monotone concave upper approximation (MCUA), which we depict in Figure <ref>. In particular, similar of maximizing the MCUA of the expected revenue function (see Section <ref>), optimizing the MCUA of the expected welfare function can be reduced to solving a linear program whose solution boils down to a greedy-like procedure presented in Step 1 of Algorithm <ref> (see Theorem <ref>).

To elucidate this greedy-like procedure, we note that the MCUA of the expected welfare function for each location $l$ is a piece-wise linear function; thus, we define $\S$ as the set of all such piece-wise linear segments of the MCUA of the expected welfare function across all locations. We then characterize each segment $s \in \S$ by three parameters: (i) $l_s$, which represents the location corresponding to segment $s$, (ii) $c_s$, which corresponds to the slope of segment $s$, and (iii) $x_s$, which represents the horizontal width, i.e., resource requirement, of segment $s$. In particular, Figure <ref> (right) depicts the associated slopes $c_s$ and resource requirements $x_s$ corresponding to the segments for the MCUA of the expected welfare function for a given location $l$. We then order the segments in the set $\S$ in the descending order of the slopes of the MCUA of the expected welfare function and find the solution corresponding to a greedy algorithm that allocates at most $z_s$ to each segment in the descending order of the slopes of the MCUA of the expected welfare function.

Next, as with Algorithm <ref>, we compute an allocation corresponding to spending all the available resources at a single location that yields the highest expected welfare of the administrator. Finally, we return the best of the greedy allocation corresponding to optimizing the MCUA of the expected welfare function and the allocation corresponding to spending all the available resources at a single location that achieves a higher expected welfare for the administrator. This procedure is formally presented in Algorithm <ref>.

Total Resource capacity $R$, Location Types $\Theta_l^i = (\Lambda_l^i, d_l^i, v_l^i)$ for all locations $l$ and types $i$
Resource Allocation Strategy $\sigmaa_A^*$
Step 1: Greedy Allocation Based on Slopes of MCUA of Expected Welfare Function:

Generate MCUA of the expected welfare function for each location $l$
$\Tilde{\S} \leftarrow $ Ordered list of segments $s$ across all locations of this MCUA in descending order of slopes $c_s$
Initialize allocation strategy $\Tilde{\sigmaa} \leftarrow \mathbf{0}$
segment $s \in \Tilde{\S}$
$\Tilde{\sigma}_{l_s} \leftarrow \Tilde{\sigma}_{l_s} + \min\{ R, x_s\}$ ;
$R \leftarrow R -  \min\{R, x_s\}$;

Step 2: Find Solution $\sigmaa'$ that Maximizes expected welfare from spending on Single Location:

$\sigmaa^l \leftarrow \argmax_{\sigmaa \in \Omega_R: \sigma_{l'} = 0, \forall l' \neq l} W_R(\sigmaa)$ for all locations $l$
$\sigmaa' \leftarrow \argmax_{l \in L} W_R(\sigmaa^l)$
Step 3: Return Solution with a Higher Expected Welfare:

$\sigmaa^*_A \leftarrow \argmax \{ W_R(\Tilde{\sigmaa}), W_R(\sigmaa') \}$
Greedy Algorithm for Administrator's Expected Welfare Maximization Objective

Total Resource capacity $R$, Location Types $\Theta_l^i = (\Lambda_l^i, d_l^i, v_l^i)$ for all locations $l$ and types $i$
Generate monotone concave upper approximation (MCUA) of the expected welfare function for each location $l$
Step 1: Solve MCUA of expected welfare function to obtain allocation $\Tilde{\sigmaa}$:

Define $c_s$ as the slopes of all piece-wise linear segments $s$ of MCUA of expected welfare function across all locations and let $x_s$ be the horizontal width, i.e., required resource amount, corresponding to segment $s$, and $l_s$ be the location associated with segment $s$
Order segments $s$ in descending order of slopes of the MCUA of the expected welfare function
Initialize $\Tilde{R} \leftarrow R$
segment $s$ in descending order of slopes of MCUA of the expected welfare function
$\Tilde{\sigma}_{l_s} \leftarrow \min \{ R, x_{s} \}$ ;
$\Tilde{R} \leftarrow \Tilde{R} -  \Tilde{\sigma}_{l_s}$;

Step 2: Find Optimal Solution $\sigmaa'$ that Maximizes expected welfare from spending on Single Location:

$l^* \leftarrow \max_{l \in L} \min \{ R, \frac{d_l^{|\I|}}{d_l^{|\I|} + k} \sum_{i \in \I} q_l^i v_l^i \}$;
Define $\sigmaa'$ such that $\sigma'_l \leftarrow 0$ for all $l \neq l^*$ and $\sigma'_l \leftarrow \min \{ R, \frac{d_l^{|\I|}}{d_l^{|\I|} + k} \}$ for $l = l^*$
Step 3: Return Solution with a Higher Expected Welfare:

$\sigmaa^*_A \leftarrow \argmax \{ W_R(\Tilde{\sigmaa}), W_R(\sigmaa') \}$
Greedy Algorithm for Administrator's Expected Welfare Maximization Objective

Depiction of the expected welfare as a function of the amount of resources allocated to location $l$ (left), its upper bound (center), and its corresponding monotone concave upper approximation (right) for a setting with five types, i.e., $|\I|  = 5$. Note that the expected welfare remains constant after a resource allocation that exceeds $\max_i \frac{d_l^i}{d_l^i+k}$. Further, for the MCUA of the expected welfare function, there are three segments $s$ for location $l$, with corresponding slopes $c_s$ of the segments and the corresponding width $x_s$ of the segments marked in the plot on the right.

We now present the main results of this section, which establish the approximation guarantees of Algorithm <ref> to the optimal expected welfare of the administrator. Our first result establishes that Algorithm <ref> achieves at least half the expected welfare as that corresponding to the solution of Problem (<ref>)-(<ref>).